Résolution de problèmes en IA:

Les algorithmes de recherche

Salima Hassas
Université Lyon1

Ce cours réutilise les transparents de cours de Mr. Pelligrini (Univ. Genève)

 La résolution de problème
 Problème
Trouver une application entre l’ensemble des lettres et des chiffres qui vérifie
l’opération
 Représenter le problème

SEND - Ensembles L={S,E,N,D,R,O,M,Y, r1,r2,r3,r4}, C={0,.,9}

MORE - contraintes (permettant de vérifier l’opération)
M O NEY  Etat initial

- D=0,1 ou 2 ou,..9 , E=0, 1, ..,9 etc

- M=1, ou, ..9, idem pour S
- r1, r2, r3, r4= 0 ou 1

 Etat final : {M=1, O=0, S=9, R=8, D=7, N=6, E=5, Y=2}

2
 La résolution de problème
..
État initial

Espace d’états (du problème)

- Successeur : état suivant État final
- Actions: Transition entre états ..
Algorithme de recherche : trouver le chemin de l’état initial à l’état final

3
Algorithmes de recherche
Autre exemple: le taquin-8

4
Algorithmes de recherche
Autre exemple: le taquin-8

5
Algorithmes de recherche

6
Algorithmes de recherche
 Les algorithmes de recherche de la solution
fournissent des mécanismes de résolution généraux
et efficaces.

 Formalisation de la résolution par recherche d’un

problème:
 l’état initial : point de départ dans le processus de recherche
 l’ensemble d’opérateurs (actions) : transitions d’1 état à
l’autre
 l’état solution (final) : le but de la recherche

7
 Algorithmes de recherche
• Espaces d’états =
•Abstraction du monde réel
• Décrit par l’état initial et l’ensemble des opérateurs

• Un chemin dans l’espace d’états=

• une suite d’états résultant de l’application valide des opérateurs
• Il peut aussi être décrit par l’état de départ et la séquence
des opérateurs qui a produit la suite d’états

8
 Algorithmes de recherche
• Algorithme de recherche : consiste à trouver un chemin qui
part de l’état initial et arrive à l`état final (solution).

• Au cours de l’algorithme, un état parcouru est testé par

une fonction appelée fonction test-but, pour déterminer si
c’est un état solution

• Il peut exister plusieurs chemins menant à l'état solution.

Dans ce cas : déterminer meilleur chemin
(critère de performance) => fonction coût-chemin

• Solution du problème = chemin menant à l`état solution.

⇒ Etat initial + séquence d’opérations valides vers l’état solution

9
 Algorithmes de recherche
Plus formellement

10
 Algorithmes de recherche
Un algorithme de recherche doit réaliser une exploration de
l’espace d`états d’une manière systématique et contrôlée.

On distingue deux classes d'algorithmes de recherche :

• Algorithmes non informés ou « aveugles » :
==> recherche exhaustive, aucune information concernant
la structure de l’espace d`états pour optimiser la recherche

• Algorithmes informés ou heuristiques =

