¿La distancia de Manhattan es monotónica cuando se usa como función heurística?

25

Tengo un mapa cuadrado. Solo se permiten movimientos horizontales y verticales (no diagonales). El costo de movimiento es siempre 1.

Estoy implementando un algoritmo A * en ese mapa, usando la distancia de Manhattan como heurística de distancia. ¿Es esto heurístico consistente? ¿Puedo evitar verificar los g(node)nodos que están en el conjunto CERRADO?

Editar: Por consistente quiero decir monótono.

tiles path-finding geometry Emiliano
fuente
1
Si su costo de movimiento es uniforme en todas las fichas, puede reemplazar A * con Jump Point Search
Nick Caplinger el
Oye, eso es lindo!
Emiliano

Respuestas:

10

Para responder realmente a su pregunta: la distancia entre el hombre y la mujer es consistente cuando se ve obligado a moverse verticalmente / horizontalmente a lo largo de una cuadrícula no ponderada (esto puede mostrarse fácilmente en la definición de wikipedia) . Entonces sí, en su caso puede evitar volver a comprobar los nodos en el conjunto cerrado.

Sin embargo, una vez que permite el movimiento en diagonal o en cualquier ángulo, la distancia de la pantalla se vuelve inadmisible porque sobreestima los costos diagonales, lo que necesariamente significa que no es consistente.

BlueRaja - Danny Pflughoeft
fuente
Sí, este es exactamente el tipo de respuesta que estaba buscando. Sería bueno saber qué sucede si la función heurística es h(x) = min(manhattan(p1), manhattan(p2))( es decir, p1 o p2 son un buen punto final y quiero llegar al más cercano). ¿ h(x)Sigue siendo monótono?
Emiliano
1
@happy_emi: Sí, si h(x, p1)y h(x, p2)son consistentes, entonces min(h(x,p1), h(x,p2))también serán consistentes. Esto es fácil de mostrar desde la definición en wikipedia (tendríamos que mostrar eso min(h(x, p1), h(x, p2)) <= distance(x,y) + min(h(y, p1), h(y, p2))para todos los nodos xy ycon un borde entre ellos. Ahora suponga que h(x, p1)es el mínimo; ¿puede mostrar que definitivamente es <=el lado derecho, usando el hecho de que ambas heurísticas son consistentes?)
BlueRaja - Danny Pflughoeft
31

Sí, la distancia de Manhattan entre dos puntos es siempre la misma, al igual que la distancia regular entre ellos. Puedes pensar en la distancia de Manhattan como los componentes X e Y de una línea que corre entre los dos puntos.

Esta imagen ( de Wikipedia ) ilustra esto bien:

Distancias de Manhattan

La línea verde es la distancia real.

Las líneas azul , roja y amarilla representan la misma distancia de Manhattan (12 unidades). No importa qué combinación de movimientos hacia arriba y hacia la derecha dibuje desde el punto inferior izquierdo hacia el inferior derecho, obtendrá la misma distancia total de Manhattan.

