Agregar waypoints a la búsqueda de gráfico A *

Question

Tengo la capacidad de calcular la mejor ruta entre un punto inicial y final usando A *. En este momento, estoy incluyendo waypoints entre mis puntos de inicio y final aplicando A * a los pares en todas las permutaciones de mis puntos.

Ejemplo:

quiero ir desde el punto 1 al punto 4. Adicionalmente, quiero pasar a través de los puntos 2 y 3.

calculo las permutaciones de (1, 2, 3, 4):

1 2 3 4 
1 2 4 3 
1 3 2 4 
1 3 4 2 
1 4 2 3 
1 4 3 2 
2 1 3 4 
2 1 4 3 
2 3 1 4 
2 3 4 1 
2 4 1 3 
2 4 3 1 
3 1 2 4 
3 1 4 2 
3 2 1 4 
3 2 4 1 
3 4 1 2 
3 4 2 1 
4 1 2 3 
4 1 3 2 
4 2 1 3 
4 2 3 1 
4 3 1 2 
4 3 2 1 

entonces, para cada permutación, calculo el a * ruta desde la primera a la segunda, a continuación, anexar a la ruta de la segunda a la tercera, a continuación, la tercera a la cuarta.

Cuando tengo esto calculado para cada permutación, clasifico las rutas por distancia y devuelvo el más corto.

Obviamente, esto funciona, pero implica una gran cantidad de cálculo y totalmente colapsa cuando tengo 6 puntos de interés (8 permutaciones de los elementos es 40320 :-))

¿Hay una mejor manera de hacer esto?

Answer 1

Antes que nada, debe almacenar todos los cálculos intermedios. Una vez que calculó la ruta del 1 al 2, nunca debería volver a calcularla, solo mire en una tabla. En segundo lugar, si su gráfico no está dirigido, una ruta de 2 a 1 tiene exactamente la misma distancia que una ruta de 1 a 2, por lo que tampoco debe volver a calcularla.

Y finalmente, en cualquier caso, tendrá un algoritmo que es exponencial al número de puntos que necesita pasar. Esto es muy similar al problema del vendedor ambulante, y será exactamente este el problema si incluye todos los puntos disponibles. El problema es NP-completo, es decir, tiene complejidad, exponencial a la cantidad de puntos de referencia.

Así que si tienes muchos puntos que debes pasar, el colapso exponencial es inevitable.

Answer 2

Como se mencionó en la respuesta anterior, este problema es el problema del vendedor itinerante NP completo.

Hay un método mejor que el que utiliza. El solucionador de TSP de última generación se debe a Georgia Tech's Concorde solver. Si no puede simplemente usar su programa gratuito o utilizar su API, puedo describir las técnicas básicas que utilizan.

Para resolver el TSP, comienzan con una heurística codiciosa llamada la heurística de Lin-Kernighan para generar un límite superior. Luego utilizan el método de ramificación y corte en una formulación de programación entera mixta del TSP. Esto significa que escriben una serie de restricciones lineales y enteras que, cuando se resuelven, le dan la ruta óptima del TSP. Su bucle interno llama a un solucionador de programación lineal como Qsopt o Cplex para obtener un límite inferior.

Como mencioné, este es el estado de la técnica así que si estás buscando una mejor manera de resolver el TSP de lo que estás haciendo, aquí está el mejor. Pueden manejar más de 10,000 ciudades en unos pocos segundos, especialmente en el TSM plano y simétrico (que sospecho es la variante en la que estás trabajando).

Si la cantidad de puntos de referencia que necesita manejar es pequeña, digamos del orden de 10 a 15, entonces puede realizar una búsqueda de bifurcación utilizando el minimum spanning tree heuristic. Este es un ejercicio de libros de texto en muchos cursos introductorios de IA.Más puntos de referencia que eso probablemente sobrevivirán el tiempo real de ejecución del algoritmo, y tendrá que usar Concorde en su lugar.