Représentation et résolution de problèmes :
Intelligence artificielle II

Philippe Muller
IRIT

dernière mise à jour: Février 2003

Plan du cours :
Objectif : Introduire les méthodes de recherches arborescentes informées permettant de trouver une "bonne" solution à un problème à forte combinatoire et ceci en un temps acceptable.
Thèmes des bureaux d'étude (en Camel)
Ouvrages conseillés :
Résolution de problèmes et Intelligence artificielle
c'est quoi ?
Le match homme-machine
Les ordis c'est bon pour Les gens sont meilleurs pour
l'arithmétique perception, vision, parole, etc.
manipuler des chaînes de caractères l'action
les tâches répétitives comprendre et produire des phrases en langage naturel
faire ce qu'on leur dit apprendre par exemples, observation,...
  le raisonnement de sens commun
  les jeux
  les mathématiques et la logique formelle
  la conception et l'analyse (ingénierie, diagnostic médical, architecture, planification, etc)

Souvent, ce qui est facile pour l'humain et difficile pour la machine (et réciproquement).

Les domaines couverts par l'IA
raisonnement démonstration automatique, planification
jeux  
apprentissage  
langage interfaces, recherche d'informations
vision extraction, reconnaissances de formes, surveillance
diagnostic pannes, diagnostic médical
base de données base de connaissances
Domaines concernés
Une méthodologie commune ?
  1. modélisation d'un domaine ou d'un problème particulier (mathematique ou logique)
  2. représentation
  3. résolution (algorithmique, raisonnement, optimisation)
  4. évolution
L'étape (3) nécessite des recherches dans des ensembles de possibilités très grands → ``recherche opérationnelle''. La première partie du cours concernait le point 1 et en partie 2. Cette deuxième partie concerne les points 2 et 3.
Un exemple: chercher son chemin

Un exemple: chercher son chemin
Un exemple: chercher son chemin
Un exemple: chercher son chemin
Un exemple: chercher son chemin
Un autre exemple ? les missionnaires et les cannibales
Les missionnaires et les cannibales: exploration
Les missionnaires et les cannibales: solution
Les missionnaires et les cannibales: l'espace de recherche

Complexité algorithmique
Analyse des algorithmes : évaluation des ressources consommées par les algorithmes, en temps d'éxécution et en espace mémoire.

→ moyen de comparaison des algorithmes = ``complexité'' des algorithmes.

le temps de calcul d'un programme dépend :
Calculabilité et complexité algorithmique
Questions :
• comment l'évaluer indépendemment de la machine ?
• comment tenir compte des données différentes ?
→ la taille des données d'entrée est un paramètre du temps de calcul.

On notera T(n) le temps de calcul d'un algorithme en fonction de la taille des données d'entrées (variable suivant les instances du problème traité).

Ex: pour trier une liste, n=taille de la liste. Pour rester indépendant de la machine, on considère que les opérations élémentaires sont de même temps, et on s'intéresse à l'ordre de grandeur du temps de calcul, et à son évolution en fonction de la taille des données.
En général on s'intéresse au temps maximum pour un n donné (le pire cas, un majorant) ou bien au temps moyen estimé (nécessite une analyse statistique selon la forme de l'entrée). notions à retenir:
- l'ordre de grandeur du temps de calcul.
- son évolution
- le pire cas
Taux de croissance
On évalue le temps de calcul en ordre de grandeur, notion mathématique:
T(n) = O(f(n))    ssi   
 
