0% ont trouvé ce document utile (0 vote)

15 vues175 pages

Résolution de Problèmes par Exploration

Le document décrit les composants d'un problème de résolution de problèmes par un agent, notamment les états, actions, état initial, fonction de test des buts et coût d'un chemin. Il présente ensuite divers exemples de problèmes comme l'aspirateur, l'agent en Roumanie, le jeu de taquin et les huit reines.

Transféré par

Amina Mami

Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.

Formats disponibles

Téléchargez aux formats PDF, TXT ou lisez en ligne sur Scribd

0% ont trouvé ce document utile (0 vote)

15 vues175 pages

Résolution de Problèmes par Exploration

Transféré par

Amina Mami

Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.

Formats disponibles

Téléchargez aux formats PDF, TXT ou lisez en ligne sur Scribd

RÉSOLUTION DE

PROBLÈMES PAR
EXPLORATION
Haythem Ghazouani
PLAN
 Agents de résolution de problèmes
 Problèmes bien définis

 Recherche de solutions

 Stratégies d’exploration :
 Non informées,
 Informées (heuristiques)
 Fonctions heuristiques

2
PLAN

 Agents de résolution de problèmes

 Problèmes bien définis

 Recherche de solutions

 Stratégies d’explorations :
 Non informées,
 Informées (heuristiques)
 Fonctions heuristiques

3
AGENTS DE RÉSOLUTION DE
PROBLÈMES

4
© Haythem Ghazouani
AGENTS DE RÉSOLUTION DE PROBLÈMES
 Se sont des agents fondés sur les buts.
 Les états du monde sont des atomes sans

© Haythem Ghazouani
structure interne visible.
 Un agent intelligent doit maximiser sa
mesure de performance en formulant un
but et en essayant de le satisfaire.
 Exemple : agent en vacances à Tunis en et
doit rejoindre Tozeur, doit formuler son
but selon la situation actuelle et la
mesure de performance. 5
APPROCHE DE L’AGENT POUR LA
RÉSOLUTION DE PROBLÈME

© Haythem Ghazouani
7
FORMULATION DU BUT
 Ensemble d’états où le but est satisfait.
 L’agent doit découvrir comment agir pour arriver

© Haythem Ghazouani
à un état but : aller à Tozeur.
 Il doit donc choisir un ensemble d’actions lui
permettant d’atteindre son but.
 Mais il ne peut pas considérer directement l’état
but, il faut le décomposer en sous-buts : c’est la
formulation de problème.

8
FORMULATION DE PROBLÈME
 Processus consistant à décider quelles actions et
quels états considérer en vue d’un but donné :

9
APPROCHE DE L’AGENT POUR LA
RÉSOLUTION DE PROBLÈME

© Haythem Ghazouani
 Un algorithme d’exploration prend en entrée un
problème et renvoie une solution optimale sous
forme d’une séquence d’actions Tunis, Nabeul,
Sid Bouzid, Gafsa, Tozeur.

11
APPROCHE DE L’AGENT POUR LA
RÉSOLUTION DE PROBLÈME

 Recherche de solutions

 Stratégies d’explorations :
 Non informées,
 Informées (heuristiques)
 Fonctions heuristiques

15
PROBLÈMES BIEN DÉFINIS

16
© Haythem Ghazouani
DÉFINITION D’UN PROBLÈME
 Information que l’agent utilise pour décider quoi
faire.

17
PROBLÈME : CINQ COMPOSANTS
 L’état initial du problème : une ville,
 Les actions : passer d’un état à un autre,

© Haythem Ghazouani
 Modèle de transition : définit l’état résultant
de l’exécution d’une action à partir d’un état,
 Test de buts : détermine si un état donné est
un état but (concret : Dans(Bucarest), abstrait
: état d’échec et mat).
 Le coût du chemin : coût numérique de
performance de l’agent (longueur en km).
18
ESPACE D’ÉTATS
 Espace d’états = état initial + actions + modèle
de transitions.

© Haythem Ghazouani
 L’ensemble de tous les états accessibles par
une séquence d’actions à partir de l’état initial.
 L’espace d’états est un graphe dont les nœuds
sont les états et les liens entre les nœuds
forment les actions.
 Un chemin est une séquence d’états reliées par
une séquence d’actions.
19
GRAPHE DE L’ESPACE D’ÉTATS
DE L’AGENT EN ROUMANIE

 Abstraction
