Intelligence artificielle — TD

Système expert
R3
BC (Base de Connaissance) + BR (Base de Règle)
Chaînage arrière : But F
Chaînage avant : Saturation (+ But) R7 A
Exercice p.3 — Chaînage avant A
R1 A →E R1
R2 B →D
E E
R3 H →A∧F
R4 E∧G →C R4 R5
R5 E∧K →B
E B
R6 D∧E∧K →C
R7 G∧K∧F →A R2
Ordre des règles : R3 - R7 - R1 - R4, R5 - R2 - R6 D
Faits non déductibles : H, G, K R6
Base de faits initiale : H, K But : C

Nb Inférence BF BR Explication
0 HK toute la base
1 HKAF BR — { R3 } H→A∧F
2 HKAFE BR — { R3, R1 } A→E
3 HKAFEB BR — { R3, R1, R5 } E∧K→B
4 HKAFEBD BR — { R3, R1, R5, R2 } B→D
5 HKAFEBDC BR — { R3, R1, R5, R2, R6 } D ∧ E ∧ K →C

Exercice p.8 — Chaînage arrière

R1 fleur ∧ graine → phanérogame ∧ ¬ cryptogame
R2 phanérogame ∧ graine nue → sapin
R3 phanérogame ∧ 1-cotylédone → monocotylédone
R4 phanérogame ∧ 2-cotylédone → dicotylédone
R5 monocotylédone ∧ rhizome → muguet
R6 dicotylédone → anémone
R7 monocotylédone ∧ ¬ rhizome → lilas
R8 feuille ∧ ¬ fleur → cryptogame
R9 cryptogame ∧ ¬ racine → mousse
R10 cryptogame ∧ racine → fougère
R11 ¬ feuille ∧ plante → thallophyte
R12 thallophyte ∧ chlorophylle → algue
R13 thallophyte ∧ ¬ chlorophylle → champignon
R14 ¬ feuille ∧ ¬ fleur ∧ ¬ plante → colibacille

M1 Info 2005 / 2006 — Université d’Angers — Intelligence artificielle — TD 1

Faits non déductibles :
fleur, graine, graine nue, 1-cotylédone, 2-cotylédone, feuille, racine, plante, chlorophylle

Base de faits initiale :

rhizome, fleur, 1-cotylédone

but = muguet
R5
VERIF(monocot., rhizome)

ET DEMO(rhizome)
DEMO(monocot.)
! BF
R3
VERIF(phanéro., 1-cotyl.)

ET
DEMO(phanéro.) DEMO(1-cotyl.)
! BF
R1
VERIF(fleur, graine)

ET
DEMO(fleur) DEMO(graine)
! BF expert: graine ? oui

phanérogame
d'où muguet = VERIF

Exercice 1 — TD numéro 1
a) Chaînage avant
R1 SI Responsabilité ET Langue-facile ET Néerlandais-parlé ALORS Dynamique
R2 SI Langue-facile ET Anglais-parlé ALORS Adaptabilité
R3 SI Slave ET Dynamique ALORS Adaptabilité
R4 SI Responsabilité ALORS Leadership
R5 SI Langue-facile ALORS Néerlandais-parlé
R6 SI Adaptabilité ET Leadership ALORS Accepté
R7 SI Slave ALORS Langue-facile
R8 SI Leadership ET Slave ALORS Adaptabilité

Faits non déductibles : Slave, Responsabilité

Base de faits initiale : Slave, Responsabilité

Chaînage avant en largeur

On déclenche toutes les règles possibles à chaque étape : on enrichit la BF au maximum.

Chaînage avant en profondeur

M1 Info 2005 / 2006 — Université d’Angers — Intelligence artificielle — TD 2

1. ( BF ) Slave, Responsabilité Propriétés de niveau 0
( R4, R7 ) Leadership, Langue-facile Propriétés de niveau 1
( R5, R8 ) Néerlandais-parlé, Adaptabilité Propriétés de niveau 2
( R1, R6 ) Dynamique, Accepté Propriétés de niveau 3

