Méthodes de résolution de problèmes
3. Résolution de problèmes
3.4. Algorithme A*
Faire une estimation du chemin complet (du nœud initial jusqu’à un but).
Fonction d’évaluation f(n)
= g(n) + h(n)
g(n) = coût jusqu’à présent pour atteindre n
h(n) = coût estimé de n à un but
f(n) = coût total du chemin passant par n à un but
Exemple: Le voyageur de commerce en Roumani
Etape 1:
Etape 2:
Etape 3:
Etape 4:
