Ciclo de celosía aleatorio que se evita a sí mismo dentro de un cuadro delimitador dado

En relación con el rompecabezas Slither Link , me he estado preguntando: supongamos que tengo una cuadrícula de celdas cuadradas , y quiero encontrar un ciclo simple de bordes de cuadrícula, uniformemente al azar entre todos los ciclos simples posibles.$n\times n$

Una forma de hacer esto sería usar una cadena de Markov cuyos estados son conjuntos de cuadrados cuyos límites son ciclos simples y cuyas transiciones consisten en elegir un cuadrado aleatorio para voltear y mantener el volteo cuando el conjunto modificado de cuadrados todavía tiene un ciclo simple como Su límite. Uno puede pasar de cualquier ciclo simple a otro de esta manera (usando resultados estándar sobre la existencia de envolturas) de modo que esto eventualmente converja en una distribución uniforme, pero ¿qué tan rápido?

Alternativamente, ¿hay una mejor cadena de Markov o un método directo para seleccionar ciclos simples?

ETA: consulte esta publicación de blog para obtener un código para calcular la cantidad de ciclos que estoy buscando y sugerencias para OEIS para algunos de estos números. Como sabemos, contar es casi lo mismo que la generación aleatoria, y deduzco de la falta de un patrón obvio en las factorizaciones de estos números y la falta de una fórmula en la entrada de OEIS que es poco probable que exista un método directo simple conocido . Pero eso todavía deja las preguntas sobre qué tan rápido converge esta cadena y si hay una cadena mejor abierta.

Parece que debido a que solo está usando los recuentos para el número de ciclos en un gráfico para elegir un ciclo aleatoriamente, que si tuviera una aproximación aleatoria para este número, aún podría elegir un ciclo aproximadamente uniformemente.

Tenga en cuenta que el número de ciclos en un gráfico , que contiene el borde ( u , v ) , es igual al número de ciclos en G - ( u , v ) más el número de rutas simples de u a v en G - ( u , v ) . Por lo tanto, con una aproximación de tiempo polinomial para el número de trayectorias u - v , la aproximación de tiempo polinomial se puede lograr aumentando gradualmente hasta G un borde a la vez, aproximándose a medida que avanza. $G$$(u, v)$$G - (u, v)$$u$$v$$G - (u, v)$$u$$v$$G$

De hecho, creo que hay un método más directo para elegir un ciclo. Sea el gráfico completo de aristas alrededor de la cuadrícula de cuadrados n × n . Para cada arista ( u , v ) encuentre el número de ciclos que contienen esa arista (que es el número de rutas u - v en G - ( u , v ) ). Luego, elija aleatoriamente una arista ponderada por el número de ciclos que la contienen. Esta será la primera ventaja en su ciclo elegido al azar. Todos los demás bordes se elegirán extendiendo un borde a la vez.$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)$

De esta manera, se elige un número polinómico de aristas, cada una de las cuales requiere un pequeño número de cálculos de un algoritmo de aproximación de tiempo polinomial. Por lo tanto, se puede elegir un ciclo de manera uniforme.

Actualmente tengo una pregunta de intercambio de pila que solicita referencias para algoritmos de aproximación de conteo de ruta rápida. He leído en algunos lugares que existen estos algoritmos pero aún no los he encontrado.