Exercice 1 :
Appliquons l’algorithme A*
Lugoj : g=0 ; h=244 ; f=244
S1= {Mehadia(g=70 ; h=241 ; f=311 ) ; Timisoara(g=111 ; h=329 ; f=440)}
S2= {Timisoara(g=111 ; h=329 ; f=440) ; Dobreta(g=145;h=242 ; f=387)}
S3= {Timisoara(g=111 ; h=329 ; f=440) ; Craiova(g=265;h =160;f=425)}
S4= {Timisoara(g=111 ; h=329 ; f=440) ; Pitesti(g=403 ; h=100;f=503) ; Rimnicu
Vilcea(g=411;h=193 ; f=604)}
S5= {Pitesti(g=403 ; h=100;f=503) ; Rimnicu Vilcea(g=411;h=193 ; f=604) ; Arad(g=229;h=366 ;
f=595)}
S6= {Rimnicu Vilcea(g=411;h=193 ; f=604) ; Arad(g=229;h=366 ; f=595) ; Bucharest(g=503 ;
h=0;f=503)}
Objectif atteint. Il faut vider la frontière.
Exercice 2 - Solution complète
1 : Les heuristiques h₁, h₂ et h₃ sont-elles admissibles ?
Une heuristique est admissible si elle ne surestime jamais le coût réel pour atteindre le but.
Pour vérifier l'admissibilité, on calcule le coût réel minimal de chaque nœud vers I et le comparer
aux valeurs des heuristiques.
Coûts réels minimaux vers I :
- A → C → F → G → I : 5 + 2 + 3 + 3 = 13 (ou A → C → B → G → I : 5 + 2 + 5 + 3 = 15)
- A → C → F → I : 5 + 2 + 3 = 10
- A → D → E → B → G → I : 5 + 2 + 5 + 5 + 3 = 20
- A → C → F → G → I : 5 + 2 + 3 + 3 = 13
- A → C → B → I : 5 + 2 + 7 = 14
- Coût minimal de A : 10 (le tableau donne h₁(A)=10)
En comparant avec les valeurs du tableau :
- h₁ : h₁(A)=10, h₁(H)=3... avec h₁(nœud) ≤ coût réel (admissible)
- h₂ : h₂(A)=10, h₂(C)=8, h₂(D)=11... avec Si h₂(D)=11 > coût réel de D vers I
- h₃ : h₃(A)=10, h₃(D)=11... Si h₃(D)=11 > coût réel
Conclusion : Seule h₁ est admissible.
2 : Relations de dominance entre les heuristiques
Une heuristique h₁ domine h₂ si : h₁(n) ≥ h₂(n) pour tout nœud n (et h₁ reste admissible).
En comparant les valeurs :
- h₁(C)=5, h₂(C)=8 alors h₁ < h₂ pour C
- h₂(C)=8, h₃(C)=6 alors h₂ > h₃ pour C
- h₁(D)=10, h₃(D)=11 alors h₁ < h₃ pour D
Aucune relation de dominance stricte n'existe entre ces trois heuristiques (les valeurs s'entrecroisent
selon les nœuds).
3 : h₄ = max(h₁, h₃) est-elle admissible ?
h₄(n) = max(h₁(n), h₃(n))
Puisque h₃ n'est pas admissible, alors h₄ héritera de ces surestimations.
Non, h₄ n'est pas admissible car max(admissible, non-admissible) = non-admissible.
4 : Recherche gloutonne avec h₃
Algorithme glouton : on choisit toujours le nœud avec la plus petite valeur d'heuristique.
Étape Nœud développé Frontière (nœud, h₃) Action
1A D(11), C(10) Développer C (h₃ = 10)
2C D(11), F(10), B(11) Développer F (h₃ = 10)
3F D(11), B(11), G(3) Développer G (h₃ = 3)
4G D(11), B(11), I(0), H(4) But atteint : I
Suite des nœuds développés : A → C → F → G → I
Coût total : 5 + 2 + 3 + 3 = 13
5 : Recherche A* avec h₁
A* : f(n) = g(n) + h(n), on développe le nœud avec le plus petit f.
Étape Nœud développé Frontière (nœud, g, h₁, f)
1A D(5, 10, 15), C(5, 5, 10)
2C D(5, 10, 15), F(7, 3, 10), B(7, 8, 15)
3F D(5, 10, 15), G(10, 3, 13), B(7, 8, 15)
4G I(13, 0, 13), D(5, 10, 15), B(7, 8, 15), H(14, 3, 17)
5I But atteint
Suite : A → C → F → G → I
Coût : 13
6 : Recherche A* avec h₂
Étape Nœud développé Frontière (nœud, g, h₂, f)
1A D(5, 11, 16), C(5, 8, 13)
2C D(5, 11, 16), F(7, 2, 9), B(7, 6, 13)
3F D(5, 11, 16), G(10, 1, 11), B(7, 6, 13)
4G I(13, 0, 13), D(5, 11, 16), B(7, 6, 13), H(14, 5, 19)
5I But atteint
Suite : A → C → F → G → I
Coût : 13
7 : Recherche A* avec h₄
h₄ = max(h₁, h₃) donne les mêmes valeurs que h₃ dans la plupart des cas.
Suite similaire : A → C → F → G → I
Coût : 13
8 : Choix de l'heuristique
Si on doit choisir entre h₁, h₂ et h₃ = max(h₁, h₂) admissibles :
Mais h1 reste le meilleur choix car elle est admissible et constante