Trova il percorso più breve in un grafico che visita determinati nodi

StackOverflow https://stackoverflow.com/questions/222413

  •  03-07-2019
  •  | 
  •  

Domanda

Ho un grafico non orientato con circa 100 nodi e circa 200 bordi. Un nodo è etichettato "start", uno è "end" e circa una dozzina è etichettato "mustpass".

Devo trovare il percorso più breve attraverso questo grafico che inizia da "inizio", termina da "fine", e passa attraverso tutti i nodi "mustpass" (in qualsiasi ordine).

( http://3e.org/local/maize-graph.png / http://3e.org/local/maize-graph.dot.txt è il grafico in questione - rappresenta un labirinto di mais a Lancaster, in Pennsylvania)

È stato utile?

Soluzione

Tutti gli altri, confrontando questo con il Problema del commesso viaggiatore, probabilmente non hanno letto attentamente la tua domanda. In TSP, l'obiettivo è quello di trovare il ciclo più breve che visiti tutti i vertici (un ciclo hamiltoniano) - corrisponde ad avere ogni nodo etichettato 'mustpass'.

Nel tuo caso, dato che hai solo una dozzina etichettata 'mustpass', e dato che 12! è piuttosto piccolo (479001600), puoi semplicemente provare tutte le permutazioni solo dei nodi 'mustpass' e guardare il percorso più breve da 'start' a 'end' che visita i nodi 'mustpass' in quell'ordine - semplicemente essere la concatenazione dei percorsi più brevi tra ogni due nodi consecutivi in ??tale elenco.

In altre parole, trova prima la distanza più breve tra ogni coppia di vertici (puoi usare l'algoritmo di Dijkstra o altri, ma con quei piccoli numeri (100 nodi), anche il più semplice da codice l'algoritmo Floyd-Warshall verrà eseguito in tempo). Quindi, una volta che hai questo in una tabella, prova tutte le permutazioni dei tuoi nodi 'mustpass' e il resto.

Qualcosa del genere: 

//Precomputation: Find all pairs shortest paths, e.g. using Floyd-Warshall
n = number of nodes
for i=1 to n: for j=1 to n: d[i][j]=INF
for k=1 to n:
    for i=1 to n:
        for j=1 to n:
            d[i][j] = min(d[i][j], d[i][k] + d[k][j])
//That *really* gives the shortest distance between every pair of nodes! :-)

//Now try all permutations
shortest = INF
for each permutation a[1],a[2],...a[k] of the 'mustpass' nodes:
    shortest = min(shortest, d['start'][a[1]]+d[a[1]][a[2]]+...+d[a[k]]['end'])
print shortest

(Ovviamente questo non è un codice reale, e se vuoi il percorso effettivo dovrai tenere traccia di quale permutazione fornisce la distanza più breve, e anche quali sono i percorsi più corti di tutte le coppie, ma ottieni l'idea. )

Funzionerà al massimo qualche secondo su qualsiasi linguaggio ragionevole :)
[Se hai n nodi e k 'mustpass' nodi, il suo tempo di esecuzione è O (n 3 ) per la parte Floyd-Warshall e O (k! N) per la parte di tutte le permutazioni, e 100 ^ 3 + (12!) (100) sono praticamente noccioline a meno che tu non abbia alcuni vincoli veramente restrittivi.]

Altri suggerimenti

esegui Algoritmo di Djikstra per trovare i percorsi più brevi tra tutti i nodi critici (inizio, fine e must-pass), quindi un attraversamento in profondità dovrebbe dirti il ??percorso più breve attraverso il sottografo risultante che tocca tutti i nodi start ... mustpasses ... end

In realtà, il problema che hai pubblicato è simile al venditore ambulante, ma penso più vicino a un semplice problema di ricerca di percorsi. Anziché dover visitare ogni singolo nodo, è sufficiente visitare un determinato insieme di nodi nel minor tempo (distanza) possibile.

La ragione di ciò è che, a differenza del problema del commesso viaggiatore, un labirinto di mais non ti permetterà di viaggiare direttamente da un punto all'altro a qualsiasi altro punto della mappa senza dover passare attraverso altri nodi per arrivarci.

In realtà consiglierei A * pathfinding come tecnica da considerare. Puoi impostarlo decidendo quali nodi hanno accesso a quali altri nodi direttamente e quale "costo" di ogni hop da un nodo particolare è. In questo caso, sembra che ogni "hop" potrebbe avere lo stesso costo, poiché i nodi sembrano spaziati in modo relativamente ravvicinato. A * può utilizzare queste informazioni per trovare il percorso di costo più basso tra due punti qualsiasi. Dal momento che devi andare dal punto A al punto B e visitare circa 12 tra di loro, anche un approccio di forza bruta usando il pathfinding non farebbe del male.

Solo un'alternativa da considerare. Sembra notevolmente come il problema del commesso viaggiatore, e questi sono buoni documenti su cui leggere, ma guardati più da vicino e vedrai che sono solo cose complicate. ^ _ ^ Questo viene dalla mente di un programmatore di videogiochi che ha già affrontato questo genere di cose.

Questi sono due problemi ... Steven Lowe lo ha sottolineato, ma non ha rispettato abbastanza la seconda metà del problema.

Dovresti prima scoprire i percorsi più brevi tra tutti i tuoi nodi critici (inizio, fine, mustpass). Una volta individuati questi percorsi, è possibile costruire un grafico semplificato, in cui ciascun bordo del nuovo grafico è un percorso da un nodo critico a un altro nel grafico originale. Esistono molti algoritmi di pathfinding che puoi utilizzare per trovare il percorso più breve qui.

Una volta che hai questo nuovo grafico, però, hai esattamente il problema del commesso viaggiatore (beh, quasi ... Non è necessario tornare al punto di partenza). Si applicherà uno qualsiasi dei post in merito, menzionato sopra.

Andrew Top ha l'idea giusta:

1) Algoritmo di Djikstra 2) Alcuni euristici TSP.

