Algoritmo para generar una caminata aleatoria que se evita a sí misma en una red

9

¿Dónde puedo encontrar algún código para generar caminatas aleatorias de autoevaluación en redes de 2 y 3 dimensiones cuyas longitudes laterales son potencias de dos? La caminata debe pasar por cada punto de la red. Más específicamente, ¿cómo puedo encontrar una ruta hamiltoniana aleatoria en un gráfico de cuadrícula grande o ?2norte×2norte2norte×2norte×2norte

La distribución no tiene que ser completamente uniforme, sin embargo, en general, la red debería verse arrugada. El método utilizado para generar el camino debe tener una baja probabilidad de producir tramos extremadamente largos de línea recta.

J. Antonio Perez
fuente
2
Está bien preguntar sobre un algoritmo aquí. Pero la recomendación de software está fuera de tema. Además, podría poner más esfuerzo en 1. definir su problema de manera más rigurosa 2. mostrar su intento de responder a su pregunta.
Apiwat Chantawibul
2
Por ejemplo, ¿te refieres a una ruta hamiltoniana aleatoria en el gráfico de cuadrícula ?
Apiwat Chantawibul
Si; eso es exactamente lo que quise decir.
J. Antonio Perez
2
Y como es una generación aleatoria. ¿Le importa si es más probable que se genere un camino en particular que otros? es decir, ¿necesita una oportunidad uniforme para cada ruta posible? (la probabilidad uniforme será más difícil de hacer).
Apiwat Chantawibul
1
¿Cuáles son exactamente los requisitos en la distribución? Dices que no necesitas una distribución uniforme. Entonces, ¿estás de acuerdo con un algoritmo que genera cualquier ruta hamiltoniana (incluso si siempre es la misma)? Si no, ¿cuáles son específicamente los requisitos? Además, ¿puede ser más preciso sobre la clase de gráficos que desea manejar? Encontrar una ruta hamiltoniana en un gráfico de cuadrícula es NP-difícil en general, aunque parece que su gráfico podría provenir de una clase de gráficos más restringida.
DW

Respuestas:

4

Aquí hay dos implementaciones de JavaScript de un algoritmo para muestrear rutas hamiltonianas en gráficos de cuadrícula bidimensionales: http://clisby.net/projects/hamiltonian_path/ y http://clisby.net/projects/hamiltonian_path/hamiltonian_path_v1.html (Esto es mi código. La implementación en el primer enlace tiene más características, mientras que el segundo le permite descargar la secuencia de sitios visitados por la ruta).

Los programas javascript generan caminos hamiltonianos en una cuadrícula n × n utilizando el movimiento de retroceso descrito en el documento "Estructuras secundarias en polímeros largos y compactos" de Richard Oberdorf, Allison Ferguson, Jesper L. Jacobsen y Jané Kondev, Phys. Rev. E 74, 051801 (2006). Papel disponible a través de APS (se requiere suscripción) o como preimpresión en arXiv en https://arxiv.org/abs/cond-mat/0508094

El código incluye un parámetro ajustable que determina qué tan cerca de la distribución uniforme estará su muestra, y puede adaptar el método (cadena de Markov Monte Carlo con movimientos de retroceso) a gráficos de cuadrícula 3D con un poco de trabajo.

Nathan
fuente
3
¿Qué algoritmo usan estos programas? Como este no es un sitio de programación, estamos más interesados ​​en el algoritmo que en su implementación.
Yuval Filmus
Gracias por la sugerencia, agregué una referencia al algoritmo utilizado.
Nathan
Muchas gracias por tu publicación. Creo que realmente entiendo el método de backbite mejor que el otro, pero no entiendo cómo hacer el proceso de backbite de manera eficiente. Entiendo cómo hacerlo; Solo que no rápidamente. ¿Podría darnos más detalles sobre esto? Todavía no he cubierto la teoría de gráficos en una clase y soy un poco nuevo en esta área de la informática. Muchas gracias!
J. Antonio Perez