Variação de TSP que visita várias cidades

Question

Eu estou olhando para discutir ramo e solução destino a TSP com várias visitas. (Que é toda cidade precisa de ser visitado pelo menos uma vez, em vez de apenas uma vez)

Editar:

Removido da dúvida, uma vez que não era relevante, apontado por Jitse. Agora, a questão é mais clara.

Answer 1

Simplesmente aumentar o gráfico adicionando, para cada par de nós A e B, que representa uma vantagem o caminho mais curto a partir de A para B. O Floyd-Warshall algoritmo permite que você faça isso em O (n ^ 3), que é muito mais rápido do que qualquer algoritmo de TSP. Uma vez feito isso, use um ramo TSP padrão e técnica de salto. Este site tem alguma informação a partir de livro de Applegate, que discute ramo e com destino a TSP de acordo com o Wikipedia TSP entrada .

Answer 2

Eu prefiro apresentar isso como um comentário sobre a resposta de Martin Hock porque eu estou dirigindo um possível descuido que seria fácil de fazer implementar sua sugestão.

O ramo e ligado algoritmo precisa de ser combinado com um algoritmo para a reconstrução de caminhos de menor custo dadas a saída do algoritmo de Floyd-Warshall. O algoritmo de derivação e limitação é o circuito externo, e que selecciona os nós não visitados. Então você usa o algoritmo de reconstrução caminho de menor custo para realmente adicionar bordas e nós para o seu ciclo. Nós deve ser marcado como visitado pelo algoritmo de reconstrução caminho de menor custo, e não apenas pelo ramo e parte vinculado.