2. Heuristiques pour le jeu du Taquin. 1
4. Greedy search (recherche glounne). 2
1. Exploration informée
L’un des composants clés de ces algorithmes est la fonction
heuristique, notée h.
h = coût estimé du
chemin le moins coûteux menant du noeud n à un but.
Par exemple, en Algérie , on pourrait estimer le coût du chemin le plus économique de saida à oran par rapport à la distance en ligne droite entre ces deux villes.
h1 = le nombre de pièces mal placées.
Exemple
2. Heuristiques pour le jeu du Taquin
Soit
h1 = le nombre de pièces mal placées. les huit pièces sont toutes mal placées; il en résulte que l’état de départ doit être h1 = 8.
• h2 = la somme des distances des pièces par rapport à leur position cible. Comme on ne peut pas déplacer les pièces en diagonale, la distance consistera en la somme des distances horizontales et verticales. C’est ce qu’on appelle parfois la distance City Block ou distance de Manhattan.
h2 = 3+1+2+2+2+3+3+2=18.
Les fonctions heuristiques sont le moyen le plus courant pour fournir à l’algorithme d’exploration des connaissances supplémentaires sur le problème.
En un nœud n on deux informations clés
g qui est le cout du chemin par lequel on est arrivé à n
et h qui est le coût estimé du chemin le moins coûteux
menant du noeud n à un but.
On pose f=g
+h
qui donne une mesure sur la qualité du nœud n.
f doit indiquer la qualité de la solution en passant par
n
3. Best first search
La stratégie d’expansion des noeuds est de développer le noeud avec la plus faible valeur de f = g +h.
4. Greedy search (recherche glounne)
Même principe avec :
F=h
5. L’algorithme A*
f = g
+h
est
une estimation du coût minimal passant
par le noeud n.
La stratégie d’expansion des noeuds est de développer le noeud avec la plus faible valeur de f = g +h.
Definition (admissibilité) Une heuristique est admissible ssi elle sous estime toujours le coût.
Theorem : A* dans la version tree-search est optimal si la fonction heuristique h est admissible
Definition (monotonicité) une heuristique est monotone si
pour tout noeud n, tout succésseur n’ de n on a h <= c(n,n’ ) +h(n’ ).
Theorem A* dans la version graph-search est optimal si la fonction heuristique h est monotone.