A * heurística: el camino más corto que pasa una vez en varios puntos

Question

Estoy tratando de encontrar una heurística buena y rápida para un juego de pacman de mapa claro.

Mi heurística está tratando de calcular la menor distancia posible que el pacman necesita para viajar para llegar a cada punto con comida en el mapa. Mi algoritmo actual es básicamente el MST de Prim, que me da un tiempo de ejecución de O (n logn), pero no da cuenta de situaciones donde el pacman necesita seguir un borde para comer y el retorno al vértice anterior ...

¿Hay algo mejor?

Diciéndolo de otra manera: ¿Cuál es el costo mínimo de conexión de varios puntos sin levantar mi pluma?

Gracias

Answer 1

Después de ejecutar un algoritmo todos los pares de-la ruta más corta y la identificación de los vértices con los alimentos, esto se convierte en la traveling salesman problem. No puede resolverlo de manera eficiente, pero puede construir aproximaciones arbitrariamente buenas a una solución en tiempo polinomial. Probablemente desees utilizar una aproximación a menos que puedas precomputar todo. Si puede calcular previamente las cosas (o garantizar que tiene tiempo suficiente para encontrar una solución exacta), una vez que tenga las rutas más cortas, podrá encontrar la longitud mínima total de caminata sobre todas las posibles permutaciones del orden en que comes las piezas de comida. Este método de fuerza bruta probablemente puede mejorarse de alguna manera al vigilar cuando el camino más corto entre dos pedazos de comida cruza otra porción de alimento.