Détecteur de Chemin Hamiltonien

Pseudocode

Aucun algorithme polynomial n'est connu, la formulation honnête est donc un retour sur trace avec élagage. C'est l'élagage qui le rend utilisable.

CheminHamiltonien(graphe):
    pour chaque sommet de depart s:
        si backtrack([s], {s}): renvoyer le chemin
    renvoyer aucun

backtrack(chemin, visites):
    si visites contient tous les sommets: renvoyer vrai

    u = chemin.dernier
    pour chaque voisin v de u non visite:
        // Elagage qui se rentabilise:
        //  - un sommet non visite devenu inatteignable -> echec
        //  - deux sommets non visites ou plus de degre 1
        //    dans le graphe restant -> echec
        visites.ajouter(v)
        si backtrack(chemin + [v], visites): renvoyer vrai
        visites.retirer(v)     // defaire et essayer le suivant

    renvoyer faux

L'élagage par atteignabilité est le plus déterminant. Après avoir choisi un chemin partiel, lance un parcours rapide sur les sommets non visités; si l'un d'eux se trouve désormais coupé de l'extrémité courante, la branche est morte et peut être abandonnée immédiatement plutôt qu'après l'exploration d'un sous-arbre entier. Sur les graphes creux, cela transforme une recherche intraitable en une recherche rapide, même si le pire cas demeure exponentiel.

Exemple détaillé, étape par étape

Cherche un chemin hamiltonien depuis A sur un graphe à cinq sommets, et vois pourquoi ce même graphe n'admet aucun cycle hamiltonien.

Graphe d'exemple: Arêtes non orientées A-B, B-C, C-D, D-E, plus les deux cordes A-C et B-D.

1. Les degrés d abord. A est de degré 2 (B et C), B de 3 (A, C, D), C de 3 (A, B, D), D de 3 (B, C, E), et E de degré 1, son unique voisin étant D. Un sommet de degré 1 doit être une extrémité de tout chemin hamiltonien, ce qui nous dit déjà que E est l'un des bouts.
2. Essayer A vers B en premier. Depuis A prends B, puis depuis B prends C, puis depuis C l'unique voisin non visité est D, et depuis D l'unique non visité est E. Cela complète A-B-C-D-E couvrant les cinq sommets.
3. Une seconde solution existe. En revenant sur trace depuis A par l'autre branche on obtient A-C-B-D-E, tout aussi valide. Les chemins hamiltoniens ne sont fréquemment pas uniques, et un algorithme renvoyant le premier trouvé répond à une question d'existence, pas de dénombrement.
4. Demander maintenant un cycle. Un cycle hamiltonien devrait revenir du dernier sommet vers A. Les deux chemins se terminent en E, et E est de degré 1 avec son unique arête vers D. Aucune arête E-A n'existe, il n'y a donc aucun cycle hamiltonien.

Deux chemins hamiltoniens existent, A-B-C-D-E et A-C-B-D-E, mais aucun cycle hamiltonien. Le sommet E de degré 1 tranche presque à lui seul les deux questions: il se contraint lui-même à être une extrémité et exclut tout cycle, puisqu'un cycle exige que chaque sommet soit de degré au moins 2. Vérifier les degrés avant de chercher coûte peu et se révèle souvent décisif.

Complexité et son origine

Temps: O(V!) naïf, O(V^2·2^V) avec PD · Espace: O(V·2^V) avec PD

Le retour sur trace naïf explore des permutations et vaut O(V factorielle) au pire, ce qui est sans espoir au-delà d'une douzaine de sommets. La programmation dynamique de Held-Karp sur les sous-ensembles fait bien mieux: l'état est un sous-ensemble de sommets visités associé à l'extrémité courante, soit 2 puissance V fois V états, et chaque transition coûte O(V), pour un total en O(V au carré fois 2 puissance V) en temps et O(V fois 2 puissance V) en mémoire. C'est praticable jusqu'à une vingtaine de sommets, où 2 puissance 20 fois 20 représente environ 20 millions d'états. Le problème est NP-complet, aucun algorithme polynomial n'est donc attendu; le retour sur trace élagué termine néanmoins souvent vite sur les graphes creux réels.

