180
Recherche de la solution la plus courte pour les puzzles
cubes et leurs états finaux [56]. On doit donc calculer pour chaque cube le nombre minimal de coups nécéssaires pour le mettre à sa place dans la bonne orientation. On fait alors
la somme de tous ces nombres de coups pour tous les cubes. To utefois, chaque rotation
fait bouger 4 cubes de coin et 4 cubes de bord, donc pour que la valeur soit admissible,
on doit la diviser par 8.
h _ L:cE Cubc Manhattan(c)
1 -
8
Une meilleure heuristique admissible est de prendre le maximum des distances de
Manhattan des cubes de coin, et des cubes de bord divisées toutes les deux par 4.
h _
(
:LcE CubcsBord lvl anhattan(c) :Lc E CubesCoin lv/ anhattan(c) )
2 -m ax
4
,
4
On a en effet toujours hi :::; h2·
Recherche de la solution la plus courte pour les puzzles
cubes et leurs états finaux [56]. On doit donc calculer pour chaque cube le nombre minimal de coups nécéssaires pour le mettre à sa place dans la bonne orientation. On fait alors
la somme de tous ces nombres de coups pour tous les cubes. To utefois, chaque rotation
fait bouger 4 cubes de coin et 4 cubes de bord, donc pour que la valeur soit admissible,
on doit la diviser par 8.
h _ L:cE Cubc Manhattan(c)
1 -
8
Une meilleure heuristique admissible est de prendre le maximum des distances de
Manhattan des cubes de coin, et des cubes de bord divisées toutes les deux par 4.
h _
(
:LcE CubcsBord lvl anhattan(c) :Lc E CubesCoin lv/ anhattan(c) )
2 -m ax
4
,
4
On a en effet toujours hi :::; h2·