Optimización del algoritmo - Ruta más corta entre varios puntos

Question

Problema: Tengo una gran colección de puntos. Cada uno de estos puntos tiene una lista con referencias a otros puntos con la distancia entre ellos ya calculada y almacenada. Necesito determinar la ruta más corta que comienza desde un origen y pasa por un número específico de puntos hasta cualquier destino.

Ejemplo: estoy de vacaciones y me estoy quedando en una ciudad específica. Estoy haciendo un viaje de UNA VÍA para ver CUALQUIER cuatro ciudades y quiero viajar la menor distancia posible. No puedo visitar la misma ciudad más de una vez.

Solución actual: en este momento estoy simplemente iterando manualmente a través de cada posibilidad y almacenando la ruta más corta. Esto funciona pero se siente ineficiente. Además, este problema eventualmente se ampliará para incluir la búsqueda desde múltiples puntos de origen a múltiples puntos de destino, por lo que creo que podría explotar el espacio de búsqueda.

¿Cuál es la mejor manera de buscar la ruta más corta?

Answer 1

Respondiendo a la publicación actualizada, su solución para controlar todas las posibilidades es óptima (al menos, nadie ha descubierto mejores algoritmos hasta el momento). Sí, es un vendedor ambulante, cuya esencia no es tocar todas las ciudades, sino tocar cada ciudad una vez. Si no desea buscar la mejor solución posible, puede resultarle útil utilizar heurísticas que funcionen más rápido, pero que permitan una discrepancia limitada de la solución ideal.

---

Para futuros que responden: Floyd-Warshall algorithm y todos Floyd-como las variaciones no son aplicables aquí.

Answer 2

Esto suena Traveling Salesman-esque? Una solución es usar una técnica de optimización como un algoritmo evolutivo. Actualmente estás haciendo una búsqueda exhaustiva, que se hará muy lenta muy rápidamente. Pero creo que esto es más o menos un problema de vendedor ambulante y se ha abordado durante varias décadas si no siglos, y hay varias formas posibles de ataque. Google es tu amigo.

Answer 3

En general, se debe a la estricta variantes malas ... creo que puedes usar algunas variaciones del método Branch_and_bound http://en.wikipedia.org/wiki/Branch_and_bound

Answer 4

De cualquier bredth primera búsqueda como norheim.se dicho o Dijkstra's algorithm sería mi sugerencia también.

Answer 5

Parece que los bordes de su gráfico son bidireccionales. En este caso, el algoritmo que está buscando es Dijkstra's algorithm.

Answer 6

Quizás esto es lo que significa el cartel original al "iterar manualmente a través de cada posibilidad y almacenar la ruta más corta", pero pensé que me gustaría hacer explícita lo que parece ser una solución de referencia.

Supongamos que ya tiene un algoritmo de ruta más corta de dos puntos; esto tiene soluciones clásicas para varios tipos de gráficos. Suponga que todas las distancias son no negativas y d (A-> B-> C) = d (A-> B) + d (B-> C).

Lo esencial es que el camino comienza en S pasa a través de una de las ciudades intermedias "ABCD" y termina con E:

por ejemplo SabcdE, SacbdE, etc ...

Con solo 4 ciudades intermedias, enumera las 24 permutaciones. Para cada permutación use su algoritmo de dos puntos más corto para calcular el camino de la cabeza a la cola, y su distancia total.

Luego, dado el punto de inicio y el punto final, hay 12 posibilidades asociadas a una de abcd y para cada dos posibilidades para el interior. Ya ha calculado estas distancias, por lo que agrega la distancia de S a la cabeza y la cola a E. Elija un mínimo. Entonces, una vez que ha calculado previamente las distancias intermedias para un conjunto fijo de ciudades interiores, necesita hacer 12 problemas de ruta más cortos de dos puntos para cualquier par de puntos de inicio y final.

Esto, evidentemente, escasea mal con el aumento del número de ciudades intermedias. No está claro para mí que podría hacerlo mejor a menos que impongas mayores restricciones en la estructura del gráfico (¿es esto en un espacio físico euclidiano? ¿Desigualdad triangular?).

Mi ejemplo de pensamiento: supongamos que todas las distancias intermedias entre ciudades son O (1). Sin restricción en el gráfico, la distancia de S a cualquier ciudad intermedia puede ser de 1000, excepto que una es 1. Lo mismo para la cola. Entonces puedes forzar a la primera ciudad a ser visitada para que sea cualquier cosa. Ahora, baje una capa, tome la primera ciudad como el "punto de inicio". Aplique el mismo argumento: puede hacer que la mejor ruta vaya a cualquiera de las siguientes ciudades al manipular las distancias en el gráfico.

Parece que no se puede evitar la complejidad sin suposiciones adicionales.

Answer 7

Esta es la situación muy común y en tiempo real en la que cualquiera puede caer. La interfaz de usuario del mapa de Google le proporciona la ruta en el mismo orden, la agrega en la lista de destinos. no le proporciona la ruta óptima, aunque su API de Google Maps proporciona la solución.

Google maps API proporciona la solución para esto. En la solicitud para averiguar el camino, debe proporcionar la marca 'optimizeWaypoints: true,'. La solicitud se verá así.

var request = { 
      origin: start, 
      destination: end, 
      waypoints: waypts, 
      optimizeWaypoints: true, 
      travelMode: google.maps.TravelMode.DRIVING 
     }; 

y se puede ver el código totalidad de la utilidad de la fuente de la visión completa utilidad que se desarrolla en JavaScript y HTML.

Espero que ayude.