Algorithmus zur Erzeugung eines sich selbst vermeidenden zufälligen Gehens auf einem Gitter

9

Wo finde ich Code, um zufällige selbstvermeidende Spaziergänge auf zwei- und dreidimensionalen Gittern zu generieren, deren Seitenlängen Zweierpotenzen sind? Die Wanderung sollte durch jeden Punkt des Gitters verlaufen. Wie kann ich einen zufälligen Hamilton-Pfad auf einem großen oder Gittergraphen finden?2n×2n2n×2n×2n

Die Verteilung muss nicht vollständig gleichmäßig sein, im Allgemeinen sollte das Gitter jedoch faltig aussehen. Das zur Erzeugung des Pfades verwendete Verfahren sollte eine geringe Wahrscheinlichkeit haben, extrem lange Strecken einer geraden Linie zu erzeugen.

random-walks lattices J. Antonio Perez
quelle
2
Es ist in Ordnung, hier nach einem Algorithmus zu fragen. Die Softwareempfehlung ist jedoch nicht thematisch. Sie könnten sich auch mehr Mühe geben, 1. Ihr Problem strenger zu definieren, 2. Ihren Versuch zu zeigen, Ihre Frage zu beantworten.
Apiwat Chantawibul
2
Meinen Sie zum Beispiel einen zufälligen Hamilton-Pfad im Gitterdiagramm ?
Apiwat Chantawibul
Ja; Genau das habe ich gemeint.
J. Antonio Perez
2
Und da es eine zufällige Generation ist. Interessiert es Sie, ob ein bestimmter Pfad mit größerer Wahrscheinlichkeit generiert wird als andere? dh Benötigen Sie eine einheitliche Chance für jeden möglichen Weg? (Eine einheitliche Chance wird wahrscheinlich schwieriger zu erreichen sein.)
Apiwat Chantawibul
1
Was genau sind die Anforderungen an die Distribution? Sie sagen, Sie brauchen keine gleichmäßige Verteilung. Sind Sie mit einem Algorithmus einverstanden, der einen beliebigen Hamilton-Pfad ausgibt (auch wenn er immer der gleiche ist)? Wenn nicht, was genau sind die Anforderungen? Können Sie auch die Klasse der Diagramme, die Sie verarbeiten möchten, genauer festlegen? Das Finden eines Hamilton-Pfads in einem Gitterdiagramm ist im Allgemeinen NP-schwierig , obwohl es sich so anhört, als würde Ihr Diagramm aus einer eingeschränkteren Klasse von Diagrammen stammen.
DW

Antworten:

4

Hier sind zwei Javascript-Implementierungen eines Algorithmus zum Abtasten von Hamilton-Pfaden in zweidimensionalen Gittergraphen: http://clisby.net/projects/hamiltonian_path/ und http://clisby.net/projects/hamiltonian_path/hamiltonian_path_v1.html (Dies ist Mein Code. Die Implementierung unter dem ersten Link bietet mehr Funktionen, während Sie mit der zweiten die Reihenfolge der vom Pfad besuchten Websites herunterladen können.)

Die Javascript-Programme erzeugen Hamilton-Pfade auf einem n × n-Gitter unter Verwendung der Backbite-Bewegung, die in der Arbeit „Sekundärstrukturen in langen kompakten Polymeren“ von Richard Oberdorf, Allison Ferguson, Jesper L. Jacobsen und Jané Kondev, Phys. Rev. E 74, 051801 (2006). Papier über das APS erhältlich (Abonnement erforderlich) oder als Vordruck auf arXiv unter https://arxiv.org/abs/cond-mat/0508094

Der Code enthält einen einstellbaren Parameter, der bestimmt, wie nahe Ihre Probe an der gleichmäßigen Verteilung liegt, und Sie können die Methode (Markov-Kette Monte Carlo mit Backbite-Bewegungen) mit ein wenig Arbeit an 3D-Gittergraphen anpassen.

Nathan
quelle
3
Welchen Algorithmus verwenden diese Programme? Da dies keine Programmierseite ist, interessieren wir uns mehr für den Algorithmus als für dessen Implementierung.
Yuval Filmus
Vielen Dank für den Vorschlag, ich habe einen Verweis auf den verwendeten Algorithmus hinzugefügt.
Nathan
Vielen Dank für Ihren Beitrag. Ich glaube, ich verstehe die Backbite-Methode tatsächlich besser als die andere, aber ich verstehe nicht, wie man den Backbite-Prozess effizient durchführt. Ich verstehe, wie es geht; nur nicht schnell. Könnten Sie dies näher erläutern? Ich habe die Graphentheorie in einer Klasse noch nicht behandelt und bin ein bisschen neu in diesem Bereich der Informatik. Ich danke dir sehr!
J. Antonio Perez