2. ( BF ) Slave, Responsabilité Propriétés de niveau 0

( R4 ) Leadership Propriétés de niveau 1
( R7 ) Langue-facile Propriétés de niveau 2
( R5 ) Néerlandais-parlé Propriétés de niveau 3
( R1 ) Dynamique Propriétés de niveau 4
( R3 ) Adaptabilité Propriétés de niveau 5
( R6 ) Accepté Propriétés de niveau 6

Accepté

Leadership
Adaptabilité

R3 R4
R2 Responsabilité
R8
Langue-facile Slave Dynamique
R7 Anglais-parlé R1

Slave Slave Resp. Langue-facile Néerlandais

Leadership
R7 R5
R4
Slave Langue-facile
Responsabilité
R7

Langue-facile

Exercice 2
Choosen beverage : ?

Château Earl of Bartonville Red

B2

expensive wine Steak

ECHEC

M1 Info 2005 / 2006 — Université d’Angers — Intelligence artificielle — TD 3

 Bond's Champagne
Honest Henry's Apple Wine OK

B1 B2
expensive wine New Year's Eve Chicken
cheap wine
BF
B10
wine

B9 sophisticated
wine impressed BF
ECHEC

TLR DE OK
Water OK

B4 B5
True
unknown bear Mexican
cheap wine
Echec BF
B10
B12
wine
Mexican
sophisticated BF
BF

COORS OK GLOP Carrot juice

B6 B7

bear Health nut

Echec
B12 B8
Mexican no carrot health nut
BF Echec Echec

M1 Info 2005 / 2006 — Université d’Angers — Intelligence artificielle — TD 4

Exercice 3
S1 S2
Table(A) Table(A)
Sur(B,A) Libre(A)
Libre(B) Table(C)
Table(C) Sur(B,C)
Sur(P,C) Libre(B)
Libre(P) Table(P)
Libre(P)

Constante(T)
Table(A) Sur(A,T)

Depiler (X, Y)
Condition Sur(X,Y)
Libre(X)
Ajout Table(X)
Libre(Y)
Retrait Sur(X,Y)

Empiler(X,Y)
Condition Table(X)
Libre(Y)
Libre(X)
Y <> P
X <> Y
Ajout Sur(X,Y)
Retrait Table(X)
Libre(Y)

Déplacer(X,Y,Z)
Condition Sur(X,Y)
Libre(X)
Libre(Z)
Z <> P
Z <> Y
Ajout Sur(X,Z)
Libre(Y)
Retrait Sur(X,Y)
Libre(Z)

SI ( Sur(X,Y), Libre(X) )
ALORS Appliquer( Dépiler(X,Y) )
Ajouter( Table(X), Libre(Y) )
Retirer( Sur(X,Y) )

M1 Info 2005 / 2006 — Université d’Angers — Intelligence artificielle — TD 5

 B
P

A C

Dépiler (P,C)
B

A C Attention aux risques

P de bouclage

B Empiler (P,C)
P

A C

B P

Dépiler(B,A) A C
Déplacer(P,C,B)

P B Dépiler(P,C) B

A C B A C A C
P

Déplacer(B,A,C)

P A B …
C B A C P
Empiler(B,A)
Dépiler(P,C)
Déplacer(P,A)
Déplacer(P,B)
P P
A C B A C B A P C B

Critère
• Compter le nombre de bloc bien placés sur la table
• Compter les faits identiques entre les deux situations

M1 Info 2005 / 2006 — Université d’Angers — Intelligence artificielle — TD 6

Détection d’incohérences dans une BR avec COVADIS
Remarque
Ne s’applique qu’à des BR monotones

Définition — cohérence globale d’une BR

Une base de règles est cohérente si et seulement si pour toute base de faits susceptibles
d’être fournie, l’ensemble des faits obtenus par saturation satisfaitles spécifications de cohé-
rence.

