: percorso più breve tra tutti i punti

Question

Supponiamo che abbia 10 punti. Conosco la distanza tra ogni punto.

Ho bisogno di trovare il percorso più breve possibile passando attraverso tutti i punti.

Ho provato un paio di algoritmi (Dijkstra, Floyd Warshall, ...) e tutti mi danno il percorso più breve tra inizio e fine, ma non fanno un percorso con tutti i punti su di esso.

Le permutazioni funzionano bene, ma sono troppo costose.

Quali algoritmi puoi consigliare per cercare questo problema? O c'è un modo documentato per farlo con gli algoritmi sopra menzionati?

Answer 1

Dai un'occhiata allo travelling salesman problem.

Si consiglia di esaminare alcuni degli heuristic solutions. Potrebbero non essere in grado di darti risultati esatti al 100%, ma spesso possono trovare soluzioni sufficientemente buone (dal 2 al 3% lontano dalle soluzioni ottimali) in un ragionevole lasso di tempo.

Answer 2

Questo è ovviamente Travelling Salesman problem. Specificatamente per N=10, è possibile provare l'algoritmo ingenuo O(N!) o utilizzare Dynamic Programming, è possibile ridurlo a O(n^2 2^n), scambiando spazio.

Oltre a ciò, poiché questo è un problema NP-difficile, puoi solo sperare in un'approssimazione o euristica, dati i soliti avvertimenti.

Answer 3

Come altri hanno menzionato, questa è un'istanza del TSP. Penso che lo Concord, sviluppato da Georgia Tech, sia l'attuale soluzione all'avanguardia. Può gestire fino a 10.000 punti in pochi secondi. Ha anche un'API facile da usare.

Answer 4

credo che questo è quello che stai cercando, in realtà:

Floyd Warshall

In informatica, l'algoritmo di Floyd-Warshall (a volte conosciuto come l'algoritmo WFI [chiarificazione necessaria], Algoritmo Roy-Floyd o solo Algoritmo di Floyd) è un algoritmo di analisi del grafico per trovare i cammini più corti in un grafico ponderato (con pesi di bordo positivi o negativi). Un singola esecuzione dell'algoritmo troveranno le lunghezze (riassunto pesi) dei cammini minimi tra tutte le coppie di vertici sebbene non restituisce dati dei percorsi stessi

Nella sottosezione "Path ricostruzione" it spiega la struttura dei dati che ti servirà per memorizzare i "percorsi" (in realtà devi solo memorizzare il nodo successivo in cui andare e quindi ricostruire banalmente qualunque percorso sia necessario, se necessario).