L'algorithme prend en entrée un problème et retourne soit une solution sous forme d'une séquence d'actions à faire ou bien une notification d'échec. Le problème se définit formellement comme suit :
On va dans un premier temps modéliser le monde. Tous les états, toutes les actions, tous les arcs, sont mémorisés. Puis on développera des algorithmes agissant sur ce modèle-monde à l'aide d'un interface de commandes. Dans le modèle-monde les états sont appelés des noeuds.
On symétrise d'emblé le problème, en considérant un ensemble d'états de départ possibles et un ensemble d'états d'arrivé possibles. On considère donc que l'agent a un premier choix à faire, qui consite à choisir l'état initial parmi l'ensemble des états initiaux possibles.
La solution s'appelle un chemin, c'est une liste qui commence par le choix d'un état initial suivi par une succcesion d'actions (qui, si on les applique dans l'ordre doit nous mener à un état but).
Le modèle est déterministe, c'est à dire qu'une action autorisée appliquée à un noeud ne produit qu'un seul noeud résultat.
Nous explicitons la distinction entre les arcs et les actions. Le modèle étant déterministe, une action, selon son point de départ, correspond à un ensemble d'arcs, définissant une fonction de l'ensemble des noeuds du graphe sur lui-même.
L'arc partant du noeud, traduit l'exécution d'une action à partir de ce noeud. Il est donc naturel d'imposer en plus que deux arcs partant d'un même noeud correspondent nécessairement à deux actions distinctes.
Les arcs possèdent un attribut supplémentaire désignant l'action à la quelle elles appartienent. Et il existe un ensemble de toutes les actions enviseageables.
La fonction de coût dans le cas général ne dépend pas seulement de l'action mais aussi du noeud de départ. Car elle dépend seulement de l'arc.
On enrichie donc la définission du graphe précédent :
Liste des actions. Liste des actions applicables sur le noeud `e`. Le noeud obtenu en appliquant l'action `a` à partir du noeud `e`. Coût à partir du noeud `e` en faisant l'action `a`. Arc correspondant à l'action `a` à partir du noeud `e`. Action auquel appartient l'arc `p`. Coût de l'arc `p`.
On redéfinit :
`G ="Grafo"(N"="10,alpha"="3,p"="0.75,s"="1)`
Crée un nouveau graphe `G` de `N` noeuds, avec un nombre d'actions `alpha`, une probabilité qu'une action soit autorisée valant `p`, et une graine de hasard `s`
Crée un arc correspondant à l'action `a` partant du noeud `x` et allant sur le noeud `y`.
Lorsqu'on crée un graphe, on utilise les paramètres `N` et `alpha` et on construit un nouveau graphe ayant les caractéristiques suivantes :
Le nombre de nœuds est égal à `N`.
La liste des actions est la liste des entiers `1,2,3,...,alpha`.
La probabilité qu'une action soit autorisée vaut `p`.
Sur ce second prompt, ChatGPT reprogramme les troix classes.
On introduit un nouveau type de donnée appelé l'action et qui est représentée par un entier. Modifit les trois classes comme suit :
La classe `"Arco"` comprend deux attributs supplémentaires :
L'attribut `"accion"` qui est l'action correspondant à l'arc.
L'attribut `"costo"` qui est le coût de l'arc.La classe `"Nodo"` comprend trois méthodes supplémentaires :
La classe `"Grafo"` comprend un attribut supplémentaire :
La méthode `"A"("self")` retourne la liste des actions possibles applicables au noeud, obtenu en parcourant la liste des arcs partants du noeud et en accumulants leur action correspondante.
La méthode `"R"("self", a)` retourne le noeud obtenue en appliquant l'action `a` au noeud.
La méthode `"C"("self", a)` retourne le coût obtenue en appliquant l'action `a` au noeud.
Dans chaque noeuds, les arcs partant correpondent nécessairement à des actions différentes.
L'attribut `"accion"` qui contient la liste des actions uttilisées dans le graphe.
Lorsqu'on crée un graphe, on utilise les paramètres `N`, `alpha`, `p`, et on construit un nouveau graphe ayant les caractéristiques suivantes :
Le nombre de nœuds est égal à `N`.
La liste des actions est la liste des entiers de `1` à `alpha`.
La probabilité qu'une action soit autorisée vaut `p`.
Les noeuds sont appelés des états.
Le modèle monde étant en place, on définit ce qu'est un problème par le cintuplet de fonctions suivant `(S,"A","R",B,"C")` :
`"A"(e) = e".A"()` : Liste des actions possibles applicables sur l'état `e`.
`"R"(e,a) = e".R"(a)` : Etat résultat en appliquant l'action `a` à partir de l'état `e`.
`"C"(e,a) = e".C"(a)` : Coût de l'action `a` appliqué à l'état `e`.`S` : Ensemble des états initiaux possibles.
`B` : Ensemble des états buts possibles.
L'ensemble des états finaux peut aussi être définie par une fonction caractéristique `"B"(e)` qui retourne `1` si l'état `e` est un but et `0` sinon.
Si le coût est constant, le problème est défini par le quadruplet `(S,"A","R",B)`.
Un chemin est une suite commençant par un état initial et se poursuivant par une succesion d'actions.
L'environnement du problème est le modèle monde. L'algorithme de résolution n'utilise que les fonctions `(S,"A","R",B)` et aucune propre au modèle monde. Une solution sera un chemin dans le graphe partant d'un état initial pour aller sur un état but. La solution est dite optimale si la somme des coûts des arcs du chemin est minimale parmi toutes les solutions.
On pose 4 critère de performance des algorithmes d'exploration :
La complexité s'exprime en fonction des valeurs suivantes, et se calcul dans le pire des cas :
Et on considère des graphes ressemblant à des arbres, ce qui nous permet d'utiliser les mêmes paramètres pour exprimer les complexités en temps et en espace.
Le problème comprend :
Lorsque le nombre d'actions possibles pour un état est supposé fini, et davantage encore, lorsqu'il est supposé d'une grandeurr raisonnable telle que la boucle listant toutes ses actions reste une opération de complexité négligeable devant celle de l'algorithme dans son ensemble. La procédure est la suivante :
EXPLORER-ARBRE(`S,"A","R","B"`) :
Si il y a un état initial qui est un but alors retourner le chemin contenant cet état.
Initialiser la frontière avec la liste des états initiaux possibles.
Répéter indéfiniment :
Si la frontière est vide alors retourner échec.
Choisir un état dans la frontière, et le retirer de la frontière.
Pour chaque fils de cet état :
Si c'est un but alors retourner le chemin allant à ce fils.
Ajouter ce fils dans la frontière.
Notez que si on applique cet algorithme à un graphe, dès qu'il repasse sur un état déjà exploré, il boucle indéfiniment.
On mémorise l'ensemble des états déjà explorés pour éviter de les explorer plusieurs fois. On ajoute 3 instructions (notées en rouge) à l'algorithme d'exploration générale d'un arbre :
EXPLORER-GRAPHE(`S,"A","R","B"`) :
Si il y a un état initial qui est un but alors retourner le chemin contenant cet état.
Initialiser la frontière avec la liste des états initiaux.
Initialiser l'ensemble exploré à vide.
Répéter indéfiniment :
Si la frontière est vide alors retourner échec.
Choisir un état dans la frontière, et le retirer de la frontière.
Ajouter l'état à l'ensemble exploré.
Pour chaque fils de cet état :
Si c'est un but alors retourner le chemin allant à cet état
Si il n'est ni dans la frontière ni dans l'ensemble exploré alors ajouter cet état dans la frontière
Dés que l'on commence à explorer un état de la frontière, on le retire de la frontière pour le mettre dans l'ensemble exploré. La frontière est l'ensemble des états atteints mais non encore explorés. L'ensemble exploré est l'ensemble des états déjà explorés.
Sur ce troisième prompt, ChatGPT programme l'algorithme `"EXPLORER-GRAPHE"(S,"A","R","B")`, et il distingue bien le modèle monde, de l'algorithme qui n'utilise comme interface de commande que les seules fonctions `S,"A","R","B"` définies avec le problème.
On programme un algorithme adapté aux graphes. Les noeuds sont appelés des états.
On définit 2 fonctions `A,R` :
`A(e)=e".A"()` qui donne la liste des actions possibles applicables sur l'état `e`.
`R(e,a)=e".R"(a)` : qui donne l'état résultat en appliquant l'action `a` à partir de l'état `e`.Un état possède une liste d'actions possibles qui appliquée à l'état retourne une liste d'états résultats appelés états fils.
Un chemin est une liste commençant par un état et se poursuivant par des actions.
La frontière est l'ensemble des états à traiter.
L'ensemble exploré est l'ensemble des états déjà explorés.
La liste `S` contient les états initiaux.La liste `B` contient les états finaux..
L'algorithme `"EXPLORER-GRAPHE"(S,"A","R",B)` est décrit comme suit :
`"EXPLORER-GRAPHE"(S,"A","R",B)` :
Peut-tu programmer cet algorithme en utilisant seulement les fonctions `S,"A","R",B` et pas celle des classes `"Grafo"`, `"Nodo"`, `"Arco"` qui représentent le modèle monde ?
Si il existe un état initial qui est un état final alors retourner le chemin contenant cet état.
Initialiser la frontière avec la liste des états initiaux.
Initialiser l'ensemble exploré à vide.
Répéter indéfiniment :
Si la frontière est vide alors retourner échec.
Choisir un état dans la frontière, et le retirer de la frontière.
Ajouter l'état à l'ensemble exploré.
Pour chaque fils de cet état :
Si c'est un état final alors retourner le chemin allant à ce fils.
Si il n'est ni dans la frontière ni dans l'ensemble exploré alors ajouter cet état dans la frontière.
On utilise la frontière comme une file. ChatGPT le propose d'emblé :
" Voici une première version simple, en parcours en largeur, c’est-à-dire que la frontière est utilisée comme une file. "
Il convient donc de trouver les notations formelles les plus pratiques pour exprimer le retrait d'une donnée dans une file, et l'écriture d'une donnée dans une file.
Le parcours du graphe en largeur d'abord nous assure :
Il est alors possible d'établir des statistiques empiriques sur la connexité, et la longueur des chemins optimums, dans un graphe binaire au hasard, et de vérifier si cela correspond bien aux valeurs théorique.
Programme le calcul statistique (probabilité d'absence de chemin, moyenne des longueur de chemins, écart-type des longueurs de chemin) comme suit :
TEST(N, NS=100, na=2, p=1, n1=1, n2=1)
k0=0
k1=0
L=0
L2=0
Pour la graine i variant de 1 à 1+ NS :
G=Grafo(N,na,p,i)
S regroupe les n1 premiers noeuds dans G.nodo
B regroupe les n2 noeuds suivants dans G.nodo
Z=EXPLORER_GRAPHE(S,A,R,B)
si Z==None alors k0=k0+1
sinon
k1=k1+1
L = L + len(Z) - 1
L2=L2 + (len(Z) - 1)**2
Si k1==0 alors retourne [1,None,None]
Si k1==1 alors retourne [k0/(k0+k1),L/k1,None]
Retourne [k0/(k0+k1), L/k1, math.sqrt(L2/(k1-1) - (L/k1)**2)]
Faite le calcul sur 10 000 000 graphe binaires au hasard. Puis demander à CHatGPT de faire un shéma récapitulant les résultats :
On utilise la frontière comme une pile.
Il convient donc de trouver les notations formelles les plus pratiques pour exprimer le retrait d'une donnée dans une pile, et l'écriture d'une donnée dans une pile.
On se limite aux chemins de longueur `l`. On ajoute le paramètre d'entrée `l` et on ne dépasse pas la taille des chemin au delà de `l`.
Le parcours du graphe en profondeur limitée nous assure :
On explore en profondeur d'abord de façon limité à `l` puis on incrémente `l` et on recommence.
Le parcours du graphe en profondeur itérative d'abord nous assure :
La recherche bidirectionnelle part à la fois, de l’état initial vers le but, et du but vers l’état initial. L’idée est que deux recherches de profondeur `d"/"2` coûtent beaucoup moins cher qu’une seule recherche de profondeur `d`.
Mais cela nécessite d'avoir un jeu d'actions inverses. Le graphe doit considérer la possibilité de parcourir ses arcs dans le sens inverse, et construire un jeu d'actions inverse. On ajoute à la classe des arcs un nouvel attribut désignant l'action inverse correspondante, et pour chaque noeud on attribut les arcs entrants sur le noeud à des actions inverses à chaque fois toutes distinctes.
Une fois le modèle monde mis en place, on définit ce qu'est un problème d'exploration bidirectionnelle par le cintuplet de fonctions suivant `(S,"A","R","inv","A_","R_",B)` :
`"A_"(e)` |
L'ensemble des actions inverses possibles applicables à l'état `e`. |
`"R_"(e,a)` |
L'état obtenu en appliquant l'action inverse `a` à partir de l'état `e`. Le résultat ne comprend qu'un seul état car l'environnement est déterministe. |
`"inv"(e,a)` |
Retourne l'action inverse correspondant à l'arc sortant de `e` et d'action `a`. |
Le parcours du graphe nous assure :
Le coût d'un état `X` est le coût du chemin le moins couteux partant d'un état initial pour aller sur `X`. On note `g(X)`, le coût pour atteindre le noeud `X`
La frontière est une file ordonnée selon le coût
EXPLORER-COÜT-UNIFORME-(`S,"A","R","B","C"`) :
Initialiser la frontière avec la liste des états initiaux, en une file ordonnée selpon le coût de l'état.
Initialiser l'ensemble exploré à vide.
Répéter indéfiniment :
Si la frontière est vide alors retourner échec.
Choisir un état dans la frontière avec le coût le plus faible, et le retirer de la frontière.
Si c'est un but alors retourner le chemin allant à cet état
Ajouter l'état à l'ensemble exploré.
Pour chaque fils de cet état :
Calculer son coût
Si il n'est ni dans la frontière ni dans l'ensemble exploré alors ajouter cet état dans la frontière
Si il est dans la frontière avec un coût plus élevé, alors remplacé son coût par l'autre coût plus plus faible.
`C"*"` : Coût du chemin optimal vers un noeud but.
`epsilon` : Coût minimum de chaque action.
Complétude : oui.
Optimalité : oui.
Compléxité en temps : `O(b^(1+"floor"((C"*")/epsilon)))`
Compléxité en espace : idem
Nous avons une fonction d'évaluation `f`. Pour chaque état `X`, l'évaluation `f(X)` indique un niveau de désintérêt.
La recherche par le meilleur d'abord passe d'abord par les états d'évaluation les plus faibles.
La frontière est une file ordonnée selon cet évaluation.
`h(X)=` coût estimé du chemin le moins couteux partant de `X` pour aller sur un état but.
`h(X)>=0` et si `X` est un but alors `h(X)=0`
`f(X)=h(X)`
Complétude : non (sauf si nombre de noeux fini).
Optimalité : non.
Compléxité en temps : `O(b^m)`
Compléxité en espace : idem
L'heuristique `h` est admissible si elle ne surestime jamais le coût pour atteindre le but. La valeur `h(X)` ne doit jamais être supérieur au coût réel du meilleur chemin partant de `X` pour allez sur un état but.
L'heuristique `h` est consistante si quelques soient un état `X` et une action autorisée `a` nous avons l'inégalité suivante :
`h(X)<=C(X,a)+h(X')`
`X'=R(X,a)`
Autrement dit `h(X)-h(X') <= C(X,a)`. C'est l'inégalité triangulaire d'une distance, où l'on interprète l'heuristique `h(X)` comme étant la distance de `X` à un état but, et `h(X')` comme étant la distance de `X` au même état but.
`h` est une heuristique consistante `=>` `h` est une heuristique admissible
`f(X) = g(X)+h(X)`
Optimalité A* exploration arbre : oui si `h` est admissible
Optimalité A* exploration graphe : oui si `h` est consistant