Variación del TSP que visita varias ciudades

Question

Busco para discutir la rama y la solución con destino a TSP con múltiples visitas. (Es decir cada ciudad necesita ser visitado al menos una vez, en lugar de sólo una vez)

Editar:

Se ha quitado la duda ya que no era relevante como se ha señalado por Jitse. Ahora la cuestión es más clara.

Answer 1

Simplemente aumentar la gráfica añadiendo, para cada par de nodos A y B, un borde que representa el camino más corto de A a B. La algoritmo de Floyd-Warshall le permite hacer esto en O (n ^ 3), que es mucho más rápido que cualquier algoritmo TSP. Una vez hecho esto, utilice una rama estándar TSP y la técnica de salto. Este sitio tiene alguna información de libro de Applegate, que discute la rama y con destino a TSP según la Wikipedia TSP entrada .

Answer 2

Yo prefiero presentarla como un comentario sobre la respuesta de Martin Hock porque estoy frente a un posible descuido que sería fácil de hacer que la implementación de su sugerencia.

La rama y el algoritmo de límite tiene que ser combinada con un algoritmo de reconstrucción de menos caminos costo dado la salida del algoritmo de Floyd-Warshall. El algoritmo de rama y unido es el bucle externo, y selecciona los nodos no visitados. A continuación, se utiliza el algoritmo de reconstrucción ruta de coste mínimo para agregar realmente bordes y nodos de su ciclo. Los nodos deben marcarse como visitado por el algoritmo de reconstrucción ruta de coste mínimo, no sólo por la rama y la parte consolidados.