: suppression des détails :
paysage, météo, radio, …

 Recherche de solutions

 Stratégies d’explorations :
 Non informées,
 Informées (heuristiques)
 Fonctions heuristiques

21
EXEMPLES DE PROBLÈMES

22
© Haythem Ghazouani
TYPES DE PROBLÈMES
 Problèmes de jouets (Toys problems) :
illustrer ou expérimenter diverses méthodes

© Haythem Ghazouani
de résolution de problèmes (recherche).
 Problèmes du monde réel : un problème réel
dont la description est compliquée, mais on
peut trouver une idée de leur formalisation :
 Certains sont des extensions du problème de
Roumanie (systèmes embarqués dans les voitures,
voyageur de commerce),
 D’autres sont plus complexes (routage de flux
vidéo, planification d’opérations militaires).
23
EXEMPLES DE PROBLÈMES DE JOUETS

 Jeu de taquin,
 Problème des tours de Hanoi,

 L'aspirateur,

 Le problème des huit reines,

 Les mots croises,

 Les jeux d’échecs, de dames,…

24
EXEMPLE 1(ASPIRATEUR)
États :
Actions :
Les emplacements
Gauche, droite,
de l’agent et de la

État initial : Coût

Un état arbitraire 1 par déplacement

Test du but : Modèle de transition :

Vérifie que le sol Effets prévus à part
est propre quelques uns

25
© Haythem Ghazouani
EXEMPLE 2 (AGENT EN ROUMANIE)

États : Actions :
Graphe des points Arrêtes sortantes
de la carte d’un point

Coût
État initial :
Distance, durée,
Point de départ
difficulté, danger,
arbitraire
etc.

Test du but : Modèle de transition :

Destination finale Ville suivante

26
© Haythem Ghazouani
EXEMPLE 3 (JEU DE TAQUIN)

États : Actions :
Un état est une Déplacer une case à
configuration du jeu de droite, à gauche, en
taquin haut, en bas.

Coût
État initial : Un point par
déplacement, nombre
Un état arbitraire
de cases mal placées,
etc.

Etat Etat
Modèle de transition : initial final
Test du but :
Etats résultants des
Un état arbitraire actions

27
EXEMPLE 4 (HUIT REINES)
Actions :
États :
Ajouter une reine sur
Configuration de 0 à 8
n’importe quelle case vide
reines sur la grille sans
la plus à gauche de la grille

Coût
État initial :
Un coût constant pour
La grille vide
chaque action ou 0

Test du but :
Configuration de huit Modèle de transition :
reines avec aucune reine Configuration résultante
sous attaque de l’ajout d’une reine

28
EXERCICE (REPRÉSENTATION DU
PROBLÈME DES BIDONS)

 Vous disposez de 2 bidons, un de 4 gallons et

l’autre de 3 gallons, vides.

© Haythem Ghazouani
Il n’y a aucune marque de graduation.
Vous disposez également d’une pompe capable de
remplir les bidons.
 Comment remplir le bidon de 4 gallons avec
exactement 2 gallons d’eau ?

29
ESPACE D’ÉTATS DE L’ASPIRATEUR

 Recherche de solutions

 Stratégies d’explorations :

 Non informées,
 Informées (heuristiques)
 Fonctions heuristiques

32
RECHERCHE DE SOLUTIONS

33
© Haythem Ghazouani
RECHERCHE DE SOLUTIONS
 Une solution est une séquence d’actions.
 Les algorithmes d’exploration examinent diverses

© Haythem Ghazouani
séquences d’actions possibles à partir de l’état
initial, c’est l’arbre d’exploration ( espace
d’états) :
 État initial : racine,
 Branches : actions,
 Nœuds : états de l’espace d’états du problème.

34
ARBRE D’EXPLORATION PARTIEL DE
L’ITINÉRAIRE ARAD-BUCAREST

Arad

Rimnic
Arad Fagaras Oradea Arad Lugoj Arad Oradea
u Vilcea

35
ARBRE D’EXPLORATION PARTIEL DE
L’ITINÉRAIRE ARAD-BUCAREST

Arad

Rimnic
Arad Fagaras Oradea Arad Lugoj Arad Oradea
u Vilcea

36
ARBRE D’EXPLORATION PARTIEL DE
L’ITINÉRAIRE ARAD-BUCAREST

