En utilisant Traveling Salesman Solver pour décider hamiltonien chemin

Question

Ceci est un projet où on me demande de mettre en œuvre une heuristique pour le problème d'optimisation du voyageur de commerce et aussi le chemin hamiltonien ou cycle de problème de décision. Je ne pas besoin d'aide à la mise en œuvre elle-même, mais une question sur la direction que je vais dans.

Je l'ai déjà une heuristique TSP basée sur un algorithme génétique: il suppose un graphe complet, commence par un ensemble de solutions aléatoires en tant que population, et travaille pour améliorer la population depuis plusieurs générations. Puis-je utiliser pour résoudre les problèmes ou chemin hamiltonien cycle? Au lieu d'optimiser pour obtenir le chemin le plus court, je veux juste vérifier s'il y a un chemin.

Maintenant tout graphe complet aura un chemin hamiltonien, donc l'heuristique TSP devrait être étendue à un graphique. Cela pourrait se faire en définissant les bords à une valeur de l'infini s'il n'y a pas de chemin entre les deux villes, et en retournant le premier chemin qui est un chemin hamiltonien valide.

Est-ce la bonne façon de l'aborder? Ou devrais-je utiliser une heuristique différente pour le chemin hamiltonien? Ma principale préoccupation est de savoir si c'est une approche viable puisque je peux être un peu sûr qui fonctionne l'optimisation TSP (parce que vous commencez avec des solutions et de les améliorer), mais pas si un decider de chemin hamiltonien trouverez tout chemin dans un nombre fixe de générations.

Je suppose que la meilleure approche serait de tester moi-même, mais je suis limité par le temps et je pensais que je demande avant d'aller dans cette voie ... (je pourrais trouver une heuristique différente pour le chemin hamiltonien à la place)

Answer 1

Je ne sais pas si vous avez pu vous une réponse à cela. L'astuce simple consiste à ajouter un point fictif qui a une distance de zéro à tous vos autres points. Résoudre le TSP et se débarrasser du point fictif - ce qui reste est le chemin hamiltonien. Simple!

Answer 2

Les deux sont NP problèmes complets, donc, par définition, vous pouvez convertir l'entrée et utiliser le même algorithme; -)

Mais l'idée de base devrait fonctionner. Bien sûr, vous devrez peut-être changer la génération de nouveaux chemins et les critères de réussite.

EDIT: BTW: Il y a une suggestion pour un algorithme aléatoire: http://en.wikipedia.org/wiki/Hamiltonian_path_problem