Quand utiliser Chemin Hamiltonien, et quand l'éviter

Confirme quel problème tu as réellement avant de sortir la machinerie exponentielle, car deux d'entre eux sont faciles.

Pièges fréquents

• Le confondre avec le problème eulérien. Les noms se ressemblent et les difficultés diffèrent énormément. L'eulérien couvre les arêtes et est linéaire; l'hamiltonien couvre les sommets et est NP-complet. Résoudre le mauvais est l'erreur la plus coûteuse possible ici.
• Chercher sans élagage. Le retour sur trace pur sans test d'atteignabilité explore d'immenses sous-arbres morts. Vérifier que tous les sommets non visités restent atteignables depuis l'extrémité courante, et qu'au plus deux d'entre eux sont de degré 1 dans le graphe restant, réduit typiquement la recherche de plusieurs ordres de grandeur.
• Supposer qu un chemin implique un cycle. Un chemin hamiltonien peut exister sans qu'aucun cycle hamiltonien n'existe, exactement comme dans l'exemple ci-dessus. Le cycle exige en outre une arête du dernier sommet vers le premier, et tout sommet de degré 1 l'exclut entièrement.
• Appliquer la condition de Dirac à l envers. Dirac affirme que si chaque sommet est de degré au moins V/2 alors un cycle hamiltonien existe. La réciproque est fausse: quantité de graphes à faibles degrés possèdent des cycles hamiltoniens, échouer à la condition ne prouve donc rien.
• S attendre à ce que cela passe à l échelle. Au-delà de 20 à 25 sommets environ, une réponse exacte peut être tout simplement hors de portée. Si le but réel est une bonne route et non une preuve, modélise-le en TSP et emploie des heuristiques.

Questions fréquentes

Qu'est-ce qu'un chemin hamiltonien?

Un chemin hamiltonien est un chemin qui visite chaque sommet d'un graphe exactement une fois. S'il revient en outre à son sommet de départ, c'est un cycle hamiltonien. Contrairement à un chemin eulérien, il n'a pas besoin d'emprunter toutes les arêtes, et il ne peut revisiter aucun sommet.

Pourquoi trouver un chemin hamiltonien est-il difficile?

Parce que la propriété ne peut être vérifiée localement. Les chemins eulériens sont faciles car un simple comptage des degrés à chaque sommet tranche l'existence, mais il n'existe aucun test local comparable pour visiter chaque sommet une fois. Le problème est NP-complet, aucun algorithme polynomial n'est connu et en trouver un résoudrait P contre NP.

Quelle est la différence entre chemins hamiltoniens et eulériens?

Un chemin hamiltonien visite chaque sommet exactement une fois et peut ignorer des arêtes. Un chemin eulérien emprunte chaque arête exactement une fois et peut revisiter des sommets. L'existence eulérienne se décide en O(V + E) en comptant les sommets de degré impair; l'hamiltonienne est NP-complète.

Comment trouve-t-on un chemin hamiltonien?

Pour de petits graphes, par retour sur trace depuis chaque départ possible avec un élagage énergique: abandonne une branche dès qu'un sommet non visité devient inatteignable, ou dès que deux sommets non visités ou plus sont de degré 1 dans le graphe restant. Jusqu'à une vingtaine de sommets, la programmation dynamique de Held-Karp sur les sous-ensembles donne une réponse définitive en O(V au carré fois 2 puissance V).

Quel est le lien entre chemins hamiltoniens et TSP?

Le problème du voyageur de commerce est la version pondérée d'optimisation: au lieu de demander si un circuit visitant tous les sommets existe, il réclame le moins cher dans un graphe complet pondéré. Décider l'existence d'un cycle hamiltonien se réduit au TSP, ce qui explique que le TSP soit également NP-difficile.