==> utilisent des sources d`information supplémentaires
==> meilleures performances

11
 Algorithmes de recherche
Caractéristiques - critères d’évaluation

• Optimalité – trouver la meilleure solution (cas plusieurs solutions)

• Complétude – garantir de trouver la solution si elle existe
• Complexité en temps – estimation du temps nécessaire pour
résoudre le problème
• Complexité en espace – estimation de l’espace mémoire nécessaire
pour résoudre le problème.

Les deux complexités, en temps et en espace, sont exprimées

comme des fonctions de la dimension du problème.

12
 Algorithmes de recherche
Définir un problème de recherche

• Espace d'états

• État initial

• Fonction "successeur »

• Test-solution

• Coût du chemin

13
 Algorithmes de recherche
• Espace d'états
– chaque état est une représentation abstraite de
l'environnement
– l'espace d’état est discret
• État initial

• Fonction « successeur »

• Test-solution

• Coût du chemin

14
 Algorithmes de recherche
Définir un problème de recherche

• Espace d'états

• Etat initial
– habituellement l’état courant
– parfois un ou plusieurs états hypothétiques
• Fonction "successeur »

• Test-solution

• Coût du chemin

15
 Algorithmes de recherche
Définir un problème de recherche

• Espace d'états

• État initial
• Fonction "successeur"
– fonction : [ Etat sous-ensemble d’états ]
– une représentation abstraite des actions possibles

• Test-solution

• Coût du chemin

16
 Algorithmes de recherche
Définir un problème de recherche

• Espace d'états

• État initial

• Fonction "successeur »
• Test-solution
– habituellement une condition à satisfaire
– parfois la description explicite d'un état

• Coût du chemin

17
 Algorithmes de recherche
Définir un problème de recherche

• Espace d'états

• État initial

• Fonction "successeur »

• Test-solution

• Coût du chemin
– fonction : [ chemin nombre positif ]
– habituellement: coût du chemin = somme des coûts de ses étapes
– Ex: # déplacements de la plaquette "vide » (Taquin)

18
Exemple1 : Voyage en Roumanie
 En vacance en Roumanie à Arad, L’avion quitte
Bucharest le lendemain

 Formulation:
 But:
 être Bucharest
 Problème:
 Etats : les différentes villes possibles
 Actions: se déplacer d’une ville à une autre
 Solution:
 Une suite de villes : Arad, Sibiu, Fagars, Bucharest

19
Exemple1 : Voyage en Roumanie

20
 Exemple 2: L’aspirateur
 Le monde consiste en 2 positions:
 pièce gauche, pièce droite
 Chaque pièce peut-être poussièreuse
 L’aspirateur est dans l’une des 2
pièces
 Il y’a au total :
 8 états possibles
 3 actions possibles: aller à gauche,
aller à droite, aspirer

21
Exemple 2: L’aspirateur
 L'aspirateur est dans l'une des 2 pièces

 Formulation
 But : éliminer toute poussière
 Problème:
 Etats: les 8 états possibles du problème
 Actions: se déplacer à gauche, se déplacer à droite, aspirer
 Solution
 Être dans l’état 7 ou 8

22
 Types de problèmes
 Problèmes à état  Problèmes contingents
unique:  Effet conditionnel des
actions
 Etat exact connu
 Perception limitée
 Effet des actions connu
 Algorithmes plus
complexes nécessitant
 Problèmes à états de la planification
multiples:  Problèmes d’exploration
 Un ensemble parmi  L’exécution révèle les
plusieurs ensembles états
d’états
 besoin d’expérimenter
 Effets des actions pour trouver la solution
connus
 Le plus difficile

23
Types de problèmes
 Déterministe, totalement observable => problème à
état unique
 Déterministe, inaccessible=> problème à états
multiples
 Non déterministe, inaccessible=> problème
contingent
 Besoin de perception durant l’exécution
 Solution à une structure d’arbre
 Souvent mélange entre recherche et exécution
 Espace d’états inconnu => problème exploratoire
(« online »)

24
 Exemple: aspirateur
Etat unique
– état initial: #5
– solution ??

25
 Exemple: aspirateur
Etat unique
– état initial: #5
– solution ??
[aller à droite, aspirer]

26
 Exemple: aspirateur
Etat unique
– état initial: #5
– solution ??
[aller à droite, aspirer]
Etats multiples
– état initial {1,2,3,4,5,6,7,8}
– aller à droite produit {2,4,6,8}
– solution ??

27
 Exemple: aspirateur
Etat unique
– état initial: #5
– solution ??
[aller à droite, aspirer]
Etats multiples
– état initial {1,2,3,4,5,6,7,8}
– aller à droite produit {2,4,6,8}
– solution ??
[aller à droite, aspirer, aller à gauche, aspirer]

28
 Exemple: aspirateur
Etat unique
– état initial: #5
– solution ??
[aller à droite, aspirer]
Etats multiples
– état initial {1,2,3,4,5,6,7,8}
– aller à droite produit {2,4,6,8}
– solution ??
[aller à droite, aspirer, aller à gauche, aspirer]
Contingent
– état initial: #5
– perception locale: poussière
– solution ??

29
 Exemple: aspirateur
Etat unique
– état initial: #5
– solution ??
[aller à droite, aspirer]
Etats multiples
– état initial {1,2,3,4,5,6,7,8}
– aller à droite produit {2,4,6,8}
– solution ??
[aller à droite, aspirer, aller à gauche, aspirer]
Contingent
– état initial: #5
– perception locale: poussière
– solution ??
[aller à droite, si poussière alors aspirer]

30
 Exemple: aspirateur (état unique)

• Etats:
- entiers indiquant la position du robot et de la poussière
(ignorer la quantité de poussière)
• Opérateurs:
- aller à gauche (L), aller à droite (R), aspirer (S), ne rien faire (NoOp)
• Test: plus de poussière nulle part
• Fonction-coût: chaque action coûte 1 unité, (0 pour NoOp)
31
 Exemple: Taquin-8

• Etats:
- numéros des positions des plaquettes (ignorer les positions intermédiaires)
• Opérateurs:
- déplacer la case vide à gauche (L), à droite (R), en haut (U), en bas (D)
• Test: état courant = état final
• Fonction-coût: chaque déplacement de la case vide vaut 1,
coût total = nombre total de déplacements de la case vide
• Remarque: solution optimale pour Taquin-n est NP-difficile

32
Exemple: problème des 8 reines
Placer 8 reines sur un échiquier de façon à ce qu'il n'y ait aucune
attaque mutuelle (c.à.d. n'occupe la même ligne, la même colonne ou
la même diagonale)

33
 Exemple: problème des 8 reines
1ère formulation

• États: n'importe quel arrangements de 0 à 8 reines sur l'échiquier

• État initial: aucune reine sur l'échiquier

• Fonction "successeur": ajouter une reine sur n'importe quelle case

• Test-solution: 8 reines placées, pas d'attaque.

==> 648 états avec 8 reines

34
 Exemple:
problème des 8 reines
2ème formulation

• États: n'importe quel arrangements de k = 0 à 8 reines sur les k

colonnes de gauche de l'échiquier sans attaque

• État initial: aucune reine sur l'échiquier

• Fonction "successeur": ajouter une reine sur n'importe quelle case de

la première colonne vide à partir de la gauche sans qu'elle ne soit
attaquée par les autres reines déjà placées

• Test-solution: 8 reines correctement placées sur l'échiquier.

==> 2,067 états

35
 Problèmes réels
• Recherche de parcours
– itinéraires automatiques, guidage routier, planification de routes
aériennes, routage sur les réseaux informatiques, …

• Configuration de circuits VLSI

– placement de millions d'éléments sur un chip déterminant pour le
fonctionnement efficace du circuit

• Robotique
– assemblage automatique, navigation autonome, …

• Planification et ordonnancement
– horaires, organisation de tâches, allocation de ressources, ...

36
Typologie des problèmes de recherche?
 Tous les problèmes qui peuvent être décrits par
 un ensemble fini d’états,
 un ensemble fini d'actions,
 un sous-ensemble d’ états initiaux et finaux,
 une relation "successeur" définie sur l'ensemble des états et des
actions dans l'ensemble des états,
 et une fonction de coût positive.
 Principalement les problèmes dont la solution s'exprime en termes
de chemin dans des graphes finis.

 Principalement les problèmes dont la solution s'exprime en

termes de chemin dans des graphes finis

37
Algorithmes de recherche aveugles

38
Problème général de recherche

39
Critères d’évaluation

40
Critères d’évaluation

41
Algorithme général de recherche

42
Exemple

43
Concepts de base pour la recherche

44
Etats vs Noeuds

45
Etats vs Noeuds

46
File d’attente

47
Algorithme général de recherche

48
Stratégies de recherche

49
Exemple: taquin-8

50
Exemple: taquin-8

51
Stratégies aveugles

52
Recherche en largeur

53
Recherche en largeur

54
Recherche en largeur (Propriétés)

55
Algorithme de recherche en coût
uniforme

56
Algorithme de recherche en coût
uniforme

57
Algorithme de recherche en coût
uniforme

58
Algorithme de recherche en coût
uniforme

59
Algorithme de recherche en coût
uniforme - Propriétés

60
Algorithme de recherche en Profondeur

61
Algorithme de recherche en Profondeur

62
Algorithme de recherche en profondeur -
Propriétés

63
Algorithme de recherche en profondeur
limitée

64
Algorithme de recherche en profondeur
limitée - Propriétés

65
Algorithme de recherche par
approfondissement itératif (IDS)

66
Algorithme de recherche par
approfondissement itératif (IDS)

67
Algorithme de recherche par
approfondissement itératif (IDS)
Approfondissement itératif L = 0

68
Algorithme de recherche par
approfondissement itératif (IDS)
Approfondissement itératif L = 1

69
Algorithme de recherche par
approfondissement itératif (IDS)
Approfondissement itératif L = 2

70
Propriétés de la recherche par
approfondissement itératif

71
Algorithme de recherche bi-
directionnelle

72
Stratégie bi-directionnelle

73
Propriétés de la recherche bi-
directionnelle

74
Comparaison des algorithmes de
recherche aveugles

75
Algorithmes de recherche heuristique

76
Méthodes de recherche heuristique

77
Fonction heuristique

78
Exemples de fonctions heuristiques

79
Best-First search

80
Best-First search

81
Greedy search

82
Exemple 1: voyage en Roumanie

83
Exemple 1: voyage en Roumanie

84
Exemple 2: puzzle-8

85
Exemple 2: puzzle-8

86
Propriétés de Greedy search

87
Greedy search-Commentaires

88
Fonction heuristique admissible

89
Fonction heuristique admissible:
Exemple

90
Algorithme A*

91
Exemple: voyage en Roumanie

92
Exemple: puzzle-8

93
Complétude et optimalité de A*

94
Propriétés de A*

95