WIESLAW ZIELONKA

www.irif.fr/~zielonka

INTRODUCTION À L'INTELLIGENCE
ARTIFICIELLE ET LA THÉORIE DE JEUX
 PROBLÈMES DE RECHERCHE
Jeu de Taquin

1 3 2 1 2 3

7 4 4 5 6

8 5 6 suite d'actions 7 8

Etat initial Etat final

• états

• état initial

• actions

• transitions (état,action) → état

• coût de chemin

• teste de l'état final, état → true, false

 PROBLÈMES DE RECHERCHE
PROBLÈME DE HUIT DAMES

État initial : échiquier vide (ou échiquier avec 8 dames dans les positions
quelconques).

Action -

• ajouter une dame sur une position vide ou

• deplacer une dame

 PLANIFICATION DE VOYAGE AVION

difficile :

• contraintes date de départ,

• changement d'avion (sur un trajet A → B → C l'avion A → B doit

arrivé avant le départ de l'avion B → C)

• le coût

• la durée totale
 LE PROBLÈME DE COMMIVOYAGEUR

Faire le tour de toutes les villes en passant par chaque ville une
seule fois. Minimiser la longueur totale du trajet. NP-complet.
 ALGORITHME GÉNÉRIQUE - TREE-SEARCH

Les feuilles de l'arbre de recherche forment une frontière .

On ne mémorise pas les noeuds déjà visités dont toutes les arêtes
sortantes ont déjà été examinées.

fonction tree-search(problème) retourne solution ou échec

n = new noeud(état_init); frontière = { n };
loop do
si frontière vide retourner échec
n = élément de la frontière; supprimer n de la frontière;
si n.état est un état but alors retourner solution
pour chaque action a faire
nouvel_état = transition(n.état, a)
m = new noeud(nouvel_état)
ajouter m dans la frontière
fait
end loop
 ALGORITHME GÉNÉRIQUE — GRAPHE-SEARCH

fonction graph-search(problème) retourne solution ou échec

n = new noeud(état_init);
FRONTIERE = { n }; FERMES = {};
loop do
si frontière vide retourner échec
n = élément de la FRONTIERE
supprimer n de la FRONTIERE
if n.état est un état but alors retourner solution
ajouter n dans FERMES
pour chaque action a faire
nouvel_état = transition(n.état, a)
si nouvel_état dans un noeud de FRONTIERE
ou dans un noeud de FERMES alors continue
m = new noeud(nouvel_état)
ajouter m dans FRONTIERE
fait
end loop

Quelle structure pour stocker les noeuds dans la frontière?

 QUELLE FILE ?

• FIFO — first in first out, file habituelle

• LIFO — last in first out, pile

• file de priorité
 IMPLÉMENTER LA FRONTIÈRE COMME UNE FILE

• créer_file() — retourne une file vide

• est_vide(file) — retourne true si la file vide

• premier(file) — retourne le premier élément (celui avec le coût

minimal)

• supprimer_premier(file) — supprime le premier élément de la file

• insérer(file, élément) — ajouter un élément dans la file

INFRASTRUCTURE POUR LE PROBLÈME DE RECHERCHE

• n.état — état du noed

• n.parent — le parent du noeud

• n.action — l'action qui appliquée au parent donne l'état du nouer

• n.coût le coût du chemin de la racine jusqu'au noeud

fonction créer_noeud(Noeud parent, Action action)

retourne Noeud
n = new noeud()
n.état = transition(parent.état, action)
n.action = action
n.coût = parent.coût + coût(parent.état,action)
n.parent = parent
INFRASTRUCTURE POUR LE PROBLÈME DE RECHERCHE

fonction créer_noeud_initial(État état)

retourne Noeud
n = new noeud()
n.état = état
n.action = null
n.coût = 0
n.parent = null
 TREE-SEARCH

fonction tree-search(problème) retourne solution ou échec

n = créer_noeud_initial(état_initial)
frontière = créer_file()
loop do
si est_vide(frontière) retourner échec
n = premier(frontière); supprimer_premier(frontière);
if n.état est un état but alors retourner n
pour chaque action a faire
nouveau_noeud = créer_noeud(n, a)
insérer(frontière,nouveau_noeud)
fait
end loop
 CRITÈRES DE PERFORMANCES

• algorithme complet ? Oui, s'il trouve une solution quand elle

existe.

• l'algorithme optimal ? est-ce que la solution trouvée est optimale?

