Ottimizzazione dell'algoritmo: percorso più breve tra più punti

Question

Problema: ho una vasta collezione di punti. Ciascuno di questi punti ha una lista con riferimenti ad altri punti con la distanza tra loro già calcolata e memorizzata. Devo determinare il percorso più breve che inizia da un'origine e passa attraverso un numero specifico di punti verso qualsiasi destinazione.

Es: Sono in vacanza e resto in una città specifica. Sto facendo un viaggio di ONE WAY per vedere QUALSIASI quattro città e voglio viaggiare la minima distanza possibile. Non posso visitare la stessa città più di una volta.

Soluzione corrente: In questo momento sto solo iterando su ogni possibilità manualmente e memorizzando il percorso più breve. Funziona ma sembra inefficiente. Inoltre, questo problema verrà espanso per includere la ricerca da più punti di origine a più punti di destinazione, quindi penso che potrebbe esplodere lo spazio di ricerca.

Qual è il modo migliore per cercare il percorso più breve?

Answer 1

Rispondendo al post aggiornato, la soluzione di controllo di ogni possibilità è ottimale (almeno, nessuno ha scoperto algoritmi migliori finora). Sì, è un venditore ambulante, la cui essenza non tocca tutte le città, ma tocca ogni città una volta. Se non si desidera cercare la migliore soluzione possibile, potrebbe essere utile utilizzare l'euristica che funziona più rapidamente, ma consentire una discrepanza limitata dalla soluzione ideale.

---

Per answerers futuri: Floyd-Warshall algorithm e tutto Floyd-come variazioni sono inapplicabili qui.

Answer 2

Questo suona come un commesso viaggiatore? Una soluzione è utilizzare una tecnica di ottimizzazione come un algoritmo evolutivo. Attualmente stai facendo una ricerca esaustiva, che diventerà molto lenta molto rapidamente. Ma penso che questo sia più o meno un problema di commesso viaggiatore e sia stato affrontato per diversi decenni se non secoli, e quindi ci sono diverse possibili vie di attacco. Google è tuo amico.

Answer 3

In generale si dovrebbe le severe varianti cattive ... Credo che si dovrebbe usare alcune varianti del metodo Branch_and_bound http://en.wikipedia.org/wiki/Branch_and_bound

Answer 4

In entrambi i bredth prima ricerca come norheim.se detto o Dijkstra's algorithm sarebbe il mio suggerimento pure.

Answer 5

Sembra che i bordi del grafico siano bidirezionali. In questo caso, l'algoritmo che stai cercando è Dijkstra's algorithm.

Answer 6

Forse questo è ciò che il manifesto originale intende "iterando attraverso ogni possibilità manualmente e memorizzando il percorso più breve", ma ho pensato che mi piacerebbe rendere esplicita quella che sembra essere una soluzione di base.

Supponiamo che tu abbia già un algoritmo a due punti di percorso più breve - questo ha soluzioni classiche per vari tipi di grafici. Si supponga che tutte le distanze siano non negative e d (A-> B-> C) = d (A-> B) + d (B-> C).

Gli elementi essenziali sono che il percorso inizia S passa attraverso una delle città intermedie "ABCD" e termina con E:

esempio SabcdE, SacbdE, ecc ...

Con solo 4 città intermedie, si elencano tutte e 24 le permutazioni. Per ogni permutazione usa il tuo algoritmo a due punti più breve per calcolare il percorso dalla testa alla coda e la sua distanza totale.

Quindi, dato il punto di partenza e di arrivo, ci sono 12 possibilità di collegamento a una di abcd e per ogni due possibilità per l'interno. Hai già calcolato queste distanze, quindi aggiungi la distanza da S alla testa e la coda a E. Scegli il minimo. Quindi, una volta che hai precalcolato le distanze intermedie per un insieme fisso di città interne, devi fare 12 problemi con il percorso più breve in due punti per ogni coppia di punti iniziali e finali.

Questo ovviamente peggiora scarsamente con il numero crescente di città intermedie. Non è chiaro per me che potrebbe fare meglio a meno che non impongano maggiori restrizioni sulla struttura del grafico (è questo in uno spazio fisico di Euclidenan? Disuguaglianza del triangolo?).

Il mio esempio di riflessione: supponiamo che tutte le distanze intermedie tra le città siano O (1). Senza alcuna restrizione sul grafico, la distanza da S a qualsiasi città intermedia potrebbe essere 1000 tranne che per uno è 1. Lo stesso per la coda. Quindi puoi costringere la prima città a essere visitata per essere qualsiasi cosa. Ora, abbassa uno strato, prendi la prima città come "punto di partenza". Applica lo stesso argomento: puoi fare in modo che il percorso migliore vada in una delle seguenti città manipolando le distanze nel grafico.

Quindi sembra che la complessità non possa essere aiutata senza ulteriori presupposti.

Answer 7

Questa è la situazione molto comune e in tempo reale in cui ognuno può rientrare. L'interfaccia utente di Google Map fornisce il percorso nello stesso ordine, si aggiunge all'elenco di destinazione. non ti dà il percorso ottimale anche se la loro API di Google Maps fornisce la soluzione.

L'API di Google Maps fornisce la soluzione per questo. Nella richiesta di scoprire il percorso devi fornire il flag 'optimizeWaypoints: true'. La richiesta sembrerà così.

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

e si può vedere tutto il codice del programma di utilità nella sorgente di visualizzazione come completa utility è sviluppato in JavaScript e HTML.

Spero che possa essere d'aiuto.