Un problema de programación particular que encontré recientemente se reduce a encontrar caminos hamiltonianos en una cuadrícula rectangular que se vería algo así como,
A 0 0 0
0 0 0 0
0 0 C D
¿Cuáles son algunas heurísticas efectivas que podrían aplicarse para encontrarlas y, en particular, técnicas para recortar / descartar rutas en el camino?
Editar: solo para aclarar, los bordes se forman cuando los elementos se conectan horizontal y verticalmente, pero no diagonalmente. El problema también establece que cualquier elemento marcado con 0 puede usarse para formar una ruta, pero los elementos que no son 0 son "obstáculos" que deben evitarse.
A-0-0-0
|
0-0-0-0
|
0-0-C D
podría ser un camino, por ejemplo. Otro puede ser,
A 0-0-0
| | |
0 0 0-0
| | |
0-0 C D
ds.algorithms
hamiltonian-paths
viksit
fuente
fuente
Respuestas:
No veo una manera fácil de contar sin enumerar. Puede visitar fácilmente todos los caminos hamiltonianos con una búsqueda exhaustiva de profundidad con retroceso. En realidad, puedes hacer trampa un poco y darte cuenta de que, si N es el número de caminos hamiltonianos que comienzan yendo hacia la derecha, el número total de caminos hamiltonianos es 2N (debido a la simetría de la cuadrícula). Esto no se extiende por completo (para algunos vértices, no todos los caminos conducirán al mismo número de ciclos, pero puedes limitar el número de caminos hamiltonianos fácilmente con un argumento similar (con la ventaja de que puedes resolver partes de él exactamente) para mejorar su límite con argumentos de simetría). Esta es la estrategia que elegiría.
Pero si no quieres esto, algunas heurísticas genéricas:
También puede limitar fácilmente el número de caminos hamiltonianos como | E | elija | V | -1 (donde | E | es el número de aristas y | V | el número de vértices en el gráfico), que puede ser mucho mejor para un gráfico disperso que | V |! (El ingenuo límite que supone que el gráfico está completo).
Una manera fácil de mejorar este límite es recortando combinaciones malas conocidas, al no considerar dos veces los bordes del mismo vértice. Entonces obtendrías algo como prod_v (deg_v-1) (que aún debería limitar el número de rutas hamiltonianas, ya que ahora estás contando ciclos más de una vez, creo).
fuente