De l'importance des énoncés

Pour résoudre un problème posé informellement en langage naturel, on procède en deux étapes :

1. choix d'une représentation et spécification formelle de l'énoncé ;
2. résolution par la machine de l'énoncé formalisé et construction de la solution.

La première étape est très importante : bien posé, le problème est parfois déjà résolu (exemples de l'échiquier écorné et de l'échange de cavaliers).

On distingue souvent trois types d'énoncés.

1. Énoncés de type combinatoire. Ils sont constitués d'un ensemble de solutions potentielles (X) et un ensemble de contraintes (K) et il faut trouver une solution respectant les contraintes. Il s'agit par exemple du problème des huit reines, d'une addition du type SEND+MORE=MONEY ou encore d'une grille de sudoku.
2. Énoncés de type états / opérateurs de changement d'état. Un tel énoncé contient un état initial, des états finaux à atteindre ou leurs caractérisation et des opérateurs <conditions, effets>. Il s'agit alors de découvrir un enchaînement d'opérateurs permettant de passer de l'état initial à un état final. Le jeu de taquin appartient à cette catégorie.
3. Énoncés de type buts / opérateurs de décomposition. On fournit un problème à résoudre (un but), une liste de problèmes que l'on sait résoudre (problèmes primitifs) et des opérateurs de décomposition de problèmes en sous-problèmes. Àpartir de là, il faut trouver une décomposition du problème initial en problèmes primitifs. On pensera par exemple à l'analyse grammaticale d'une phrase.

La suite ne concerne que les énoncés de type 2 : états et opérateurs.

Définitions et exemple du jeu de taquin

États et opérateurs

Il faut viser à systématiquement avoir un nombre minimal d'états et d'opérateurs, cela simplifiera la recherche à suivre.

Ainsi, dans le cas du jeu de taquin, on préférera quatre opérateurs indiquant les déplacements possibles de la case vide, plutôt que d'imaginer des opérateurs dédiés à chaque chiffre. Finalement, l'énoncé du problème serait le suivant.

Graphes sous-jacents

On peut développer un graphe d'états : à partir de l'état initial, on applique tous les opérateurs dont les conditions d'application sont vérifiées et on recommence sur les états obtenus. De plus, les arcs sont étiquetés par le nom de l'opérateur appliqué. On appelle ce graphe, le graphe sous-jacent au problème, ou le graphe de résolution.

Si l'on refuse de passer plusieurs fois par un même état, ce graphe est alors un DAG (graphe acyclique orienté) dont la racine) est l'état initial et les feuilles sont des états finaux ou des impasses.

Résoudre le problème revient à chercher un chemin dans ce graphe menant de l'état initial à un état final.