Arad

Rimnic
Ara Fagara Orade
u Arad Lugoj Arad Oradea
d s a
Vilcea

37
EXPLORATION DE L’EXEMPLE
1. Le nœud racine est le nœud initial (Arad).
2. On teste si l’état courant (Arad) est un état but.

© Haythem Ghazouani
3. Si oui, on renvoie la solution et arrêt.
4. Si non, et si l’état peut être développé, on
développe l’état courant (fils : Sibiu, Timisoara,
Zerind).
5. On sélectionne l’état à examiner, les autres
restent en attente.
6. On revient à 2 avec l’état sélectionné est l’état
courant.

38
FRONTIÈRE
 Nœuds feuilles générés mais non
encore développés.

Sibiu
Timisoara Zerind

Rimnic
Ara Fagara Orade
u
d s a
Vilcea
39
ALGORITHME GÉNÉRAL D’EXPLORATION EN
ARBRE

 Chemins avec boucles (cas particulier) :

 Présence d’états répétés,

© Haythem Ghazouani
 Arbre d’exploration infini.
 Chemins redondants :
 Plusieurs façons d’aller d’un état à un autre.
 Problèmes impraticables même si on évite les
boucles.

41
ALGORITHME GÉNÉRAL D’EXPLORATION EN
GRAPHE

 Lesalgorithmes qui oublient leur

histoire sont condamnés à la répéter

42
EXPLORATION
 Les algorithmes d’exploration ont la même structure de
base, ils diffèrent par la stratégie d’exploration.

© Haythem Ghazouani
 Nœud de recherche :
 État : l’état de l’espace des états.
 Nœud parent : le nœud dans l’arbre d’exploration qui a
produit ce nœud.
 Action : L’action qui a été appliquée au parent pour
générer ce nœud.
 Coût du chemin : coût g(n) du chemin à partir de l’état
initial jusqu’à ce nœud.
 Nœud  état.

43
EVALUATION DE LA RÉSOLUTION DE
PROBLÈMES

 Complétude : si une solution existe, l’algorithme

garanti son obtention.

 Complexité en temps : temps nécessaire pour

trouver la solution.
 Complexité en espace : mémoire nécessaire pour
effectuer l’exploration.

44
COMPLEXITÉ
 La complexité en temps et en espace dépend de :
 b : facteur de branchement, c’est le nombre maximal
de successeurs d’un nœud donné,

© Haythem Ghazouani
 d : profondeur à laquelle se trouve le meilleur nœud
solution (moins d’étapes depuis la racine),
 m : longueur maximale d’un chemin dans l’espace
d’états.

45
PLAN
 Agents de résolution de problèmes
 Problèmes bien définis

 Recherche de solutions

 Stratégies d’explorations :
 Non informées,
 Informées (heuristiques)
 Fonctions heuristiques

46
STRATÉGIES D’EXPLORATION

47
© Haythem Ghazouani
TYPES DE STRATÉGIES D’EXPLORATION
 Exploration aveugle :
 Pas d’autres informations sur les états que celles
fournies dans la définition du problème.

© Haythem Ghazouani
 Elles génèrent des successeurs et distinguent un état
final d’un état non final.
 Exploration informée (heuristiques) : peuvent
déterminer si un état non final est meilleur qu’un
autre.

48
PLAN
 Agents de résolution de problèmes
 Problèmes bien définis

 Recherche de solutions

 Stratégies d’explorations :

 Non informées,
 Informées (heuristiques)
 Fonctions heuristiques

49
EXPLORATION NON INFORMÉE
 N'exploitent aucune information sur la structure de l'arbre ou la
présence potentielle de nœuds-solution pour optimiser la
recherche :

© Haythem Ghazouani
 Exploration en largeur d’abord
 Exploration à coût uniforme
 Exploration en profondeur d’abord
 Exploration en profondeur limitée
 Exploration itérative en profondeur
 Exploration bidirectionnelle
 La plupart des problèmes réels sont susceptibles de provoquer
une explosion combinatoire du nombre d'états possibles.

50
EXPLORATION EN LARGEUR
D’ABORD

© Haythem Ghazouani 51
PRINCIPE DE L’EXPLORATION EN LARGEUR
D’ABORD
 On commence par développer le nœud racine puis tous
les nœuds successeurs, puis les successeurs des
successeurs, …

