Aus diesem Wikipedia-Artikel:
Ein randomisierter Algorithmus für den Hamilton-Operator Pfad, der auf den meisten Graphen schnell ist Folgendes: Beginne von einem Zufall Vertex, und fortfahren, wenn es ein gibt Nachbar nicht besucht. Wenn es keine gibt mehr unbesuchte Nachbarn und der Weg gebildet ist nicht Hamilton, wählen Sie ein Nachbar zufällig, und rotiere mit diesem Nachbarn als Drehpunkt. (Das heißt, fügen Sie eine Kante hinzu Nachbar, und entfernen Sie eine der vorhandene Kanten von diesem Nachbarn so um keine Schleife zu bilden.) Dann fahre fort der Algorithmus am neuen Ende der Pfad.
Ich verstehe nicht ganz, wie dieser Schwenkprozess funktionieren soll. Kann jemand diesen Algorithmus genauer erklären? Vielleicht können wir den Wiki-Artikel eventuell mit einer klareren Beschreibung aktualisieren.
Edit 1: Ich glaube, ich verstehe den Algorithmus jetzt, aber es scheint, als ob er nur für ungerichtete Graphen funktioniert. Kann das jemand bestätigen?
Hier ist, warum ich denke, dass es nur für ungerichtete Graphen funktioniert:
alt text http://www.michaelogleman.com/static/images/graph.png
Geben Sie vor, dass die Scheitelpunkte wie folgt nummeriert sind:
%Vor% Sagen wir, mein bisheriger Weg ist: 9, 5, 4, 7, 8 . Die Nachbarn von 8 wurden alle besucht. Nehmen wir an, ich wähle 5, um eine Kante zu entfernen. Wenn ich (9, 5) entferne, erzeuge ich einfach einen Zyklus: 5, 4, 7, 8, 5 , also scheint es, dass ich (5, 4) entfernen und erstellen muss (8, 5). Wenn der Graph ungerichtet ist, ist das in Ordnung, und jetzt ist mein Pfad 9, 5, 8, 7, 4. Aber wenn man sich vorstellt, dass diese Kanten gerichtet sind, ist das nicht unbedingt ein gültiger Pfad, da (8, 5) eine Kante ist. 5, 8) möglicherweise nicht.
Edit 2: Ich schätze für einen gerichteten Graph könnte ich die (8, 5) Verbindung erstellen und dann den neuen Pfad nur 4, 7, 8, 5 haben, aber das scheint kontraproduktiv zu sein, da ich es muss hacke alles ab, was zuvor zu Scheitelpunkt 5 geführt hat.
Wenn Ihre zufällige Auswahl von Knoten einen Graphen so konstruiert hat, dass der letzte Knoten A keine unbesuchten benachbarten Knoten hat, müssen Sie einen Eckpunkt verfügbar machen, damit Sie weitermachen können.
Um dies zu tun: Wählen Sie einen benachbarten Eckpunkt nach dem Zufallsprinzip aus, entfernen Sie eine seiner vorhandenen Kanten (in einem Hamilton-Pfad können nur zwei Kanten von einem einzelnen Eckpunkt vorhanden sein), zeichnen Sie dann eine neue Kante von Ihrem aktuellen Eckpunkt zufällig ausgewählt. Sie verfolgen dann vom zufällig ausgewählten Eckpunkt zum Ende des Graphen (der erste Eckpunkt, der nur eine einzige Kante hat, der ihn verlässt) und setzt den Algorithmus fort.
In allen möglichen schrecklichen Pseudo-Codes:
%Vor%Es ist in der Tat eine sehr unklare Erklärung, und der Algorithmus scheint auch nicht von einer der aufgeführten Referenzen zu kommen.
Die Idee scheint darin zu bestehen, zuerst einen zufälligen Pfad zu erstellen, indem man den Anfangsknoten zufällig auswählt und davon ausgehend zufällige Nachbarn auswählt, solange dies möglich ist. Wenn keine weiteren Nachbarn ausgewählt werden können, ist der Pfad entweder Hamilton-Operator oder nicht. Wenn dies nicht der Fall ist, hat dieser letzte Knoten auf dem Pfad einen Nachbarn bereits auf dem Pfad (siehe unten), so dass das Pivotieren bedeutet, eine Kante vom letzten Knoten zum Nachbar bereits auf dem Pfad zu machen und einen der Links aus dem Pfad zu löschen Nachbar, die für den Weg ausgewählt wurden. Dann gibt es ein neues Ende des Pfades, von dem aus der Prozess fortgesetzt wird.
Dieser Algorithmus geht beispielsweise davon aus, dass es keine Knoten mit nur einer Kante gibt. Diese sind jedoch leicht zu decken: Wenn es eine davon gibt, fange einfach damit an, wenn es zwei gibt, starte von einer von ihnen und versuche, an der anderen vorbeizukommen, und wenn es mehr als zwei gibt, kann es nicht sein ein Hamilton-Pfad.
Verstehst du was eine Kante ist? Wenn die Ecken v1, v2, .. vn sind, dann ist eine Kante ein Paar (v1, v2) - stellen Sie sich vor, Sie zeichnen eine Linie zwischen v1 und v2, und das ist eine Kante.
Also, im Grunde genommen machst du einen grundlegenden Hill-Climbing-Algorithmus (füge Kanten hinzu und besuche unbesuchte Knoten), abhängig von der Einschränkung, dass du einen Knoten nicht mehr als einmal besuchst.
Und wenn Sie feststellen, dass Sie nicht mehr fortfahren können (Sie können keine der noch nicht besuchten Knoten vom aktuellen Scheitelpunkt aus erreichen), wählen Sie einen zufälligen Scheitelpunkt, der verbunden ist (zwischen diesem Scheitelpunkt und einer Kante befindet sich eine Kante) der Scheitelpunkte, die Sie bereits besucht haben, und fügen Sie eine Kante zwischen diesem Scheitelpunkt und den besuchten Knoten hinzu, die sich noch nicht im Pfad befindet.
Dies könnte (und möglicherweise muss dies den Mathematikern überlassen werden) eine Schleife erzeugen. Sie können die Schleife entfernen, indem Sie eine andere Kante von den Kanten im Pfad entfernen.
Im Grunde handelt es sich um einen Hill-Climbing-Algorithmus mit ein wenig randomisierter Störung, wenn Sie nicht weiterkommen. Wenn Sie stecken bleiben, fügen Sie im Grunde eine weitere Kante hinzu und entfernen eine aus der Grafik und versuchen, fortzufahren. Wenn Sie völlig falsch lagen, können Sie immer noch zu einer Lösung kommen, weil Sie theoretisch alle richtigen Kanten hinzufügen und alle Ihre ursprünglichen falschen Entscheidungen löschen könnten.
Tags und Links algorithm language-agnostic random graph
