Il percorso più breve per visitare tutti i nodi

Question

Sto cercando un algoritmo che mi sembra molto tipico, ma sembra che le soluzioni comuni siano tutte leggermente diverse.

In un grafico non orientato, voglio il percorso più breve che visita ogni nodo. I nodi possono essere rivisitati e non devo tornare al nodo iniziale.

Il Problema di venditore ambulante sembra aggiungere la limitazione che ogni nodo può essere visitato solo una volta e che il percorso deve tornare a dove è stato avviato.

Gli alberi con spanning minimo possono essere parte di una soluzione, ma tali algoritmi forniscono solo l'albero, non un percorso minimo. Inoltre, poiché sono alberi e quindi non hanno loop, costringono il backtracking in cui un loop può essere più efficiente.

Answer 1

È possibile ridurlo al normale problema del venditore ambulante trasformando il grafico.

Prima di tutto, calcolare la distanza minima per ogni coppia di nodi. Puoi usare l'algoritmo di Floyd-Warshall per quello. Una volta ottenuto, basta costruire il grafo completo in cui il bordo tra i nodi u e v è il costo minimo da u a v.

Quindi, è possibile applicare un normale algoritmo TSP in quanto non è più necessario rivedere i nodi, che è già nascosto nei costi dei bordi.