3. Hill-Climbing
Hill-Climbing améliore localement l’état courant. Il ne conserve pas toutes les branches abandonnées.
3.1 Version simple
- Générer les enfants de l’état courant dans l’ordre imposé.
- Les tester un à un.
- Dès qu’un enfant est strictement meilleur que son parent, le choisir comme nouvel état courant.
- Répéter jusqu’au but ou jusqu’à l’impossibilité d’avancer.
L’ordre des opérateurs influence directement le chemin, puisque le premier enfant améliorant l’état est retenu.
3.2 Version la plus escarpée
- Générer tous les enfants de l’état courant.
- Calculer leur heuristique.
- Retenir le meilleur enfant parmi tous ceux qui améliorent strictement le parent.
- Continuer depuis cet enfant.
Cette version examine davantage d’options locales, mais elle n’offre toujours pas de retour vers une autre branche. En cas d’égalité, une règle de départage doit être annoncée; l’égalité avec le parent ne constitue pas une amélioration.
3.3 Échecs typiques
- Maximum local : aucun enfant n’est meilleur que l’état courant, même si un meilleur état existe ailleurs.
- Cul-de-sac : aucun nouvel état n’est accessible.
- Mauvais choix de branche : un état localement prometteur conduit à une impasse, alors qu’une autre branche contenait une solution.
Hill-Climbing est peu coûteux en mémoire et simple, mais il n’est pas complet dans sa forme présentée : il peut échouer alors qu’une solution accessible existe.