Question

Je cherche à discuter de branche et d'une solution liée à TSP avec plusieurs visites. (Qui est chaque ville doit être visité au moins une fois, au lieu d'une seule fois)

Edit:

Suppression du doute était pas pertinent comme l'a fait par Jitse. Maintenant, la question est plus claire.

Était-ce utile?

La solution

augmenter simplement le graphique en ajoutant, pour chaque paire de noeuds A et B, représentant un bord le plus court chemin de A à B. Le algorithme de Floyd-Warshall vous permet de le faire en O (n ^ 3), ce qui est beaucoup plus rapide que tout algorithme de TSP. Une fois que vous avez fait cela, utilisez une branche norme TSP et technique liée. Ce site a quelques informations livre de Applegate , qui porte sur la branche et à destination de la TSP selon le Wikipedia TSP entrée.

Autres conseils

Je préfère soumettre cela comme un commentaire sur la réponse de Martin Hock parce que je me adresse un oubli possible qui serait facile à faire mettre en œuvre sa suggestion.

La branche et Bound doit être associé à un algorithme de reconstruction moins chemins de coût étant donné la sortie de l'algorithme de Floyd-Warshall. L'algorithme de dérivation et est lié à la boucle externe, et il sélectionne les noeuds non visités. Ensuite, vous utilisez le moins algorithme de reconstruction du chemin de coût pour ajouter réellement les bords et les noeuds à votre cycle. Les nœuds doivent être marqués comme visité par le moins algorithme de reconstruction du chemin des coûts, non seulement par la branche et une partie liée.

Licencié sous: CC-BY-SA avec attribution
Non affilié à StackOverflow
scroll top