Chapitre 9
Recherche de la solution la plus
courte pour les puzzles
9.1 Introduction
Des problèmes très connus de recherche de solution la plus courte que nous abordons
sont par exemple le Rubik's Cube, le Taquin ou le voyageur de commerce.
Pour résoudre ces problèmes on peut utiliser des algorithmes de force brute qui n' utilisent pas de connaissances du domaine. Pour les problèmes comme le Rubik's cube, le
Taquin et Sokoban il est très utile d' utiliser des heuristiques spécifiques au domaine pour
accélérer la recherche.
Nous commencerons par décrire les algorithmes de recherche qui n ' utilisent pas de
connaissances du domaine. Puis nous continuerons par les algorithmes de recherche heuristique comme A* et IDA* qui utilisent des connaissances du domaine.
9.2 Le voyageur de commerce
Un voyageur de commerce doit visiter un ensemble de villes. Il cherche à trouver le
trajet le plus court qui passe par toutes les villes. Si il y a N villes à visiter, il a le choix
entre N - 1 villes pour sa première visite, N - 2 pour sa deuxième et ainsi de suite.
Une recherche exhaustive de tous les trajets possibles considérera donc (N - 1 )! trajets
possibles.
Un cycle hamiltonien d' un graphe connecté est un chemin qui visite tous les noeuds
du graphe, sans passer deux fois par le même et qui se termine sur le noeud par lequel il
Recherche de la solution la plus
courte pour les puzzles
9.1 Introduction
Des problèmes très connus de recherche de solution la plus courte que nous abordons
sont par exemple le Rubik's Cube, le Taquin ou le voyageur de commerce.
Pour résoudre ces problèmes on peut utiliser des algorithmes de force brute qui n' utilisent pas de connaissances du domaine. Pour les problèmes comme le Rubik's cube, le
Taquin et Sokoban il est très utile d' utiliser des heuristiques spécifiques au domaine pour
accélérer la recherche.
Nous commencerons par décrire les algorithmes de recherche qui n ' utilisent pas de
connaissances du domaine. Puis nous continuerons par les algorithmes de recherche heuristique comme A* et IDA* qui utilisent des connaissances du domaine.
9.2 Le voyageur de commerce
Un voyageur de commerce doit visiter un ensemble de villes. Il cherche à trouver le
trajet le plus court qui passe par toutes les villes. Si il y a N villes à visiter, il a le choix
entre N - 1 villes pour sa première visite, N - 2 pour sa deuxième et ainsi de suite.
Une recherche exhaustive de tous les trajets possibles considérera donc (N - 1 )! trajets
possibles.
Un cycle hamiltonien d' un graphe connecté est un chemin qui visite tous les noeuds
du graphe, sans passer deux fois par le même et qui se termine sur le noeud par lequel il