9.7 L'algorithme IDA*
173
On veut aussi disposer d' une fonction qui développe un noeud. Elle crée tous ses fils,
les insère dans l 'ensemble des ouverts, et met le noeud développé dans l 'ensemble des
fermés.
Exercice : É crire pour le Taquin 4x4 la fonction Noeud * meilleur ( ) qui
renvoie un ouvert avec un f minimal, et la fonction bool deve loppe (Noeud *
noeud ) qui développe l' ouvert qui a le plus petit f, et qui retourne false si il n ' y a plus
de noeuds à développer.
L' algorithme A* commence par initialiser l 'ensemble des ouverts avec la position de
départ. L'ensemble des fermés est vide. L' algorithme s ' arrête lorsqu' on a atteint la position finale ou lorsque la fonction bool devel oppe (Noeud * noeud ) renvoie
f al se.
Exercice : É crire l ' algorithme A* pour le Taquin 4x4 à l ' aide des fonctions précédentes.
9.7 L'algorithme IDA*
L' inconvénient principal de A * est qu' il nécessite de grandes quantités de mémoire.
Comme l ' information minimale qu' on doit garder en mémoire est la liste des ouverts, A*
dépasse rapidement les capacités mémoires des machines actuelles pour des problèmes
assez simples. Cela ne pose pas de problème pour le Taquin 3x3, mais un Taquin 5x5 peut
remplir la mémoire disponible.
L' algorithme IDA* [52] permet de résoudre le problème de mémoire de A* tout en
gardant l'optimalité de la solution. IDA* est un acronyme pour lterative Deepening A* .
Chaque itération de l' algorithme est une recherche en profondeur d' abord qui calcule
dynamiquement !(Position) = g(Position) + h(Position) pour chaque noeud développé. Dès que la fonction f d'un noeud excède le seuil propre à l ' itération, le noeud est
coupé, et la recherche continue sur les autres chemins non coupés.
Le seuil est initialisé avec l 'évaluation heuristique h de l 'état initial. A chaque itération, le seuil est incrémenté. L' algorithme se termine lorsque un état final est atteint.
Exercice : Programmez l' algorithme IDA * pour le Taquin 4x4.
9.8 Le Rubik's cube
Le Rubik's cube peut être résolu pratiquement instantanément par un programme qui
utilise des macro coups. Ce sont des suites de coups qui échangent deux cubes sans modifier la place des autres. Nous nous intéressons à la résolution optimale du Rubik's cube
qui est plus difficile. La résolution optimale consiste à trouver une solution contenant le
173
On veut aussi disposer d' une fonction qui développe un noeud. Elle crée tous ses fils,
les insère dans l 'ensemble des ouverts, et met le noeud développé dans l 'ensemble des
fermés.
Exercice : É crire pour le Taquin 4x4 la fonction Noeud * meilleur ( ) qui
renvoie un ouvert avec un f minimal, et la fonction bool deve loppe (Noeud *
noeud ) qui développe l' ouvert qui a le plus petit f, et qui retourne false si il n ' y a plus
de noeuds à développer.
L' algorithme A* commence par initialiser l 'ensemble des ouverts avec la position de
départ. L'ensemble des fermés est vide. L' algorithme s ' arrête lorsqu' on a atteint la position finale ou lorsque la fonction bool devel oppe (Noeud * noeud ) renvoie
f al se.
Exercice : É crire l ' algorithme A* pour le Taquin 4x4 à l ' aide des fonctions précédentes.
9.7 L'algorithme IDA*
L' inconvénient principal de A * est qu' il nécessite de grandes quantités de mémoire.
Comme l ' information minimale qu' on doit garder en mémoire est la liste des ouverts, A*
dépasse rapidement les capacités mémoires des machines actuelles pour des problèmes
assez simples. Cela ne pose pas de problème pour le Taquin 3x3, mais un Taquin 5x5 peut
remplir la mémoire disponible.
L' algorithme IDA* [52] permet de résoudre le problème de mémoire de A* tout en
gardant l'optimalité de la solution. IDA* est un acronyme pour lterative Deepening A* .
Chaque itération de l' algorithme est une recherche en profondeur d' abord qui calcule
dynamiquement !(Position) = g(Position) + h(Position) pour chaque noeud développé. Dès que la fonction f d'un noeud excède le seuil propre à l ' itération, le noeud est
coupé, et la recherche continue sur les autres chemins non coupés.
Le seuil est initialisé avec l 'évaluation heuristique h de l 'état initial. A chaque itération, le seuil est incrémenté. L' algorithme se termine lorsque un état final est atteint.
Exercice : Programmez l' algorithme IDA * pour le Taquin 4x4.
9.8 Le Rubik's cube
Le Rubik's cube peut être résolu pratiquement instantanément par un programme qui
utilise des macro coups. Ce sont des suites de coups qui échangent deux cubes sans modifier la place des autres. Nous nous intéressons à la résolution optimale du Rubik's cube
qui est plus difficile. La résolution optimale consiste à trouver une solution contenant le