algorithm - opciones - ¿Hay alguna manera de mantener las prioridades de dirección en A*?(es decir, generar el mismo camino que amplitud-primero)

opciones de activación de la etiqueta

Question

Tengo una aplicación que se beneficiaría del uso de A *; sin embargo, por razones heredadas, necesito que siga generando exactamente las mismas rutas que antes, cuando hay varias rutas para elegir.

Por ejemplo, considera este laberinto

...X FX.S .... S = start F = finish X = wall . = empty space

con dirección-prioridades Arriba; Derecha; Abajo; Izquierda Al usar el ancho primero, encontraremos la ruta DLLLU; sin embargo, al usar A * inmediatamente vamos a la izquierda, y terminamos encontrando el camino LULLD.

Intenté asegurarme de expandirme siempre en la dirección correcta al romper las ataduras; y sobrescribir los punteros de PrevioNodo cuando se mueve desde una dirección más importante, pero ninguno de los dos funciona en ese ejemplo. ¿Hay alguna forma de hacer esto?

Answer 1

En general, no hay una forma no trivial de hacer esto:

La búsqueda de primer orden encuentra la ruta más corta de orden más bajo determinada por el orden en que se consideran los vértices. Y este orden debe tener prioridad sobre cualquier otro factor cuando se rompen vínculos entre trayectos de igual longitud.

Ejemplo: si los nodos se consideran en el orden A, B, C, entonces Node A < Node C Por lo tanto, si hay un empate entre un camino más corto que comienza con A y uno que comienza con C, se encontrará el que tiene A.

Por otro lado, la búsqueda A * encontrará la ruta más corta de orden más bajo determinada por el valor heurístico del nodo. Por lo tanto, la heurística debe tener en cuenta la ruta lexicográfica más baja para cada nodo. Y la única forma de encontrar eso es BFS.

Answer 2

Construiría la preferencia en el orden de ruta directamente en la función heurística

me gustaría ver el algoritmo de pan primero

defina una función para cada ruta que elija el algoritmo bread-first:

consideramos que estamos ejecutando un algoritmo de profundidad, y es en n-ésima profundidad las decisiones hechas anteriormente por el algo: x_i / en {U, R, D, L} asignar U = 0, R = 1, D = 2, L = 3

luego define:

g(x_1,..,x_n) = sum_{i=1}^n x_i * (1/4)^i

arreglemos el valor g de este paso como g ''en cada paso cuando el algoritmo visite un nodo más profundo que este, la función g () sería mayor.

en cada paso futuro cuando se cambia de {1..n} x_i, será mayor, por lo tanto, es cierto que la función g siempre aumenta al ejecutar primero la profundidad.

Nota: si el algoritmo de profundidad primero es exitoso, selecciona la ruta con el valor mínimo de g ()

nota: g () <1 beacuse max (L, R, U, D) = 3

Agregar g a la función heurística de A * no interferirá con la longitud de ruta más corta porque la longitud de borde mínima es> = 1

la primera solución que un A * modificado como este encontraría sería la que encontraría la primera profundidad

para ti ejemplo:

h_bread=g(DLLLU) = (23330)_4 * c
h_astar=g(LULLD) = (30332)_4 * c

() _4 es base4 c es una constante (4 ^ {- 5})

para ti ejemplo: h_bread <h_astar

Answer 3

Si el algoritmo original era BFS, está buscando el camino más pequeño de los más cortos donde "más pequeño" es según el orden lexicográfico inducido por un orden total Ord en los bordes (y por supuesto "más corto" es según la longitud del camino).

La idea de ajustar los pesos sugerida por amit es natural, pero no creo que sea muy práctica porque los pesos necesitarían tener una cantidad de bits comparable a la longitud de una ruta para evitar descartar la información, lo que haría que el algoritmo órdenes de magnitud más lento.

Afortunadamente esto aún puede hacerse con dos modificaciones simples y económicas a A *:

1. Una vez que alcanzamos el objetivo, en lugar de devolver un camino arbitrario más corto hacia la meta, debemos continuar visitando los nodos hasta que la longitud de la ruta aumente, de modo que visitamos todos los nodos que pertenecen a la ruta más corta.
2. Al reconstruir la ruta, construimos el conjunto de nodos que contribuyen a las rutas más cortas. Este conjunto tiene una estructura DAG cuando se consideran todos los bordes de ruta más cortos, y ahora es fácil encontrar la ruta más pequeña de lexicografía desde el start hasta el goal en este DAG, que es la solución deseada.

Esquemáticamente, el clásico A * es:

path_length = infinity for every node
path_length[start] = 0

while score(goal) > minimal score of unvisited nodes:
    x := any unvisited node with minimal score
    mark x as visited
    for y in unvisited neighbors of x:
        path_length_through_x = path_length[x] + d(x,y)
        if path_length[y] > path_length_through_x:
            path_length[y] = path_length_through_x
            ancestor[y] = x

