...
La logique propositionnelle comprend des inconnues booléens `x,y,z,...` et des connecteurs booléens. La valeur logique vrai est notée `1`, la valeur logique faux est notée `0`. Les connecteurs booléens les plus utilisés sont `"¬", "∧","∨","→","↔"` et correspondent à des opérations booléennes défini comme suit :
`"¬"1=0`
`0"∧"1=0`
`1"∧"0=0`
`1"∧"1=1`
`0"∨"1=1`
`1"∨"0=1`
`1"∨"1=1`
`0"→"1=1`
`1"→"0=0`
`1"→"1=1`
`0"↔"1=0`
`1"↔"0=0`
`1"↔"1=1`
S'il y a `n` inconnus booléens `x_1,x_2,x_3,..., x_n` alors il y a `2^n` modèles envisageables (`2^n` combinaisons).
Etant donnée deux propositions `alpha, beta` érites dans ce langage `"<""¬", "∧","∨","→","↔",0,1,x_1,x_2,...,x_n">"`, l'implication sémantique `alpha |== beta` signifie que tout modèle qui réalise `alpha` réalise `beta`. Tandis que l'implication syntaxique `alpha |-- beta` signifie qu'il existe une démonstration de `beta` utilisant `alpha` comme hypothèse. En logique propositionnelle, et avec les règles de déduction naturel, nous avons la propriété de complétude qui dit que tout ce qui est vrai est démontrable, ou en d'autre terme que pour toutes propositions `alpha`, `beta`, si `alpha |== beta` alors `alpha |-- beta`. La réciproque étant évidente, les deux symboles ont alors la même signification. On utilise le symbole `|==` pour évoquer les modèles (combinaisons), et on utilise le symbole `|-` pour évoquer les démonstrations.
On remarque les règle de substitutions autorisée où `x, y, z` représente n'importes quelles propositions :
Commutativité de `∧` Commutativité de `∨` Associativité de `∧` Associativité de `∨` Élimination de la double négation Contraposition Élimination de l’implication Élimination de l'équivalence De Morgan De Morgan Distributivité de `∧` sur `∨` Distributivité de `∨` sur `∧`
Etant donné une proposition `B` servant de base de connaissance. Etant donné une proposition `p`. Voici l'algorithme pour déterminer si `p` est vrai sachant que la base de connaissance `B` est vrai, c'est à dire pour savoir si `B|==p`. On regarde si `B"∧¬"p` est intrinsèquement faux, autrement dit, si c'est contradictoire, si c'est faux quelques soient les hypothèses.
On met la base de connaissance `B`, ainsi que la proposition `p`, sous forme normale conjonctive c'est à dire une conjonction de clauses disjonctives de littéraux. Une clauses disjonctives de littéraux est appellé simplement une clause. On regroupe les deux pour former la proposition `B"∧¬"p` que l'on remet sous forme normale conjonctive et sur laquelle on applique le traitement suivant :
La conjonction en cours de traitement correspond à un ensemble de clauses. Et chaque clause correspond à un ensemble de littéraux,
PL-RESOLUTION(B,p) :
.
On considère une base de connaisance mise sous forme d'une conjonction de clauses de littéraux, et une proposition mise sous forme d'une conjonction de littéraux.
L'algorithme détermine si la base de connaissance permet de savoir si la proposition est vrai ou fausse ou non déterminée.
---- 12 juin 2026 ----
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 vrai si l'état `e` est un but, et faux 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 graphes 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 :
Remarque : La complexité est la même que précédement car `O(1"+"b"+"b^2"+"b^3"+"..."+"b^d) = O(b^d)`
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. On complète le model-monde comme suit : Le graphe doit considérer la possibilité de parcourir ses arcs dans le sens inverse, et donc doit 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 chaque arc entrant sur le noeud à une actions inverses distinctes pour le noeud.
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`. |
`"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 selon le coût initial des états.
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 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`
On choisit comme fonction d'évaluation, l'estimation du coût :
`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(R(X,a))`
L'estimation doit être inférieure ou égale aux estimations fils dans lesquelles on a ajouter le coût de l'action. Supposons donc que `Y` soit un successeur de `X`, et que `C` soit le cout de l'arc passant de `X` à `Y`, autrement dit, `Y"="R(X,a)`, `C"="C(X,a)`. Alors nous devons avoir : `h(X)<=C+h(Y)` ou autrement dit :
`h(X)-h(Y)<=C`
Exemple : La distance à vole d'oiseaux est une heuristique consistante pour estimer la distance par la route.
`h` est une heuristique consistante `=>` `h` est une heuristique admissible
`f(X) = g(X)+h(X)`
`g(X)` : coût pour aller d'un état initial à l'état `X`.
`h(X)` : coût estimé pour aller de l'état `X` à un état but (`h(X)"="0` si `X` est un état but).
`f(X)` : coût estimé pour aller d'un état initial à un état but en passant par l'état `X`.
On note `h"*"(X)` le coût réel pour aller de l'état `X` à un état but. Une heuristique `h(X)` est dite admissible si elle ne surestime jamais le coût réel pour atteindre le but. `h(x)<=h"*"(X)`
Elle est dite consistante si elle obéït à l'inégalité triangulaire basé sur un arc avec son coût réel. `h(X)<=C(X,a)+h(R(X,a))`
Optimalité A* exploration arbre : oui si `h` est admissible.
Optimalité A* exploration graphe : oui si `h` est consistant.
Preuve par l'absurde. Considérons le but optimale `B` et un second but non-optimal `B_2`. Donc :
`g(B) < g(B_2)`
L'évaluation`f` dans une exploation A* est :
`f(X) = g(X)+h(X)`
Comme `B` et `B_2` sont des buts, `h(B)"="0` et `h(B_2)"="0`
`f(B)=g(B)+h(B)`
`f(B)=g(B)`
Si l'algorithme abouti à `B_2` alors à l'étape d'avant, il contient `B_2` dans la frontière. Puisqu'il y a d'autres états buts et que l'algorithme de parcours de l'arbre est complet, il y aura forcement aussi dans la frontière un état `A` se trouvant sur le chemin allant de la racine au but `B`. On note le coût réel pour aller d'un état `X` à un état but, `h"*"(X)`. Comme `A` est sur le chemin allant au but `B` :
`g(B)=g(A)+h"*"(A)`
`f(B)=g(A)+h"*"(A)`
D'autre part l'évaluation`f` appliquée à A donne :
`f(A) = g(A)+h(A)`
L'heuristique `h` étant admissible, `h(X) <= h"*"(X)` , donc
`f(A)<= f(B)`
Et l'algorithme choisira toujours cet autre état `A` plus-tôt que l'état `B_2`.
En conclusion l'exploration A* doit retourner une solution optimale. CQFD
Si l'heuristique consistance, démontrons d'abord que l'évaluation est monotone `f(X)<=f(R(X,a))` :
Supposons donc que `Y` soit un successeur de `X`, et que `C` soit le cout de l'arc passant de `X` à `Y`, autrement dit, `Y"="R(X,a)`, `C"="C(X,a)`.
L'heuristique `h` est consistante :
`h(X)<=C+h(Y)`
`g(X)+h(X) <= g(X) + C +h(Y)`
`f(X) <= g(Y) +h(Y)`
`f(X) <= f(Y)`
CQFD
Maintenant démontrons que chaque fois que l'algorithme A* choisit un noeud `X` à développer, le chemin optimal entre un noeud initial et le noeud `X` a été trouvé. Supposont que ce ne soit pas le cas. Alors il devrait exister un autre noeud `Y` dans la frontière appartenant à un chemin optimal entre un noeud initial et `X`.
Mais la fonction d'évaluation `f` est croissante ou égale le long de n'importe quel chemin, `f(Y)<=f(X)`. Donc `Y` aura été choisie avant `X`, d'où une contradiction. CQFD