Donné un graphe G = (V, E), nous devons trouver le circuit hamiltonien en utilisant l’approche Backtracking. Nous commençons notre recherche à partir d’un sommet arbitraire quelconque, disons ‘a’. Ce sommet ‘a’ devient la racine de notre arbre implicite. Le premier élément de notre solution partielle est le premier sommet intermédiaire du cycle hamiltonien qui doit être construit. Le sommet adjacent suivant est sélectionné par ordre alphabétique. Si, à n’importe quel stade, un sommet arbitraire fait un cycle avec un sommet autre que le sommet ‘a’, nous disons que nous sommes dans une impasse. Dans ce cas, nous revenons en arrière d’une étape, et de nouveau la recherche commence en sélectionnant un autre sommet et en revenant en arrière, l’élément de la solution partielle doit être retiré. La recherche par backtracking est réussie si on obtient un cycle hamiltonien.
Exemple : Considérons un graphe G = (V, E) représenté en fig. Nous devons trouver un circuit hamiltonien en utilisant la méthode Backtracking.
Solution : Tout d’abord, nous commençons notre recherche par le sommet ‘a’.’ ce sommet ‘a’ devient la racine de notre arbre implicite.
Puis, nous choisissons le sommet ‘b’ adjacent à ‘a’ car il vient en premier dans l’ordre lexicographique (b, c, d).
Puis, on choisit le sommet ‘c’ adjacent à ‘b.’
Puis, on choisit le sommet ‘d’ adjacent à ‘c’.’
Après, nous sélectionnons ‘e’ adjacent à ‘d.’
Après, nous sélectionnons le sommet ‘f’ adjacent à ‘e’. Le sommet adjacent à ‘f’ est d et e, mais ils ont déjà visité. Ainsi, nous obtenons l’impasse, et nous revenons en arrière d’une étape et supprimons le sommet ‘f’ de la solution partielle.
D’après le backtracking, le sommet adjacent à ‘e’ est b, c, d et f à partir duquel le sommet ‘f’ a déjà été vérifié, et b, c, d ont déjà été visités. Donc, de nouveau, nous revenons en arrière d’une étape. Maintenant, les sommets adjacents à d sont e, f dont e a déjà été vérifié, et les adjacents de ‘f’ sont d et e. Si le sommet ‘e’ est revisité, on obtient un état mort. Donc, encore une fois, nous revenons en arrière d’une étape.
Maintenant, adjacent à c est ‘e’ et adjacent à ‘e’ est ‘f’ et adjacent à ‘f’ est ‘d’ et adjacent à ‘d’ est ‘a.’ Ici, nous obtenons le cycle hamiltonien car tous les sommets autres que le sommet de départ ‘a’ ne sont visités qu’une seule fois. (a – b – c – e – f -d – a).
Encore un retour en arrière
Ici nous avons généré un circuit hamiltonien, mais on peut aussi obtenir un autre circuit hamiltonien en considérant un autre sommet.