Ich habe einen großen Graph von verbundenen Scheitelpunkten (eine verbundene Komponente) und suche nach einem Pfad, der durch alle geht, aber nie durch einen Scheitelpunkt geht zweimal. Dies ist nicht immer möglich. Zum Beispiel in dem folgenden Beispiel from wikipedia, ist es offensichtlich, dass es keinen Weg gibt, die jede Ecke besucht, wo keine Ecke mehr als einmal besucht:Einen Weg durch eine verbundene Komponente finden, wo jeder Scheitelpunkt genau einmal besucht wird
Aber wenn es wurde leicht verändert, so dass es mehr Kanten (Verbindungen), dann gibt es einige Pfade, die genau einmal durch jeden Knoten gehen können. Ich habe es gezwickt und die Eckpunkte nummeriert einen solchen Weg zu geben:
Mein Diagramm wie dieses ist, wo ich weiß, dass es einen möglichen Weg ist. Es ist jedoch ziemlich groß (20.000 Scheitelpunkte mit jeweils zwischen 2 und 11 Kanten). Ich habe Tiefensuche und Breitensuche implementiert, aber das Diagramm ist einfach zu groß, um einen Pfad zu finden (es wird zu lange dauern, um es zu berechnen).
Also meine Frage ist: Gibt es einen anderen Algorithmus, der dieses Problem lösen kann, und zwar effizienter als zuerst in die Tiefe oder Breitensuche?
Es ist ein bisschen wie das Problem des reisenden Verkäufers, nur dass die Städte nur von bestimmten anderen Städten aus erreichbar sind und die Entfernung zwischen diesen gleich ist.
Hat Ihr Graph eine [Brücke] (https://en.wikipedia.org/wiki/Bridge_ (graph_theory))? Ist Ihr Graph [planar] (https://en.wikipedia.org/wiki/Planar_graph)? Versuchen Sie in jedem Fall [approximieren Sie die Baumbreite Ihres Graphen] (http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.29.7198&rep=rep1&type=pdf), da eine niedrige Baumbreite effiziente Algorithmen für Ihre Problem. In der Tat –