Algorithmus, um einen zufälligen Hamilton-Pfad in einem Gitter zu finden?

Sie können mit dem von Ihnen erwähnten Ansatz beginnen, einen Hamilton-Pfad zu finden. Um die Lösung weiter zu randomisieren, können Sie mit dem Drehen von Kanten beginnen, wie im Wiki . Wenn Sie dies häufiger tun, wird die Lösung zufälliger. Das Drehen einer zufälligen Kante N * M mal hält den Algorithmus im effizienten Bereich, während der gefundene Hamilton-Pfad zufälliger wird.

Zunächst ist der Algorithmus, der auf Ihrem Bild aus der PDF-Datei angezeigt wird, keine Lösung für das Hamilton-Pfadproblem, sondern eine Lösung für eine Labyrinthgeneration, da der letzte Pfad mehrere Verzweigungen aufweist.

Um Algorithmen für eine Labyrinthgeneration zu finden, siehe: Ссылка

Hier ist nun ein einfacher Algorithmus, um einen Hamilton-Pfad auf einem N * M 2D-Gitter zu erzeugen:

1) Sei ein N * M-Gitter (zB 4 * 5):

2) Beginnen wir mit der Ost / Nord-Ecke und erstellen wir einen einfachen Zickzack nach Westen und Osten:

Jetzt haben wir einen Hamilton-Pfad.

3) Lassen Sie uns zwei geklebte Kanten suchen, die einander gegenüber stehen. Sie sind der Anfang und das Ende einer Schleife:

4) Stellen Sie sicher, dass sich innerhalb der Schleife mindestens eine Kante befindet, die an eine Kante außerhalb der Schleife geklebt ist. Andernfalls fahren Sie mit Schritt 3 fort:

5) Verknüpfen Sie die Schleife:

6) Befestigen Sie die Schleife wieder an den beiden anderen geklebten Kanten:

7) Wenn der Hamilton-Pfad nicht zufällig genug ist, fahren Sie mit Schritt 3 fort.

Nur der Anfang und das Ende werden nicht verschoben. Um das Ende oder den Anfang zu randomisieren, können Sie den anfänglichen Zickzack durch einen anderen Algorithmus ersetzen:

1. Wählen Sie eine der vier Ecken
2. Suche alle nicht besuchten Nachbarn
3. Wenn es keinen Nachbarn gibt, ist die Karte gefüllt, andernfalls gehe zu Schritt 4
4. Behalte nur die Nachbarn, die eine Lücke oder eine besuchte Zelle haben, auf der einen Seite, links oder rechts (mit anderen Worten, die Nachbarn, die entlang der Grenze des nicht besuchten Bereichs laufen)
5. Wähle einen dieser Nachbarn aus, besuche ihn und gehe zu Schritt 2

Das Ergebnis könnte so aussehen:

Bei diesem Algorithmus bleibt der Start in einer Ecke, aber das Ende kann überall sein. Um den Start UND das Ende zu randomisieren, können Sie einen Algorithmus anwenden, den Sie entweder am Anfang oder am Ende beliebig oft wiederholen können. Nehmen wir den Anfang:

1) Suchen Sie den Anfang:

2) Suchen Sie einen Nachbarn, der nicht direkt mit dem Anfang verbunden ist (Sie finden immer einen in einem 2D-Gitter):

3) Finden Sie von wo Sie von Anfang an (bzw. vom Ende) zu ihm gelangen:

4) Schneiden Sie diesen Link aus und erstellen Sie eine Verknüpfung zwischen diesem Punkt und dem Anfang:

Der Start hat zwei Zellen verschoben. Der Anfang und das Ende sind wie auf einem Schachbrett und sie können sich nur auf einem Fall mit der gleichen Farbe bewegen.

Jetzt ist Ihr Pfad vollständig randomisiert.

Hier ist der ganze Algorithmus in Python. Sie können es hier ausführen: Ссылка

Das Ergebnis wird in einem Array ( self.gameGrid ) gespeichert, das zweimal protokolliert wird (mit Pfeilen und mit Knoten und Linien). Die ersten zwei geklebten Kanten werden als Permutation bezeichnet und die zweiten werden als Schnittpunkte bezeichnet.

Genug Zufälligkeit ist sehr allgemein, Sie sollten einige Benchmarks haben, der berühmteste Algorithmus für den eiduadischen TSP hat eine 3/2 Approximation ( Christofides Algorithmus ), die MST verwendet ( wie Algorithmus erwähnt, der 2-Approximation ist), und wie Sie in Wiki sehen können, hat das beste PTAS, das aktuell gefunden wird, abhängig von der Laufzeit bis (n log n) ^ f (c, 2) für c & gt; 0 (in 2 dimensionalen Raum wie Ihre Probe) mit Approximation von (1 + 1 / c), und beste Approximation für TSP mit konstantem Faktor ist 3/2 - 1/500 algorithm (kürzlich gefunden), aber alle von ihnen verwenden logische Wege, es gibt einige zufällige Verwendungen, aber es führt nicht dazu, dass alle Dinge zufällig ausgewählt werden. Wenn Sie nur zufällig verwenden möchten, können Sie Random Walk verwenden. Es ist zufälliger, aber sehen Sie Markove Chain für bessere Leistung und Zufälligkeit.

Dieses Papier beschreibt eine Methode:

Oberdorf, R .; Ferguson, A .; Jacobsen, J. L .; Kondev, J. - Sekundärstrukturen in langen kompakten Polymeren (arXiv.org)

Die Methode besteht grob aus folgenden Schritten: Beginnen Sie mit einem Zick-Zack-Muster (einem nicht zufälligen Hamilton-Pfad auf dem Gitter) und wenden Sie wiederholt eine Transformation ("Backbite" genannt) auf den Pfad an. Ein Backbite besteht aus dem Hinzufügen einer Kante von einem der Endpunkte A zu einem benachbarten Vertex B, außer dem, mit dem A verbunden ist (wodurch eine Schleife entsteht), und entfernt dann die in B beginnende Kante, die nicht die gerade hinzugefügte und ist das verursacht eine Schleife (es wird immer nur eine geben, die eine andere Schleife als die gerade hinzugefügte Schleife verursacht).

Die Autoren fügen einige Bedingungen hinzu, um eine grobe Uniformität zu erhalten (einschließlich einer Schätzung, wie oft die Backbite-Bewegung angewendet wird). Details in der Zeitung.

Die Autoren beweisen auch empirisch, dass die Wahrscheinlichkeit, dass ihre Methode benachbarte Endpunkte erzeugt, ungefähr der theoretischen Wahrscheinlichkeit in homogenen zufälligen Hamilton-Pfaden entspricht.

Es gibt eine Implementierung des Algorithmus in JavaScript hier: Hamiltonian Path Generator