© Haythem Ghazouani
 Tous les nœuds à une profondeur i sont développés
avant ceux de niveau i+1.
 Graphe : on rechercherait tous les points dans un
rayon circulaire fixe, augmentant ce cercle pour
rechercher des intersections de plus en plus loin du
nœud initial.
 Il suffit de mémoriser la frontière dans une file FIFO :
les nœuds les plus profonds sont stockés à la fin et les
moins profonds au début. 52
ALGORITHME D’EXPLORATION EN LARGEUR
D’ABORD

État
initial F G

D H
C E K

État
but

54
Exemple d’exploration en largeur
d’abord en graphe

État
initial F G

D H
C E K

État
but

55
EXEMPLE D’EXPLORATION EN LARGEUR
D’ABORD EN GRAPHE

État
initial F G

D H
C E K

État
but

56
EXEMPLE D’EXPLORATION EN LARGEUR
D’ABORD EN GRAPHE

État
initial F G

D H
C E K

État
but

57
EXEMPLE D’EXPLORATION EN LARGEUR
D’ABORD EN GRAPHE

État
initial F G

D H
B D H
C E K

État
but

58
EXEMPLE D’EXPLORATION EN LARGEUR
D’ABORD EN GRAPHE

État
initial F G

D H
B D H
C E K

État
but

59
EXEMPLE D’EXPLORATION EN LARGEUR
D’ABORD EN GRAPHE

État
initial F G

D H
B D H
C E K

État
but

60
EXEMPLE D’EXPLORATION EN LARGEUR
D’ABORD EN GRAPHE

État
initial F G

D H
B D H
C E K

État
but

61
EXEMPLE D’EXPLORATION EN LARGEUR
D’ABORD EN GRAPHE

État
initial F G

D H
B D H D
C E K

État
Pas d’ajout du fils de C but
(D) à la frontière car il
y est déjà 62
EXEMPLE D’EXPLORATION EN LARGEUR
D’ABORD EN GRAPHE

État
initial F G

D H
B D H
C E K

État
but

63
EXEMPLE D’EXPLORATION EN LARGEUR
D’ABORD EN GRAPHE

État
initial F G

D H
B D H
C E K

F
État
but

64
EXEMPLE D’EXPLORATION EN LARGEUR
D’ABORD EN GRAPHE

État
initial F G

D H
B D H
C E K

F
État
but

65
EXEMPLE D’EXPLORATION EN LARGEUR
D’ABORD EN GRAPHE

État
initial F G

D H
B D H
C E K

F E G
État
but

66
EXEMPLE D’EXPLORATION EN LARGEUR
D’ABORD EN GRAPHE

État
initial F G

D H
B D H
C E K

F E G
État
Pas d’ajout du fils de D but
(G) à la frontière car il
a déjà était exploré 67
EXEMPLE D’EXPLORATION EN LARGEUR
D’ABORD EN GRAPHE

État
initial F G

D H
B D H
C E K

F E
État
but

68
EXEMPLE D’EXPLORATION EN LARGEUR
D’ABORD EN GRAPHE

État
initial F G

D H
B D H
C E K

F E K B
État
but

69
EXEMPLE D’EXPLORATION EN LARGEUR
D’ABORD EN GRAPHE

État
initial F G

D H
B D H
C E K

L’algorithme n’attend F E K B
État
pas l’exploration du fils but
de H il effectue le test
du but avant de le 70
placer dans la frontière
CONCLUSION
 Efficace si on ne sait pas par où se trouve le but (toutes
les étapes ont le même coût).

© Haythem Ghazouani
 Mais une perte de temps et d’espace si on connaît plus
d'informations sur notre destination.
 N’est pas adaptée aux problèmes exponentiels :

Profondeur Nœuds Temps Mémoire

b=10 1 000 000 1000 octets/nœud
nœuds/seconde
12 1012 13 jours 1 pétaoctets 71
16 1016 350 années 10 exaoctets
© Haythem Ghazouani
EXPLORATION À COÛT UNIFORME
(UNIFORM COST SEARCH UCS)
72
PRINCIPE DE L’EXPLORATION À COÛT
UNIFORME
 Développement du nœud qui a le coût de chemin le
plus faible g(n) :
 g(n)=coût à partir du nœud

