Méthodes de résolution de problèmes
3. Résolution de problèmes
3.2. Stratégies heuristiques
- Les stratégies informées ou heuristiques utilisent un ensemble de règles qui permettent d’évaluer la probabilité qu’un chemin allant du nœud courant au nœud solution soit meilleur que les autres.
- Cette information permet l’estimation des bénéfices des divers chemins avant de les parcourir améliore le processus de recherche.
- Les algorithmes de recherche heuristique utilisent des fonctions appelées fonctions heuristiques. h : E –>R
Heuristique:
- Une heuristique est une mesure associée à un état donné qu’on notera h(Ei).
- Une heuristique est un critère ou une méthode permettant de déterminer parmi plusieurs lignes de conduite celle qui promet d’être la plus efficace pour atteindre un but.
- Elle fournit rapidement une solution réalisable, pas nécessairement optimale, pour un problème d'optimisation difficile.
- Une
heuristique s'impose quand les algorithmes de résolution exacte sont
de complexité exponentielle.
Les heuristiques peuvent être
classées en deux catégories :
- Méthodes constructives qui génèrent des solutions à partir d’une solution initiale en essayant d’en ajouter petit à petit des éléments jusqu’à ce qu’une solution complète soit obtenue.
- Méthodes de fouilles locales qui démarrent avec une solution initialement complète (probablement moins intéressante), et de manière répétitive essaie d’améliorer cette solution en explorant son voisinage.
En effet, dans certains cas, le prix à payer pour utiliser des méthodes de programmation mathématique peut être une très grande complexité mathématique qui se traduit par des temps de calculs souvent longs. Parce qu’en pratique, une solution à un problème décisionnel doit être proposée dans des temps raisonnables, on sacrifie en partie la qualité de la solution au sens purement mathématique pour accélérer le processus de résolution.
On cite quelques algorithmes informés:- Meilleur d'abord
- Algorithmes gloutons
- Algorithme A∗
- Coût uniforme
- Méta-heuristiques