Encontrar el camino más corto para visitar todos los cuadrados no bloqueados en una cuadrícula

Digamos que usted tiene una cuadrícula como este (hecho al azar):Encontrar el camino más corto para visitar todos los cuadrados no bloqueados en una cuadrícula

Ahora digamos que usted tiene un coche de partida al azar de uno de las cajas while, ¿cuál sería la ruta más corta para recorrer cada una de las casillas blancas? Puede visitar cada casilla blanca tantas veces como quiera y no puede saltar sobre las casillas negras. Las cajas negras son como paredes. En palabras simples, puede pasar del cuadro blanco al cuadro blanco solamente.

Puede moverse en cualquier dirección, incluso en diagonal.

dos preguntas secundarias:

asuma que sabe la posición de todas las cajas negras antes de moverse.
Supongamos que solo conoce la posición de una caja negra cuando se encuentra en una casilla blanca adyacente a ella.

Fuente

2010-05-20 Laz

"¿cuál sería el camino más corto para recorrer cada una de las casillas blancas"? ¿Qué estás preguntando aquí? ¿Quiere decir "ir a cada una de las cajas blancas"? – naiad

Sí, solo tienes que atravesar TODAS las casillas blancas. – Laz

Para encontrar la ruta más corta, debe realizar una búsqueda de fuerza bruta. Realmente no importa si conoces las cajas negras por adelantado o no. – mdma

-1

Intenta construir como un gráfico (en el que cada nodo tiene otros a lo sumo 8 nodos) y tratarlo como el http://en.wikipedia.org/wiki/Travelling_salesman_problem

Fuente

2010-05-20 16:57:42 corsiKa

-1 El hecho de que se puede reducir a un problema NP-completo (que ni siquiera has mostrado) no es más ayuda que decirle que lo fuerce brutalmente. –

@BlueRaja: solo porque no te gusta la respuesta, no está mal. Hubiera dado -1 a Glowcoder porque su respuesta ignora el hecho de que TSP normalmente necesita que cada ciudad sea visitada exactamente una vez, lo que no es el modelo apropiado aquí, porque uno necesita visitar algunas cajas blancas más de una vez. –

El TSP no requiere que cada uno sea visitado exactamente una vez. Simplemente se preocupa por el camino más corto entre dos ciudades, independientemente de si viaja a través de una ciudad a la que ya viajó en el camino. No importa cómo lo cortes, este es un problema difícil para NP, y creo que es mejor abordarlo usando el mismo enfoque que TSP. – corsiKa

Esto es similar al problema caballeros Tour, donde una solución típica evalúa todas las rutas posibles originando del cuadrado que comienza. Cuando no se puede completar un recorrido, se utiliza el seguimiento retroactivo para regresar a una copia de seguridad de las decisiones anteriores. Tu problema es más relajado ya que puedes visitar cuadros más de una vez. Los viajes de los Caballeros y los problemas de Traveling Saleman generalmente requieren visitar cada casilla exactamente una vez.

Ver http://en.wikipedia.org/wiki/Knight's_tour

Fuente

2010-05-20 16:59:43 mdma

Si puede visitar plazas más de una vez, ¿cómo puede determinar cuándo un recorrido no se puede completar (y, por lo tanto, es hora de comenzar a retroceder)? Por lo general, esto se determina cuando ya se han visitado todas las plazas cercanas, pero eso ya no se aplica si puede visitarlas dos veces :-) – psmears

Puede realizar análisis de accesibilidad de sqaure a square - p. evaluar todos los caminos desde un cuadrado fuente hasta un cuadrado objetivo. Aquí, evitas ciclos, solo necesitamos un camino, por lo que cada cuadrado se visita solo una vez. Como ejemplo, considere una tabla donde los cuadrados negros del centro particionen en dos mitades. Los cuadrados en la mitad en que comienzas son accesibles, los cuadrados en la otra mitad no. – mdma

Usted debe modelar el problema como un grafo completo donde la distancia entre dos nodos (cajas blancas) es la longitud de la trayectoria más corta entre los nodos. Esas longitudes de ruta se pueden calcular mediante el algoritmo Floyd-Warshall. Entonces, puede tratarlo como "Traveling salesman", como escribió el glowcoder.

EDITAR: para hacerlo más claro: puede describir cada camino "interesante" a través del laberinto mediante una secuencia de cajas blancas diferentes. Porque si tiene una ruta arbitraria que visita cada casilla blanca, puede dividirla en subrutas, cada una terminando en una nueva casilla blanca no visitada hasta ahora. Cada una de estas subrutas de la casilla blanca A a B puede reemplazarse por una subruta más corta de A a B, por eso necesita la matriz de rutas más cortas entre todos los pares.

Fuente

2010-05-20 17:10:34

Esto es bastante intrincado. TSP se aplica directamente. ¿Por qué pasar por Floyd-Warshall?-1 hasta que elabores más. –

@Moron: de la Wikipedia, primera frase: "la tarea es encontrar el recorrido más corto posible que visite cada ciudad * exactamente una vez *". Eso es lo que hace mi sugerencia: permitir ver el problema como un problema TSP de ese tipo, incluso si tiene que visitar cada casilla más de una vez. –

@Doc: entiendo a lo que te refieres. Eliminaré el -1. Aún así, bastante intrincado. Quité un espacio para permitirme deshacer el -1. –

Esto parece ser un problema NP-Completo.

Hamiltoniano La ruta en la grilla es NP-Complete se ha mostrado aquí: Hamilton Paths in Grid Graphs.

Nota gráfica de cuadrícula = subgráfico de la cuadrícula completa.

Por supuesto, no he leído ese papel, así que confírmelo primero, especialmente el movimiento diagonal permitido.

Fuente

2010-05-20 18:16:42

¿Cómo se reduce esto a encontrar un camino hamiltoniano? Él explícitamente dice que puede visitar cada caja blanca tantas veces como quiera, lo que no es el caso en un camino hamiltoniano. – bnaul

@bnaul: una reducción similar a http://stackoverflow.com/questions/2359345/non-cycle-path-to-all-nodes/2360303#2360303 probablemente funcione. –

Doc lo tiene. Añadiré que los cuadros negros solo cambian la distancia entre todos los pares de cuadros blancos. Elaboración adicional: si hay una caja negra en la diagonal entre dos cuadros blancos (fácilmente comprobables), debe calcular un camino más corto para obtener la distancia. Una vez que tenga una matriz de distancia, entonces resuelva un TSP o una ruta de Hamilton solucionando un TSP después de crear un nodo ficticio con longitud cero para todos los otros nodos.

La clave es que para formular y resolver el TSP (o cualquier formulación de problema para el caso), DEBE tener una matriz de distancia para empezar. La matriz de distancia no se especifica al inicio, por lo que debe desarrollarse desde cero.

Fuente

2010-05-20 20:09:37 Grembo

mientras que la heurística basada en TSP es un enfoque razonable, no está claro que dé la respuesta óptima. El problema (como lo señala Moron) es el problema del camino de expansión, y en el enlace provisto en el comentario, hay muchos casos especiales para los cuales hay soluciones óptimas de tiempo lineal. Una captura que hace que el problema del PO sea diferente de la formulación del gráfico de cuadrícula utilizada en el documento citado es la capacidad de atravesar diagonalmente, lo que cambia bastante el juego.

Fuente

2010-06-30 20:56:42 Suresh

Encontrar el camino más corto para visitar todos los cuadrados no bloqueados en una cuadrícula

Respuesta

Cuestiones relacionadas