Losowy sam unikający się cykl kratowy w obrębie danego obwiedni

W związku z układanką Slither Link zastanawiałem się: Załóżmy, że mam siatkę kwadratowych komórek i chcę znaleźć prosty cykl krawędzi siatki, równomiernie losowy wśród wszystkich możliwych prostych cykli. $n\times n$

Jednym ze sposobów na to byłoby użycie łańcucha Markowa, którego stanami są zbiory kwadratów, których granice są prostymi cyklami i których przejścia polegają na wybraniu losowego kwadratu do przerzucenia i zachowaniu przerzutu, gdy zmodyfikowany zestaw kwadratów nadal ma prosty cykl jako jego granica. W ten sposób można przejść z dowolnego prostego cyklu do dowolnego innego (korzystając ze standardowych wyników dotyczących istnienia ostrzałów), więc ostatecznie zbiega się to do jednolitego rozkładu, ale jak szybko?

Alternatywnie, czy istnieje lepszy łańcuch Markowa, czy też bezpośrednia metoda wyboru prostych cykli?

ETA: Zobacz ten post na blogu, aby znaleźć kod do obliczenia liczby cykli, których szukam, i wskazuje na OEIS dla niektórych z tych liczb. Jak wiemy, liczenie jest prawie tym samym, co generowanie losowe, i wnioskuję z braku jakiegokolwiek oczywistego wzorca faktoryzacji tych liczb i braku wzoru we wpisie OEIS, że mało prawdopodobne jest, aby znana była prosta metoda bezpośrednia . Ale to wciąż pozostawia pytania o to, jak szybko ten łańcuch zbiega się i czy istnieje lepszy łańcuch szeroko otwarty.

— David Eppstein
źródło

Granica zbiorów zliczonych przez sekwencję OEIS niekoniecznie jest prostymi cyklami, na przykład dla 3x3, jeden z 218 ma wszystkie kwadraty z wyjątkiem środka, a kolejne cztery są podane przez dalsze usunięcie jednego rogu.

— Colin McQuillan

W przypadku siatek 2xn liczby są podane w oeis.org/A059020 . Dla 3xn jestem całkiem pewny, że są to 6,40 213,1049,5034,23984,114069,542295,2577870,12253948,58249011,276885683,1316170990,6256394122,29739651711,141366874247, ... (nie w OEIS). Skonfigurowałem macierz transferu, aby obliczać ją ręcznie, ale porównałem ją z macierzą wygenerowaną maszynowo, a jedyne, co różniły się pozycją, ręka była poprawna, a maszyna błędna. (Powinno to pojawić się w przypadku 3x3 - matryca maszyny pozwoliłaby na zastosowanie oktomina z dziurą w środku.)

— David Eppstein,

Powinieneś wysłać tę sekwencję do Neila Sloane'a, aby mógł umieścić ją w OEIS.

— Peter Shor,

@David: Dziękuję. Prawdopodobnie nadszedł czas, abym dokładniej nauczył się metody macierzy transferowej.

— Yoshio Okamoto

@David: Właśnie zmarnowałeś dwie godziny mojego życia z tym linkiem do układanki .. Dzięki!

— domotorp

Wygląda na to, że ponieważ używasz zliczeń tylko do liczby cykli na wykresie, aby losowo wybrać cykl, że jeśli masz losowe przybliżenie tej liczby, możesz nadal wybrać cykl w przybliżeniu równomiernie.

$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)$

W ten sposób wybiera się wielomianową liczbę krawędzi, z których każda wymaga niewielkiej liczby obliczeń algorytmu wielomianowego aproksymacji czasu. W ten sposób cykl może być jednolicie wybrany.

Obecnie mam pytanie wymiany stosu z prośbą o referencje do algorytmów aproksymacyjnych zliczania szybkich ścieżek. Przeczytałem w kilku miejscach, że te algorytmy istnieją, ale jeszcze ich nie znalazłem.

— bbejot
źródło