Ceci est le cours de Agathe et Mara, L3 info en 2017-18
qui nous ont généreusement donné accès à leurs prise
de notes au cours de cette année.
Merci à elles.
Intelligence artificielle
CT : une feuille A4 recto verso
Enjeux :
- scientifiques
- sociaux
- commerciaux
- militaires
Problème dans les espaces d’états :
- Focalisation sur les problèmes où il existe une description formelle mais pas de méthode
de résolution spécifique avec un environnement supposé déterministe
- un problème peut être décrit pas différentes données :
- l’ensemble des valeurs des variables du problème, à un instant t, est un état
- on peut passer d’un état à un autre grâce à des opérateurs de changements d’état
- autre chose ?
- autres définitions :
- descendant d’un état s, tout état accessible en appliquant une séquence non vide
d’opérateurs à s
- si la seq comporte un seul opé
- un problème est donc carc par
- la description des états possibles
- la description de l’état initial
- les description d’un état brut (explicite ou implicite par ses propriétés)
- les description des opérateurs de changement d’état
- l’espace d’état peut être représenté
- en extension
- en intention si il est trop vaste (état initial, opérateurs de changement d’état)
- les contraintes liées au problème sont prises en compte dans l’applicabilité des
opérateurs qui ne sont pas toujours applicables à tout état possible
- strat d’explo :
- strat aveugle (non informés, notées SNI) : prof d’abord, largeur d’abord, prof
bornée, Deep First Inperative Deeping (?)… Mais l’explosion combinatoire
conduit à utiliser…
- strat de recherche heuristique (informés, notées SI) glouton, meilleur d’abordn
A, A*, WA, Aε, A*ε, A**, B, BF*, IDA, HPA, …
- Autres def
- état créé : état prod par appli d’un opé à un autre état. PAr convention, l’état init
est crée est rangé dans l’ensemble EnAttente
- état exploré : état que l’on sort de EnAttente pour l’étudier
- état développé : état exploré dont on crée (génère) les successeurs
- les états explorés sont rangés dans l’état Vus
- les état créés mais non encore explo sont rangés dans l’ensemble EnAttente
- les états de Vus ou EnAttente sont des états mémoires
- complétude : si le pb admet une solution, l’algo s’arrête en fournissant une
soluce
- compléxité temp temps nécess pour trouver une solut
- complex spatiale : place mem néc pour effectuer l’explo
- admissibilité : ce critère (encore appelé optimalité) s’applique à la recherche
d’une solut avec coût. Une recherche est admissible si elle fournit la meilleure
solution (?)
- la complexité (t ou s) est toujours relative à une mesure de difficulté du pb. LA mesure
typique est la taille du graphe de l’espace d’états (nb sommets + nb d’arêtes) qui est fn
de 3 vals :
- le facteur branchement ( b = nb max de fils d’un état)
- la prof max de l’arbre de recherche (m=
- qqc
Algorithme général
Algo SNI : largeur d’abord
La fonction classe ajoute les états à la fin de la liste EnAttente (qui est donc une file).
- complet (si b est fini)
- nb d’état créé en O(b^d)
- complex tempo et spat en O(b^d)
- long opti …
- gourmand en mémoire
Algo SNI : prof d’abord
La fonction classe ajoute les états en tête de la liste EnAttente (qui est donc une pile)
- complet si on intègre les opti de la fn classe (on évite les état répétés)
- complexité tempo en O(b^m); nb d’état créés pareil
- complex spa en O(bm) nb état stockés pareil
- pas d’opti du chemin-solution
Convention :
- si égalité de la val de l’heuris on met en tête de la liste EnAttente l’état le + profond. Si
même prof on met en tête le + ancien
Algo SNI : prof itérative, DFID
Profondeur bornée en essayant des profondeurs successives (1, 2, 3, . . .).
- complet si b fini
- complex tempo en O(b^m)
- en profondeur mais par par (d’abord sur p puis 2p,...)
- quasi optimisé
notion d’heuristique : tt procédé guidant la recherche d’une solution (pour faire mieux qu’au
hasard)
- fn d’évaluation d’état permettant de choisir parmi pls le plus prometteur pour atteindre
un but donné
- classement des opé applicables ( - )
QQC
Algo SI : hill climbing (gradient)
- prof d’abord combinée avec le meilleur fils (heuris)
- arret qd aucun succ n’a une meilleure val (+ gde ou + petite selon l’heuri utilisée) que
courant
- algo incomplet mais efficace pour certains pb
- pas de retour en arrière (back-track)
- max local (ou min local)
- plateaux
- ef
Algo SI : Meilleur d’abord glouton
- un algo glouton choisi localement la meilleure solution
- f se réduit à h, qui estime le coût min d’un chem menant à l’état courant à l’état brut
- algo complet si l’esp de recherche est fini et si ...
Algo SI : meilleur d’abord A*
- f appliqué à un état : estimation du coût du chem opti menant de l’état init à un état en
passant par l’état courant
- utilise deux parties de l’heuristique
- f est de la forme f(e)=g(e)+h(e) , g et h étant des estimations de :
- g*(e) coût du chem opti état init -> état e ; ce qu’on a déjà fait
- h*(e) : coût d’un chem opti état courant -> état brut ; estimation de ce qu’il reste
à faire, heuristique
Algo SI : meilleur d’abord A
- fonction heuristique de la forme f(E) = g(E) + h(E) , g dynamique et h statique
Algo SI : A* avec W (minorante)
- comment trouv une heuristique ; relaxer le pb originel pour obtenir une fn calculable
“efficacement”
RESOLUTION DE PB
un noeud est résolu s’il traduit un pb primitifs de solutions connues
jeux :
- coop
- séquentiels : à tour de rôle
- somme nulle : toute chose gagné et perdue par l’adversaire
- info complète et parfaite : vision complète de ce que l’adversaire a joué et peut jouer
Arbre ET/OU
noeud OU : joueur de référence joue
noeud ET : l’autre joueur joue
Si tous les fils d’un noeud OU est perdant il est perdant sinon il est gagnant. Le joueur référent
OU remonte la max.
Si tous les fils d’un ET et lui même sont gagnants il est gagnant sinon il est perdant. Le joueur
adverse ET remonte le min.
Pour un minimax, on remonte le fils maximum sur un OU et le minimum sur un ET
Sur un noeud ET on parcours tous les chemins descendant possibles, sur un noeud OU on
parcours un chemin parmis ceux possibles. Si on prend comme référent l’autre joueur (car il est
gagnant) on inverse les noeud OU et ET.
Si on cherche le gagnant, on peut s’arrêter dès qu’on a au moins un GAGNANT sur un OU.
Coloration de graphe
si il y a une clique d’ordre k, il faut au moins k couleurs pour le graphe
algorithme glouton avec heuristique
début
- classer les sommets par ordre de degré (nb de connexion) décroissant
- coul <- 1
- tant que il reste des sommets à colorer faire
- - extraire le premier sommet s
- - V <- liste des voisins de s
- - nouvCoul <- plus petite couleur non utilisée dans V
- - colorier s avec nouvCoul
- - si nouvCoul > coul alors
- - - coul <- nouvCoul
coul est une approximation du nombre chromatique à la fin de l’algo ici
algorithme DSatur
Dsat(s) : nb de couleur distinctes déjà utilisées pour colorer les sommets adjacents de s
permet une heuristique dynamique
début
- classer les sommets par ordre de degré décroissant
- coul <- 1
- tant que il reste des sommets à colorer faire
- - extraire un sommet s tel que Dsat(s) est max (en cas d’égalité choisir un sommet dont le nb de
voisins non coloriés est max)
- - V <- liste des voisins de s
- - nouvCoul <- plus petite couleur non utilisée dans V
- - colorier s avec nouvCoul
- - si nouvCoul > coul alors
- - - coul <- nouvCoul
algorithme Welsh et Powell
début
- coul <- 0
- Y <- X classé par ordre de degré croissant
- tant que il reste des sommets à colorer faire
- - incrémenter coul
- - extraire le premier sommet s de Y et le colorier avec coul
- - V <- liste des voisins de s
--p our chaque sommet x de Y f aire
- - - si x ∉ V alors
- - - - colorier x avec coul
- - - - ajouter les voisins de x à V
- - éliminer les sommets coloriés de Y
théorème des 4 couleurs :
4 couleurs suffisent à colorer n’importe quelle carte découpée en régions connexes de façon à ce
que deux régions adjacentes aient toujours deux couleurs distinctes
2 heuristiques classiques pour les CSP :
- var de + petit domaine d’abord
- var les + contraintes d’abord avec les val les - contraintes d’abord