Algorithmes de Recherche

Résolution de problèmes
Plan
• Agent de résolution de problèmes
• Stratégies de recherche
– Recherche non‐informée
• Largeur d’abord, profondeur d’abord, etc.
– Recherche informée
• Meilleur d’abord greedy, A*, algorithmes génétiques, etc.

1
Résolution de problèmes Agent de résolution de problèmes
1. Formulation d’un but : un ensemble d’états à atteindre.
2. Formulation du problème : les états et les actions à considérer.
3. Recherche de solution : examiner les différentes séquences d’actions menant à un
état but et choisir la meilleure.
4. Exécution : accomplir la séquence d’actions sélectionnée.
2
Résolution de problèmes Exemple
3
• On est à Arad et on veut aller à Bucharest

– But : être à Bucharest
– Problème :
• États : villes
• Actions : aller d’une ville à une autre.
– Solution : Une séquence de villes.
• Ex: Arad, Sibiu, Fagaras, Bucharest
• Environnement très simple
– statique, observable, discret et déterministe
4
Résolution de problèmes Formulation du problème
• État initial : l’état x dans lequel se trouve l’agent

– À (Arad)
• Actions : Une fonction S(x) qui permet de trouver l’ensemble des états successeurs, sous forme de pair
(action, successeur)
– S ( à (Arad)) = (Aller à (Sibiu), à (Sibiu)), etc.
• Test de but : un test afin de déterminer si le but est atteint
– But : {à (Bucharest)}
• Coût du chemin : une fonction qui assigne un coût à un chemin. Elle reflète la mesure de performance
de l’agent. La valeur est non‐négative.
5
Résolution de problèmes Abstraction
• Enlever des détails de la représentation.
– On ne parle pas de la radio, du paysage ou de la météo.
– On conserve le minimum nécessaire pour résoudre le problème d’aller à Bucharest.
• Une abstraction est valide si l’on peut développer toutes les solutions abstraites vers une solution
dans le monde réel.
• Sans abstraction, un agent ne peut rien faire, le monde est juste trop complexe. L’humain est
pareil aussi.
6
Résolution de problèmes Exemple de problème : 8‐puzzle
• États : ?
– Positions des huit tuiles dans les cases.
• Actions : ?
– Déplacement du trou: droite, gauche, haut, bas.
• Test de but : ?
– Un état qui correspond à l’état final.
• Coût du chemin : ?
– Chaque action coûte 1.
état initial état final
7
Résolution de problèmes Recherche de solutions dans un graphe
• Le web : chaque page est un sommet du graphe, chaque lien hypertexte est une arête entre deux
sommets.
• Un réseau ferroviaire : chaque gare est un sommet, les voies entre deux gares sont les arêtes. Idem
avec un réseau routier.
• Un réseau social : les sommets sont les personnes, deux personnes sont adjacentes dans ce graphe
lorsqu'elles sont amies".
Si la notion d'amitié n'est pas réciproque, le graphe est oriente.
La structure de graphe est en science de l'informatique une structure abstraite omniprésente.
8
Résolution de problèmes Recherche de solutions dans un graphe
9
Résolution de problèmes Stratégies de recherche
• Détermine l’ordre de développement des nœuds.
• Recherches non‐informées : Aucune information additionnelle. Elles ne peuvent pas dire si un
nœud est meilleur qu’un autre. Elles peuvent seulement dire si l’état est un but ou non.
• Recherches informées (heuristiques) : Elles peuvent estimer si un nœud est plus prometteur
qu’un autre.
10
Résolution de problèmes Évaluation des stratégies
• Complétude : Est‐ce que l’algorithme garantit de trouver une solution s’il y en a une ?
• Optimalité : Est‐ce que la stratégie trouve la solution optimale ?
• Complexité de temps : Combien de temps ça prend pour trouver une solution ?
• Complexité d’espace : Quelle quantité de mémoire a‐t‐on besoin ?
11
Résolution de problèmes Complexité
• Elle est exprimée en utilisant les quantités suivantes :
– b, le facteur de branchement: le nombre maximum de successeurs à un nœud.
– d, la profondeur du nœud but le moins profond.
– m, la longueur maximale d’un chemin dans l’espace d’états.
• Complexité en temps : le nombre de nœuds générés pendant la recherche.
• Complexité en espace : le nombre maximum de nœuds en mémoire.
12
Résolution de problèmes Stratégies de recherche non‐informées
• Largeur d’abord (Breath‐First Search)
• Profondeur d’abord (Depth‐First Search)
• Profondeur limitée (Depth‐limited)
• Profondeur itératif (Iterative deepening)
• Recherche bidirectionnelle (Bidirectional search)
13
Résolution de problèmes Largeur d’abord
• Développement de tous les nœuds au niveau i avant de développer les nœuds au niveau
i+1
• Implémenté à l’aide d’une file; les nouveaux successeurs vont à la fin.
14
Vous devez parcourir toutes les pages d'un site web. Les pages sont les sommets d'un graphe et un lien
entre deux pages est une arête entre ces deux sommets.
1. Dans le parcours en largeur, on utilise une file. On enfile le sommet de départ (on visite la page
index du site).
2. On visite les voisins de la tête de le (pages ciblées par la page de tête de file). On les enfile (en les
numérotant au fur et à mesure de leur découverte) s'ils ne sont pas déjà présents dans la file, ni
déjà passés dans la file.
3. On défile (c'est a dire : on supprime la tête de file).
4. On recommence au point 2 (tant que c'est possible, c'est a dire tant que la file n'est pas vide).
En d'autres termes, on traite toujours en priorité les liens des pages le plus tôt découvertes.
15
Parcourir en largeur le graphe ci-dessous a partir du sommet s :
16
17
Enfiler : passage en gris. Défiler : passage en noir.

L'ordre pour enfiler les voisins (ni gris, ni noirs) dépend de l'implantation.
18
19
20
21
22
23
24
25
26
27
28
29
30
31
function
Algorithme largeur d’abord
BREADTH-FIRST-SEARCH(problem) returns le nœud solution ou échec
nœud  NODE(problem.INITIAL)
if problem.is-GOAL(noeud.STATE.) then return nœud
frontier  a File, avec nœud comme element
reached  {problem.INITIAL}
while not Is-EMPTY(frontier) do
nœud  POP(frontier)
for each child in EXPAND(problem, nœud) do
s  child.STATE
if problem.IS-GOAL(s) then return child
if s is not in reached then
add s to reached
add child to frontier
return failure
32
Résolution de problèmes Propriétés de largeur d’abord
• Complétude : Oui, si b est fini

• Complexité en temps : +
• Complexité en espace : garde tous les nœuds en mémoire)
• Optimal : Non en général, oui si le cout des actions est le même pour toutes les actions
33
Résolution de problèmes Profondeur d’abord
• Développe le nœud le plus profond.

• Implémenté à l’aide d’une pile. Les nouveaux nœuds générés vont sur le dessus.
Ordre de visite : A-B-D-H-I-E-J-K-C

34
35
Vous devez parcourir toutes les pages d'un site web. Les pages sont les sommets d'un graphe et un
lien entre deux pages est une arête entre ces deux sommets.
1. Dans le parcours en profondeur, on utilise une pile. On empile le sommet de départ (on visite
la page index du site).
2. Si le sommet de la pile présente des voisins qui ne sont pas dans la pile, ni déjà passés dans
la pile :
• alors on sélectionne l'un de ces voisins et on l'empile (en le marquant de son numéro de
découverte),
• sinon on dépile (c'est a dire on supprime l’élément du sommet de la pile).
3. On recommence au point 2 (tant que la pile n'est pas vide). En d'autres termes, on traite
toujours en priorité les liens des pages les plus tard découvertes.
36
Parcourir en profondeur le graphe ci-dessous a partir du sommet s :
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
Résolution de problèmes Propriétés de profondeur d’abord
• Complétude : non, si la profondeur est infinie, s’il y a des cycles. Oui, si on évite les états
répétés ou si l’espace de recherche est fini.
• Complexité en temps : O() Très mauvais si m est plus grand que d. m est la profondeur max.
• Complexité en espace : O(bm), linéaire
• Optimal : Non
65
Résolution de problèmes Algorithme profondeur d’abord
DFS(G,v) ( v est le nœud ou commence la recherche )
Pile S  {}; ( commence avec pile vide )
for each nœud u
set visited[u] False;
push Sv;
while (S is not vide) do
u  pop S;
if (not visited[u]) then
visited[u]  True;
for each unvisited neighbour w of u
push Sw;
end if
end while
66
Résolution de problèmes Stratégies de recherche informée
• Les stratégies de recherche non‐informée ne sont pas très efficaces dans la plupart des cas.
Elles sont aveugles car elles ne savent pas si elles s’approchent du but.
• Les stratégies de recherche informée utilisent une fonction d’estimation (heuristique) pour
choisir les nœuds à visiter.
67
Résolution de problèmes Stratégies de recherche informée
• Meilleur d’abord glouton (Greedy best‐first)

• A*
• Algorithme à mémoire limitée
– IDA*, RDFS et SMA*
• Escalade (Hill‐climbing)
• Recuit simulé (Simulated annealing)
• Recherche local en faisceau (local beam)
• Algorithmes génétiques
68
Résolution de problèmes Meilleur d’abord
• L’idée est d’utiliser une fonction d’évaluation qui estime l’intérêt des nœuds et de développer le nœud
le plus intéressant.
• Le nœud à développer est choisi selon une fonction d’évaluation f(n).
• Une composante importante de ce type d’algorithme est une fonction heuristique h(n) qui estime le
coût du chemin le plus court pour se rendre au but.
• Deux types de recherche meilleur d’abord: A* et meilleur d’abord glouton.
69
Résolution de problèmes Meilleur d’abord glouton
• f(n) = h(n) = distance à vol d’oiseau
• Choisit toujours de développer le nœud le plus proche du but.
70
71
Résolution de problèmes Heuristique du vol d’oiseau
• Soit h(n) = distance à vol d’oiseau pour la carte de Roumanie.
Arad 366 Mehadia 241

Bucharest 0 Neamt 234
Craiova 160 Ordea 380
Dobreta 242 Pitesti 100
Efrok 161 Rimnica Vilcea 193
Fagaras 176 Sibiu 253
Giurgiu 77 Timisoara 329
Hirsova 151 Urzoceni 80
Lasi 226 Vaslui 199
Lugo 244 Zerind 374
72
Résolution de problèmes Exemple meilleur d’abord glouton
73
Résolution de problèmes Propriétés meilleur d’abord glouton
• Complétude : Non, elle peut être prise dans des cycles. Oui, si l’espace de recherche est fini avec
vérification des états répétés (pas de cycles).
• Complexité de temps : O(bm), mais une bonne fonction heuristique peut améliorer grandement la
situation.
• Complexité d’espace : O(bm), elle retient tous les nœuds en mémoire.
• Optimale : non, elle s’arrête à la première solution trouvée.
74
F
Algorithme meilleur d’abord glouton
function BEST-FIRST-SEARCH(problem, f) returns a solution node or failure
node NODE(STATE=problem.INITIAL)
frontier  a priority queue ordered by f, with node as an element
reached  a lookup table, with one entry with key problem.INITIAL and value node
while not Is-EMPTY (frontier) do
node  POP(frontier)
if problem.IS-GOAL(node.STATE) then return node
for each child in EXPAND(problem, node) do
s  child STATE
if s is not in reached or child. PATH-COST < reached[s].PATH-COST then
reached[s]  child
add child to frontier
return failure
function EXPAND(problem, node) yields nodes

s node.STATE
for each action in problem.ACTIONS(s) do
s'  problem.RESULT(s, action)
cost  node.PATH-COST + problem.ACTION-COST(s, action, s')
yield NODE(STATE=s', PARENT=node, ACTION=action, PATH-COST=cost)
75
Résolution de problèmes Algorithme A*
• Fonction d’évaluation: f(n) = g(n) + h(n)
– g(n): coût du nœud de départ jusqu’au nœud n
– h(n): coût estimé du nœud n jusqu’au but
– f(n): coût total estimé du chemin passant par n pour se rendre au but.
• A* utilise une heuristique admissible, c’est‐à dire h(n) ≤ h*(n), où h*(n) est le véritable coût
pour se rendre de n au but.
• Demande aussi que h(n) ≥ 0 et que h(G) = 0 pour tous les buts G.
76
Résolution de problèmes Heuristique du vol d’oiseau
• Soit h(n) = distance à vol d’oiseau pour la carte de Roumanie. Cette heuristique est admissible
Arad 366 Mehadia 241

Bucharest 0 Neamt 234
Craiova 160 Ordea 380
Dobreta 242 Pitesti 100
Efrok 161 Rimnica Vilcea 193
Fagaras 176 Sibiu 253
Giurgiu 77 Timisoara 329
Hirsova 151 Urzoceni 80
Lasi 226 Vaslui 199
Lugo 244 Zerind 374
77
Résolution de problèmes Heuristique du vol d’oiseau (2)
• Soit h(n) = distance à vol d’oiseau pour la carte de Roumanie.
78
Résolution de problèmes Exemple A*
79
Résolution de problèmes Propriétés de A*
• Complétude : oui
• Complexité de temps : exponentielle selon la longueur de la solution (dépendent de l’espace
des états‐‐ ),
• Complexité en espace : elle garde tous les nœuds en mémoire: exponentielle selon la longueur
de la solution .
• Optimale : Oui
Habituellement, on manque d’espace longtemps avant de manquer de temps.
80
Résolution de problèmes Exercice
• Largeur d’abord
• Profondeur d’abord
• Meilleur d’abord glouton
• A*
Dans quel ordre les nœuds sont développés pour chacun des algorithmes?
81

Algorithmes de Recherche

Transféré par

Informations du documentcliquez pour développer les informations du document

Informations du documentcliquez pour développer les informations du document

Droits d'auteur :

Formats disponibles

Algorithmes de Recherche

Transféré par

Informations du document

Copyright

Formats disponibles

Partager ce document

Partager ou intégrer le document

Options de partage

Avez-vous trouvé ce document utile ?

Ce contenu est-il inapproprié ?

Droits d'auteur :

Formats disponibles

Algorithmes de Recherche

Transféré par

Droits d'auteur :

Formats disponibles

Résolution de problèmes

• Agent de résolution de problèmes

• Largeur d’abord, profondeur d’abord, etc.

• Meilleur d’abord greedy, A*, algorithmes génétiques, etc.

1. Formulation d’un but : un ensemble d’états à atteindre.

2. Formulation du problème : les états et les actions à considérer.

3. Recherche de solution : examiner les différentes séquences d’actions menant à un

état but et choisir la meilleure.

4. Exécution : accomplir la séquence d’actions sélectionnée.

• On est à Arad et on veut aller à Bucharest

• État initial : l’état x dans lequel se trouve l’agent

• Enlever des détails de la représentation.

– On ne parle pas de la radio, du paysage ou de la météo.

– On conserve le minimum nécessaire pour résoudre le problème d’aller à Bucharest.

dans le monde réel.

état initial état final

La structure de graphe est en science de l'informatique une structure abstraite omniprésente.

• Détermine l’ordre de développement des nœuds.

• Recherches non‐informées : Aucune information additionnelle. Elles ne peuvent pas dire si un

• Optimalité : Est‐ce que la stratégie trouve la solution optimale ?

• Complexité de temps : Combien de temps ça prend pour trouver une solution ?

• Complexité d’espace : Quelle quantité de mémoire a‐t‐on besoin ?

• Elle est exprimée en utilisant les quantités suivantes :

– b, le facteur de branchement: le nombre maximum de successeurs à un nœud.

– d, la profondeur du nœud but le moins profond.

– m, la longueur maximale d’un chemin dans l’espace d’états.

• Complexité en temps : le nombre de nœuds générés pendant la recherche.

• Complexité en espace : le nombre maximum de nœuds en mémoire.

• Largeur d’abord (Breath‐First Search)

• Profondeur d’abord (Depth‐First Search)

• Profondeur limitée (Depth‐limited)

• Profondeur itératif (Iterative deepening)

• Recherche bidirectionnelle (Bidirectional search)

• Implémenté à l’aide d’une file; les nouveaux successeurs vont à la fin.

3. On défile (c'est a dire : on supprime la tête de file).

Enfiler : passage en gris. Défiler : passage en noir.

• Complétude : Oui, si b est fini

• Complexité en espace : garde tous les nœuds en mémoire)

• Développe le nœud le plus profond.

Ordre de visite : A-B-D-H-I-E-J-K-C

Parcourir en profondeur le graphe ci-dessous a partir du sommet s :

répétés ou si l’espace de recherche est fini.

• Complexité en espace : O(bm), linéaire

choisir les nœuds à visiter.

• Meilleur d’abord glouton (Greedy best‐first)

• Le nœud à développer est choisi selon une fonction d’évaluation f(n).

coût du chemin le plus court pour se rendre au but.

• Deux types de recherche meilleur d’abord: A* et meilleur d’abord glouton.

• f(n) = h(n) = distance à vol d’oiseau

• Choisit toujours de développer le nœud le plus proche du but.

Arad 366 Mehadia 241

vérification des états répétés (pas de cycles).

• Complexité d’espace : O(bm), elle retient tous les nœuds en mémoire.

• Optimale : non, elle s’arrête à la première solution trouvée.

function EXPAND(problem, node) yields nodes

• Fonction d’évaluation: f(n) = g(n) + h(n)

– g(n): coût du nœud de départ jusqu’au nœud n

– h(n): coût estimé du nœud n jusqu’au but