Variazione di TSP che visita più città

Question

Sto cercando di discutere ramo e la soluzione diretta verso TSP con più visite. (Cioè ogni città ha bisogno di essere visitata almeno una volta, invece di una sola volta)

Modifica:

Rimosso il dubbio come non era rilevante come sottolineato dal Jitse. Ora la domanda è più chiaro.

Answer 1

Semplicemente aumentare il grafico aggiungendo, per ogni coppia di nodi A e B, un bordo che rappresenta il percorso più breve da A a B. Il algoritmo di Floyd-Warshall ti permette di fare questo in O (n ^ 3), che è molto più veloce di qualsiasi algoritmo TSP. Una volta fatto questo, utilizzare un ramo di serie TSP e la tecnica legato. Questo sito ha alcune informazioni da di Applegate libro , che discute branch and bound per TSP secondo il Wikipedia TSP .

Answer 2

Preferirei presento questo come un commento sulla risposta di Martin Hock perché sto affrontando una possibile svista che sarebbe stato facile fare attuare il suo suggerimento.

Il ramo e bound deve essere combinato con un algoritmo per ricostruire percorsi costi minori trovati l'uscita dell'algoritmo di Floyd-Warshall. L'algoritmo branch and bound rappresenta l'anello esterno, e seleziona i nodi non visitati. Poi si utilizza l'algoritmo di ricostruzione percorso a costo minimo per aggiungere bordi e in realtà i nodi per il ciclo. I nodi devono essere contrassegnati come visitato da poco algoritmo di ricostruzione percorso a costo, non solo dal ramo e parte bound.