La définition de Espace-problème

L'espace-problème correspond à l'ensemble des situations de problèmes définies par un état initial, un but et des transformations d'états.

La construction du graphe espace-problème

La notion d'espace-problème a été introduite par Allen Newell et Herbert Simon, en 1972. Une action permet de passer d'un état à un autre, mais toutes les actions ne sont pas licites. Ainsi, l'opérateur indique les conditions auxquelles doit satisfaire l'action, en général explicitées dans la consigne.
L'état initial et l'opérateur permettent de définir un ensemble d'états accessibles. En effet, l'opérateur permet de passer de l'état initial à un certain nombre d'états possibles, puis de ces états à d'autres états et ainsi de suite. Dès lors, on peut construire de proche en proche l'ensemble des états qu'il est possible d'atteindre en respectant les contraintes de l'opérateur. Si l'on joint par un arc les couples d'états entre lesquels on peut passer, on obtient un graphe qui est l'espace-problème.

Un espace de recherche

L'espace-problème constitue l'espace de recherche potentiel pour un problème donné et la recherche de la solution peut être vue comme la recherche du chemin le plus court pour passer de l'état initial à l'état final. Les stratégies de recherche (ou heuristiques) sont des règles qui permettent une exploration économique de cet espace. L'espace de recherche découle de l'interprétation de l'opérateur et de celle des objets de la situation, ainsi que de leurs propriétés. L'espace-problème peut être soit l'espace-problème correct, celui qui correspond à une bonne interprétation, soit l'espace-problème du sujet, qui peut être erroné.