Contraintes de cohérences
• Monovaluation des attributs
Att = Val∈BF et vak ≠ val’ Att = val’ BF

• Ensemble de règles d’incohérence

eg. Père(X,Y) , féminin(X) INC

• Contraintes fonctionnelles
eg. Nb_pique + Nb_coeur + Nb_carreau + Nb_trefle = 13

Contexte d’un littéral

Le contexte d’un littéral déductible est l’ensemble des faits initiaux permettant de le déduire.

Calculer les contextes de tous les littéraux déductibles

(le calcul se fait niveau par niveau, en partant du niveau 0, faits initiaux)

Exemple
R1 : père(X,Y), mère(Y,Z) -> grand_père(X,Z)
R2 : père(X,Y), père(Y,Z) -> grand_père(X,Z)
R3 : mère(X,Y), mère(Y,Z) -> grand_mère(X,Z)
R4 : mère(X,Y), père(Y,Z) -> grand_mère(X,Z)
R5 : père(U,X), grand_père(X,Z) -> bisaïeul(U,Z)
R6 : mère(U,X), grand_mère(X,Z) -> bisaïeul(U,Z)

Initiaux père, mère

Déductibles grand_père(L1), grand_mère(L2), bisaïeul(L3)

Spécification des cohérences

c1 : père(X,Y), féminin(X) -> INC
c2 : grand_père(X,Y), féminin(X) -> INC
c3 : bisaïeul(X,Y), féminin(X) -> INC

CTXT(L1) = (père(X,Y)∧mère(Y,Z))∨(père(X,Y)∧père(Y,Z))

c2 : grand_père(X,Y), féminin(X) -> INC

(père(X,Y)∧mère(Y,Z))∨(père(X,Y)∧père(Y,Z))∧féminin(X) -> INC

M1 Info 2005 / 2006 — Université d’Angers — Intelligence artificielle — TD 7

c1 : père(X,Y)∧féminin(X) -> INC

c3 : bisaïeul(X,Y)∧féminin(X) -> INC

CTXT(L3) = (père(U,X)∧grand_père(X,Z))∨(mère(U,X)∧grand_mère(X,Z))

CTXT(L2) = (mère(X,Y)∧mère(Y,Z))∨(mère(X,Y)∧père(Y,Z))

CTXT(L3) =
père(U,X)∧père(X,Y)∧mère(Y,Z)) ∨
père(U,X)∧père(X,Y)∧père(Y,Z)) ∨
mère(U,X)∧père(X,Y)∧mère(Y,Z)) ∨
mère(U,X)∧père(X,Y)∧père(Y,Z))

c3.1 : père(U,X)∧père(X,Y)∧mère(Y,Z)∧féminin(U) -> INC

c3.2 : père(U,X)∧père(X,Y)∧père(Y,Z)∧féminin(U) -> INC
c3.3 : mère(U,X)∧père(X,Y)∧mère(Y,Z)∧féminin(U) -> INC
c3.4 : mère(U,X)∧père(X,Y)∧père(Y,Z)∧féminin(U) -> INC

-> incohérence dans la Base de Règles

M1 Info 2005 / 2006 — Université d’Angers — Intelligence artificielle — TD 8

Exercice
R1 : Si nbpoints ≥ 24 alors zone = manche

R2 : Si nbcarte ≥ 8 alors fité = vrai

R3 : Si fité = vrai, zone = manche alors envisagé = manche_à_la_couleur

R4 : Si couleur = pour_sûr, zone = manche alors envisagé = sans_atout

R5 : si nbpoints ≥ 30, fité = vrai alors zone = chaleur

[ 24 ≤ nbpoints et nbpoint < 30 ] zone = manche

R4 : si couleur = peu_sûr et nbpoints ≥ 24 et nbpoints < 30 alors envisagé = sans_aout

