9.9 Corrigés des exercices
}
}
noeud = meilleur ();
if (noeud == NULL)
return -1;
if (noeud-> final ())
break ;
return noeud->f ( );
9.9.3 L'algorithme IDA * pour le Ta quin
Position pos ;
int seuil ;
bool IDAEtoileRecursif ( int g);
int IDAEtoile ( ) {
bool trouve = fa Ise ;
}
fo r (seuil = pos . h (); seuil < MaxLength && ! trouve ;
seuil + +)
trouve = IDAEtoileRecursif (0);
return seuil ;
bool IDAEtoileRecursif ( int g) {
if ( g + pos . h ( ) > seuil )
return fa lse ;
}
if (pos . fi nale ())
return true ;
char vide = pos . vide ();
for ( in t i = 1 ; i <= coups Po s si b les [ vide ] [ 0 ] ; i + + ) {
pos . joue ( coupsPossibles [vide ] [ i]);
if ( IDAEtoileRecursif (g + 1))
return true ;
pos .joue (vide );
}
return false ;
9.9.4 Le Rubik's cube
179
Le Rubik's cube contient 20 cubes, 8 cubes de coin et 12 cubes de bord. Une heuristique admissible pour la fonction h utilise la somme des distances de Manhattan entre les