lim
n→ ∞
T(n)
f(n)
= cte
Cela élimine les facteurs constants (2n2 croît comme n2 et les termes d'ordre différents. On dira donc, plutôt que T(n)=O(2n2) ou T(n)=O(n2+3n), que T(n)=O(n2).

Plus le taux de croissance est d'ordre inférieur, meilleur est l'algorithme, mais pour des petites tailles de problèmes le temps de calcul peut être meilleur pour un taux supérieur (ex. tant que n<20, 100n2 est moins bon que 5n3.

Déprimant
Si une opération prend une microseconde, voici un tableau donnant les ordres de grandeurs des temps de calcul suivant la taille n du problème, pour différents taux de croissance (tableau dans ??).

T(n) / n 10 20 30 40 50 60
n 10µs 20 µs 30 µs 40 µs 50 µs 60 µs
log n 1µs 1.3 µs 1.5 µs 1.6 µs 1.7 µs 1.8 µs
n log n 10µs 26 µs 44 µs 64 µs 85 µs 107 µs
n2 100µs 400 µs 900 µs 1.6ms 2.5 ms 3.5 ms
n3 1ms 8 ms 27 ms 64 ms 125 ms 216 ms
n5 0.1s 3.2s 24.3s 1.7 mn 5.2 mn 13 mn
2n 1ms 1s 18mn 13jours 36 ans 366 siècles
3n 59ms 58 mn 6 mn 3855 siècles 2.108 siècles 1.3.1013 siècles

NB: l'âge de l'univers est estimé à 108 siècles.
Encore plus déprimant
Impact des progrès technologiques: si aujourd'hui on peut résoudre un problème de taille N en temps raisonnable, quelle est la taille du problème que l'on peut résoudre si les machines vont 100 fois ou 100 fois plus vite ? Dans le cas linéaire on va évidemment traiter des problèmes 100 et 1000 fois plus gros. Pour le reste... N=taille du problème qu'on peut résoudre aujourd'hui

T(n) aujourd'hui si 100 fois plus vite si 1000 fois plus vite
n N 100N 1000N
n2 N 10N 32N
n3 N 4.6N 10N
n5 N 2.5N 4N
2n N N + 7 N + 10
3n N N + 4 N + 6
Analyse d'algorithmes : Algorithmes itératifs
Exemple: tri à bulle.



Résultat = O(n2)

Exercice : tri par selection:
Algorithmes récursifs
Exemple : le tri par fusion (mergesort) d'une liste de n=2m nombres.

En supposant que le partage et la fusion sont en O(n), on estime un majorant :
T(n)≤ c1 si n = 1
T(n)≤ 2T(n/2)+c2n si n > 1

Pour résoudre les équations récurrentes classiques : la solution générale de T(n)=anb + c*T(n/2) Résultat tri fusion: O(nlog n)

Pour les autres cas:
Exercices
  1. fibonacci doublement récursif (indice: a*(3/2)n ≤ fib(n) ≤ b*(5/2)n)
  2. fibonacci récursif terminal
  3. puissance efficace (avec resursif pair sur n div 2) solution subtile en fonction codage base 2 (et resultat est log2 n)
  4. recherche nb occurences chaînes dans sous-chaînes
Complexité théorique
Au delà des algorithmes : classification des problèmes. Il peut y avoir plusieurs algorithmes qui résolvent un problème : on va alors caractériser les problèmes en fonction des algorithmes que l'on peut leur appliquer.

Exemples de problèmes : On peut diviser les problèmes en trois grandes catégories après ce que l'on a déjà vu (n étant la dimension des données d'entrées) : Les plus sympathiques sont bien sûr les premiers...

Pour évaluer ces complexités, il faut un modèle plus rigoureux et uniformisé de machine. La Machine de Turing est l'exemple d'une machine idéalisé réalisant des calculs sur des symboles qui permet de montrer la complexité exacte d'un algorithme. Par ailleurs on peut aussi s'en servir pour montrer comment ramener un problème à un autre problème.
La machine de Turing
NB: Turing : mathématicien, travaux sur entre autres la notion de calculabilité d'une fonction. La machine de turing est une idéalisation d'un processus de calcul mécanisé. Elle consiste en : Un algorithme est la définition exacte du comportement de l'automate en fonction du ruban. Sa complexité en temps est le nombre d'opérations qu'il doit effectuer avant de terminer avec succès.
La machine de Turing
On distingue deux sortes de machine de Turing:
déterministe
à chaque instant il est dans un certain état et l'action qu'il effectue ne dépend que de cet état. (correspond +/- à l'ordinateur moderne idéalisé)
non déterministe
il existe une instruction de choix non déterministe entre deux états pour déterminer l'état suivant.
Un algorithme non déterministe accepte un donnée s'il termine avec succès pour au moins un calcul possible. Sa complexité en temps est la longueur du plus petit calcul qui accepte la donnée.
Exemple


Un autre exemple
L'exemple de SAT
-- algo déterministe stupide : tester toutes les instanciations des n variables propositionnelles (O(2n)) et vérifier la formule (en O(m), taille de la formule)
-- algo non déterministe : pour toute variable xi, le choix est entre affecter la variable à vrai ou l'affecter à faux. Quand c'est fini, on teste la formule (si vrai alors succès).

Donc l'algo non déterministe est < C1*n+C2*m donc en O(m).

En fait l'algo non-dét. est similaire en complexité à celui, déterministe, consistant à vérifier qu'une instanciation du problème est solution (→ ``vérification'').


Autre problème: comment ramener un problème d'optimisation à un problème soluble par la MT ? (la MT résoud des problèmes de ``reconnaissance'')
sur ex. du voyageur de commerce :
reconnaissance
existe-t-il un circuit de longueur ≤ c donné.
optimisation
trouver le circuit optimal
valeur optimale
trouver seulement la longueur du circuit optimal
témoin
trouver un circuit de longeur ≤ c donné
complexité de rec≤ témoin,val. optimale ≤ optimisation

Catégories de problèmes
La classe P est la classe des problèmes qui admettent un algorithme déterministe avec un temps d'éxécution polynomial en fonction de la taille du ruban d'entrée.

La classe NP est la classe des problèmes qui admettent un algorithme non-déterministe avec un temps d'éxécution polynomial en fonction de la taille du ruban d'entrée.

Attention: NP veut donc dire ``non-deterministe polynomial'' et pas ``non polynomial''.

La confusion est d'autant plus facile que les ordinateurs étant jusqu'à présent uniquement déterministes, les problèmes de NP sont résolus par des algos déterministes non-polynomiaux.

On a donc de façon évidente P ⊆ NP.

La question à 1 million de $ est :
tab a-t-on NP = P ?
Question ouverte (et ce malgré des décennies d'efforts à la recherche d'algo polynomiaux).
NP complétude
retour sur SAT : SAT est dans NP

et il a étémontré (Cook, 1971) que :
P = NP ⇔ SAT ∈ P

SAT est un ``prototype'' des problèmes de NP.

il a été prouvé en fait que tout problème de NP pouvait se ramener à SAT en temps polynomial.

On dit alors que SAT est NP-complet → tout un ensemble de problèmes de NP sont NP-complet.

Un problème est NP-complet
s'il est dans NP et si tout problème de NP lui est réductible en temps pôlynomial.

exemple de pbs NP complets: Il existe bien d'autres classes de complexité, mais ca sera pour une autre fois....

en IA et recherche op: NP
Maîtriser l'explosion combinatoire
quand on n'a pas le choix... pourquoi arrive-t-on à cette différence théorie-pratique ? → le problème du pire cas: rare sur certains cas (le pire cas donne image faussée de la résolution, mais on aime bien être paré...).

problème aussi de la précision voulue...

la clé est donnée par Calvin & Hobbes :
...the key to happiness is to lower your expectations to the point where they are already met.
Représentation de la connaissance : éléments de théorie des graphes
Définition

Graphe dirigé G = (N,A)
N est un ensemble de noeuds (ou sommets)
A est un ensemble d'arêtes, A ⊆ N × N
(v,w)∈ A est une arête de v à w (les extrémités de l'arête).
Un graphe est donc une relation binaire sur l'ensemble N. On représente couramment un graphe par un schéma du type de la figure 1.


Figure 1: Représentation graphique d'un graphe

L'ordre du graphe est son nombre de noeuds.

Deux sommets sont dits adjacents s'ils sont reliés par une arête.

Un graphe simple est le graphe d'une relation irréflexive (aucun noeud n'est relié à lui-même), symétrique.

Graphe non dirigé (i,j)∈ A → (j,i)∈ A
c'est un graphe pour lequel l'orientation n'a pas d'importance (on représente tout lien par un lien simple).

Graph complet
On appelle degré d'un sommet le nombre d'arêtes dont ce sommet est une extrémité.

Si tous les sommets d'un graphe ont le même degré k, le graphe est dit k-régulier.

Pour un graphe orienté, on définit le degré entrant (d+) et le degré sortant (d-) d'un noeud.

Un graphe simple d'ordre n qui est (n-1)-régulier est dit complet. Deux sommets quelconques sont alors adjacents.
Propriétés
• Pour un graphe non orienté (N,A) :
 
∑
x∈ N
d(x)= 2 |A|
• Pour un graphe orienté (N,A) :
 
∑
x∈ N
d+(x)=
 
∑
x∈ N
d-(x)= |A|

• Un graphe simple a au plus n(n-1)/2 arêtes.

Sous-graphe soit un graphe G=(N,A), N'⊆ N, A'⊆ A. G'=(N',A') est un sous-graphe de G si pour tout arête de A', les extrémités de l'arête dans G sont dans N'.
Parcours dans les graphes
Chemin Un chemin entre deux arêtes v et w d'un graphe (N,A) est une suite C=(v,u1,...,un,w) de noeuds de N tels que (v,u1)∈ A, (ui,ui+1)∈ A et (un,w)∈ A.

Si v=w, le chemin C est fermé.
Si ∀ i,j ui≢ uj, le chemin est simple.
Un cycle est un chemin fermé simple.

Fermeture transitive la fermeture transitive d'un graphe dirigé G=(N,A) est un graphe dirigé G*=(N,A*) tel que : (v,w) ∈ A* ↔ il y a un chemin de v à w dans G

Graphe non dirigé connexe ∀ i,j ∈ N , ∃ un chemin de i à j


composante connexe d'un graphe non dirigé: sous-graphe connecté maximal

composante fortement connexe idem pour graphe orienté

graphe fortement connexe graphe dirigé connexe : il existe un chemin pour toute paire de noeuds (u,v), u et v distincts (de u à v et de v à u).
Exemple : vérification de la forte connexité d'un graphe de rues


Figure 2: Plan de rues

Arbres
Un arbre est un graphe connexe sans cycle.

Un arbre de n noeuds a donc exactement n-1 arêtes.

Tout graphe connexe contient un graphe partiel (N,A'), avec A'⊆ A, qui est un arbre. On dit que l'arbre est un arbre recouvrant du graphe (en anglais spanning tree).

Un arbre pointé est un arbre où on a distingué un sommet qcq. Ce sommet est la racine de l'arbre.

Pour un graphe orienté, la racine de l'arbre est un noeud qui n'a pas d'arcs entrants (il est unique).

Une feuille est un noeud de degré 1 (graphe orienté : uniquement un arc entrant)
Explorations
On appelle exploration ou parcours d'un graphe un procédé déterministe qui permet de choisir un sommet à partir de l'ensemble des sommets déjà visités de manière à passer par tous les sommets du graphe.

Deux types simples de parcours exhaustif : le parcours en profondeur et le parcours en largeur.

Parcours en profondeur
Il consiste, à partir d'un noeud à toujours explorer un noeud voisin jusqu'à ce qu'il n'y en ait plus, puis à remonter dans le parcours pour visiter les voisins laissés de côté au fur et à mesure.

Pour cela il faut marquer les noeuds déjà visités. Un algorithme type est par exemple :


Ce parcours trouve donc un arbre recouvrant (il y en a plusieurs possibles en général).


Figure 3: Un exemple de parcours en profondeur

Complexité ? en espace O(n+m)

En temps : traitement d'un noeud proportionnel à son degré. Le temps total est proportionnel à la somme des degrés = 2m donc O(m).
Parcours en largeur
On crée un arbre recouvrant en profondeur T au fur et à mesure.




Figure 4: Parcours en largeur

Théorème : si G est connexe tous les sommets seront marqués par l'agorithme et toutes les arêtes seront explorées au moins une fois.

Théorème : soit G=(N,A) un graphe connexe non orienté, soit T=(N,B) un arbre recouvrant en profondeur G, construit par l'algorithme. Toute arête a∈ A appartient aussi à B ou bien connecte deux sommets de G tels que l'un des deux soit un ancête de l'autre.


Complexité de l'algorithme :
Partition des sommets en couches
Définition : la distance de deux sommets d'un graphe est la longueur du plus court chemin reliant les deux sommets, en convenant que cette distance est infinie s'ils ne sont pas reliés.

on fixe un sommet initial r. Une partition en couches associée à r est la séquence d'ensembles définie comme suit :

C0={r }
C1={x∈ N / d(r,x)=1 }
Ci={x∈ N / d(r,x)=i }
Algorithme : on visite les sommets en construisant les couches dans l'ordre en partant de la racine r, et en marquant successivement tous les sommets des couches. La nouvelle couche est créée en prenant la liste des voisins non marquée de la liste précédente.

Représentation et résolution de problèmes
Pour résoudre un problème dans sa généralité, il est nécessaire de suivre une méthodologie assurant que la solution fonctionne dans tous les cas envisageables du problème.

approche rigoureuse :
  1. poser correctement le problème : définition du problème
  2. analyser la structure du problème
  3. définir une stratégie de résolution à partir de l'analyse.
Comme il s'agit d'informatiser le problème il ne faut pas perdre de vue en plus la représentation formelle du problème et des connaissances nécessaires à sa résolution.

On peut diviser les méthodes de résolution en deux grandes classes, étudiées ici :
  1. les méthodes systématiques
  2. les méthodes heuristiques (= empiriques).
Résolution sur des graphes d'états simples
On part du principe que tous les problèmes étudiés sont composés d'un ensemble de situations ou objets que l'on peut décrire de façon univoque à l'aide d'un ensemble de variables appelés variables d'états du problèmes.

l'état
d'un problème est alors l'ensemble des valeurs prises par les variables à un instant donné.
l'espace d'état
d'un problème est l'ensemble de tous les états possibles de ce problème
On peut considérer que la résolution d'un problème est la découverte d'un état du problème ayant des caractéristiques données (=la solution).

L'analyse de la structure du problème va généralement permettre d'identifier des liens entre états qui permettent de les visiter tous de façon systématique. Dans cette optique on va chercher : On peut dire que la dernière partie est la seule partie algorithmique (c'est la stratégie de contrôle des opérations) alors que la résolution d'un problème implique aussi fortement les deux premières : la modélisation des données du problème et les opérateurs sur ces données.

Exemple : Les missionnaires et les cannibales (ou bien l'équivalent avec la chèvre le loup, le paysan et le chou)

Trois missionnaires et trois cannibales se trouvent sur la même rive d'un fleuve. Ils désirent traverser le fleuve et disposent pour cela d'un barque ne pouvant contenir que deux personnes. Si sur une de ces deux rives les missionnaires se trouvent en nombre strictement inférieurs aux cannibales, ils se font cannibaliser. Les missionnaires doivent trouver une méthode pour traverser le fleuve en restant entiers...
Retour sur les cannibales et les missionaires
Première étape de résolution : le codage du problème. Plusieurs solutions s'avèrent possibles :

Dans le premier cas quels sont les codages des états initiaux et finaux et les contraintes portant sur les données ?

  1. 0≤ X ≤ 3 et 0≤ Y ≤ 3, et P=D ou G
Quelle est :

- la plus compacte ? (1!!)

- la plus pratique ? (? peut pas savoir avant de définir les opérateurs)

Opérateurs sur les données/ système de production
Le système de production est la description de l'ensemble des mécanismes permettant de passer d'un état à un autre du problème. Chaque état possède un ensemble d'états qui lui sont acessibles dans le problème. Les opérateurs permettent de définir cet ensemble, et c'est la stratégie de résolution qui donnera la façon de choisir parmi ces états accessibles celle menant à une solution.

Il y aura deux façons de procéder suivant les opérateurs que l'on définit : On peut également faire un mélange des deux méthodes pour donner un chaînage mixte.

Exemple des M & C:
Les opérateurs consistent à faire passer 1 ou 2 personnes à la fois de l'autre côté du fleuve en respectant les contraintes du problème :

-- Il faut (Y≤ X) ou X=0 et 3-Y≤ 3-X ou 3-X=0 (au moins autant de M et de C, quand il y a des missionnaires)

Les opérations valides sont donc par exemple :

(X,Y,G) → (X-2,Y,D) si X > 2 et X-2 > 2

ou (2,Y,G) → (0,Y,D) Représentation formelle plus pratique : la représentation par arbre. A chaque fois que l'on génère un état on le relie à l'état précédent. (sans tester si on génère un état déjà rencontré)



-2cm Avec un graphe : même chose avec un test d'occurrence : si un état a déjà été rencontré on ajoute un arc au graphe, sinon un noeud et un arc.



Propriétés des systèmes de production
Monotone
un système de production est dit monotone si l'application d'une règle à l'instant t laisse applicable à l'instant t'>t toutes les autres règles qui étaient applicables à l'instant t. (M & C ? non)
Partiellement commutatif
un système est partiellement commutatif s'il vérifie la condition suivante :
si X est un état et (s1,s2,...,sn) une séquence de règles de production telle que
X -s1-> X1 -> ... -> Y
alors pour toute permutation σ, la séquence (sσ(1),...,sσ(n)) transforme létat X en Y pourvu que les conditions d'applications des règles soient vérifiées à chaque étape.
Un système est commutatif s'il vérifie cette condition et qu'il est aussi monotone.

En pratique : heum, rare.

Autre exemple: le taquin ...
Graphes ET/OU
Certains problèmes peuvent être représentés par la technique de réduction de problème, c'est-à-dire que le problème peut être considéré comme une conjonction de plusieurs sous-problèmes indépendants les uns des autres, que l'on peut résoudre séparément.

D'autre part, il peut se présenter dans la résolution d'un problème un ensemble de possibilités indépendantes les unes des autres (donc exclusives) telles que la résolution d'une seule de ces possibilités suffit à résoudre le problème.

On peut représenter ces deux possibilités par des arcs différents dans le graphe représentant l'espace de recherche :
- Les arcs qui représentent différentes possibilités dans la résolution d'un problème associés au noeud dont ils découlent sont des arcs OU
- Les arcs qui représentent différents sous-problèmes composant la résolution d'un problème associés au noeud dont ils découlent sont des arcs ET.

Un graphe utilisant ce type d'arcs est un graphe ET/OU.

Un tel graphe est solution d'un problème si : Notation : arc ET avec courbe (figure)

Un sommet qui n'a que des arcs ET est dit sommet ET (resp. OU)

Un sommet d'un arbre d'exploration d'un espace de recherche est dit résolu si : exemples:

0) M et C que des OU
1) tours de Hanoi, avec n disques. ? que des ET
2) planification

figure ...
Stratégies de contrôle
On associe à la génération des états une stratégie de contrôle. Elle est dite systématique si elle vérifie les principes suivants :
  1. elle permet de générer tous les états sans en oublier.
  2. elle ne génère chaque état qu'une fois. Le premier principe garantit la complétude de la procédure (on finit par tomber sur une solution si elle existe.
Le deuxième évite les calculs répétitifs.
Ex: l'algo. suivant parfois appelé "algo du British Museum" (origine ?) est il systématique:

à partir d'un état qcq on génère au hasard l'état suivant jusqu'à trouver une solution. si on est dans une impasse on recommence au début. -> ni principe 1 ni le 2

Résumé de vocabulaire:
génération d'un noeud
calcul du nouveau code de la représentation d'un noeud à partir d'un noeud qcq l'ancien noeud est alors "exploré", le nouveau "généré".
développement d'un noeud
génération de tous ses successeurs.
Lors d'une exploration l'ensemble des sommets du graphe de recherche peut être divisé en quatre ensembles. on se contente le plus souvent de gérer deux listes de sommets : une de mémorisation des sommets fermés cad des noeuds développés et une liste des sommets ouverts  cad ceux dont les successeurs sont générés mais non encore développés.
Recherche systématique aveugle (ou non informée)
Recherche en profondeur Dans la recherche en profondeur la priorité est donnée aux sommets des niveaux les plus profonds du graphe de recherche. Chaque sommet choisi pour être exploré voit tous ses successeurs générés avant qu'un autre sommet ne soit exploré. Dans la liste OUVERTS le sommet le plus profond est celui le plus récemment généré. Cette ensemble aura donc une structure de pile.

Les graphes de recherche des problèmes qu'on cherche à résoudre peuvent être de très grande taille (voire infinie). Une recherche en profondeur peut se révéler dangereuse : l'algorithme risque de développer une branche infinie stérile sans que le mécanisme de retour en arrière puisse se déclencher.On ajoute dans ce cas une limite de profondeur. On a maintenant deux possibilités pour le retour arrière : Recherche en largeur: Cette stratégie donne une plus grande priorité aux sommets les moins profonds du graphe de recherche en explorant les sommets de même profondeur. L'ensemble OUVERT aura une structure de file. ex / figure taquin
Méthodes informées / Heuristiques
Une heuristique est un critère ou une méthode permettant de déterminer parmi plusieurs lignes de conduite celle qui promet d'être la plus efficace pour atteindre un but.

Exemples:
Hill-climbing
Meilleur d'abord
Coût uniforme
A*
Hill-climbing (méthode de l'escalade)
Cette méthode de recherche en profondeur utilise une fonction heuristique pour choisir à chaque étape le noeud à générer. C'est la stratégie de l'alpiniste (soi-disant) qui choisit la direction de la pente la plus forte pour arriver au sommet le plus vite.

Cette méthode comporte quelques dangers de dévissage : Cette méthode ne fonctionne bien que si on a une fonction heuristique très instructive ou si le système de transition est commutatif (...)

Si la méthode n'autorise pas de retour en arrière, elle est dite inéluctable. C'est le cas de la méthode du gradient en optimisation mathématique.

Exemple du taquin : fonction d'évaluation = somme des mouvements à effectuer pour mettre chaque case à sa place. algo avc profondeur maximum de 3, on ne développe que les sommets dont le score est > à celui du noeud père.

ex : figure
Stratégie du meilleur d'abord (Best first)
On cherche dans cette stratégie à sélectionner le sommet le plus prometteur par rapport à l'heuristique, parmi tous les sommets rencontrés depuis le début, quelle que soit sa positon dans l'arbre partiellement développé.
Le caractère prometteur d'un sommet peut être estimé de diverses manières :-30pt Dans tous les cas l'estimation est numérique et elle est calculée au moyen d'une fonction heuristique d'évaluation f(n) qui peut donc dépendre de n (le noeud), du but, de l'information de toute la branche. exemples figures avec arbre p236 (heuristique pas croissante)
Stratégie A* (spécialisation du meilleur d'abord)



insere_selon_f, insere dans la file par ordre croissant de f (puis g)

Cas particuliers : La fonction h(n) tente d'estimer le minimum sur tous les chemins de n à l'état final de la somme des k(n,..) sur le chemin

La valeur réelle de ce miminum est notée h*(n)


Plusieurs cas d'heuristiques :
heuristique parfaite
h est parfaite ssi h(u)=h(v) ↔ h*(u)=h*(v)
heuristique presque parfaite
h(u)<h(v) ↔ h*(u)<h*(v)
heuristique monotone
(ou consistante) si pour tout v descendant de u, h(u)-h(v)≤ k(u,v) (NB: ca vaut mieux si h est censé etre le minimum)
heuristique minorante ou admissible
h(u)≤ h*(u)
Propriétés formelles des méthodes heuristiques
Les méthodes heuristiques semblent être parfois assez imprévisibles. Les heuristiques peuvent réduire de façon considérable l'exploration de l'espace de recherche pour la plupart des jeux de données d'un problème, et échouer complètement sur des cas simples si certaines conditions sont réunies. L'étude formelle des heuristiques permet dans certains cas de prévoir le comportement de l'algorithme qui va l'utiliser. Notations:
nj est un successeur de ni sera noté nj∈ succ(ni)

Γ est l'ensemble des sommets terminaux du graphe de l'espace de recherche.

Pni-nj={ chemins de ni à nj}

Pn-Γ={ chemins de n à Γ}

de même pni-nj, pn-γ Pni-nj*, chemins de coût minimum.

k(ni,nj) coût d'un chemin minimum de ni à nj.


Les coûts de chemin contenant u0 l'état initial où un élément de Γ portent des noms spéciaux :

g*(n)= coût minimum des chemins reliant u0 à un sommet n.

g*(n)=k(s,n)

h*(n)= coût minimum des chemins allant de n à Γ
h*(n)=min
 
γ∈Γ
k(n,γ)

Γ* st l'ensemble des buts optimaux γ accessibles depuis u0 par un chemin de coût minimum c*.
c*=k*(u0)

on suppose que le but de la recherche est de trouver un chemin de coût minimal joignant u0 à n'importe quelle sommet de Γ. Chaque arc porte une étiquette de coût positif c(ni,nj)> delta > 0 . Le coût d'un chemin est la somme des coûts des arcs qui le composent.
Propriétés algorithmiques de A*
Définitions
Complétude
: un algo est dit complet lorqu'il débouche sur une solution quand il en existe une.
Admissibilité
: un algorithme est dit admissible lorsqu'il donne une solution optimale à chaque fois qu'li en existe une.
Dominance
: un algorithme A1 domine un algo A2 si tout sommet développé par A1 l'est aussi par A2. A1 domine strictement A2 si A1 domine A2 mais A2 ne domine pas A1. (algo plus efficace, car il développe moins de sommets).
Optimalité
: un algorithme est optimal dans une classe d'algorithme s'il domine tous les autres membres de sa classe.

A*: recherche optimale d'une solution optimale :

La fonction f de A* consiste à ajouter deux parties g(n) et h(n) où : Notons γ une solution. Lorsqu'on voudra spécifier les coûts réels de Pu0-n et de Pn-γ sur un chemin particulier P on écrira gp(n) et hp(n). Pour tout chemin p on gp(n)> g*(n) et hp(n)> h*(n)

Lorsque g et h coïncident avec leur valeurs optimales, la fonction f résultante prend une signification particulière.

Soit f*(n)=g*(n)+h*(n), f*(n) est le coût optimal pour tous les chemins solution passant par u0. En particulier f*(u0)=h*(u0)=g*(γ)=f*(γ)=c*, ∀ γ∈Γ*


Proposition : Si n* est un sommet quelconque sur un chemin optimal allant de u0 à γ il doit satisfaire : f*(n*)=c*.

Preuve : soit n* ∈ Pn*-γ, il existe un chemin solution p passant par n dont le coût est c*. Sur ce chemin g*(n)+h*(n)≤ c*. Si jamais on avait g*(n)+h*(n)< c*, il existerait un chemin p' tel que gp'(n)+hp'(n)<c*, ce qui est en contradiction avec l'optimalité de c*.

Si n est un sommet qui n'appartient pas à un chemin optimal solution on a f*(n)>c*


Terminaison et complétude

A* s'arrête toujours sur les graphes finis.

A* est complet pour tous les graphes.

Chaque fois que h(n) est une estimation optimiste de h*(n) A* retourne une solution optimale. Cette classe d'heuristiques est dite heuristiques admissibles. (cad quand h(n)≤ h*(n)).

A* est admissible ssi il utilise une heuristique admissible

Si l'heuristique est parfaite, l'algo convergera immédiatement vers le but (sans explorer de branches inutiles).

Si h est minorante alors A* trouvera toujours le chemin optimal.

Dans le pire des cas la complexité en temps de A* est en 2N, N étant le nombre de sommets du graphe d'état.

Si h est minorante la complexité est en N2 Si h est monotone la complexité est linéaire en N.

Cette complexité n'est pas forcément aussi bonne qu'elle en a l'air, car le nombre de sommets du graphe d'état est également variable en fonction de la taille de l'entrée du problème (ex pour le voyageur de commerce, N=!n où n est le nombre de villes à visiter.
Exemple d'application de A*: le taquin.
On veut minimiser la longueur des solutions. Tous les arcs de l'espace d'état auront donc un coût associé de 1.

L'heuristique h choisie est :

h(n)=distance_de_manatthan(n)+3*score de déplacement(n).

score de déplacement de n= somme des scores des cases du taquin: -10pt Exemple:
1 3 4
8   2
7 6 5
   5cmmanhattan=4
score de dep=7 h n'est pas admissible, elle ne vérifie pas h≤ h*

par exemple pour la configuration ci-dessus, on a h=22 et h*=4 le chemin solution le plus court ne sera pas trouvé avant les autres. exemple plus complet;;; figure
Arbres de jeux
Plan:
Recherche locale dans les problèmes à forte combinatoire
Quelques Problèmes des méthodes exactes/complètes
  1. Les méthodes complètes/exactes explorent de façon systématique l'espace de recherche. → ne marche pas dans de nombreux problèmes à cause explosion combinatoire.
  2. ces méthodes sont généralement à base de recherche arborescente → contrainte par l'ordre des noeuds dans l'arbre
    → impossibilité de compromis qualité/temps) (≢ algo ``anytime'')
Or il y a souvent des cas ou on peut se contenter d'une solution approchée, pourvu qu'elle soit suffisament ``bonne''. (ex du TSP, on ne veut pas forcement le minimum mais quelque chose d'assez court, par exemple <= distance donnée).
Un autre principe: les méthodes incomplètes
on peux adopter deux types de stratégie :
Une famille de méthodes incomplètes: les méthode ``locales''
Le principe d'une recherche locale est de
  1. partir d'une solution sinon approchée du moins potentiellement bonne et d'essayer de l'améliorer itérativement.

    Pour améliorer une solution on ne fait que de légers changements (on parle de changement local, ou de solution voisine.
  2. relancer la méthode plusieurs fois en changeant le point de départ pour avoir plus de couverture

  3. tout problème est considéré comme un problème d'optimisation (même les problèmes de satisfaction : le coût à optimiser est alors le nombre de contraintes insatisfaites).
Quelques définitions
une solution
est une affectation de toutes les variables du problème.
une solution optimale
est une solution de coût minimal
un mouvement
est une opération élémentaire permettant de passer d'une solution à une solution voisine (exemple: changer la valeur d'une variable, échanger deux variables).
le voisinage
d'une solution est l'ensemble des solutions voisines, c'est à dire l'ensemble des solutions accessibles par un mouvement (et un seul).
un essai
est une succession de mouvements.
une recherche locale
est une succession d'essais.
Un algorithme de recherche locale typique


f: fonction à optimiser
Les paramètres à régler
Exemples de recherches locales
le hill-climbing
Aussi appelé descente en gradient suivant le sens de l'optimisation (min ou max recherché).
choisir_un_voisin : choix aléatoire dans le voisinage courant.
acceptable : seulement s'il il y a une amélioration (d≤0).
méthode opportuniste
la version gloutonne (greedy)

choisir_un_voisin : après avoir déterminé l'ensemble des meilleures solutions voisines de la solution courante (exceptée celle-ci), on en choisit une aléatoirement.
acceptable : toujours.
il peut y avoir des dégradations (provisoires) de solutions.
minimisation de conflits

choisir_un_voisin :
  1. déterminer l'ensemble des variables en conflit (eg. liées dans un ensemble de contraintes).
  2. choisir une de ces variables au hasard.
  3. déterminer l'ensemble de ses meilleures valeurs (recherche complète ou pas ?).
  4. en choisir une au hasard, affecter la variable.
  5. retourner la solution.
acceptable : toujours.
il ne peut y avoir de dégradation de solutions (→ attention aux optimum locaux).
Les classiques en question(s)
Comportement général :
  1. une majorité de mouvements améliorent la solution courante.
  2. le nb d'améliorations devient de plus en plus faible.
  3. il n'y a plus d'améliorations : on est dans un optimum, qui peut être local.
Les questions à se poser (1)
Illustration (1)
Illustration (2)
Les questions à se poser (2)
Pour le critère d'arrêt : Avidité ou opportuniste :
Amélioration des classiques : l'approche probabiliste
Pour éviter d'être coincé dans un optimum local, on peut ajouter du bruit : une part de mouvements aléatoires pendant une recherche classique.

Principe : Reste le problème : comment régler p ?
Amélioration des classiques : le Tabou
basée sur une recherche par gradient En pratique, au lieu de mémoriser les k dernières solutions courantes (parfois trop coûteux en temps et mémoire), on mémorise les k derniers mouvements (plus restrictif mais peu coûteux en temps)

Amélioration des classiques : le recuit simulé
méthode inspirée par une analogie avec un phénomène de physique statistique, l'obtention d'un état stable d'un métal.

En termes de recherches locales, la probabilité d'acceptation d'un mouvement de A à A' :
p(φ(A')-φ(A))=1 si φ(A')≤φ(A)
p(φ(A')-φ(A))=e-(φ(A')-φ(A))/T si φ(A')>φ(A)
(issu de lois thermodynamiques)

Principe : on simule le processus de recuit des métaux : Au départ on choisit T assez élevée pour que chaque mouvement ait une probabilité d'acceptation de plus de 50% (mouvement très chaotique)

Après chaque plateau, T est baissée (réduction du bruit jusqu'à ne plus accepter de solutions plus mauvaises que la solution courante).
Réglage des paramètres
Avantages des recherches locales
Inconvénients des recherches locales
Les Algorithmes génétiques
Les algorithmes génétiques sont une forme de recherche locale qui se démarque un peu des méthodes précédentes. Le principe est inspiré d'une analogie biologique : on considère un ensemble de solutions comme une population d'individus susceptible d'évoluer et de se croiser, en suivant certaines règles proches de la sélection naturelle.

L'intérêt principal est de couvrir l'espace de recherche plus largement.

Trois opérations sont réalisées successivement sur la population :
Quelques caractéristiques des Algorithmes génétiques
-- Historiquement, un individu était codé par une chaîne de bits (son ``patrimoine génétique''). En pratique chaque problème appelle un codage particulier.

-- La sélection se base sur l'adaptation (ou fitness) d'un individu, donnée par une fonction d'utilité (on cherche à maximiser l'adaptation des individus).

-- La sélection permet de focaliser la recherche sur les zones intéressantes, alors que mutations et croisements permettent de diversifier la recherche (on retrouve, plus lâchement, le paradigme des recherches locales).

-- Les algorithmes génétiques sont semblables à des recherches locales effectuées +/- en parallèle.

-- Utilité dans le cas de problèmes dont on ignore la structure (espace de recherche mal connu par exemple
Quelques inconvénients des algorithmes génétiques
Les problèmes techniques importants sont :
Conclusion
les méthodes incomplètes fournissent un ensemble de résolutions empiriques variées, parfois trop, car l'absence de modélisation les rend difficiles à adapter d'un problème à un autre (bricolage...).

Par contre elles sont à peu près indifférentes à la taille du problème, et donnent de bons résultats (approchés) à condition de bien les paramétrer.

→ peuvent fournir un bon complément aux méthodes complètes.

This document was translated from LATEX by HEVEA.