Zufälliger, sich selbst vermeidender Gitterzyklus innerhalb eines gegebenen Begrenzungsrahmens

Im Zusammenhang mit dem Slither-Link- Puzzle habe ich mich gefragt: Angenommen, ich habe ein Gitter aus quadratischen Zellen, und ich möchte einen einfachen Zyklus von Gitterkanten finden, der unter allen möglichen einfachen Zyklen gleichmäßig zufällig ist.$n\times n$

Ein Weg, dies zu tun, wäre, eine Markov-Kette zu verwenden, deren Zustände Mengen von Quadraten sind, deren Grenzen einfache Zyklen sind und deren Übergänge darin bestehen, ein zufälliges Quadrat zum Umdrehen auszuwählen und das Umdrehen beizubehalten, wenn die modifizierte Menge von Quadraten noch einen einfachen Zyklus als hat seine Grenze. Man kann auf diese Weise von einem einfachen Zyklus zu einem anderen gelangen (unter Verwendung von Standardergebnissen über das Vorhandensein von Schalen), so dass dies schließlich zu einer gleichmäßigen Verteilung konvergiert, aber wie schnell?

Alternativ gibt es eine bessere Markov-Kette oder eine direkte Methode zur Auswahl einfacher Zyklen?

ETA: In diesem Blog-Beitrag finden Sie einen Code zur Berechnung der Anzahl der von mir gesuchten Zyklen und Hinweise auf OEIS für einige dieser Zahlen. Wie wir wissen, ist das Zählen fast dasselbe wie das zufällige Erzeugen, und ich schließe aus dem Fehlen eines offensichtlichen Musters bei der Faktorisierung dieser Zahlen und dem Fehlen einer Formel im OEIS-Eintrag, dass es wahrscheinlich keine bekannte einfache direkte Methode gibt . Damit bleibt jedoch die Frage offen, wie schnell diese Kette konvergiert und ob es eine bessere Kette gibt, die weit offen ist.

Es scheint, dass Sie, da Sie nur die Zählungen für die Anzahl der Zyklen in einem Diagramm verwenden, um einen Zyklus zufällig auszuwählen, wenn Sie eine zufällige Annäherung für diese Anzahl hätten, dennoch einen Zyklus ungefähr gleichmäßig auswählen könnten.

Es ist zu beachten, dass die Anzahl der Zyklen in einem Graphen , der die Kante ( u , v ) enthält , gleich der Anzahl der Zyklen in G - ( u , v ) plus der Anzahl der einfachen Pfade von u nach v in G - ( u , v) ist ) . Mit einer Polynomzeit-Approximation für die Anzahl der u - v- Pfade kann die Polynomzeit-Approximation erreicht werden, indem schrittweise jeweils eine Flanke bis zu G aufgebaut wird, die sich annähert, während Sie gehen. $G$$(u, v)$$G - (u, v)$$u$$v$$G - (u, v)$$u$$v$$G$

$G$$n \times n$$(u, v)$$u$$v$$G$$(u, v)$

$C$$v_s$$v_e$$N$$v_e$$C$$u \in N$$u$$v_s$$G[V - (C - \{v_s, v_e \} ) ]$$u$$v_e$$(v_e, u)$

Auf diese Weise wird eine polynomielle Anzahl von Kanten ausgewählt, von denen jede eine kleine Anzahl von Berechnungen eines Polynomzeitnäherungsalgorithmus erfordert. Somit kann ein Zyklus gleichmäßig gewählt werden.

Ich habe derzeit eine Stapelaustausch-Frage , in der Referenzen für Algorithmen zur Näherung der Anzahl schneller Pfade angefordert werden. Ich habe an einigen Stellen gelesen, dass diese Algorithmen existieren, sie aber noch nicht gefunden haben.