Problème du chemin hamiltonien

Il y a n ! séquences différentes de sommets qui pourraient être des chemins hamiltoniens dans un graphe donné à n sommets (et le sont, dans un graphe complet), donc un algorithme de recherche par force brute qui teste toutes les séquences possibles serait très lent.Un premier algorithme exact pour trouver un cycle hamiltonien sur un graphe dirigé était l’algorithme énumératif de Martello. Une procédure de recherche de Frank Rubin divise les arêtes du graphe en trois classes : celles qui doivent être dans le chemin, celles qui ne peuvent pas être dans le chemin et celles qui sont indécises. Au fur et à mesure de la recherche, un ensemble de règles de décision classe les arêtes indécises et détermine s’il faut arrêter ou poursuivre la recherche. L’algorithme divise le graphe en composantes qui peuvent être résolues séparément. De plus, un algorithme de programmation dynamique de Bellman, Held et Karp peut être utilisé pour résoudre le problème en temps O(n2 2n). Dans cette méthode, on détermine, pour chaque ensemble S de sommets et chaque sommet v dans S, s’il existe un chemin qui couvre exactement les sommets de S et se termine à v. Pour chaque choix de S et v, un chemin existe pour (S,v) si et seulement si v a un voisin w tel qu’un chemin existe pour (S – v,w), qui peut être recherché à partir des informations déjà calculées dans le programme dynamique.

Andreas Björklund a fourni une approche alternative utilisant le principe d’inclusion-exclusion pour réduire le problème du comptage du nombre de cycles hamiltoniens à un problème de comptage plus simple, de comptage des couvertures de cycles, qui peut être résolu en calculant certains déterminants matriciels. En utilisant cette méthode, il a montré comment résoudre le problème des cycles hamiltoniens dans des graphes arbitraires à n sommets par un algorithme de Monte Carlo en temps O(1,657n) ; pour les graphes bipartis, cet algorithme peut être encore amélioré en temps o(1,415n).

Pour les graphes de degré maximum trois, une recherche prudente par backtracking peut trouver un cycle hamiltonien (s’il existe) en temps O(1.251n).

Les chemins et cycles hamiltoniens peuvent être trouvés à l’aide d’un solveur SAT.

En raison de la difficulté de résoudre les problèmes de chemins et de cycles hamiltoniens sur des ordinateurs conventionnels, ils ont également été étudiés dans des modèles non conventionnels de calcul. Par exemple, Leonard Adleman a montré que le problème du chemin hamiltonien pouvait être résolu à l’aide d’un ordinateur ADN. En exploitant le parallélisme inhérent aux réactions chimiques, le problème peut être résolu à l’aide d’un nombre d’étapes de réaction chimique linéaire par rapport au nombre de sommets du graphe ; cependant, il nécessite un nombre factoriel de molécules d’ADN pour participer à la réaction.

Une solution optique au problème hamiltonien a également été proposée. L’idée est de créer une structure en forme de graphe faite de câbles optiques et de séparateurs de faisceau qui sont traversés par la lumière afin de construire une solution au problème. Le point faible de cette approche est la quantité d’énergie requise, qui est exponentielle en fonction du nombre de nœuds.

La solution optique du problème Hamiltonien a également été proposée.