Utilisation du solveur itinérant pour déterminer le chemin d'accès hamiltonien

Question

Ceci est pour un projet où l'on me demande d'implémenter une heuristique pour le problème d'optimisation du vendeur itinérant et également le problème de chemin ou de décision de cycle hamiltonien. Je n'ai pas besoin d'aide pour l'implémentation elle-même, mais j'ai une question sur la direction dans laquelle je vais.

J'ai déjà une heuristique TSP basée sur un algorithme génétique: elle suppose un graphe complet, commence par un ensemble de solutions aléatoires en tant que population, et travaille à améliorer la population pour un certain nombre de générations. Puis-je également l'utiliser pour résoudre le problème du chemin ou du cycle hamiltonien? 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 devra être étendue à n'importe quel graphe. Cela peut être fait en définissant les arêtes à une valeur infinie s'il n'y a pas de chemin entre 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 car je peux être certain que l'optimisation TSP fonctionne (parce que vous commencez avec des solutions et les améliorez) mais pas si un décideur hamiltonien trouverait un chemin dans un nombre fixe de générations. Je suppose que la meilleure approche serait de le tester moi-même, mais je suis contraint par le temps et la pensée que je demanderais avant de descendre cette route ... (Je pourrais trouver une autre heuristique pour le chemin hamiltonien à la place)

Answer 1

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

Answer 2

Les deux sont des problèmes complets NP, 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 succès.

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