La résolution de problèmes comme recherche

Avant de pouvoir être fouillé, un problème doit être décrit d’une manière particulière. La description est délibérément dépouillée, et c’est cette sobriété qui permet à un même algorithme de résoudre un calcul d’itinéraire, un casse-tête et un ordonnancement sans savoir duquel il s’agit.

Les cinq parties d’un problème de recherche

Un problème de recherche est donné par un état initial, un ensemble d’actions disponibles dans chaque état, un modèle de transition indiquant vers quel état mène chaque action, un test de but, et un coût de pas pour chaque action. Ensemble, les trois premiers définissent implicitement l’espace d’états : le graphe de tous les états atteignables depuis le départ.

Le mot implicitement fait tout le travail. L’espace d’états n’est jamais écrit. Il est engendré à la demande, un successeur à la fois, ce qui rend possible la fouille d’espaces comptant plus d’états qu’il n’y a d’atomes dans l’univers observable. Une solution est une suite d’actions de l’état initial jusqu’à un but, et une solution optimale est une solution de coût total minimal.

Quatre questions à poser sur toute stratégie

Chaque stratégie de cette leçon est jugée sur les mêmes quatre critères :

• Complétude - si une solution existe, l’algorithme est-il garanti de la trouver ?
• Optimalité - trouve-t-il la solution la moins coûteuse ?
• Complexité en temps - combien de nœuds engendre-t-il ?
• Complexité en espace - combien en garde-t-il en mémoire à la fois ?

La complexité s’exprime avec le facteur de branchement $b$, le nombre de successeurs par nœud, et la profondeur $d$ du but le moins profond.

La largeur d’abord et le mur de la mémoire

La recherche en largeur développe le nœud non développé le moins profond : elle trouve donc un but le moins profond. Elle est complète quand $b$ est fini, et engendre de l’ordre de $b^d$ nœuds à condition que le test de but soit appliqué à chaque nœud dès qu’il est engendré. Reportez le test au développement, comme la recherche à coût uniforme doit le faire, et tout le niveau suivant est engendré d’abord : $O(b^{d+1})$.

Le piège est l’espace. Toute la frontière est conservée d’un coup, donc la mémoire est elle aussi en $O(b^d)$ - la même exponentielle que le temps. Russell et Norvig tabulent ce que cela signifie avec $b = 10$, un million de nœuds par seconde et un kilo-octet par nœud, et en tirent la leçon sans détour :

les besoins en mémoire sont un problème plus grave pour la recherche en largeur que ne l’est le temps d’exécution.

Une recherche à la profondeur 12 prend environ treize jours, ce que l’on pourrait attendre. Elle demande aussi un pétaoctet de mémoire, dont aucune machine ordinaire ne dispose. Le temps est une gêne ; la mémoire est un mur.

Il y a une seconde limite. La recherche en largeur renvoie le but le moins profond, qui n’est le but le moins coûteux que si tous les pas coûtent la même chose. Quand les coûts diffèrent, le remède est la recherche à coût uniforme : développer le nœud de plus faible coût de chemin $g(n)$ plutôt que de plus faible profondeur. Elle est optimale pour tous coûts de pas positifs, même si elle peut gaspiller de l’effort à explorer de grands arbres de tout petits pas avant d’essayer un grand.

La profondeur d’abord et l’approfondissement itératif

La recherche en profondeur descend aussi loin qu’elle peut avant de revenir en arrière : elle ne stocke donc que le chemin courant et ses frères non développés, soit $O(bm)$ en mémoire pour une profondeur maximale $m$. L’économie est spectaculaire. Le prix est qu’elle n’est ni optimale ni - sur un espace infini ou comportant des boucles - complète.

L’approfondissement itératif prend la bonne moitié de chacune. On lance une recherche à profondeur limitée avec la limite 0, puis 1, puis 2, jusqu’à trouver un but :

Les deux lignes en $O(b^d)$, ainsi que les treize jours et le pétaoctet ci-dessus, supposent le test de but à l’engendrement ; au développement, chacune devient $O(b^{d+1})$.

L’objection évidente est que les niveaux supérieurs sont réengendrés à chaque itération. La réponse est que, dans un arbre à facteur de branchement à peu près constant, presque tous les nœuds sont au dernier niveau, qui n’est engendré qu’une fois : la répétition coûte donc un facteur constant tandis que l’économie de mémoire est exponentielle. C’est pourquoi l’approfondissement itératif est la méthode non informée standard quand l’espace est vaste et la profondeur de la solution inconnue.

Avant le quiz

Sachez énoncer les cinq parties d’un problème de recherche, énumérer les quatre critères d’évaluation, donner les complexités en temps et en espace de chacune des stratégies ci-dessus, dire précisément quand la recherche en largeur est optimale, et expliquer le compromis qui rend l’approfondissement itératif rentable malgré son travail répété. Le module suivant ajoute une heuristique et demande quelle part de cet espace peut être sautée.