• complexité en temps et espace

 RECHERCHE EN LARGEUR

• coût(état,action) est 1

• la file : FIFO, arrêter dès que la solution trouvée (testez si l'état destination
avant de mettre le noeud dans la frontière et non pas à la sortie de la frontière)

• Est-ce que l'algorithme est complet ?

• Optimal?

• complexité : si chaque sommet possède b fils et la solution se trouve à distance

d de la racine alors le nombre de noeuds générés

b+b^2+b^3+…+b^{d-1} = O(b^d)
 RECHERCHE EN LARGEUR

b = 10 (facteur de branchement)

un million de noeuds par seconde, mémoire par noeud 1000 octets

profondeur noeuds temps mémoire

8 10^8 2 minutes 103 GB

10 10^10 3 heures 10 TB

12 10^12 13 jours 1 petabyte

14 10^14 3.5 année 99 petabytes

16 10^16 350 ans 10 exabytes

RECHERCHE À COÛT UNIFORME (UNIFORM COST SEARCH)

• file = file de priorité

• le coût coût(état,action) doit être positif

• Trouve toujours le plus court chemin donc complet et optimal.

• Il est très important qu'on teste de terminaison quand un noeud

sort de la frontière (si le teste à l'entrée de la frontière
l'algorithme n'est pas optimal).
 RECHERCHE EN PROFONDEUR

• utilise LIFO (une pile)

• ni complet, ni optimal

• quel coût en espace ?

• une variante : backtracking search - on garde que le sommet

courant, son parent, parent de parent etc.
 RECHERCHE EN PROFONDEUR AVEC BACKTRACKING

1. mettre le noeud de départ sur la pile (la frontière = FIFO)

2. si la frontière vide alors sortir avec échec, sinon continuer

3. soit n le premier élément de la pile

4. si toutes les arêtes avec la source n ont déjà été examinées alors enlever n de la
pile et aller en 2 sinon continuer

5.gérer un nouveau successeur m de n (l'arête (n,m) n'était pas examinée

précédemment), mettre m au sommet de la pile,

6.marquer n pour indiquer que l'arrête (n,m) a été visitée)

7.si m est le but alors sortir, le chemin le plus court sur la pile

8.si m est l'impasse alors dépiler m

9.aller en 2
 ITERATIVE DEEPENING DEPTH-FIRST SEARCH

limited_depth_first_search(k) — fait la recherche en profondeur

jusqu'au niveau k et retourne soit une solution soit échec

deepening_depth_first_search()
for k=1 to infinity
do
solution = limited_depth_first_search(k)
si solution != échec alors
retourner solution
done

limited_depth_first_search(k) - effectue recherche

effectue recherche en profondeur mais ne dépasse
jamais le niveau k.
 RECHERCHE INFORMÉE (AVEC AIDE DE HEURISTIQUE)

• appelé BEST_FIRST_SEARCH

• la fonction heuristique h(n) — le coût estimé de chemin le plus

court de sommet n jusqu'au but

• g(n) — le coût de chemin courant de sommet initial vers le

