9.9 Corrigés des exercices
175
}
if ( coutChemin < meilleurCout ) {
meilleurCout = coutChemin ;
}
for (int i= O; i <= N; i++)
meilleurTrajet [i] =t rajet [i];
el se
for (int i = 1; i < N; i++)
if (! visitee [i]) {
trajet [depth ] = i;
visitee [i] = true ;
plusCourtTrajet ( depth + 1, coutChemin +
distance [trajet [depth - 1)) [i],
trajet );
visitee [i] = false ;
}
}
9.9.2 L'algorithme A* pour le Ta quin
On définit la classe Position comme suit :
int coupsPossibles [ 16] [ 5] =
{{2, 1 '
4, 0, O } '
{3 '
0, 5 '
2,
{2 , 2, 7, 0, O } ,
{{3 , 0, 5 '
8, O } , {4 , 1 '
4, 6,
{3 , 3 '
6 '
11 , O } '
O } '
{3 ,
9 } , {4 ,
{{3 , 4, 9 , 12 '
O } , {4 , 5 '
8, 10, 13 } '
{4 , 6, 9, 11 , 14 } '
{3 '
7, 10, 15 '
O } ,
{{2, 8 '
13 '
0, O } , {3 '
9 , 12 '
14, O } ,
1 '
2,
{3 , 10 '
13 '
15 '
O } , {2, 11 '
14, 0, O }} ;
class Position {
char _pos [ 16);
char _vide ;
public :
init () {
}
for (int i = O; i < 15; i++)
_pos [ i ] = i + 1 ;
_pos [ 15] = 0;
vide = 15;
void joue (int coup ) {
_pos [_vide ] = _pos [coup ];
_pos [coup] = O;
vide = coup ;
6, 3 '
O } ,
5 '
7 ' 10 } ,