algorithm - modelo - ¿A*heurísticas admisibles en una grilla con teletransportadores?

modelo de busqueda heuristica

Question

Supongamos que tiene una cuadrícula 2D de celdas, algunas de las cuales están rellenas con paredes. Los personajes pueden tomar un paso de un cuadrado a cualquier cuadrado que esté a un paso horizontal o vertical, pero no pueden cruzar las paredes.

Dada una posición inicial y una posición final, podemos encontrar la ruta más corta desde la posición inicial hasta la posición final utilizando el algoritmo A * con una heurística admisible. En esta configuración actual, la distancia de Manhattan sería admisible, ya que nunca sobreestima la distancia al destino.

Ahora supongamos que además de las paredes, el mundo tiene pares de teletransportadores. Al pisar un teletransportador, inmediatamente se transporta un personaje al teletransportador vinculado. La existencia de teletransportadores rompe la heurística admisible dada anteriormente, ya que podría ser posible llegar al destino más rápido que tomar la distancia óptima de Manhattan utilizando un teletransportador para reducir la distancia. Por ejemplo, considere este mundo lineal con los teletransportadores marcados con T, la posición inicial marcada con S y la posición final marcada con E:

T . S . . . . . . . . . . . . . E . T

Aquí, la mejor ruta es caminar hacia el teletransportador a la izquierda y luego dar dos pasos a la izquierda.

Mi pregunta es la siguiente: ¿qué es una buena heurística admisible para A * en un mundo interconectado con teletransportadores?

¡Gracias!

Answer 1

Forme una gráfica de los teletransportadores:

• Tiene un nodo para cada teletransportador y un nodo para la posición final.
• Tiene un borde que conecta cada nodo con cada otro nodo, formando un gráfico totalmente conectado.
• Para los pesos de borde, use la distancia de Manhattan entre la celda de destino de cada nodo (la que va cuando ingresa al teletransportador) y todos los demás nodos.

Utilice el algoritmo de Dijkstra para calcular la distancia más corta desde cada nodo hasta el final.

Ahora puede utilizar el mínimo de la distancia entre una posición particular y todos los nodos más la distancia calculada previamente desde el nodo hasta el final como una función heurística. El algoritmo de Dijkstra solo debe ejecutarse una vez como un paso de preprocesamiento. Sin embargo, si el número de teletransportadores es un gran porcentaje del número de células, es posible que no obtenga ningún beneficio sobre el uso de una función heurística más simple.

Answer 2

Si no hay demasiados teletransportadores en su mundo, probaría la siguiente heurística, donde MHD(a,b) es la distancia de Manhattan entre las celdas a y b y T(i) es el teletransportador más cercano a la celda i :

h(x,y) = min( MHD(x,y), MHD(x,T(x)) + MHD(T(y),y) )