Introduction à l’Intelligence
Artificielle
(L2 Portail Sciences et Technologies)
Andrea G. B. Tettamanzi
Laboratoire I3S – Équipe SPARKS
[Link]@[Link]
Séance 2
Résolution de problèmes
Andrea G. B. Tettamanzi, 2022
Plan pour cette séance
●
Résolution par recherche
●
Espace de recherche
●
Algorithmes de recherche sur les graphes
●
Stratégies de recherche aveugles
●
Stratégies de recherche heuristiques
●
Algorithme A*
Andrea G. B. Tettamanzi, 2022 3
Problème
●
État initial
●
Actions disponibles à chaque état
●
Modèle de transition : état × action → état
– Espace des états (un graphe)
●
Test objectif (l’état est-il une solution ?)
●
Coût d’un pas (et d’une solution)
Andrea G. B. Tettamanzi, 2022 4
Jeu de taquin
1 2 3
4 5 6
7 8
1 2 3
4 5 6
7 8
1 2 3
4 5
7 8 6
Andrea G. B. Tettamanzi, 2022 5
Arbre
●
Structure de données récursive
●
Un arbre est formé par
– Un nœud (dit « racine »), contenant
●
Des données ou une référence à des données
●
Des références (ou pointeurs) à des (sous-)arbres
– Zéro ou plus sous-arbres
●
Un nœud n'ayant pas des sous-arbres est dit « feuille »
●
Les autres nœuds sont dits « nœuds internes »
Andrea G. B. Tettamanzi, 2022 6
Arbre
Andrea G. B. Tettamanzi, 2022 7
Arbre
●
La racine r de l'arbre est l'unique nœud ne possédant pas de parent
●
Tout nœud x qui n’est pas la racine a
– un unique parent, noté [Link] ou parent(x) (appelé « père »
parfois)
– 0 ou plusieurs fils ; [Link] ou fils(x) désigne l’ensemble des fils de x
●
Si x et y sont des nœuds tels que x soit sur le chemin de r à y,
– x est un ancêtre de y
– y est un descendant de x
●
Les feuilles n'ont pas de fils
Andrea G. B. Tettamanzi, 2022 8
Arbre
1 est la racine
9,10,6,3,11,12,8 sont les feuilles
11 est un descendant de 4, mais pas de 2
2 est un ancêtre de 10
Andrea G. B. Tettamanzi, 2022 9
Arbre
●
Quand il n’y a pas d’ambiguïté, on regarde les arêtes d’un
arbre comme étant orientées de la racine vers les feuilles
●
La profondeur d’un nœud (depth) est définie récursivement
par
– prof(v) = 0, si v est la racine
– prof(v) = prof(parent(v)) + 1
●
La hauteur d’un nœud (height) est la plus grande profondeur
d’une feuille du sous-arbre dont il est la racine
Andrea G. B. Tettamanzi, 2022 10
Arbre
1 est la racine
2,3,4 sont à la profondeur 1
5,6,7,8 à la profondeur 2
La hauteur de 2 est 2, celle de 9 est 0, celle de 3 est 0, celle de 1 est 3
Andrea G. B. Tettamanzi, 2022 11
Graphe orienté
●
Un Graphe Orienté G = (X, U) est déterminé par la donnée :
– d’un ensemble de sommets ou nœuds X
– d’un ensemble ordonné U de couples de sommets appelés
arcs.
●
Si u = (i, j) est un arc de G, alors
– i est l’extrémité initiale de u
– j est l’extrémité terminale de u.
●
Les arcs ont un sens (« orientés »).
– L’arc u = (i, j) va de i vers j.
●
Ils peuvent être munis d’un coût, d’une capacité etc. (arcs
étiquetés)
Andrea G. B. Tettamanzi, 2022 12
Graphe
Andrea G. B. Tettamanzi, 2022 13
Graphe non orienté
●
Un Graphe Non Orienté G = (X, U) est
déterminé par la donnée :
– d’un ensemble de sommets ou nœuds X
– d’un ensemble de paires de sommets
appelées « arêtes ».
●
Les arêtes ne sont pas orientées
Andrea G. B. Tettamanzi, 2022 14
Graphe non orienté
Andrea G. B. Tettamanzi, 2022 15
Chemins et circuits
● Chemin de longueur q : séquence de q arcs {u1, u2,
…, uq} telle que
– u1 = (i0, i1)
– u2 = (i1, i2)
– uq = (iq – 1, iq)
●
Chemin : tous les arcs orientés dans le même sens
●
Circuit : chemin dont les extrémités coïncident
Andrea G. B. Tettamanzi, 2022 16
Chaînes et cycles
●
Chaîne de longueur q : séquence de q arêtes
{u1, u2, …, uq} telle que
– u1 = (i0, i1)
– u2 = (i1, i2)
– uq = (iq – 1, iq)
●
Cycle : chaîne dont les extrémités coïncident
Andrea G. B. Tettamanzi, 2022 17
Jeu de taquin 4 1 2
7 3
8 5 6
4 2
7 1 3
8 5 6
2 3 6 1 2 3 4 1 2
1 5 4 5 6 7 3
4 7 8 7 8 8 5 6
7 7
2 3 6 4 1 2 4 1 2
1 5 7 5 3 7 3
4 7 8 8 6 8 5 6
7 7
Pour chaque chiffre au centre,
3 6 7 4 1
2 5 8 8 5 2
1 4 7 6 3
cycles distincts de 64 nœuds
7 7
6 8 8 7 4
3 5 7 5 1
2 1 4 6 3 2
7 7
6 5 8 8 7 8 7 4
3 7 6 5 4 5 1
2 1 4 3 2 1 6 3 2
Andrea G. B. Tettamanzi, 2022 18
1 2 3
4 5
7 8 6
Jeu de taquin
1 5 2
4 3
1 2 3 1 2 3 7 8 6 « ponts » entre
1 2
4 5 6
7 8
4 5
7 8 6 4 5 3 quatre cycles
7 8 6
1 2
4 5 3
7 8 6
4 1 2
1 2 5 3
4 5 3 7 8 6
7 8 6
4 1 2 4 1 2 4 2
7 3
7 5 3
7 8 6 8 5 6
7 1 3
8 5 6
4 1 2
4 1 2 7 3
7 5 3 8 5 6
8 6
4 1 2
7 3
8 5 6
4 1 2
7 5 3
8 6
Andrea G. B. Tettamanzi, 2022 19
Jeu de taquin
1
2368754
5 4 1 2
5 3
3
1236874 7 8 6 1268754
8
7541236
Andrea G. B. Tettamanzi, 2022 20
Arbres comme graphes
●
Un arbre est un graphe non orienté connexe et
sans cycle
●
Un graphe non orienté G ayant n sommets est
un arbre si et seulement si il vérifie l’une des
deux propriétés
– G est connexe et possède n – 1 arêtes
– G n’a pas de cycle et a n – 1 arêtes
Andrea G. B. Tettamanzi, 2022 21
Algorithme Général
Fonction RECHERCHE(problème), renvoie « échec » ou une solution
Front ← { état_initial }
Exploré ← { }
Répéter :
Si Front est vide, renvoyer « échec »
Choisir (et retirer) un nœud du front
Si le nœud contient un état final, renvoyer la solution correspondante
Ajouter le nœud à l’ensemble Exploré
Développer le nœud
Pour chacun de ses successeurs :
Si successeur ni dans Front ni dans Exploré :
Ajouter successeur au Front
Andrea G. B. Tettamanzi, 2022 22
Stratégies de recherche
« aveugles »
●
Aucune information sur la structure du problème
●
On sait seulement tester si un état est final et générer un
nouveau état en appliquant une action
●
Les stratégies ne diffèrent que par l’ordre par lequel les
nœuds sont développés
– Exploration en largeur d’abord
– Exploration à coût uniforme
– Exploration en profondeur d’abord
– Exploration en profondeur limitée
– Exploration par approfondissement itératif
Andrea G. B. Tettamanzi, 2022 23
Exploration en largeur d’abord
Fonction LARGEUR(problème), renvoie « échec » ou une solution
Front ← file(état_initial)
Exploré ← { }
Répéter :
Si Front est vide, renvoyer « échec »
Défiler le premier nœud du front
Si le nœud contient un état final, renvoyer la solution correspondante
Ajouter le nœud à l’ensemble Exploré
Développer le nœud
Pour chacun de ses successeurs :
Si successeur ni dans Front ni dans Exploré :
Enfiler successeur dans Front
Andrea G. B. Tettamanzi, 2022 24
Exploration en largeur d’abord
a b c d e
f g h i j
k l m n o
p q r s t
u v w x y
Front = [ m ]
Exploré = { }
Andrea G. B. Tettamanzi, 2022 25
Exploration en largeur d’abord
a b c d e
f g h i j
k l m n o
p q r s t
u v w x y
Front = [ h, n, r, l ]
Exploré = { m }
Andrea G. B. Tettamanzi, 2022 26
Exploration en largeur d’abord
a b c d e
f g h i j
k l m n o
p q r s t
u v w x y
Front = [ n, r, l, g, c, i ]
Exploré = { h, m }
Andrea G. B. Tettamanzi, 2022 27
Exploration en largeur d’abord
a b c d e
f g h i j
k l m n o
p q r s t
u v w x y
Front = [ r, l, g, c, i , o, s]
Exploré = { h, m, n }
Andrea G. B. Tettamanzi, 2022 28
Exploration en profondeur d’abord
Fonction PROFONDEUR(problème), renvoie « échec » ou une solution
Front ← pile(état_initial)
Exploré ← { }
Répéter :
Si Front est vide, renvoyer « échec »
Dépiler le nœud au sommet de la pile Front
Si le nœud contient un état final, renvoyer la solution correspondante
Ajouter le nœud à l’ensemble Exploré
Développer le nœud
Pour chacun de ses successeurs :
Si successeur ni dans Front ni dans Exploré :
Empiler successeur sur la pile Front
Andrea G. B. Tettamanzi, 2022 29
1)Exploration en profondeur d’abord
a b c d e
f g h i j
k l m n o
p q r s t
u v w x y
Front = [ m ]
Exploré = { }
Andrea G. B. Tettamanzi, 2022 30
1)Exploration en profondeur d’abord
a b c d e
f g h i j
k l m n o
p q r s t
u v w x y
Front = [ h, n, r, l ]
Exploré = { m }
Andrea G. B. Tettamanzi, 2022 31
1)Exploration en profondeur d’abord
a b c d e
f g h i j
k l m n o
p q r s t
u v w x y
Front = [ g, c, i, n, r, l ]
Exploré = { h, m }
Andrea G. B. Tettamanzi, 2022 32
1)Exploration en profondeur d’abord
a b c d e
f g h i j
k l m n o
p q r s t
u v w x y
Front = [ f, b, c, i, n, r, l ]
Exploré = { g, h, m }
Andrea G. B. Tettamanzi, 2022 33
1)Exploration en profondeur d’abord
a b c d e
f g h i j
k l m n o
p q r s t
u v w x y
Front = [ a, b, c, i, n, r, l ]
Exploré = { f, g, h, m }
Andrea G. B. Tettamanzi, 2022 34
1)Exploration en profondeur d’abord
a b c d e
f g h i j
k l m n o
p q r s t
u v w x y
Front = [ b, c, i, n, r, l ]
Exploré = { a, f, g, h, m }
Andrea G. B. Tettamanzi, 2022 35
Exploration à coût uniforme
Fonction COUT_UNIFORME(problème), renvoie « échec » ou une solution
Front ← { état_initial }
Exploré ← { }
Répéter :
Si Front est vide, renvoyer « échec »
Choisir (et retirer) de Front le nœud n tel que coût(n) est le moindre
Si n contient un état final, renvoyer la solution correspondante
Ajouter le nœud à l’ensemble Exploré
Développer le nœud
Pour chacun de ses successeurs :
Si successeur ni dans Front ni dans Exploré :
Ajouter successeur au Front
Si successeur est déjà dans Front mais avec un coût supérieur
Mettre à jour coût (et chemin) du successeur
Andrea G. B. Tettamanzi, 2022 36
Recherche heuristique
●
Idée : choisir le nœud à développer suivant une
fonction d’évaluation, f(n)
●
Coût du chemin jusqu’à n : g(n)
●
Estimation du coût du chemin le moins cher
pour aller de n à l’objectif : h(n)
●
f(n) = g(n) + h(n)
Andrea G. B. Tettamanzi, 2022 37
Algorithme A*
Fonction A*(problème), renvoie « échec » ou une solution
Front ← { état_initial }
Exploré ← { }
Répéter :
Si Front est vide, renvoyer « échec »
Choisir (et retirer) de Front le nœud n tel que f(n) est le moindre
Si n contient un état final, renvoyer la solution correspondante
Ajouter le nœud à l’ensemble Exploré
Développer le nœud
Pour chacun de ses successeurs :
Si successeur ni dans Front ni dans Exploré :
Ajouter successeur au Front
Si successeur est déjà dans Front mais avec un coût supérieur
Remplacer successeur, avec son coût actuel
Andrea G. B. Tettamanzi, 2022 38
Optimalité de A*
●
Une heuristique admissible ne surestime jamais
le coût pour atteindre l’objectif
●
Une heuristique est cohérente (ou monotone)
si, pour tout node n et successeur n’ obtenu par
l’action a,
h(n) ≤ c(n, a, n’) + h(n’)
●
Toute heuristique cohérente est aussi admissible
●
Si h est cohérente, A* est optimal
Andrea G. B. Tettamanzi, 2022 39
A* et Jeu de taquin
2 8 4 1 2 3
7 3 5 4 5 6
6 1 7 8
Deux heuristiques :
1) Distance de Hamming : nombre de tuiles hors place
2) Distance de Manhattan : somme des distances de l’objectif pour chaque tuile
Tuile : 1 2 3 4 5 6 7 8 Total
Distance : 3 1 2 3 1 3 1 2 16
Andrea G. B. Tettamanzi, 2022 40
1 2 3
A* et Jeu de taquin 4 5 6
7 8
2 8 4
7 3 5
6 1
2 8 4 2 8 4 2 8 4
7 5 7 5 7 5
6 3 1 6 3 1 6 3 1
2 4
7 8 5
6 3 1
Andrea G. B. Tettamanzi, 2022 41
Andrea G. B. Tettamanzi, 2022 42
