¿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 ?
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.
random-walks
lattices
J. Antonio Perez
fuente
fuente
Respuestas:
Se describe un procedimiento en un algoritmo combinatorio para la generación efectiva de largas cadenas de celosía máximas compactas .
fuente
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.
fuente