8.5 Corrigés des exercices
161
admissible. De plus chaque mise à jour du tableau heuristique conserve l ' admissibilité ; on
a donc toujours heuristique[x] < h* (x). Si on définit l' erreur globale comme la somme
pour tous les états de h* (x) - heuristique[x] et la disparité comme la somme de l 'erreur
globale et de heuristique[x] pour l 'état courant de LRTA * . A chaque coup, cette valeur
ne peut que décroitre. Or lorsqu' elle atteint 0 le problème est résolu. Le problème sera
donc résolu par LRTA * .
8.4.5 Recherche avec cible mouvante
La recherche avec cible mouvante est une généralisation de LRTA * au cas où la cible
bouge. La recherche doit alors avoir un heuristique pour chaque position possible de la
cible. On utilise donc une table heuristique(x, y ) qui donne l 'heuristique pour atteindre
la cible y à partir de la position x. heuristique(x, y ) est initialisée avec l 'heuristique
admissible initiale h.
Pour déplacer le chasseur on appelle nouvellePosition, et on appelle deplaceCible
lorsque la cible se déplace.
Algorithm 9 Recherche d' un chemin sur une carte avec cible mouvante
nouvellePosition (cible, pas)
for tous les voisins de pas do
if heuristique (voisin, cible) + 1 < best then
best +--- heuristique (voisin, cible) + 1
meilleur Voisin +--- voisin
end if
end for
if heuristique (pas, cible) + 1 < best then
affecteHeuristique (pas, cible, best)
end if
retourner meilleur Voisin
deplaceCible (prevCible, cible, pas)
if heuristique (pas, prevCible) < heuristique (pas, cible) - l then
affecteHeuristique (pas, prevCible, heuristique (pas, cible) - 1)
end if
8.5 Corrigés des exercices
8.5.1 Dijkstra
#include
#include
#include