4. Meilleur d’abord
Le meilleur d’abord (Best-First Search) corrige la perte d’information du Hill-Climbing en conservant tous les états générés dans une file de priorité OUVERTS.
4.1 Déroulement
- Placer l’état initial dans
OUVERTS. - Trier
OUVERTSselonh(n)et retirer le meilleur état disponible. - Si cet état satisfait le but, arrêter.
- Sinon, le placer dans
FERMÉS, générer ses enfants non déjà traités et les ajouter àOUVERTS. - Réordonner la liste et recommencer.
La liste permet un saut de branchement : après une impasse, le meilleur état restant peut provenir d’une autre partie de l’arbre.
4.2 Différence essentielle avec Hill-Climbing
Un enfant n’a pas besoin d’être meilleur que son parent. Il est comparé à l’ensemble des états ouverts. Un enfant moins prometteur localement peut donc rester disponible et devenir le meilleur choix global après l’exploration d’autres candidats.
4.3 Règles de départage
Si plusieurs états ont la même valeur, la stratégie doit préciser une règle stable : ordre gauche-droite, ancienneté dans la file ou autre convention donnée dans l’énoncé. Cette règle peut modifier la trace, même si elle ne change pas nécessairement l’existence d’une solution.
4.4 Trace et solution
La trace d’exploration comprend tous les états développés, y compris ceux d’une branche finalement abandonnée. Le chemin solution est la chaîne de parents menant de l’état final à l’état initial. Les deux ne doivent pas être confondus.