2. Représenter un problème par un espace d’états

2. Représenter un problème par un espace d’états

2.1 Du problème au graphe

Un graphe est constitué de nœuds et d’arcs. Dans la modélisation d’un problème :

• un nœud représente un état, c’est-à-dire une configuration valide;
• un arc représente une opération légale qui transforme un état en un autre;
• un chemin est une séquence ordonnée de nœuds reliés par des arcs;
• un cycle apparaît lorsqu’un chemin revient à un nœud déjà rencontré;
• un arbre est un graphe sans cycle où deux nœuds sont reliés par un chemin unique;
• la racine est un nœud sans parent, généralement l’état initial dans un arbre de recherche.

La représentation enseignée est le quadruplet :

[N, A, S, GD]

où :

• N est l’ensemble des nœuds, donc des états possibles;
• A est l’ensemble des arcs, donc des opérations possibles;
• S est l’ensemble de départ, réduit ici à l’état initial EI;
• GD est l’ensemble des états d’arrivée, soit le ou les états finaux EF.

Une solution est un chemin de EI vers un élément de EF, composé uniquement d’opérations applicables.

2.2 Ce qu’une formalisation complète doit contenir

Une réponse satisfaisante ne se limite pas à décrire le problème en prose. Elle doit préciser :

1. la structure de données ou les symboles qui décrivent un état;
2. les contraintes qui rendent cet état valide;
3. l’état initial;
4. le ou les états finaux, ou un test de but;
5. chaque opération, avec son nom, ses préconditions et son effet;
6. les invariants qui doivent demeurer vrais après toute opération.

Il faut distinguer représentation et stratégie. La représentation dit quels états et transitions existent. La stratégie décide lequel des états générés sera développé ensuite. La même représentation peut donc être explorée par plusieurs stratégies.

Cette formalisation systématise une démarche intuitive : observer la situation, énumérer les options légales, prévoir leurs conséquences, puis choisir une option. L’espace d’états encode les trois premières étapes; la stratégie de recherche formalise la dernière.

2.3 Graphe implicite

Il n’est généralement ni nécessaire ni réaliste d’énumérer toutes les configurations. L’algorithme reçoit plutôt les règles qui permettent :

• de reconnaître un état valide;
• de générer les successeurs d’un état courant;
• de détecter un état final.

Il construit alors seulement la portion du graphe qu’il explore. Cette distinction est essentielle lorsque le nombre de configurations croît très vite, comme aux échecs ou même au tic-tac-toe.