Camino más corto en un grafo no dirigido?

Question

Así que pensé que esta pregunta (aunque algo básico) pertenecía aquí:

decir que tengo un gráfico de tamaño de 100 nodos dispuestos en un patrón de 10x10 (pensar tablero de ajedrez). La gráfica se no dirigido, y no ponderado. Moviéndose a través de la gráfica implica mover tres espacios hacia delante y un espacio a la derecha o a la izquierda (similar a cómo un caballero ajedrez mueve a través de una junta).

Dado un nodo inicial fija, ¿cómo se encuentra la ruta más corta a cualquier otro nodo en la pizarra?

I imaginó que sólo habría un borde entre nodos que son mueve viables. Por lo tanto, teniendo en cuenta esta información, me gustaría encontrar el camino más corto desde un nodo de inicio a un nodo final.

Mi idea inicial era que cada borde se pondera con el peso 1. Sin embargo, el gráfico se no dirigidos, por lo Djikstras no sería un ajuste ideal. Por lo tanto, decidí hacerlo utilizando una forma alterada de una primera búsqueda en profundidad.

Sin embargo, no pude por la vida de mí visualizar cómo conseguir el camino más corto utilizando la búsqueda.

Otra cosa que probé estaba poniendo el gráfico en forma de árbol con el nodo de inicio como la raíz, y luego seleccionando el resultado más superficial (menor número de fila) que me dio el nodo final deseado ... esto funcionó, pero era increíblemente ineficiente , y por lo tanto no funcionaría para un gráfico más grande.

¿Alguien tiene alguna idea de lo que me podría apuntar en la dirección correcta en este caso?

Muchas gracias.

(Traté de poner en una visualización de la gráfica, pero no pudo debido a mi baja reputación)

Answer 1

Si los bordes en el gráfico sólo representan movimientos válidos entre ciertas posiciones, utilizando Dijkstra funcionaría bien. Sin embargo, como la gráfica es ponderado sería una exageración. Un simple primero en amplitud búsqueda dará la respuesta óptima.

Answer 2

Nicholas ya proporcionó una respuesta perfecta. Sin embargo, permítanme abordar su original intento de uso de búsqueda en profundidad.

En primer lugar, ya sea Dijkstra (que funciona bien con los nodos no ponderados como se indica por Nicholas Mancuso) o en amplitud buscar incurrir en los residuos exponencial de su memoria. Su ventaja, sin embargo, es que nunca vuelva a expandir los nodos, mientras que están garantizados para encontrar soluciones óptimas. Por desgracia, su limitación es bastante importante y que no se debe esperar para ampliar razonable.

Si se quiere resolver grandes casos de su consumo problemático de iterativo-Profundización primero en profundidad Búsqueda (IDFS). Sólo emitir una búsqueda en profundidad de su estado de inicio con un conjunto profundidad máxima a un umbral específico, $ d_ {max} $. Si no ha encontrado la solución, incremente la profundidad de la última iteración por una constante k $ $ fijo. Así, en el $ i $ -ésima iteración, una búsqueda en profundidad se lanza en profundidad $ d_ {max} + i \ times k $ (con la primera iteración siendo el número 0). Si $ d_ {max} = k = 1 $, entonces usted está garantizado para encontrar la solución óptima durante el uso de la memoria lineal en la profundidad de la solución.

Bueno, usted podría estar pensando que re-expansión de nodos es un lugar mala idea. ¡De ningún modo! Esto es lo que garantiza un consumo lineal de la memoria, mientras que la iteración de dominar el tiempo total de ejecución es sólo el último de manera que se pueda demostrar que este algoritmo incurre en una sobrecarga de $ \ frac {b} {B-1} $ con $ b $ siendo el factor de ramificación eficaz, y esto es claramente una pena muy pequeña vale la pena tomar en cuenta cuando se enfrentan a problemas difíciles.

Saludos,