170
Recherche de la solution la plus courte pour les puzzles
FIGURE 9.1 - Position finale au Taquin 3x3.
a commencé.
Le problème du voyageur de commerce est donc de trouver le plus petit cycle hamiltonien débutant sur une ville donnée, dans le graphe des villes.
Exercice : On dispose d' une matrice NxN appelée distance qui donne les distances
entre les villes. La distance de la ville i à la ville j est donnée par distance [i] [j]. Le
voyageur de commerce se trouve au début dans la ville numéro O. É crire un programme
qui trouve le plus court trajet et le stocke dans un tableau meilleurTrajet de taille N + 1.
9.3 L'espace du problème
L'espace du problème est l 'ensemble des états que peut prendre le problème et l' ensemble des coups qui permettent de passer d' un état à un autre. Un problème est un espace
de problème associé à un état initial et à un état final. L'état initial est l 'état dans lequel
on commence la recherche, l 'état final est celui que l' on cherche à atteindre.
On peut représenter l ' espace d' un problème par un graphe. Les états du problème sont
les noeuds du graphe, et les coups sont les arêtes du graphe. Le but de la résolution de
problème est de trouver un chemin, si possible optimal, de l ' état initial à l' état final.
Certains des algorithmes de ce chapitre développent des arbres de recherche dont la racine est l 'état initial, et non des graphes. Cette simplification amène à recalculer plusieurs
fois les noeuds du graphe que l 'on peut atteindre par plusieurs chemins différents. Pour se
retrouver dans le cas de graphes, et éviter ces recalculs, on peut aj outer aux algorithmes
que nous verrons des tables de transposition.
9.4 Le Taquin
Un problème typique de recherche de plus court chemin dans un graphe d'états est le
Taquin. Dans sa version 3x3, le but est de trouver une séquence minimale de coups qui
permet d' atteindre la position de la figure 9 .1.
Recherche de la solution la plus courte pour les puzzles
FIGURE 9.1 - Position finale au Taquin 3x3.
a commencé.
Le problème du voyageur de commerce est donc de trouver le plus petit cycle hamiltonien débutant sur une ville donnée, dans le graphe des villes.
Exercice : On dispose d' une matrice NxN appelée distance qui donne les distances
entre les villes. La distance de la ville i à la ville j est donnée par distance [i] [j]. Le
voyageur de commerce se trouve au début dans la ville numéro O. É crire un programme
qui trouve le plus court trajet et le stocke dans un tableau meilleurTrajet de taille N + 1.
9.3 L'espace du problème
L'espace du problème est l 'ensemble des états que peut prendre le problème et l' ensemble des coups qui permettent de passer d' un état à un autre. Un problème est un espace
de problème associé à un état initial et à un état final. L'état initial est l 'état dans lequel
on commence la recherche, l 'état final est celui que l' on cherche à atteindre.
On peut représenter l ' espace d' un problème par un graphe. Les états du problème sont
les noeuds du graphe, et les coups sont les arêtes du graphe. Le but de la résolution de
problème est de trouver un chemin, si possible optimal, de l ' état initial à l' état final.
Certains des algorithmes de ce chapitre développent des arbres de recherche dont la racine est l 'état initial, et non des graphes. Cette simplification amène à recalculer plusieurs
fois les noeuds du graphe que l 'on peut atteindre par plusieurs chemins différents. Pour se
retrouver dans le cas de graphes, et éviter ces recalculs, on peut aj outer aux algorithmes
que nous verrons des tables de transposition.
9.4 Le Taquin
Un problème typique de recherche de plus court chemin dans un graphe d'états est le
Taquin. Dans sa version 3x3, le but est de trouver une séquence minimale de coups qui
permet d' atteindre la position de la figure 9 .1.