9.9 Corrigés des exercices
} ;
La structure d 'un noeud de l ' arbre de recherche est la suivante :
class Noeud {
Po s i t i o n _p ;
int _g , _h ;
public :
Noeud *parent , *Suivant ;
Noeud () {
suivant = NULL ;
}
void in i t ( const
_p = p;
_g = g;
h = p.h ();
}
Position & p,
int f () { return _g + _h ; }
int g)
bool final () { return _p . finale (); }
void joue (in t coup ) {
}
} ;
_p .joue (coup );
_g ++;
h = _p . h ();
{
177
On utilise un tableau de piles pour représenter l 'ensemble des ouverts. Un indice dans
le tableau correspond à une valeur de f. L' insertion se fait en temps constant, et la recherche dans le tableau du noeud qui a le plus petit f est aussi très rapide.
11 valeur maximum de f
const int MaxLength = 1000;
11 une pile d'ouverts par f possible
Noeud ouverts [MaxLength + 1];
void insere (Noeud * noeud) {
}
Noeud * tmp = & ou verts [ noeud->f ()];
noeud->s uivant = tmp->suivant ;
tmp-> s uivant = noeud ;
On suppose que f est toujours croissante, ce qui est vrai pour de nombreuses fonctions h, notamment dans le cas du Taquin. Les fonctions meilleur et developpe s 'écrivent