Recherche dans l'espace d'états

La recherche dans l'espace d'états est l'exploration systématique de l'ensemble des états atteignables à partir d'un état initial via des actions disponibles, dans le but de trouver un état qui satisfait un test d'objectif ou un chemin qui y mène.

Definition

La recherche dans l'espace d'états traite un problème comme un graphe dont les nœuds sont des états et les arêtes des actions, et procède en développant des états à partir d'une frontière selon une stratégie fixe jusqu'à ce qu'un état objectif soit trouvé ou que l'espace soit épuisé.

Scope

Ce sujet aborde la formulation d'un problème comme un espace d'états (états, actions, modèle de transition, test d'objectif, coût du chemin) et les stratégies de recherche non informées qui l'explorent sans guidage spécifique au domaine : recherche en largeur d'abord, recherche à coût uniforme, recherche en profondeur d'abord, recherche en profondeur limitée et recherche par approfondissement itératif. Il inclut l'analyse de ces stratégies en termes de complétude, d'optimalité, de complexité temporelle et de complexité spatiale, ainsi que la distinction entre la recherche arborescente et la recherche graphique avec détection des états répétés. Le guidage heuristique est traité dans le sujet distinct sur la recherche heuristique et A*.

Core questions

• Comment un problème est-il représenté par des états, des actions, un modèle de transition et un test d'objectif ?
• En quoi les recherches en largeur d'abord, en profondeur d'abord, à coût uniforme et par approfondissement itératif diffèrent-elles dans l'ordonnancement de leur frontière ?
• Quelles sont les garanties de complétude, d'optimalité, de temps et d'espace de chaque stratégie non informée ?
• Comment la recherche graphique évite-t-elle la réexploration inutile d'états que la recherche arborescente permet ?

Key concepts

• état initial et test d'objectif
• modèle de transition et successeurs
• frontière (liste ouverte) et ensemble exploré
• recherche en largeur d'abord
• recherche en profondeur d'abord
• recherche à coût uniforme
• approfondissement itératif
• recherche arborescente vs. recherche graphique

Key theories

L'ordonnancement de la frontière détermine la stratégie

Les algorithmes de recherche non informés se distinguent uniquement par l'ordre dans lequel ils retirent les états de la frontière : une file FIFO donne la recherche en largeur d'abord, une pile LIFO donne la recherche en profondeur d'abord, et une file de priorité basée sur le coût du chemin donne la recherche à coût uniforme.

L'approfondissement itératif comme optimum économe en espace

La recherche par approfondissement itératif en profondeur d'abord exécute de manière répétée une recherche en profondeur d'abord avec des limites de profondeur croissantes, combinant l'espace linéaire de la recherche en profondeur d'abord avec la complétude et l'optimalité (pour les coûts unitaires) de la recherche en largeur d'abord.

Clinical relevance

La recherche non informée dans l'espace d'états constitue le fondement conceptuel et d'implémentation pour la recherche de chemins, la résolution de puzzles, l'analyse d'atteignabilité dans la vérification de modèles, et sert de substrat sur lequel se construisent les recherches heuristiques et adverses ; la compréhension de sa complexité permet de déterminer quand une recherche aveugle est réalisable et quand des heuristiques sont nécessaires.

History

La recherche systématique dans l'espace d'états dérive des algorithmes de parcours de graphes des années 1950, y compris les travaux de Moore et Dijkstra sur les chemins les plus courts, et a été formulée comme un modèle de résolution de problèmes dans l'IA primitive. L'analyse de Korf en 1985 sur l'approfondissement itératif a établi son optimalité parmi les recherches arborescentes admissibles avec un espace linéaire.

Key figures

• Nils J. Nilsson
• Richard E. Korf
• Edward F. Moore
• Edsger W. Dijkstra

Seminal works

• nilsson1971
• russell2020

Frequently asked questions

Quand la recherche en largeur d'abord est-elle optimale ?

La recherche en largeur d'abord est optimale lorsque chaque étape a le même coût, car elle trouve d'abord l'objectif le moins profond. Lorsque les coûts des étapes diffèrent, la recherche à coût uniforme (qui ordonne la frontière par le coût de chemin accumulé) est la stratégie non informée qui garantit une solution de moindre coût.

Pourquoi utiliser l'approfondissement itératif plutôt que la simple recherche en largeur d'abord ?

La recherche en largeur d'abord stocke toute la frontière et peut nécessiter une mémoire exponentielle par rapport à la profondeur. L'approfondissement itératif effectue de manière répétée une recherche en profondeur d'abord avec des limites de profondeur croissantes, n'utilisant qu'une mémoire linéaire tout en étant complet et optimal pour les problèmes à coût unitaire, au prix de la réexpansion des nœuds peu profonds.