MichaelHouse
fuente
2
Gran respuesta: corta, dulce, al punto y con una imagen bonita.
Tom 'Blue' Piddock
1
Esta respuesta está cerca, pero es incorrecta. Esta imagen no muestra que la distancia Manhattan es constante (de hecho, si se tiene en cuenta la línea verde como la distancia, es no ! Coherente) , y el razonamiento de que él no necesita volver a revisar los nodos debido a "la distancia entre Manhattan dos puntos son siempre iguales " no se cumple (la afirmación también es cierta h(x) = 1000, lo que obviamente no es consistente) . Se puede evitar volver a comprobar los nodos, pero sólo porque la distancia Manhattan es consistente, que esta respuesta no mostrar.
BlueRaja - Danny Pflughoeft
2
Creo que por la definición que vinculaste, la distancia de Manhattan es consistente. La distancia de la línea verde estaría usando una heurística diferente. Las líneas roja, azul y amarilla muestran que la distancia entre los dos nodos permanece igual (cuando se usa la misma heurística). Acercarse reduce la heurística y alejarse aumenta la heurística. Esto cumple con el requisito monótono del OP. A medida que se construye el gráfico, con un nodo en cada "intersección", la distancia de Manhattan es consistente. Si fuera un escenario diferente (como permitir el movimiento diagonal), la heurística sería mala.
MichaelHouse
2
Ya dije que la distancia de Manhattan es consistente, pero no por las razones que mencionas. Su respuesta no muestra coherencia, ni su argumento en los comentarios. "Heurística coherente / monótona" tiene una definición precisa (dada en mi enlace anterior) , que no es lo mismo que una función monótona para la que parece confundirla. Afirmar que "acercarse reduce la heurística y alejarse aumenta la heurística" no es suficiente para demostrar que es consistente, por ejemplo. 2*manhattensatisface eso, pero no es consistente.
BlueRaja - Danny Pflughoeft
3
No sé por qué dice que es incorrecto , parece que insiste en que esta respuesta es incompleta . La prueba en su respuesta parece ser igual de débil: "la distancia entre los hombres es constante ...", luego continúa reiterando las especificaciones originales de la pregunta, y luego explica cómo sería no admisible si el escenario fuera diferente . No sentía que la respuesta justificara una prueba matemática completa. Si cree que esta pregunta requiere eso, inclúyala en su respuesta y la votaré. Gracias por la critica constructiva.
MichaelHouse
6

En extensión de la respuesta de Byte56, me gustaría señalar que, en su conjunto de datos específico, usar la Distancia de Manhattan como su función heurística siempre será una heurística perfecta en el sentido de que siempre devolverá el costo real de la ruta (suponiendo que haya nada "bloqueando" los caminos).

También debe tener en cuenta que todos los nodos en la dirección correcta (ya sea horizontal o vertical) producirán la misma distancia esperada (porque hay muchos caminos igualmente cortos hacia la meta). Debe tener en cuenta que su cola de prioridad (conjunto abierto) debe, en caso de prioridades vinculadas, eliminar primero el último nodo agregado (LIFO - Último en entrar, primero en salir). Al hacerlo, solo examinará los nodos que terminarán en la ruta óptima . Si examina nodos igualmente adecuados de manera FIFO (primero en entrar, primero en salir), examinará efectivamente todos los nodos que forman parte de una mejor ruta. Este problema surge porque hay múltiples rutas igualmente buenas para el nodo objetivo.

Thorkil Holm-Jacobsen
fuente
"(suponiendo que no haya nada bloqueando el camino)" , esa es una suposición bastante grande. Si no hay nada bloqueando el camino, ¡no hay necesidad de un algoritmo de búsqueda de camino para empezar!
BlueRaja - Danny Pflughoeft
@ BlueRaja-DannyPflughoeft: Eso es cierto, fue solo un pensamiento que surgió al mirar la imagen de Byte56. El resto es cierto, no obstante.
Thorkil Holm-Jacobsen
4

No estoy seguro de qué quieres decir con "siempre" consistente. ¿La distancia de Manhattan en una cuadrícula fija es independiente del camino tomado? Sí, como decía la respuesta de Byte56.

Sin embargo, por ejemplo, la distancia de Manhattan no es invariable bajo rotaciones. Por ejemplo, la distancia de Manhattan ( norma L1 ) entre el origen y un punto (10,10)es |10-0| + |10-0| = 20. Sin embargo, si gira sus coordenadas 45 grados (por lo que ahora su punto fijo se encuentra a lo largo de una de las direcciones de la cuadrícula), ahora encontrará que el mismo punto está ahora (10sqrt(2),0), por lo que tiene una distancia de Manhattan al origen de 10sqrt(2)~14.14.

dr jimbob
fuente
+1 por señalar esto; OTOH, la distancia de Manhattan es invariante bajo rotaciones de 90 grados, que son realmente las únicas que se pueden hacer 'consistentemente' en una cuadrícula discreta.
Steven Stadnicki
1
Buena captura, aunque mencionó que solo se permiten movimientos horizontales y verticales.
Thorkil Holm-Jacobsen
1
La pregunta original era consistente como en monotónica.
Emiliano