INC [ nbcarte ≥ 8 et nbpoints ≥ 24 et nbpoints < 30 et couleur = peu_sûr ]

R1’ : Si 24 ≤ nbpoints < 30 alors zone = manche

Raisonnement non monotone

Rappel : Logique des défauts

A:B
⇔ Si A alors C sauf si non B
C

∆=<W,D>

Γ∆(E) : le plus petit ensemble de formules du langage

- contenant W
- déductivements clos
- tel que pour tous les défauts A : B1…Bn ∈D
C
pour lesquels A∈Γ(E) et i∈[1…n], ¬Bi E, on a C∈Γ(E)
E est un extension de L si et seulement si E = Γ(E)

Les faits
En général les êtres vivants ne volent pas
En général les oiseaux volent, à moins qu’ils ne soient trop jeunes ou qu’ils aient une aile
cassée
Les pingouins et les autruches sont des oiseaux qui ne volent pas
Les autruches des bandes dessinées volent
Cuicui est un oiseau
Lulu est un pingouin ou une autruche
Lili est une autruche de bande dessinée
Paul est un homme
Les hommes sont des êtres vivants
Les oiseaux sont des êtres vivants

M1 Info 2005 / 2006 — Université d’Angers — Intelligence artificielle — TD 9

D={
être_vivant(X) : ¬ oiseau(X)
¬ vole(X)
oiseau(X) : ¬ trop_jeune(X) ∧ ¬ aile_cassée(X) ∧ ¬pingouin(X)
vole(X)
autruche(X) : ¬ BD(X)
¬ vole(X)
}

W={
oiseau(Cuicui),
pingouin(Lulu) ⊕ autruche(Lulu),
autruche(Lili), BD(Lili),
homme(Paul),
homme(X) -> être_vivant(X),
oiseau(X) -> être_vivant(X),
autruche(X) -> oiseau(X),
pingouin(X) -> oiseau(X),
}

E={
oiseau(Cuicui), pingouin (Lulu) ⊕ autruche(Lulu),
autruche(Lili), BD(Lili), homme(Paul), être_vivant(Cuicui), oiseau(Lulu),
oiseau(Lili), ¬ vole(Lulu), ¬ vole(Paul), vole(Cuicui), vole(Lili)
}

Exercice particulier
∆ = < W, D >
W={A}
⎧ A : ¬B ⎫
D=⎨ ⎬
⎩ B ⎭
E ? On ne peux pas calculer E. Cette théorie n’admet pas d’extension.

Dempster Shaffer
Rappel
E : sous-ensemble de propositions
m : E -> [0…1]
(i) m(Ø) = 0
(ii) ∑ m(A) = 1, A E

1. µ(Ø) = 0
∑ m(S) * m(T )
A ≠ Ø, µ(A) = S∩T = A

1− ∑ m(S) * m(T )
S∩T =Ø

M1 Info 2005 / 2006 — Université d’Angers — Intelligence artificielle — TD 10

 pl(Ø) = 0
∑ m (A) * m (B) 1 2
A ≠ Ø, pl(S) = A∩B=S

1− ∑ m (A) * m (B) 1 2
A∩B=Ø

n
E1 : A1 …An ∑ m (A ) = 1
1 i
i=1
m
E2 : B1 …Bm ∑ m (B ) = 1
2 j
j=1
m

∑ m (A ) *m (B )
1 1 2 j
j=1
m
m1(A1 ) ∑ m2 (B j ) = m1(A1 )
j=1
  
1

m1(A1 ) ∑ m2 (B j ) = m1(A1 )(1− ∑ m2 (B j ))

A1∩B j ≠Ø A1∩B j =Ø

n n

∑ m1(Ai ) ∑ m2 (B j ) = ∑ m (A )(1− ∑
1 i
m2 (B j ))
i=1 A1∩B j ≠Ø i=1 A1∩B j =Ø

n n n