© Haythem Ghazouani
initial jusqu’au nœud
développé.
 La frontière est stockée dans une file triée par coût (g)
croissant.
 Le test du but est appliqué à un nœud une fois choisi.
 Un test vérifie si un meilleur chemin existe vers un
nœud sur la frontière.
 Equivalent a l'exploration en largeur d'abord si tous
les coûts des actions sont égaux. 73
ALGORITHME D’EXPLORATION À COÛT
UNIFORME

© Haythem Ghazouani
74
EXEMPLE
 Le nœud Rimnicu Vilcea (80)
Sibu est développé en premier.
 Ensuite Fagaras (99),
meilleur que Pitesti (80 +97 =
99 177).
80  Ensuite Pitesti (80 +97 =
177), meilleur que Bucarest
(99+211=310).
Fagaras  Ensuite Bucarest à partir de
211 Pitesti (80+97+101) meilleur
Rimnicu que 310.
Vilcea 97  Le chemin est donc : Sibiu-
Rimnicu Vilcea –Pitesti-
Pitesti Bucarest.
101 75
Bucarest
© Haythem Ghazouani
PERFORMANCES
 Complétude : oui, si le coût de chaque étape ≥ à
une constante positive ε.

© Haythem Ghazouani
 Optimalité : oui, les nœuds sont développés dans
l'ordre de coût de chemin optimal (mais les coûts
ne doivent pas être négatifs).
 Complexité en temps et en espace :
 Soit C* le coût de la solution optimale
 Soit ɛ le coût minimal de chaque action
 Dans le pire des cas: O(b1+C*/ɛ)
 Egal à O(bd+1) si les coûts des actions sont égaux

76
© Haythem Ghazouani
EXPLORATION EN PROFONDEUR
D’ABORD (DEPTH FIRST SEARCH
DFC)
77
EXPLORATION EN PROFONDEUR D’ABORD

D E F G

H I J K L M N O

78
EXPLORATION EN PROFONDEUR D’ABORD

D E F G

H I J K L M N O

79
EXPLORATION EN PROFONDEUR D’ABORD

D E F G

H I J K L M N O

80
EXPLORATION EN PROFONDEUR D’ABORD

D E F G

H I J K L M N O

81
EXPLORATION EN PROFONDEUR D’ABORD

D E F G

H I J K L M N O

82
EXPLORATION EN PROFONDEUR D’ABORD

D E F G

H I J K L M N O

83
EXPLORATION EN PROFONDEUR D’ABORD

D E F G

H I J K L M N O

84
EXPLORATION EN PROFONDEUR D’ABORD

D E F G

H I J K L M N O

85
EXPLORATION EN PROFONDEUR D’ABORD

D E F G

H I J K L M N O

86
EXPLORATION EN PROFONDEUR D’ABORD

D E F G

H I J K L M N O

87
EXPLORATION EN PROFONDEUR D’ABORD

D E F G

H I J K L M N O

88
EXPLORATION EN PROFONDEUR D’ABORD

D E F G

H I J K L M N O

89
EXPLORATION EN PROFONDEUR D’ABORD

D E F G

H I J K L M N O

90
EXPLORATION EN PROFONDEUR D’ABORD EN
ARBRE AVEC LIBÉRATION DE LA MÉMOIRE

D E F G

H I J K L M N O

91
EXPLORATION EN PROFONDEUR D’ABORD EN
ARBRE AVEC LIBÉRATION DE LA MÉMOIRE

D E F G

H I J K L M N O

92
EXPLORATION EN PROFONDEUR D’ABORD EN
ARBRE AVEC LIBÉRATION DE LA MÉMOIRE

D E F G

H I J K L M N O

93
EXPLORATION EN PROFONDEUR D’ABORD EN
ARBRE AVEC LIBÉRATION DE LA MÉMOIRE

D E F G

H I J K L M N O

94
EXPLORATION EN PROFONDEUR D’ABORD EN
ARBRE AVEC LIBÉRATION DE LA MÉMOIRE

D E F G

I J K L M N O

95
EXPLORATION EN PROFONDEUR D’ABORD EN
ARBRE AVEC LIBÉRATION DE LA MÉMOIRE

E F G

J K L M N O

96
EXPLORATION EN PROFONDEUR D’ABORD EN
ARBRE AVEC LIBÉRATION DE LA MÉMOIRE

E F G

J K L M N O

