178
Recherche de la solution la plus courte pour les puzzles
comme suit :
int fcourant = O;
Noeud fermes ;
Noeud * meilleur () {
}
w hile ( o u v e r t s [ f c o u r a n t ] . s u i v a n t -- NULL &&
fcourant < MaxLength )
fcouran t++;
return ouverts [fcourant ]. suivant ;
bool developpe (Noeud * noeud) {
}
II On ote le noeud déve loppé de l 'ensemble des Ouverts
ouverts [noeud->f ()]. suivant = noeud->suivant ;
Il on insere les fi ls dans les ouverts
for ( int i= 1; i <= coupsPossibles [noeud->vide ()] [0] ;
i ++) {
}
Noeud * tmp = new Noeud (noeud );
if (tmp == NULL) {
}
fprintf (stderr , "Abandon , �mémoire�saturée \ n" );
return false ;
tmp->parent = noeud ;
tmp ->joue ( coupsPossibles [ noeud->v ide ()] [ i]);
insere (tmp);
11 On l'ajoute à l'ensemble des fe rmes
noeud->suivant = fermes . suivant ;
fermes . suivant = noeud ;
return true ;
D 'où l ' algorithme A * :
int AEtoile (Position & p) {
Noeud * racine = new Noeud ;
racine ->init (p , 0);
insere (racine );
Noeud * noeud = meilleur ();
while (true ) {
if (!developpe (noeud ))
return -1;