[C++] parcours d'arbre ternaire

Principe général

Il fonctionne sur le principe de la recherche du « meilleur-d’abord » (Best first search).

On dispose d’une situation initiale START bien connue, d’une (ou plusieurs) situation(s) finale(s) déterminée(s) GOAL. La préoccupation est alors de trouver comment passer de START à GOAL avec un coûts minimal ou un profit maximum.

On appelle état l’ensemble des informations permettant d’identifier un sous - problème. Pour passer d’un état à un autre, on dispose d’opérateurs apportant un gain additif. Appliquer ces opérateurs à un état s’appelle développer l’état. Réciproquement, on suppose qu’on dispose de marqueurs permettant de retrouver les développements successifs ayant conduit à une solution. Car c’est d’avantage le cheminement nécessaire pour identifier une solution que la solution elle même qui compte dans cette approche : cette dernière étant connue.
Une fonction d’évaluation

En fait l’algorithme parcours un arbre de recherche et, pour éviter de s’engager vers un noeud par un chemin plus mauvais qu’un précédant, il va stocker des informations sur les nœuds qu’il parcours. Pour cela, il va évaluer la qualité du nœud auquel il se trouve grâce à une fonction d’évaluation f.

Lorsque l’on examine l’état v, on connaît le coût de START à v : c’est la somme des coût c(START, v1), c(v1, v2), …, c(vk, GOAL) des opérateurs nécessaires pour passer de START à v. Mais, à moins que v = GOAL, le coût (« futur ») de v à GOAL est inconnu : on ne peut que l’estimer.

En général, la fonction d’évaluation est donc définie comme la somme de deux autres fonctions notées couramment g et h, telles que pour un nœud donné v:

·      g donne le coût du chemin déjà parcouru depuis la racine, de START à v,

·     
	

v
 
h est une estimation du coût du chemin restant à faire jusqu’au nœud final, de v à GOAL.

Figure 1 : Recherche avec l’algorithme A*

Mais on peut aussi pondérer le rapport entre le gain connu g et le gain espéré  h par la formule du type f = w.g + (1 - w).h où wÎ[0; 1].

L’idéal est d’avoir une estimation exacte de cette distance, ainsi l’effort d’exploration de l‘espace de recherche sera minimal. Cependant de telles estimations demandent souvent trop de temps de calcul pour être applicables. Il faut donc trouver un compromis entre le temps de calcul et l’exploration de l’espace de recherche pour rendre l’algorithme pratiquement acceptable [Nils82] [PeKi82].

C’est pour cela qu’on parle de stratégie informée. En effet, à tout instant, pour chaque nœud, on doit pouvoir fournir une estimation de la valeur du chemin restant à parcourir.
L’algorithme

         Le principe de l’algorithme consiste à chaque étape à choisir un état u dans la liste A_VOIR (1°) des états à développer, initialement égale à START, et ce jusqu'à ce que GOAL ait été identifié, ou que cette liste soit vide (le problème n’admet pas de solution). Cette sélection suit une stratégie « meilleur d’abord », dans la mesure où l’élément sélectionné dans A_VOIR est celui dont l’évaluation est la meilleure.

On supprime u de A_VOIR pour l’ajouter à la liste DEJA_VU (2°), initialement vide, qui contient l’ensemble de tous les états parcourus pendant la recherche.

Par application d’opérateurs sur l’état sélectionné u, on obtient de nouveaux états vi, les successeurs de u, que l’on ajoute à la liste A_VOIR (3°).

Si ces situations vi ont déjà été envisagées, mais avec un coût  moindre, on met les coût à jour, et on considère que l’état doit être réexaminé en tenant compte de cette nouvelle situation.

Cela donne de manière plus formelle :

1.        Fonction A_star(START, GOAL : T_Data) : T_Path
2.                        A_VOIR ← {START}                      // Liste des éléments à développer
3.                        DEJA_VU ← Æ                                 // Liste des éléments déjà explorés
4.                        u ← Æ
5.                        Tant que (A_VOIR ≠ Æ) et (u ≠ GOAL) faire
6.                                           v ← Choix_dans(A_VOIR)          // En meilleur d’abord
7.                                           Si (u ¹ G) alors
8.                                                              A_VOIR ← A_VOIR \ {u}
9.                                                              DEJA_VU ← DEJA_VU È {u}
10.                                                           LISTE_FILS ← Developper(u) // En appliquant les opérateurs
11.                                                           Pour chaque v dans LISTE_FILS faire
12.                                                                              Si (v Ï (A_VOIR È DEJA_VU)) alors
13.                                                                                                 A_VOIR ← A_VOIR È {(v; f(v))}
14.                                                                                                 Pred(v) ← u
15.                                                                              Sinon
16.                                                                                                 w ← Pred(v)
17.                                                                                                 Si (g(w) + c(w, v) < g(u) + c(u, v)) alors
18.                                                                                                                   Pred(v) &#8592; u
19.                                                                                                                   g(v) &#8592; g(u) + c(u, v)
20.                                                                                                                   f(v) &#8592; g(v) + h(v)
21.                                                                                                                   Si (v Î DEJA_VU) alors
22.                                                                                                                                      DEJA_VU &#8592; DEJA_VU \ {v}
23.                                                                                                                                      A_VOIR &#8592; A_VOIR È {v}
24.                                                                                                                   Fin_Si
25.                                                                                                 Fin_Si
26.                                                                              Fin_Si
27.                                                           Fin_Pour
28.                                        Fin_Si
29.                     Fin_TantQue
30.                     Si (u = GOAL) alors
31.                                        Retourner (START, ..., Pred(Pred(u)), Pred(u), u)
32.                     Sinon
33.                                        Pas de solution
34.                     Fin_Si

Configuration: Windows XP
Firefox 2.0.0.3