Raccomando l'euristico Lin-Kernighan: è uno dei più noti per qualsiasi problema NP Complete. L'unica altra cosa da ricordare è che dopo aver espanso nuovamente il grafico dopo il passaggio 2, potresti avere dei loop nel tuo percorso espanso, quindi dovresti aggirarli cortocircuitandoli (guarda il grado di vertici lungo il tuo percorso).

In realtà non sono sicuro di quanto sarà buona questa soluzione rispetto all'ottimale. Probabilmente ci sono alcuni casi patologici che riguardano il corto circuito. Dopotutto, questo problema sembra MOLTO simile a Steiner Tree: http://en.wikipedia.org/wiki/Steiner_tree e sicuramente non puoi approssimare Steiner Tree semplicemente contraendo il tuo grafico ed eseguendo Kruskal per esempio.

Questo è non un problema TSP e non NP-difficile perché la domanda originale non richiede che i nodi must-pass vengano visitati una sola volta. Questo rende la risposta molto, molto più semplice alla forza bruta dopo aver compilato un elenco di percorsi più brevi tra tutti i nodi must-pass tramite l'algoritmo di Dijkstra. Potrebbe esserci un modo migliore per andare, ma uno semplice sarebbe semplicemente lavorare un albero binario all'indietro. Immagina un elenco di nodi [inizio, a, b, c, fine]. Somma le semplici distanze [start- > a- > b- > c- > end] questa è la tua nuova distanza target da battere. Ora prova [start- > a- > c- > b- > end] e se è meglio impostalo come obiettivo (e ricorda che proviene da quel modello di nodi). Lavorare all'indietro sulle permutazioni:

  • [start > a- > b- > c- > fine]
  • [start > a- > c- > b- > fine]
  • [start > b- > a- > c- > fine]
  • [start > b- > c- > a- > fine]
  • [start > c- > a- > b- > fine]
  • [start > c- > b- > a- > fine]

Uno di questi sarà il più corto.

(dove sono i nodi "visitati più volte", se ce ne sono? Sono appena nascosti nel passaggio di inizializzazione del percorso più breve. Il percorso più breve tra aeb può contenere ce il punto finale. bisogno di cura)

Considerando che la quantità di nodi e spigoli è relativamente finita, puoi probabilmente calcolare ogni possibile percorso e prendere il più breve.

Generalmente noto come problema del venditore ambulante e ha un runtime polinomiale non deterministico, indipendentemente dall'algoritmo utilizzato.

http://en.wikipedia.org/wiki/Traveling_salesman_problem

Che ne dici di usare la forza bruta sulla dozzina di nodi 'must visit'. Puoi coprire tutte le possibili combinazioni di 12 nodi abbastanza facilmente, e questo ti lascia con un circuito ottimale che puoi seguire per coprirle.

Ora il tuo problema è semplificato a quello di trovare percorsi ottimali dal nodo iniziale al circuito, che poi segui fino a quando non li hai coperti, e quindi trova il percorso da quello alla fine.

Il percorso finale è composto da:

inizio - > percorso verso il circuito * - > circuito di deve visitare i nodi - > percorso fino alla fine * - > end

Trovi i percorsi contrassegnati con * in questo modo

Esegui una ricerca A * dal nodo iniziale in ogni punto del circuito per ognuno di questi fai una ricerca A * dal nodo successivo e precedente sul circuito fino alla fine (perché puoi seguire il giro del circuito in entrambe le direzioni) Ciò che si finisce con sono molti percorsi di ricerca e puoi scegliere quello con il costo più basso.

C'è molto spazio per l'ottimizzazione memorizzando nella cache le ricerche, ma penso che ciò genererà buone soluzioni.

Non si avvicina affatto alla ricerca di una soluzione ottimale, perché ciò potrebbe comportare l'abbandono del circuito da visitare all'interno della ricerca.

Una cosa che non è menzionata da nessuna parte è se è giusto che lo stesso vertice venga visitato più di una volta nel percorso. La maggior parte delle risposte qui presuppone che sia ok visitare lo stesso bordo più volte, ma la mia opinione data la domanda (un percorso non dovrebbe visitare lo stesso vertice più di una volta!) È che è non ok per visitare lo stesso vertice due volte.

Quindi sarebbe ancora applicabile un approccio di forza bruta, ma dovresti rimuovere i vertici già utilizzati quando tenti di calcolare ogni sottoinsieme del percorso.

Autorizzato sotto: CC-BY-SA insieme a attribuzione
Non affiliato a StackOverflow
scroll top