174
Recherche de la solution la plus courte pour les puzzles
plus petit nombre de coups possibles.
Le Rubik's Cube se prête bien à une résolution par IDA* [56]. Le coût des recherches
exhaustives à une profondeur inférieure à celle du seuil n'est que de 8% du coût de la
recherche à la profondeur du seuil. L' utilisation de IDA* dans ce cas est donc justifiée.
Elle est même nécessaire étant donné le très grand nombre de noeuds à développer pour
les profondeurs utiles.
Exercice : Trouver une heuristique admissible simple basée sur la distance de Manhattan pour le Rubik 's cube. Est il possible de l'améliorer simplement ?
9.9 Corrigés des exercices
9.9.1 Le voyageur de commerce
Nous donnons un programme simple et naïf pour résoudre le voyageur de commerce.
Il existe une vaste littérature sur le sujet. Les lecteurs intéressés par ce problème peuvent
se référer à [7 1] par exemple.
const int N = 10;
int distance [N] [N] ;
bool visitee [N] ;
int meilleurTrajet [N + 1];
int meilleurCout ;
void plusCourtTraj et ( int depth , int coutChemin ,
int trajet [N + l]);
void voyageur () {
}
int trajet [N + 1];
for (int i = O; i < N; i++)
visitee [ i] = false ;
visitee [O] = true ;
trajet
[0] = 0;
meilleurCout = MAXINT;
plusCourtTrajet (1 , 0, trajet );
void plusCourtTrajet ( int depth , int coutChemin ,
int trajet [N + 1]) {
if (depth == N) {
trajet [N] = O;
coutChemin += distance [trajet [N - 1]] [O] ;