return [..., ancestor[ancestor[goal]], ancestor[goal], goal]

donde la score(x) representa path_length[x] + heuristic(x, goal) de path_length[x] + heuristic(x, goal) .

Simplemente convertimos la estricta desigualdad de ciclo en una no estricta y agregamos una fase de reconstrucción de ruta:

path_length = infinity for every node
path_length[start] = 0

while score(goal) >= minimal score of unvisited nodes:
    x := any unvisited node with minimal score
    mark x as visited
    for y in unvisited neighbors of x:
        path_length_through_x = path_length[x] + d(x,y)
        if path_length[y] > path_length_through_x:
            path_length[y] = path_length_through_x

optimal_nodes = [goal]
for every x in optimal_nodes:  // note: we dynamically add nodes in the loop
    for y in neighbors of x not in optimal_nodes:
        if path_length[x] == path_length[y] + d(x,y):
            add y to optimal_nodes

path = [start]
x = start
while x != goal:
    z = undefined
    for y in neighbors of x that are in optimal_nodes:
        if path_length[y] == path_length[x] + d(x,y):
            z = y if (x,y) is smaller than (x,z) according to Ord
    x = z
    append x to path

return path

Advertencia: para citar a Knuth, solo lo he probado correcto, no lo he probado.

En cuanto al impacto en el rendimiento, debe ser mínimo: el bucle de búsqueda solo visita nodos con una puntuación 1 unidad más alta que la A * clásica, y la fase de reconstrucción es casi lineal en la cantidad de nodos que pertenecen a la ruta más corta. El impacto es menor si, como implica, solo hay una ruta más corta en la mayoría de los casos. Incluso puede optimizar para este caso especial, por ejemplo, recordando un nodo ancestor como en el caso clásico, que establece un valor de error especial cuando hay más de un antecesor (es decir, cuando path_length[y] == path_length_through_x ). Una vez que el bucle de búsqueda termina, intenta recuperar una ruta a través de un ancestor como en el clásico A *; solo necesita ejecutar la reconstrucción completa de la ruta si se encontró un valor de error al construir la ruta.

Answer 4

He encontrado dos formas de hacer esto. Ambos requieren continuar con el algoritmo, mientras que la parte superior de la cola tiene un valor g de distancia-inicio <= g (nodo-final). Dado que la heurística utilizada en A * es admisible , esto garantiza que cada nodo que pertenece a alguna de las mejores rutas eventualmente se expandirá.

El primer método es cuando llegamos a un conflicto (es decir, encontramos dos nodos con el mismo valor f que podrían ser los padres de algún nodo a lo largo de la mejor ruta) , lo resolvemos retrocediendo al primer punto a lo largo del camino que se encuentran (podemos hacerlo fácilmente en O(path-length) ) . Luego simplemente verificamos las prioridades de dirección de ambas rutas, y elegimos la ruta que tenga la prioridad más alta en una búsqueda BFS.

El segundo método solo funciona para cuadrículas donde cada nodo toca los nodos adyacentes horizontal y verticalmente (y posiblemente en diagonal) (es decir, cuadrículas conectadas en 4) . Hacemos lo mismo que antes, pero en lugar de retroceder para resolver un conflicto, comparamos los nodos a lo largo de las rutas desde el principio y encontramos el primer lugar en el que difieren. El primer lugar en el que difieran será el mismo nodo crítico que antes, desde el cual podemos verificar las prioridades de dirección.

Hacemos esto almacenando la mejor ruta hasta el momento para cada nodo. Normalmente esto sería engorroso, pero dado que tenemos un gráfico de 4 conexiones, podemos hacer esto de manera bastante eficiente almacenando cada dirección tomada a lo largo de la ruta. Esto tomará solo 2 bits por nodo. Por lo tanto, podemos esencialmente codificar la ruta usando enteros, con registros de 32 bits podemos comparar 16 nodos a la vez; 32 nodos con registros de 64 bits; y 64 (!) nodos a la vez con registros de 128 bits (como los registros SSE en procesadores x86 y x64), lo que hace que esta búsqueda sea muy económica incluso para rutas con 100 de nodos.

Implementé ambos, junto con el algoritmo de @generic human, para probar la velocidad. En una cuadrícula de 50x50 con 400 torres,

• El algoritmo de @generic human ejecutó aproximadamente un 120% más lento que lo normal A *
• mi algoritmo backtracking corrió aproximadamente un 55% más lento que lo normal A *
• El algoritmo de codificación de enteros solo ejecutó menos del 10% más lento que A *

Por lo tanto, dado que mi aplicación usa gráficos conectados en 4, parece que el algoritmo de codificación de enteros es mejor para mí.

Copié un correo electrónico que escribí a un profesor aquí . Incluye descripciones más detalladas de los algoritmos, junto con bocetos de pruebas que funcionan.