97
EXPLORATION EN PROFONDEUR D’ABORD EN
ARBRE AVEC LIBÉRATION DE LA MÉMOIRE

E F G

K L M N O

98
EXPLORATION EN PROFONDEUR D’ABORD EN
ARBRE AVEC LIBÉRATION DE LA MÉMOIRE

F G

L M N O

99
© Haythem Ghazouani
100
O
G

N
C

M
F

L
A
EXPLORATION EN PROFONDEUR D’ABORD EN
ARBRE AVEC LIBÉRATION DE LA MÉMOIRE

F G

L M N O

101
EXPLORATION EN PROFONDEUR D’ABORD EN
ARBRE AVEC LIBÉRATION DE LA MÉMOIRE

F G

M N O

102
EXPLORATION EN PROFONDEUR D’ABORD EN
ARBRE AVEC LIBÉRATION DE LA MÉMOIRE

F G

M N O

103
© Haythem Ghazouani
EXPLORATION EN PROFONDEUR
LIMITÉE (DEPTH LIMITED
SEARCH DLS)
104
PRINCIPE DE L’EXPLORATION EN
PROFONDEUR LIMITÉE

 Profondeur limitée : l.
 Nœuds à la profondeur l sont considérés sans

 Equivalent a profondeur d'abord si l est infinie.

105
© Haythem Ghazouani
EXPLORATION ITÉRATIVE EN
PROFONDEUR IDS (OU
EXPLORATION PAR
APPROFONDISSEMENT ITÉRATIF)
106
PRINCIPE DE L’EXPLORATION ITÉRATIVE
EN PROFONDEUR

 Variante de l’exploration en profondeur d’abord.

 Détermine la meilleure profondeur limite.

© Haythem Ghazouani
 Essaye toutes les profondeurs graduellement (0, puis
1, puis 2, …) jusqu’à atteindre le but (profondeur
optimale d).
 Combine les avantages de :
 l’exploration en largeur d’abord (complète et optimale) et
 l’exploration en profondeur d’abord (complexité
temporelle).
 Recommandée lorsque l’espace d’états est important
et la profondeur de la solution est inconnue. 107
ALGORITHME D’EXPLORATION ITÉRATIVE
EN PROFONDEUR

109

 Exécution de deux explorations simultanément :

 en aval depuis l’état initial

© Haythem Ghazouani
 en amont à partir du but
 Arrêt lorsque les deux frontières se rencontrent
au milieu.
 Réduction de moitié de la profondeur explorée.

 Vérification de l’existence d’un nœud commun

aux deux arbres
 Tenir une table de hachage.
 Conserver tous les nœuds d’un des arbres.
 Difficile à appliquer si le but est une description 111
abstraite (n reines).
VUE SCHÉMATIQUE DE L’EXPLORATION
BIDIRECTIONNELLE

 Recherche de solutions

 Stratégies d’explorations :

 Non informées,
Informées (heuristiques)

 Fonctions heuristiques

113
© Haythem Ghazouani
STRATÉGIES D’EXPLORATION
INFORMÉES (HEURISTIQUES)
114
POURQUOI UNE EXPLORATION INFORMÉE ?

 Stratégies d’exploration non informées sont

généralement très peu efficaces.

© Haythem Ghazouani
 Stratégies d’exploration informées :
 Utilisent des connaissances du problème : une fonction
heuristique.
 Plus efficaces que l’exploration aveugle.

115
STRATÉGIES D’EXPLORATION INFORMÉE
 Exploration par meilleur d’abord

 Basée sur l’exploration en arbre et en graphe.

 Le nœud à développer est choisi selon une

© Haythem Ghazouani
fonction d’évaluation f(n) :
 La fonction f(n) est une estimation coût.
 Le nœud qui a un f(n) le plus faible est développé en
premier.
 Comme l’exploration à coût uniforme mais f est
utilisée au lieu de g pour ordonner la file.

117
FONCTION D’ÉVALUATION F(N)
 g(n) : coût réel (somme
A des meilleurs coûts du
nœud initial à n).

© Haythem Ghazouani
g(B)
 h*(n) : coût réel (somme
des coûts du nœud n au
f(B)=g(B)+h(B) B
nœud but).
 h(n) : coût heuristique
h*(B)
h(B) (estimation du chemin le
Bu
moins coûteux de l’état
t du nœud n à nœud but).
118
FONCTION D’ÉVALUATION F(N)

