Méthodes de résolution de problèmes
3. Résolution de problèmes
- On part du principe que tous les problèmes étudiés sont composés d’un ensemble de situations que l’on peut décrire à l’aide d’un ensemble de variables appelés variables d’états.
- L’état d’un problème est alors l’ensemble des valeurs prises par les variables à un instant donné. L’espace d’état d’un problème est l’ensemble de tous ses états possibles.
- Chaque état possède un ensemble d’états qui lui sont accessibles dans le problème. Les opérateurs permettent de définir cet ensemble, et c’est la stratégie de résolution qui donnera la façon de choisir parmi ces états accessibles celle menant à une solution.
- Un problème est défini pour un objectif particulier. On doit donc également définir une fonction de test de but atteint qui détermine si un état du problème correspond à un état but du problème.
- Une solution est une séquence d’actions permettant de passer de l’état initial vers un état but.
- On peut considérer que la résolution d’un problème est la découverte d’un état du problème ayant des caractéristiques données (la solution).
Le processus de résolution de
problème consiste donc à construire un arbre de recherche où chaque nœud de l’arbre correspond
soit à l’état initial du problème, soit à un développement du sommet parent par
un des opérateurs du problème.
Généralement, on représente un problème par un
espace d'états (arbre/graphe) où chaque état est une configuration
possible du problème. Et donc résoudre le problème consiste à
trouve un chemin dans le graphe.
- La racine de l’arbre correspond à l’état initial du problème.
- Les feuilles de l’arbre correspondent à des états sans successeur dans l’arbre ou des nœuds qui n’ont pas encore été développés.
- Un chemin est une séquence de sommets partant du sommet à une feuille.
- Le coût d’un chemin est défini par la somme des coûts de chaque opérateur intervenant dans la construction du chemin.