Algoritmo per determinare il percorso più veloce che passa in tutti i punti

Questo è un problema NP-Hard

Ci sono state molte ricerche sulle approssimazioni al TSP. Dovresti cercare "approssimazioni per commessi viaggiatori". Questi saranno veloci, ma non garantiti ottimali / corretti.

Se riesci a risolverlo correttamente / ottimamente in tempo polinomiale, sarai un eroe CS eterno.

Come è stato ripetutamente menzionato, si tratta di un problema NP-difficile. Se il tuo problema è limitato a 5 vertici, allora puoi sicuramente forzare la tua strada verso la soluzione, come Eric Tressler menziona sopra. Vorrei aggiungere i miei due centesimi, però, perché trovo che i problemi difficili siano affascinanti ...

Se desideri che il tuo algoritmo sia trattabile, questa soluzione non funzionerà, perché man mano che il numero di vertici nel tuo grafico cresce, raggiungerà un punto che sarà semplicemente impossibile per il tuo algoritmo calcolare un percorso più breve durante la nostra vita (o persino dell'universo, a seconda di come hanno i vertici del tuo grafico). Esistono algoritmi di approssimazione per varianti del problema che potresti trovare interessante, sebbene ...

Esiste una 2-approssimazione (che in breve significa che si può dimostrare che il risultato restituito da questo algoritmo è a MOST 2 volte la lunghezza della rotta ottimale effettiva ... quindi potrebbe effettivamente restituire la rotta ottimale reale, qualcosa al massimo 2 volte la lunghezza, o qualsiasi altra via di mezzo, a seconda dell'ingresso) dell'algoritmo per il problema del venditore ambulante metrico. Questo è un caso speciale del problema del venditore ambulante in cui la distanza interurbana soddisfa la disuguaglianza triangolare, quindi non è lo stesso problema.

L'assunto fatto sta semplicemente cercando di far rispettare la disuguaglianza triangolare (ad esempio se hai il triangolo ABC, il percorso più breve tra A e C è AC rispetto a ABC. Ecco l'algoritmo che funziona in tempo polinomiale per TSP metrico:

G - il grafico G (V, E), dove V è l'insieme di vertici ed E è l'insieme di spigoli. C - funzione di costo definita come C: E- > N_o (la parte metrica ... il costo per prendere un margine)

ApproxMetricTSP(G, C):
    -Build a minimum spanning tree T (use Kruskal's or Prim's algorithms for
     this)
    -Run Depth-First-Search on T and keep track of the order in which the
     vertices are discovered
    -Return the cycle induced by the discovery order of vertices as H, the
     Hamiltonian cycle.

L'edificio T richiede tempo O (V ^ 2).

La parte DFS può essere eseguita in O (V), quindi l'algoritmo è O (V ^ 2).

Per ulteriori informazioni, consulta questo link !

Suppongo che tu stia cercando una leggera generalizzazione della pianificazione del percorso: hai una grande mappa con un numero enorme di connessioni possibili, vuoi guidare da A ad E (quale algoritmo di Dijkstra gestirà), ma tu voglio anche toccare i punti B, C e D.

Ovviamente è possibile eseguire l'algoritmo "distanza più breve" sei volte. Vorresti fare di meglio.

Comincerei ordinando le sei permutazioni di (B, C, D) in base alla lunghezza della connessione in linea retta. Diciamo che la connessione lineare A- > C- > D- > B- > E è la più corta. Trovi il percorso più breve da A a C, da C a D, da D a B, da B a E. Quindi provi gli altri percorsi, fermando il calcolo quando puoi dimostrare che il percorso sarà più lungo.

C'è una variazione intelligente dell'algoritmo "percorso più breve" se si ottimizzano solo le distanze: non si ottimizza la distanza totale, si ottimizza la differenza tra linea retta e distanza effettiva. Se pianifichi un percorso da A a B, e una delle connessioni X- > Y ha una distanza d, ma passando da X a Y ti avvicini al bersaglio B, quindi conti la distanza d - d ' , non d.

Con questa variazione, sarai spesso in grado di dimostrare rapidamente che una connessione sarà più lunga di quella ottimale. Dire che la distanza in linea retta A- > C- > D- > B- > E è 15.725 metri, il percorso effettivo più breve è 17,290 metri e la distanza in linea retta per un percorso diverso A- > C- & gt ; B- > D- > E è 17,260 metri, quindi è molto probabile che trovi rapidamente che toccare gli altri punti in quell'ordine non sia ottimale.

Qualcuno sembra insistere sul fatto che questo è il problema del "venditore ambulante". Non lo è, come capiresti se effettivamente leggi la domanda posta. È esattamente il problema che Google Maps risolve abitualmente quando lo chiedi per il percorso più breve da A a B mentre passi attraverso altri punti. Si tratta di una mappa con migliaia e migliaia di strade e un numero limitato di luoghi da visitare. La parte difficile del problema è trovare il percorso più breve da un luogo all'altro. Anche se fosse il problema del "commesso viaggiatore": perché mi interessa che un problema sia NP-completo se la dimensione del problema è 3?