sommet courant n (calculé par l'algorithme)

• f(n) — la fonction d'évaluation, à chaque itération on cherche dans

la frontière le sommet n avec f(n) minimal
 HEURISTIQUE

pour le problème de plus court chemin entre les villes

h(n) - la distance à vol d'oiseau de la ville n jusqu'à la ville

destination
ALGO DE RECHERCHE GLOUTON (GREEDY BEST-FIRST SEARCH)

• on prend f(n) = h(n) et on utilise la file de priorité où pour chaque

sommet n on stocke la valeur h(n)

• à chaque étape on prend de la file de priorité le sommet n avec

f(n)=h(n) minimal

• le coût du chemin de sommet source vers n n'est pas pris en

compte

• la version tree-like de l'algorithme n'est pas complète

• la version graph-like est complète mais pas optimale

 ALGO COÛT UNIFORME

• si f(n)=g(n), c'est-à-dire on n'utilise pas la heuristique alors la

recherche à coût uniforme (déjà étudiée)
 ALGORITHME A^* - MINIMISER LE COÛT TOTAL

• dans chaque sommet n on stocke g(n) et f(n)=g(n)+h(n)

• la file de priorité pour les valeurs de f(n), à chaque étape on

choisit un noeud avec f(n) minimal
 ALGORITHME A^*

1. mettre le sommet initial s dans FRONTIERE, g(s)=0, f(s)=h(s)

2. Si FRONTIERE vide, sortir avec échec

3. retirer de FRONTIERE et mettre dans FERMES le noeud n pour lequel

f(n) est minimal

4. si n est le but alors terminer et retracer la solution, le chemin de s à n

5. développer n pour engendrer tous ses successeurs. Pour tout

successeur m de n :

A. si m n'est pas encore dans FRONTIERE ni dans FERMES calculer

f(m)=g(m)+h(m), où g(m)=g(n)+coût(n, m)

6. aller à 2
 INFRASTRUCTURE POUR L'ALGORITHME A^*

• n.état — état du noed

• n.parent — le parent du noeud

• n.action — l'action qui appliquée au parent donne l'état du nouer

• n.coût — le coût du chemin de la racine jusqu'au noeud, c'est g(n)

• n.f — la valeur f(n), la file de priorité selon les valeur n.f

fonction créer_noeud(Noeud parent, Action action)

retourne Noeud
n = new noeud()
n.état = transition(parent.état, action)
n.action = action
n.coût = parent.coût + coût(parent.état,action)
n.parent = parent
n.f = n.coût + h(n.état)
 INFRASTRUCTURE POUR L'ALGORITHME A^*

fonction créer_noeud_initial(État état)

retourne Noeud
n = new noeud()
n.état = état
n.action = null
n.coût = 0
n.parent = null
n.f = 0
 HEURISTIQUE ADMISSIBLE

la fonction heuristique h est admissible si pour chaque sommet n

h(n) <= coût réel du chemin le plus court de n vers un état but

donc heuristique admissible ne surestime jamais le coût réel.

 HEURISTIQUE CONSISTANTE

Une heuristique est consistante (ou cohérente) si elle satisfait l'inégalité

de triangle:

pour chaque couple de sommets n et m et action a telle que

m=transition(n,a) on a

h(n) <= coût(n,a,m) + h(m)

n
destination

a
m

coût(n,a,m) - coût de l'action a

HEURISTIQUE CONSISTANTE

heuristique h





si h consistante alors h admissible
 OPTIMALITÉ DE A^*

A. Si la heuristique h est admissible alors la version tree-search de

l'algorithme A^* est optimale.

B. Si la heuristique h est consistante alors la version graph-search de

l'algorithme A^* est optimale.

Demonstration de A.

Soit C* le coût minimal d'un chemin de l'état initial vers un état but.

A chaque moment FRONTIERE contient un noeud n tel que f(n)<=C*.

 COMMENT TROUVER LES HEURISTIQUES OPTIMALES?

• en assouplissant les conditions (ajoutant les actions)

• en travaillant avec des sous-problèmes

 HEURISTIQUES POUR LE JEU TAQUIN

• h1 - le nombre de pièces qui ne sont pas à leurs places

• soit (x1,y1), (x2,y2) deux positions sur la grille.


la distance de

Manhattan((x1,y1),(x2,y2))=l x1-x2 l + l y1 - y2 l

h2 = sommes sur toutes les pièces de la distance Manhattan entre la

position courante de la pièce et sa position finale dans l'état but
 HEURISTIQUES

ABSOLVER - un programme qui trouve des heuristiques pour les

problèmes relâchés

Il a trouvé la meilleures heuristique pour le jeu taquin et la première

heuristique intéressante pour le cube de Rubik.

si h1,...,hn sont admissible alors 


h = max{ h1,...,hn }

est admissible et domine chaque hi
HEURISTIQUES ADMISSIBLES A PARTIR DE SOUS-PROBLEMES

taquin 4 sur 4

remplacer les pièces 1,2,3,4 par une pièce unique *

Résoudre taquin avec l'état but

* * * *

5 6 7 8

9 10 11 12

13 14 15

Prendre comme la heuristique le nombre de coups minimal dans ce sous- problème.


Résoudre le taquin pour d'autres sous-problèmes similaires.

Constituer une base de données avec les sous-problèmes (pattern database).

Accélération 10000 par rapport à la distance Manhattan pour le taquin de 4 sur 4,

l'accélération de l'ordre d'un million pour le taquin de 5 sur 5.

HEURISTIQUES ADMISSIBLES A PARTIR DE SOUS-PROBLEMES

Heuristique de Gasching : on peut déplacer une pièce quelconque

sur une position vide. Comment calculer efficacement cette
heuristique?