Wenn ein gerichteter Graph gegeben ist, was ist ein Algorithmus, der jeden Scheitelpunkt des Graphen nur einmal aufruft. Dies unterscheidet sich vom Hamilton-Zyklus insofern, als ich nicht voraussetze, dass der Pfad am selben Knoten beginnt und endet.10 Suche nach einem Pfad, der alle Scheitelpunkte eines gerichteten Graphen genau einmal aufruft
Backtracking-Algorithmus Ein Algorithmus, der in den Sinn kommt, ist Backtracking, Implementiert mit Rekursion, wo bei jedem Schritt, Sie alle möglichen Verbindungen/Pfade erkunden und haben immer eine boolean besuchte Array, um sicherzustellen, dass keine Ecke besucht mehr als einmal. Beim Backtracking würde dieser Boolesche Wert auf false gesetzt (der wesentliche Schritt beim Backtracking). Der Basisfall wäre, die Anzahl der besuchten Knoten zu vergleichen und zu sehen, dass sie mit der Anzahl der Knoten in der Grafik übereinstimmt. In diesem Fall würde sie den Wert true zurückgeben. Ein anderer Grundfall wäre, false zurückzugeben, wenn nicht alle Vertices besucht wurden, aber keine andere Verbindung existiert, um die Rekursion fortzusetzen. Die Zeitkomplexität hierfür wäre O(n!), was nicht wünschenswert ist.
Gibt es einen besseren Algorithmus, um den Pfad/Traversal eines gerichteten Graphen zu finden, der jeden einzelnen Eckpunkt in Graph genau einmal abdeckt.
Nicht sicher, ob das funktioniert, aber das Betrachten der stark verbundenen Komponenten (https://en.wikipedia.org/wiki/Strongly_connected_component) und die Kondensation des Graphen können helfen, die Laufzeit zu reduzieren. Aber mein Gefühl ist, dass du im schlimmsten Fall nicht besser als O (n!) Wirst. – Henry
Wenn Sie einen effizienten Algorithmus zur Lösung dieses Problems hätten, könnten Sie auch den Hamilton-Zyklus effizient lösen (wobei "effizient" "in polynomieller Zeit" bedeutet): Für jede gegebene Instanz des Hamilton-Zyklus erstellen Sie n Instanzen des Hamilton-Pfadproblems durch Löschen ein einzelner Eckpunkt. Verwenden Sie Ihren effizienten Algorithmus n Mal (einmal pro Instanz), um eine HP in jedem von ihnen zu finden, wenn sie existiert. Wenn in einem dieser n Graphen ein HP vorhanden ist und dieser in einen HC konvertiert werden kann, indem der bestimmte Eckpunkt hinzugefügt wird, der in diesem Graph gelöscht wurde, dann haben Sie einen HC gefunden - und wenn nicht, können Sie t sei irgendein HC. –
@Henry, wie ich verstehe stark verbundenen Komponenten sind diejenigen, wo jeder Scheitelpunkt in der Komponente von einem anderen Scheitelpunkt in der gleichen Komponente erreichbar ist. Obwohl es dafür effiziente Algorithmen wie Tarjan gibt, ist mein Problem etwas anders. Ich suche nur alle Ecken zu erreichen. Denkst du immer noch, dass es eine Lösung gibt, die besser ist als n! um das zu lösen? – saltmangotree