Percorso più corto a una via attraverso più nodi

Question

Ho una serie di coordinate grafiche e ho bisogno di trovare il percorso unidirezionale più breve attraverso tutte. Non ho un inizio/fine predeterminato, ma ogni punto deve essere toccato una sola volta e NON è necessario ritornare all'origine ottimale.

Ho provato un paio di approcci TSP, ma sembrano tutti basati sul ritorno all'origine alla fine che dà risultati terribilmente inefficienti in questo caso.

Esempio

1, 13
3, 0
3, 7
2, 21
2, 11
3, 12
1, 19
3, 6

risolverebbe a

3, 0
3, 6
3, 7
3, 12
2, 11
1, 13
1, 19
2, 21

Note:

Sì ho provato la ricerca funzione, c'è una domanda sostanzialmente identica Algorithm: shortest path between all points tuttavia l'unica vera risposta è un TSP, che ancora una volta, circuito chiuso è inefficiente per questo.

Non ha bisogno di essere accurato al 100%, ho già un metodo di permutazioni, ma il suo troppo lento, ho bisogno di gestire almeno ~ 25-30 punti, stabilendosi con una buona approssimazione funziona per me

Grazie in anticipo.

Modifica per chiarire, TSP tende a risolvere come in img # 1, il mio risultato desiderato è img # 2
img 3 è il campione sopra risolto tramite un TSP e img # 4 è desiderato (x coordinate spostato indietro - .5 per visibilità)

Coppia più buona misura # 1 = TSP, # 2 = desiderata,

Fondamentalmente voglio più breve collegamento in catena di punti, utilizzando il punto di inizio e di fine più efficiente

Answer 1

Questa è un'istanza di all-pairs shortest path problem con tutti i bordi con peso = 1. Troverai soluzioni comuni come l'algoritmo Dijkstra o A-star nella pagina collegata.
Un approccio ingenuo è quello di iterare sui nodi e trovare il percorso più breve per ogni altro nodo.

$paths = array(); 
foreach ($nodes as $start) { 
    foreach ($nodes as $end) { 
     if ($start !== $end) { 
      $path[$start][$end] = findShortestPath($graph, $start, $end); 
     } 
    } 
} 

In un approccio più sofisticato findShortestPath avrebbero ricordato sottotracciati di piste precedenti (o utilizzare $paths a tal fine) per ottenere prestazioni migliori.

Answer 2

Dato che non ti interessa trovare un circuito chiuso, tutto ciò che ti serve è un singolo percorso: puoi apportare una piccola modifica ai punti che devi evitare il costo di un circuito chiuso. Per fare ciò, aggiungi un nuovo punto, chiamalo v, che definisci essere alla distanza 0 da tutti gli altri punti. Ora, trova una soluzione TSP per questo grafico. Ad un certo punto, entrerai e poi uscirai v. Se esegui il ciclo e poi rimuovi i bordi dentro e fuori da v da esso, avrai un percorso che visita ogni nodo esattamente una volta senza cicli.

Questo richiede ancora di risolvere o approssimare TSP, ma elimina l'enorme sovraccarico di ritorno al punto di partenza.

Answer 3

ci sono molti algoritmi che cercano il percorso chiuso più corto in un grafico. Penso che non sia troppo difficile adattare uno degli algoritmi che risolvono quel problema (a.k.a come travelling salesman problem) ai tuoi bisogni (il percorso dovrebbe essere un modo hamiltoniano non un ciclo hamiltoniano). Alcune delle soluzioni ben note per il problema del venditore sono l'algoritmo di Dijkstra e l'algoritmo di Prim.