∑ m1(Ai ) − ∑ m1(Ai ) ∑ m2 (B j ) = 1− ∑ m1(Ai )(1− ∑ m2 (B j )) = 1− ∑ m1(Ai )m2 (B j ))

i=1 i=1 A1∩B j =Ø i=1 A1∩B j =Ø A1∩B j =Ø

∑ m (A ) ∑ 1 i
m2 (B j )
A1∩B j ≠Ø
∑
i=1
= 1= S= A1∩B j ≠Ø
pl(S)
1− ∑ m1(Ai )m2 (B j ))
A1∩B j =Ø

2.
mA({ pierre, paul }) = 0,5
m ({ paul,marie}) = 0,2
A

m ({ pierre, paul,marie}) = 0,3

A

m ({ pierre}) = 0,6
B

m ({ pierre, paul,marie}) = 0,4

B

∑ m (A) * m (B) A B
pl AB (S) = S= A∩B≠∅

1− ∑ m (A) * m (B) A B
S= A∩B=∅

M1 Info 2005 / 2006 — Université d’Angers — Intelligence artificielle — TD 11

 pl AB ({ pierre}) = 0,6 1−
* 0,5 + 0,6 * 0,3 48
0,6 * 0,2
=
88

pl AB ({ paul,marie}) = 0,2 * 0,4

1− 0,12 88
=
8

pl AB ({ pierre, paul,marie}) = 0,30,88

* 0,4 12
=
88

pl AB ({ pierre, paul }) = 0,50,88

* 0,4 20
=
88

mC({ paul,marie}) = 0,5

m ({ pierre, paul,marie}) = 0,5
C

48
* 0,5
pl ABC ({ pierre}) = 88 =
48 64
24

1− 0,5 *
88

pl ABC ({ paul }) = 10
64

pl ABC ({ pierre, paul }) = 10

64

pl ABC ({ paul,marie}) = 14
64

pl ABC ({ pierre, paul,marie}) = 646

On a d’abord calculer plAB puis plABC , on trouve les mêmes sous-ensembles, donc la con-
frontation est associative.

Cas pathologique

({
⎧m pierre = 0,99})
⎪ A ⎧ pl ({ pierre}) = 0
⎪
({ })
⎪⎪mA paul = 0,01
⎪ AB
⎨
⎪
⇒ ⎨ pl AB ({marie}) = 0
({ })
⎪mB marie = 0,99 ⎪
⎪ ⎪ pl ({ paul }) = 1
({
⎪m paul = 0,01
⎪⎩ B }) ⎩ AB

M1 Info 2005 / 2006 — Université d’Angers — Intelligence artificielle — TD 12

3. Grand et grand 0,6 * 0,2 = 0,12 Pierre, Paul
Grand et lunettes 0,6 * 0,7 = 0,42 Pierre
Grand et Ø 0,6 * 0,1 = 0,06 Pierre, Paul
Blond et grand 0,3 * 0,2 = 0,18 Paul
Blond et lunettes 0,3 * 0,7 = 0,21 Ø
Blond et Ø 0,3 * 0,1 = 0,03 Paul
Ø et grand 0,1 * 0,2 = 0,02 Pierre, Paul
Ø et lunettes 0,1 * 0,7 = 0,07 Pierre
Ø et Ø 0,1 * 0,1 = 0,01 Pierre, Paul, Jacques

pl ({ pierre}) = 0,42 + 0,07 49

1− 0,21
=
79
 0,62

pl ({ paul }) = 0,06 + 0,03 9

1− 0,21
=
79

pl ({ pierre, paul }) = 0,12 +1−0,06 + 0,02 20

0,21
=
79

pl ({ pierre, paul, jacques}) = 1−0,01 =

1
0,21 79

Mycin
Rappels
• Règle + affectée d’un coefficient p :
(
MBnouveau = MBancien + p 1− MBancien )
MDnouveau = MDancien

