2. Heuristiques et recherche informée
2.1 Définition
Une fonction heuristique h(n) estime la qualité d’un état n ou le coût restant pour atteindre un état final. Elle est :
- approximative : elle ne calcule pas nécessairement le vrai coût;
- rapide : son calcul doit rester beaucoup moins coûteux que l’exploration évitée;
- contextuelle : une bonne estimation pour un problème ne se transpose pas automatiquement à un autre;
- ordonnante : elle permet surtout de décider quel état considérer avant les autres.
Exemples du cours : distance à vol d’oiseau sur une carte, nombre de tuiles correctement placées, nombre de tuiles mal placées, nombre de pièces restantes dans un jeu ou gain estimé de MAX.
2.2 Sens de l’heuristique
Il faut toujours déterminer dans quel sens la valeur s’améliore :
- heuristique croissante : une valeur plus grande indique un état plus prometteur, par exemple le nombre de tuiles bien placées;
- heuristique décroissante : une valeur plus petite indique un état plus proche du but, par exemple le nombre de tuiles mal placées ou une distance restante; le but peut alors avoir
h=0.
Le mot « meilleur » n’est donc pas synonyme de maximum. Il dépend de la définition de h.
2.3 Compromis information–calcul
Une heuristique plus précise n’est utile que si son coût demeure raisonnable. Une estimation simple mais rapide peut produire une meilleure performance globale qu’une estimation très fine qui exige presque autant de calcul que la recherche elle-même.