Trovare il percorso più breve attraverso un digrafo che visita tutti i nodi

3

Sto cercando di trovare il percorso più breve possibile che visita ogni nodo attraverso un grafico (un nodo può essere visitato più volte, la soluzione può selezionare qualsiasi nodo come nodo di partenza). Il grafico è diretto, il che significa che essere in grado di viaggiare dal nodo A al nodo B non significa che si possa viaggiare dal nodo B al nodo A. Tutte le distanze tra i nodi sono uguali. Sono stato in grado di codificare una ricerca di forza bruta che ha trovato un percorso di soli 27 nodi quando avevo 27 nodi e ogni nodo aveva una connessione a 2 o 1 altro nodo. Tuttavia, il vero problema che sto cercando di risolvere è costituito da 256 nodi, con ogni nodo che si connette a 4 o 3 altri nodi. L'algoritmo a forza bruta che ha risolto il grafico a 27 nodi può produrre una soluzione a 415 nodi (non ottimale) in pochi secondi, ma l'utilizzo della potenza di elaborazione che ho a disposizione impiega circa 6 ore per arrivare a una soluzione a 402 nodi.

Quale approccio dovrei utilizzare per arrivare a una soluzione che posso essere certa è quella ottimale? Ad esempio, utilizzare un algoritmo di ottimizzazione per abbreviare una soluzione non ottimale? O in qualche modo adottare una ricerca di forza bruta che scarta percorsi non ottimali?

EDIT: (Copia un commento per una risposta qui per chiarire meglio la domanda) Per chiarire, non sto dicendo che esiste un percorso hamiltoniano e ho bisogno di trovarlo, sto cercando di trovare il percorso più breve nel 256 grafico del nodo che visita ogni nodo almeno una volta. Con il 27 nodo eseguito, sono stato in grado di trovare un percorso hamiltoniano, il che mi ha assicurato che si trattava di una soluzione ottimale. Voglio trovare una soluzione per il grafico a 256 nodi che è il più breve.

    
posta Boluc Papuccuoglu 21.08.2014 - 14:24
fonte

4 risposte

5

Questo è NP-difficile. Se si dispone di una soluzione per questo problema, è possibile utilizzarlo su un grafico con tutti i pesi del bordo impostati su 1. Quindi il percorso risultante avrà lo stesso numero di nodi del grafico se e solo se esiste un percorso hamiltoniano. Dal momento che determinare l'esistenza di un percorso hamiltoniano è NP-difficile anche senza trovare soluzioni specifiche, qualsiasi soluzione a questo problema è altrettanto difficile.

Pagina di Wikipedia: link

Modifica: potresti voler dare un'occhiata a soluzioni approssimate, ma ho poca esperienza con quelle. La pagina wiki ti dice molto più di quanto posso: link

    
risposta data 21.08.2014 - 14:40
fonte
2

Se vuoi visitare tutti i nodi, allora hai una variazione del problema del venditore ambulante.

dato che sei autorizzato a visitare un nodo più volte puoi generare qualsiasi mancante con un costo del percorso più breve tra i 2 nodi.

Per esempio per arrivare a V3 da V1 devi passare V2, puoi aggiungere un bordo tra V1 e V3 con un costo di (V1, V2) + (V2, V3).

In questo modo puoi risolverlo come un problema di commesso viaggiatore e il percorso ottimale non comporterà viaggi inutili. Nell'esempio sopra se il bordo costruito viene preso, l'altra visita a V2 è parte del percorso ottimale altrimenti il percorso attraverso V2 sarebbe stato preso.

    
risposta data 21.08.2014 - 15:22
fonte
0

Dalla tua descrizione questo sembra essere un problema di percorso più breve per un grafo diretto strongmente connesso. Non sono del tutto sicuro che tu voglia realmente una soluzione a coppia singola o una soluzione all-pair.

Se quest'ultimo, sembra che l'algoritmo di Floyd-Warshall svolgerà il lavoro, con una complessità di O (n ^ 3). Altrimenti guarda qui: link .

    
risposta data 23.08.2014 - 10:37
fonte
-2

DFS può risolvere questo problema. Tuttavia, è necessario definire una funzione di valutazione efficiente per eliminare il ramo in precedenza. Alcuni suggerimenti sulla valutazione: - usa il goloso per trovare prima un buon percorso, questo potrebbe non essere un percorso più breve, ma permette di fermarsi su altri percorsi non buoni - per ogni stato, provare prima lo stato più vicino - per ogni stato, valutare la lunghezza minima per visitare tutti gli stati. La valutazione dovrebbe essere il più stretta possibile. Questo problema è più difficile ma puoi fare riferimento al mio post su questo problema qui link

    
risposta data 25.03.2015 - 14:08
fonte

Leggi altre domande sui tag