Algorithme rapide pour trouver le tour du chevalier fermé

Question

J'apprends l'algorithme de la tournée des chevaliers. J'ai implémenté l'utilisation de l'algorithme récursif fin mais cela prend beaucoup de temps et presque pas de tour fermé.

Maintenant, je suis en train de trouver un algorithme rapide pour trouver un circuit fermé. Quelqu'un peut-il me recommander un algorithme ?

Mise à jour : J'ai lu quelque part une heuristique pour trouver un tour de chevalier fermé comme ceci : Min[F(x, y)] donde F(x,y) is a set of f(x,y)=Min(x-1, n-x) + Min(y-1, n-y) y (x, y) est la position de l'étape suivante et n est la taille de l'échiquier. Mais comment puis-je utiliser cette heuristique ?

Answer 1

Le problème du tour du chevalier consiste en fait à trouver un cycle hamiltonien dans le graphe correspondant, ce qui est connu pour être NP-hard, donc ce problème peut aussi être difficile à résoudre.

Cependant, il existe plusieurs heuristiques qui permettent d'effectuer une recherche rapide. L'une de ces heuristiques est la règle de Warnsdorff :

À chaque étape, se déplacer vers la case à partir de laquelle le moins de mouvements possibles sont disponibles. S'il y a plusieurs cases de ce type, déplacez-vous vers l'une d'entre elles.

C'est une très bonne heuristique, qui a longtemps été considérée comme la solution au problème du chemin du chevalier, et des exemples montrant que la deuxième partie de la règle peut conduire à une décision incorrecte ont été trouvés beaucoup plus tard avec l'utilisation de l'ordinateur.

Answer 2

J'ai résolu ce problème aujourd'hui en implémentant une recherche de type "Depth First Search" dans le Knight Graph (le graphe modélisant les mouvements possibles du chevalier).

Alors que j'ai passé tout mon après-midi à me demander pourquoi l'heuristique de Warnsdorff ne suffisait pas, le problème était mon point de départ.

Je démarrais le DFS à partir de la position (0,0). Il semble que la DFS soit nettement améliorée si l'on commence quelque part au milieu, comme (3,3). Après avoir changé cela, la vitesse de l'algorithme est passée de (aucune solution en 1 heure) à (1 solution en 1 seconde).

J'ai également testé votre heuristique Min[F(x,y)], et elle a apparemment fonctionné avec les mêmes performances que la règle de Warnsdorff (pour un tableau 8x8).