Encontrar un camino hamiltoniano en un gráfico

Question

Declaración de problemas

Dada una gráfica de todos los cuadrados azules en la siguiente imagen donde cada cuadrado azul está conectado a otros cuadrados azules en las 4 direcciones cardinales.

Dado cualquier nodo de inicio.

Qué algoritmo permitirá encontrar la ruta más larga (ish).

Considerando que cada nodo solo se puede visitar una vez.

Considerando que no nos importa donde termine el camino.

Considerando que la velocidad es más importante que necesariamente visitar cada nodo.

Ejemplo

He trazado un ejemplo del resultado deseado en la imagen a continuación.Como puede ver, la ruta no visita cada nodo y eso está bien.Estoy buscando un algoritmo rápido que me dé uno de los rutas más largos posible en este gráfico.El 80% de cobertura o más es lo que estoy disparando.

Answer 1

Terminé usando el UCT (MCT con UCB1) algoritmo pero con un giro.

Normalmente, en el UCT, la fase de simulación es un juego simulado de un juego con movimientos elegidos al azar. Si el juego simulado termina en una victoria, la puntuación del nodo, desde donde se jugó la simulación, y todas las puntuaciones de los padres de regreso a la raíz, se incrementan en 1.

En mi implementación, el "desempate" simulado es en realidad solo un paseo aleatorio por el árbol de azulejos vecinos que aún no han visitado. Una vez que la simulación alcanza un nodo terminal (sin salida), asigna una puntuación de S= D / M donde D es la profundidad del nodo terminal en el árbol y M es la profundidad máxima posible.

En una cuadrícula de 15 x 15 sin obstáculos, establecería M a 225, ya que el camino más largo visitaría cada azulejo. Les he fijado un poco ligeramente más bajo que eso, ya que necesito que el algoritmo se generalice y trabaje en mapas generados al azar que generalmente tienen 10-30 azulejos ocupados por obstáculos.

En lugar de incrementar la puntuación de los padres, el algoritmo de retroceso establece la puntuación de cada padre a la puntuación recién calculada, si es más alta que su puntaje actual. En otras palabras, la puntuación de un nodo siempre representa la longitud de la ruta más larga alcanzada hasta el momento de este nodo.

UCT utiliza UCB1 para seleccionar qué nodo explotar o explorar una vez que se han ampliado todos los niños del nodo actual y he mantenido en gran medida con eso. La única modificación que he realizado es el término de explotación. En UCB1, el término de explotación es W / V donde W es la puntuación acumulada del nodo y V es el número de tiempo que se visitó el nodo. Esto funciona muy bien en un juego donde desea seleccionar el movimiento que maximiza sus posibilidades de ganar. En mi caso, dado que la puntuación no refleja una función binaria de win= 1 y perder= 0, sino más bien una escala de 0= sendero súper corto vs 1= la ruta más larga posible y quiero bajar la ruta más larga encontrada por el algoritmo , Simplemente he establecido el término de explotación a S= puntuación= ruta más larga accesible desde este nodo.

El contexto en el que estoy usando este algoritmo me permite aproximadamente 40 ms de tiempo de cómputo en un entorno NODEJS antes de tener que seleccionar un movimiento. Esto generalmente ofrece alrededor de 785 Transversales de árboles en mi máquina. En promedio, en ese momento, y en el mapa mostró en OP, este algoritmo encontrará un camino que es 70 nodos profundos. Lo que es más que suficiente para mis propósitos, ya que tengo que ejecutar el algoritmo nuevamente el siguiente turno. En la práctica, cuando se usa este algoritmo para seleccionar los próximos movimientos, termino viajando una ruta de 100-110 pasos antes de golpear un callejón sin salida y cubro una porción muy grande de las baldosas azules.

Por diversión, he corrido el algoritmo durante mucho más tiempo y en alrededor de 300 000 turversales (30 segundos en mi máquina), en promedio, nuevamente en el mapa que se muestra en OP, encuentra un camino que es de 125 nodos profundos, lo cual es bonito cerca de la profundidad máxima en este mapa.

Answer 2

Este es el problema del camino más largo.Es NP-Difícil encontrar el camino más largo en un gráfico general.Puede intentar aplicar cualquier algoritmo estándar para encontrar caminos más largos.Busque en este sitio para "Ruta más larga" y "Ruta Hamiltoniana" para encontrar muchas referencias.Dado que está dispuesto a aceptar soluciones subóptimas, es posible que busque un algoritmo heurístico o de aproximación (por ejemplo, utilizando un algoritmo de búsqueda local).