h(n) :

Le prochain h(n)
nœud est Nœud
f(n)=g(n)+h(n) courant
choisi selon la
valeur de f(n) n
g(n)

Nœud
119
initial
TYPES D’EXPLORATION PAR LE MEILLEUR
D’ABORD

 Exploration gloutonne par le meilleur d’abord.

120
© Haythem Ghazouani
EXPLORATION GLOUTONNE PAR
LE MEILLEUR D’ABORD
121
PRINCIPE DE L’EXPLORATION GLOUTONNE
MEILLEUR D’ABORD

 Développe le nœud le plus proche du but.

 f(n)=h(n).

© Haythem Ghazouani
 Exemple du voyageur en Roumanie :
 Heuristique distance à vol d’oiseau (Straight-line
distance SLD : hSLD).

122
HEURISTIQUE HSLD

hSLD distance à vol d’oiseau

jusqu’à Bucarest

© Haythem Ghazouani
124
© Haythem Ghazouani
EXPLORATION A* : A ÉTOILE
125
PRINCIPE DE L’EXPLORATION A*
 Fonction d’évaluation f :
 f(n)=g(n)+h(n).

126
CONDITIONS D’OPTIMALITÉ DE A*
 A* doit utiliser une heuristique h(n) admissible.
 Une heuristique h est admissible si elle ne surestime
jamais le coût réel pour atteindre le but : h(n) ≤h*(n)

© Haythem Ghazouani
 Consistance (monotonie) : pour l’exploration de
graphes :
 h(n) est consistante si pour tout nœud n et chaque
successeur n’ de n, produit par une action a,
h(n)c(n,a,n’) +h(n’)

127
A* : ILLUSTRATION

D Nœud destination

132
EXEMPLE 1
Nœud développé

Nœud généré 10 +

Référence au 133
parent
EXEMPLE 1
Nœud développé 20 +
40

Nœud généré 20 + 10 +

Référence au 134
parent
EXEMPLE 1
Nœud développé 20 +
40

Nœud généré 20 + 10 +

Référence au 135
parent
EXEMPLE 1
Nœud développé 20 +
40

Nœud généré 20 + 10 +

20 + 60

Référence au 136
parent
EXEMPLE 1
Nœud développé 30 + 20 +
50 40

Nœud généré 20 + 10 +

20 + 60

Référence au 137
parent
EXEMPLE 1
Nœud développé 30 + 20 + 30 +
50 40 30

Nœud généré 20 + 10 +

20 + 60

Référence au 138
parent
EXEMPLE 1
Nœud développé 30 + 20 + 30 + 40 +
50 40 30 20

Nœud généré 20 + 10 +

20 + 60

Référence au 139
parent
EXEMPLE 1
Nœud développé 30 + 20 + 30 + 40 + 50 +
50 40 30 20 10

Nœud généré 20 + 10 +

20 + 60

Référence au 140
parent
EXEMPLE 1
Nœud développé 30 + 20 + 30 + 40 + 50 +
50 40 30 20 10

Nœud généré 20 + 10 + 60 + 0

20 + 60

Référence au 141
parent
EXEMPLE 1 : CHEMIN COMPLET

142
EXEMPLE 2
S Nœud source

D Nœud destination

143
EXEMPLE 2
Nœud développé

Nœud généré

G+H

Référence au 144
parent
EXEMPLE 2
Nœud développé

Nœud généré

G+H

Référence au 145
parent
EXEMPLE 2
Nœud développé

Nœud généré 20 +

G+H
20 + 60

Référence au 146
parent
EXEMPLE 2
Nœud développé 30 +
50

Nœud généré 20 +

G+H
20 + 60

Référence au 147
parent
EXEMPLE 2
Nœud développé 30 +
50

Nœud généré 20 +

G+H
20
20 ++ 60
60

Référence au 148
parent
EXEMPLE 2
Nœud développé 30 +
50

Nœud généré 20 +

G+H
20
20 ++ 60
60

30 + 70

Référence au 149
parent
EXEMPLE 2
Nœud développé 30 +
50

Nœud généré 20 +

G+H
20
20 ++ 60
60
40 +
60
30 + 70

Référence au 150
parent 40 + 80
EXEMPLE 2
Nœud développé 30 +
50

Nœud généré 20 +

