adjacency - shortest path matrix

Cómo encontrar el camino más corto en este tipo de laberinto.

Question

Red Dot - Represents the initial location
Black Dot - Already occupied
Green - Free to occupy
Destination - Boundry of the matrix [which means either x = 0 or y = 0 or x = 8 or y = 8]

Ejemplo:

El red dot puede colocarse solo un movimiento a la vez y puede moverse en uno de los seis círculos verdes que se le unen. ¿Cuál será el método más rápido para calcular la ruta más corta en este tipo de laberinto?

Answer 1

En primer lugar, no necesita Dijkstra, porque todos los valores de los bordes son iguales. Puede utilizar un algoritmo simple BFS o DFS . Las complejidades de los peores casos son las mismas, pero yo usaría BFS ya que tiene una complejidad de caso promedio mejor. Sin embargo, O (| V | + | E |) es lo más rápido que puede llegar hasta aquí y está comprobado.

¿Cómo tener tu gráfica representada? La mejor manera es mantener una lista de vecinos para cada Node . Los puntos negros de tu ejemplo no se cuentan como vecinos. Entonces, en su ejemplo, cada nodo tendría 0 (totalmente cubierto por puntos negros) a 6 vecinos. Luego, puede llegar a cualquier lugar que pueda obtener desde cualquier punto de nodo a través de estas listas.

El algoritmo BFS tiene una propiedad que asigna una capa a cada nodo, lo que significa qué tan lejos está de un nodo inicial. Empiezas en tu punto de inicio y tu capa actual será 0. Luego, solo sigues todos los nodos de una capa actual (generalmente mantenidos en la cola) e intentas encontrar sus vecinos (de su lista de vecinos), que no tienen capa Asignado y les asignas +1 capa superior. Una vez que encuentre su Nodo, (que aún puede tener x, y como atributos para el control de borde (o borde de la propiedad)), en el borde de su laberinto, sabe que está tan lejos como está el valor de su capa. Si desea imprimir de la manera exacta, solo tiene que encontrar el camino de regreso (a través de sus listas de vecinos) que cumpla con la condición de que cada paso esté en -1 capa inferior. Esto imprimirá el camino de principio a fin, pero estoy seguro de que obtendrá su resultado con un poco de ayuda de la estructura de datos de la Stack :)

Answer 2

Lo que tienes es un problema gráfico "simple". La conectividad gráfica es el movimiento legal que tienes. El nodo de inicio es tu punto rojo. Para obtener un solo nodo terminal, invente un círculo más fuera del laberinto dado; conecte todos los nodos de salida reales al nuevo círculo con un movimiento de costo cero.

Ahora, aplique el algoritmo de Dijkstra. Hecho.

Otra forma de ver el problema es con la recursividad. Mueve el punto rojo, marcando la ubicación antigua en negro. Repetir desde la nueva posición. Regrese cuando salga (devuelva la longitud del camino 1) o no tenga movimientos legales (devuelva la longitud del camino infinito). Mantener el camino más corto conocido.

¿Te quitan eso?

Answer 3

A * algoritmo de búsqueda

(de: https://en.wikipedia.org/wiki/A*_search_algorithm )

El siguiente pseudocódigo describe el algoritmo [dudoso - discutir]:

function A*(start,goal)
    ClosedSet := {}       // The set of nodes already evaluated.
    OpenSet := {start}    // The set of tentative nodes to be evaluated, initially containing the start node
    Came_From := the empty map    // The map of navigated nodes.


    g_score := map with default value of Infinity
    g_score[start] := 0    // Cost from start along best known path.
    // Estimated total cost from start to goal through y.
    f_score := map with default value of Infinity
    f_score[start] := g_score[start] + heuristic_cost_estimate(start, goal)

    while OpenSet is not empty
       current := the node in OpenSet having the lowest f_score[] value
        if current = goal
            return reconstruct_path(Came_From, goal)

       OpenSet.Remove(current)
       ClosedSet.Add(current)
       for each neighbor of current
           if neighbor in ClosedSet 
               continue     // Ignore the neighbor which is already evaluated.
        tentative_g_score := g_score[current] + dist_between(current,neighbor) // length of this path.
        if neighbor not in OpenSet  // Discover a new node
            OpenSet.Add(neighbor)
        else if tentative_g_score >= g_score[neighbor] 
            continue        // This is not a better path.

        // This path is the best until now. Record it!
        Came_From[neighbor] := current
        g_score[neighbor] := tentative_g_score
        f_score[neighbor] := g_score[neighbor] + heuristic_cost_estimate(neighbor, goal)

return failure

function reconstruct_path(Came_From,current)
    total_path := [current]
    while current in Came_From.Keys:
        current := Came_From[current]
        total_path.append(current)
    return total_path

así que, según tengo entendido, puede establecer su nodo de inicio en la posición del punto rojo / posición central y el nodo objetivo como x = 0 o y = 0 o x = 8 o y = 8 (puede hacer 4 llamadas de función , y tomar el mínimo)

En cuanto a los valores heurísticos para el nodo, simplemente configure los nodos bloqueados en negro con valores heurísticos muy altos, lo que los hará inalcanzables, de modo que el algoritmo los rodeará.