Ce graphe est en général trop gros pour être développé complètement en mémoire (même dans le cas du jeu de taquin qui autorisent plusieurs centaines de milliers d'états !). Il va falloir mettre en place des stratégies ou des heuristiques pour décider des parties les plus intéressantes du graphe.

La partie du graphe de résolution qui est explorée lors de la recherche est nommé le graphe de recherche.

Propriétés d'une recherche

• Terminaison : si une solution existe, la recherche s'arrête en fournissant une solution.
• Admissibilité : la recherche fournit systématiquement la meilleure solution.
• Complexité : la coût de la recherche, en particulier la taille du graphe de recherche par rapport au graphe de résolution.

Recherche non informée

Algorithme avec retour arrière

Dans ce cas, il y a à chaque instant un seul chemin explicite en mémoire.

Algorithme Recherche_RA (e)
{ Recherche à partir d'un état e }
Début
  Si (est_final(e)) Alors retourner(chemin=vide)
  Sinon opérateurs = OpérateursApplicables(e)
    (*) Si (opérateurs=vide) Alors retourner(échec)
        Sinon op         = premier(opérateurs)
              opérateurs = reste(opérateurs)
              chemin     = Recherche_RA(op(e))
              Si (chemin=échec)
              Alors aller au point de retour (*)
              Sinon retour (op,chemin)
              Fin si
        Fin si
  Fin si
Fin

À noter l'importance de l'ordre dans lequel la fonction OpérateursApplicables fournit les opérateurs.

Propriété : la recherche avec retour arrière n'est pas admissible.

Algorithme avec graphe

Algorithme Recherche_G
Début
  ouverts = { état initial }
  fermés  = vide
  succès  = faux
  Tant que (ouverts non vide) et (non succès) faire
    n = noeud_choisi(ouverts)
    Si est_final(n) Alors succès=vrai
    Sinon ouverts = ouverts privé de n
          fermés  = fermés + n
          Pour chaque successeurs s de n faire 
            Si (s n'est ni dans ouverts ni dans fermés)
            Alors
              ouverts = ouverts + s
              père(s) = n
            Fin si
          Fin pour
    Fin si
  Fin TQ
Fin

Points importants :

• La fonction noeud_choisi décide de la stratégie :
  • profondeur d'abord si noeud_choisi=dernier, dans ce cas, ouverts est une pile, on parle de LIFO (Last In First Out) ; dans ce cas, la recherche est comparable à celle effectuée par la méthode avec retour arrière ;
  • largeur d'abord si noeud_choisi=premier, dans ce cas, ouverts est une file, on parle de FIFO (First In First Out) ; avec ce choix, la méthode est admissible.
• le test est_final est appliqué lorsque le nœud est extrait de ouverts, pas avant ;
• la fonction père nous fournit au final le chemin solution.

Recherche informée : l'algorithme A*

En général, les méthodes décrites précédemment sont irréalistes, elles consomment trop de mémoire ou trop de temps. Une solution est d'ajouter de l'information heuristique pour orienter la recherche.

On se donne une fonction f capable d'évaluer un nœud et définie comme suit :

avec

• g(n) le coût du meilleur chemin connu pour atteindre n depuis l'état initial ;
• h(n) l'estimation du coût du chemin entre n et un état final ;
• f(n) est donc une estimation du coût du meilleur chemin solution passant par n.

On note f*, g* et h* les coûts optimaux.

Insistons sur le fait que h(n) garde la même valeur alors que g(n) varie en cours de recherche. On a cependant toujours g(n) supérieure ou égale à g*(n).

Algorithme A-étoile
Début
  ouverts = { état initial }
  fermés  = vide
  succès  = faux
  Tant que (ouverts non vide) et (non succès) faire
    choisir n dans les ouverts tel que f(n) est minimum
    Si est_final(n) Alors succès=vrai
    Sinon ouverts = ouverts privé de n
          fermés  = fermés + n
          Pour chaque successeurs s de n faire 
            Si (s n'est ni dans ouverts ni dans fermés)
            Alors
              ouverts = ouverts + s
              père(s) = n
              g(s) = g(n) + coût(n,s)
            Sinon
              Si (g(s) > g(n) + coût(n,s)) Alors
                père(s) = n
                g(s) = g(n) + coût(n,s)
                Si (s se trouve dans fermés) Alors
                  fermés  = fermés  - s
                  ouverts = ouverts + s
                Fin si
              Fin si
            Fin si
          Fin pour
    Fin si
  Fin TQ
Fin

Cas particuliers :

• si h=0, alors f(n)=g(n) et l'algorithme se comporte comme une largeur d'abord ;
• si f(n) = h(n), l'algorithme ressemble à une profondeur d'abord, on parle de gradient ;

Propriétés de h et de l'algorithme A*

• h est dite minorante si pour tout nœud n, on a h(n) inférieure ou égale à h*(n) ;
• h est dite monotone si pour tout nœud n, et pour tout ses successeurs s, on a h(n)-h(s) inférieure ou égale à coût(n,s) ;
• si h est minorante alors l'algorithme A* est admissible ;
• si h est monotone alors on est dispensé des mises à jour dans l'algorithme, on est sûr que la première rencontre d'un nœud fournit le meilleur chemin pour y arriver.

Même si l'algorithme A* ne développe pas systématiquement l'arbre de résolution, le nombre de nœuds ouverts peut devenir prohibitif. Une solution est de ne garder dans les ouverts que les k meilleurs nœuds. On parle alors de beam search.