G+H
20
20 ++ 60
60
40 + 50 +
60 50
30 + 70

Référence au 151
parent 40 + 80 50 + 70
EXEMPLE 2
Nœud développé 30 +
50

Nœud généré 20 +

G+H
20 + 60
40 + 50 + 60 +
60 50 40

Référence au 152
parent 50 + 70 60 + 60
EXEMPLE 2
Nœud développé 30 +
50

Nœud généré 20 +

G+H
20 + 60
40 + 50 + 60 + 70 +
60 50 40 30

Référence au 153
parent 50 + 70 60 + 60 70 + 50
EXEMPLE 2
Nœud développé 30 +
50

Nœud généré 20 +

G+H 80 +
20
20
20++60
60
40 + 50 + 60 + 70 +
60 50 40 30
30 + 70

Référence au 154
parent 40 + 80 50 + 70 60 + 60 70 + 50 80 + 40
EXEMPLE 2
Nœud développé 30 +
50

Nœud généré 20 +

G+H 80 +
20
20 + 60
40 + 50 + 60 + 70 +
60 50 40 30

Référence au 155
parent 50 + 70 60 + 60 70 + 50
EXEMPLE 2
Nœud développé 30 +
50

Nœud généré 20 + 100 +

G+H 80 +
20
20
20++60
60
40 + 50 + 60 + 70 +
60 50 40 30
30 + 70

Référence au 156
parent 40 + 80 50 + 70 60 + 60 70 + 50 80 + 40
EXEMPLE 2 : CHEMIN COMPLET

20 + 60

157
APPLICATION (LABYRINTHE)
Au début la distance parcourue est 0
(Distance parcourue, Distance estimée)

Nœud non
encore
(0,55) généré

Nœud
généré

Nœud
développé

158

APPLICATION (LABYRINTHE)
(Distance parcourue, Distance estimée)

Nœud non
encore
(0,55) généré

Nœud
généré

(20,40)
Nœud
développé

APPLICATION (LABYRINTHE)
(Distance parcourue, Distance estimée)

Nœud non
encore
(0,55) généré

Nœud
généré

(40,50) (20,40) (55,30)

Nœud
développé

APPLICATION (LABYRINTHE)
(Distance parcourue, Distance estimée)

Nœud non
encore
(0,55) généré
(65,40)
Nœud
généré

(40,50) (20,40) (55,30)

Nœud
développé

APPLICATION (LABYRINTHE)
(Distance parcourue, Distance estimée)
(60,70)
Nœud non
encore
(0,55) généré
(65,40)
Nœud
généré

(40,50) (20,40) (55,30)

Nœud
développé

APPLICATION (LABYRINTHE)
(Distance parcourue, Distance estimée)
(60,70)
Nœud non
encore
(70,43) généré
(0,55)
(65,40)
Nœud
(90,50)
généré

(40,50) (20,40) (55,30)

Nœud
développé

APPLICATION (LABYRINTHE)
(Distance parcourue, Distance estimée)
(60,70)
Nœud non
encore
(70,43) généré
(0,55)
(65,40)
Nœud
(90,50)
généré

(40,50) (20,40) (55,30)

Nœud
(90,25)
développé

APPLICATION (LABYRINTHE)
(Distance parcourue, Distance estimée)
(60,70)
Nœud non
encore
(70,43) généré
(0,55)
(65,40)
Nœud
(90,50)
généré

(40,50) (20,40) (55,30)

(125,30) Nœud
(90,25)
développé

APPLICATION (LABYRINTHE)
(Distance parcourue, Distance estimée)
(80,115) (60,70)
Nœud non
encore
(70,43) généré
(0,55)
(65,40)
Nœud
(90,50)
généré

(40,50) (20,40) (55,30)

(125,30) Nœud
(90,25)
développé

APPLICATION (LABYRINTHE)
(Distance parcourue, Distance estimée)
(80,115) (60,70) (110,90)
Nœud non
encore
(70,43) généré
(0,55)
(65,40)
Nœud
(90,50)
généré

(40,50) (20,40) (55,30)

(125,30) Nœud
(90,25)
développé

APPLICATION (LABYRINTHE)
(Distance parcourue, Distance estimée)
(80,115) (60,70) (110,90)
Nœud non
encore
(70,43) généré
(0,55)
(65,40)
Nœud
(90,50)
généré