• Règle – affectée d’un coefficient p :

MBnouveau = MBancien

(
MDnouveau = MDancien + p 1− MDancien )

M1 Info 2005 / 2006 — Université d’Angers — Intelligence artificielle — TD 13

Si un même fait est la conclusion de n règles, la valeur finale de son CF (Certainty Factor)
est-elle indépendante de l’ordre d’application des règles ?

Soient 2 règles renforçant le MB avec des coefficients p et p’

CF = MBnouveau − MDnouveau

avec

(
MBint ermediaire = MBancien + p 1− MBancien ) MDint ermediaire = MDancien

(
MBnouveau = MBint ermediaire + p' 1− MBint ermediaire ) MDnouveau = MDint ermediaire

( ) (
MBnouveau = MBancien + p 1− MBancien + p' 1− MBancien − p 1− MBancien ( ))
(
MBnouveau = MBancien + 1− MBancien p + p'− pp' )( ) MDnouveau = MDancien

Concordances de témoignages
1. E a eu lieu E n’a pas eu lieu

p(B dit E) ?

A dit E(p) et B dit E(p’)

A dit ¬E(1 - p) et B dit E(1 - p’)

pp’ + (1 - p)(1 - p’)

2.
(
p E ∧ A dit E ∧ B dit E )= pE * p * p'
(
p E / A dit E ∧ B dit E = )
(
p A dit E ∧ B dit E ) (
p A dit E ∧ B dit E )
pE * p * p'
=
( ) (
p E ∧ A dit E ∧ B dit E + p ¬E ∧ A dit E ∧ B dit E )
pE * p * p'
=
( )(
pE * p * p'+ 1− pE 1− p 1− p' )( )

M1 Info 2005 / 2006 — Université d’Angers — Intelligence artificielle — TD 14

Algorithme A*
Résolution de problème par exploration d’un espace de recherche

Exemple : Recherche de chemin dans un graphe

2 8 3 1 2 3

1 6 4 8 _ 4

7 _ 5 7 6 5

état initial But

Formalisation d’un problème

Définir ce qu’est un état et sa représentation

Problème
• Etat initial
• Ensemble d’opérateurs
• Fonction Test-But
• Fonction de coût

L’espace de recherche est représenté par un graphe d’états que l’on représentera par un arbre

Exemple : Taquin
1. Préciser la représentation du problème
2. Proposer une fonction qui évaluera la distance entre un état courant et le but
3. Développer une recherche par escalade pour ce problème

Etat
Position des 8 chiffres et de la case blanche

Opérateurs
Déplacer la case blanche :
• vers le haut
• vers le bas
• vers la droite
• vers la gauche

Fonction test-but
Comparer les positions des chiffres et de la case blanche dans un état avec les positions sou-
haitées

Fonction de coût
Coût de 1 à chaque opération

Evaluation de la distance entre un état et le but

M1 Info 2005 / 2006 — Université d’Angers — Intelligence artificielle — TD 15

 2 8 3

1 6 4 w1 = 5

7 _ 5

H D G

2 8 3 2 8 3 2 8 3

1 _ 4 w2 = 4 1 6 4 w2 = 6 1 6 4 w2 = 6
7 6 5 7 5 _ _ 7 5

H D G

2 _ 3 2 8 3 2 8 3

1 8 4 w3 = 4 1 4 _ w3 = 5 _ 1 4 w3 = 4

7 6 5 7 6 5 7 6 5

D G H B

2 3 _ _ 2 3 _ 8 3 2 8 3

1 8 4 1 8 4 2 1 4 7 1 4
w4 = 3
7 6 5 7 6 5 7 6 5 _ 6 5

w4 = 5 w4 = 4 w4 = 5
B

1 2 3

_ 8 4 w5 = 2

7 6 5

B D

1 2 3 1 2 3

7 8 4 w6 = 3 8 _ 4 w6 = 0

_ 6 5 7 6 5

M1 Info 2005 / 2006 — Université d’Angers — Intelligence artificielle — TD 16

Recherche du meilleur d’abord : Profondeur + w1
w’ : somme des nombres minimaux de déplacement pour amener chaque chiffre à sa place

2 8 3

1 6 4 w' = 1 + 2 + 1 + 1 = 5
7 _ 5

w” : faire tourner les cases externes autour du centre

2 pour chaque chiffre marqué par son successeur

1 pour case blache mal placée.

2 8 3

1 6 4 w" = 1 + 2 + 2 + 2 + 2 = 9
7 _ 5

Complexité
En temps / en espace => en largeur d’abord / en profondeur d’abord

On suppose : chaque nœud a b successeurs (facteur de branchement)

Le problème a une solution de profondeur d.

Largeur d’abord
Trouver la solution si elle existe. Si plusieurs solutions, on trouve la moins profonde.

Complexité en temps : O ( bd )
Complexité en espace : O ( bd )

Exemple
b = 10

1000 nœuds peuvent être développés (et testés) par seconde.

1 nœud = 100 bits en mémoire

Profondeur Nombre de nœuds Temps Mémoire

0 1 1 ms 100 bits
2 111 0,1 s 10 Kbits
4 11111 11 s 1 Mbits
6 106 18 mn 111 Mb
8 108 31 h 11 Gb

M1 Info 2005 / 2006 — Université d’Angers — Intelligence artificielle — TD 17

Recherche par escalade (Hill-climbing)
Parmi les fils d’un nœud, on développe celui qui a la plus petite valeur pour sa fonction heu-
ristique (fonction d’évaluation). On gère une pile dans laquelle on stocke les fils dans l’ordre
décroissant de la valeur heuristique (distance évaluée à la solution)

Le meilleur d’abord (Best-first)

La structure de données est une structure ordonnée dans l’ordre croissant. Chaque fois qu’on
développe un nœud, on trie de nouveau sur l’ensemble des valeurs.

Branch and Bound

Au lieu de stocker des nœuds, on stocke des chemins incomplets. On ordonne la liste des
chemins par coûts et on développe l’extrémité du chemin le moins coûteux. On n’a pas
vraiment d’heuristique mais on a des coûts k.

Arrêt ?
Le chemin jusqu’à un but est moins coûteux que le moins coûteux des chemins incomplets
(et non seulement quand on a atteint un but)

Algorithme A* = Brand and Bound + Heuristique

k+h

f(e) = g(e) + h*(e)

g(e) : coût de l’origine à e

h*(e) : coût de e à un objectif
f(e) : coût réel d’une solution passant par e.

f(e) = g*(e) + h*(e)

g*(e) : coût optimal de l’origine à e

f(e) = g(e) + h(e)

h(e) : estimation du coût d’un chemin de e à l’objectif

Finalement, f(e) est l’estimation du coût d’une solution passant par e. Quand on fait le
Branch and Bound au lieu d’ordonner par f(e), on ordonne par g(e) + h(e) -> BB amélioré

Si de plus on retrouve une manière d’aller à e de coût inférieur au coût actuel, on ne retient
que le chemin de coût minimal -> Algorithme A*

M1 Info 2005 / 2006 — Université d’Angers — Intelligence artificielle — TD 18

 Ensemble ordonné A
successeurs de u successeurs de u
Etat u développé g(u), f(u), père(u) par f ! , g " ,
mis dans A non modifiés
ui(g(u), f(u))
u5 (2, 17),
u0 0, 17, _ u1, u3, u5 u1 (4, 19),
u3 (5, 21)
u8 (7, 14),
u7 (4, 17),
u5 2, 17, u0 u7, u8 u3
u1 (4, 19),
u3 (5, 21)
u7(4, 17),
u8 7, 14, u5 u1(4, 19),
u3(5, 21)
u1(4, 19),
u7 4, 17, u5 u10 u8, u0 u3(5, 21),
u10(19, 25)
u2(5, 20)
u4(9, 21)
u1 4, 19, u0 u2, u4 u3
u3(5, 21)
u10 (19, 25)
u4(9,21)
u2 5, 20, u1 u3, u5, u7 u3(5, 21)
u10(19, 25)
u9(13, 20)
u3(5, 21)
u4 9, 21, u1 u6, u9
u6(12, 23)
u10(19, 25)
u10(14, 20)
u3(5, 21)
u9 13, 20, u4 u10, u11, u4, u15 u6(12, 23)
u11(15, 24)
u15(25, 25)
u13(18, 20)
u12(15, 21)
u3(5, 21)
u10 14, 20, u9 u12, u13 u5
u6(12, 23)
u11(15, 24)
u15(25, 25)
u12(15, 21)
u3(5, 21)
u16(22, 22)
u13 18, 20, u10 u16 u15
u6(12, 23)
u11(15, 24)
u15(24, 24)

M1 Info 2005 / 2006 — Université d’Angers — Intelligence artificielle — TD 19

 Ensemble ordonné A
successeurs de u successeurs de u
Etat u développé g(u), f(u), père(u) par f ! , g " ,
mis dans A non modifiés
ui(g(u), f(u))
u13(5, 21)
u16(22, 22)
u12 15, 21, u13 u15 u13, u16 u6(12, 23)
u11(15, 24)
u15(24, 24)
u16(22, 22)
u6(12, 23)
u13 5, 21, u12 u6 u4
u11(15, 24)
u15(24,24)
u16 22, 22, u13

(u0, u1, u4, u9, u10, u13, u16)

f(u16) = 22

M1 Info 2005 / 2006 — Université d’Angers — Intelligence artificielle — TD 20

Algorithme AO*
Etats actualisés après Etats pendants
Etat u développé h(u) f(u) ( f1(u), … fi(u) )
le dév. de u dans G(u0)
u0 ( 55, 47, 52 ) Ø u8
u8 28 ( 25, 30 ) u0 (55, 44, 52) u18
u8 (55, 30) u19
u18 5 ( 35 )
u0 (55, 49, 52) u14
u8 (55, 44) u3
u19 11 ( 25 )
u0 (55, 63, 52) (u4)
u3 40 ( 38, 44 ) u0 (55, 53, 50) u7
u3 ( 52, 44 ) u1
u7 30 ( 44 )
u0 ( 55, 63, 56 ) u2
u9
u1 20 ( 35, 39, 47 ) u0 ( 70, 63, 56 )
u10
u9 25 ( 35 ) u3 ( 52, 54 ) u14
u9 ( 46 )
u8 ( 55, 55 )
u5
u7 ( 53 )
u14 4 ( 15 ) u2
u1 ( 35, 39, 53 )
u6
u3 ( 63, 65 )
u0 ( 70, 74, 75 )
u2
u1 ( 34, 39, 58 )
u5 16 ( 15, 18 ) u6
u0 ( 69, 74, 75 )
u11
u2 30 ( 30, 59 ) Ø u6 u11 u13
u1 ( 38, 39, 58 )
u6 15 ( 19 ) u13 u11 u12
u0 ( 73, 74, 75 )
u13 10 ( 10, 65 ) Ø u11 u12
u5 ( 17, 18 )
u11 10 ( 12 ) u1 ( 40, 39, 58 ) Ø
u0 ( 74, 76, 75 )

M1 Info 2005 / 2006 — Université d’Angers — Intelligence artificielle — TD 21

MINI-MAX et élagage α-ß

A 10

B 10 C 2

D 10 E 14 F 2 G 20

H 10 I 9 J 14 K 13 L 2 M 1 N 3 O 20

10 11 9 12 14 15 13 14 5 2 4 1 3 22 20 21

M1 Info 2005 / 2006 — Université d’Angers — Intelligence artificielle — TD 22