Algorithmes de recherche et de tri - UPJV
Structurer les données est indispensable pour les manipuler dans les programmes Il faut cependant savoir retrouver les données dans ces structures, c'est le but des algorithmes de recherche, et de tri Algorithmes de recherche et de tri The Analytical Engine has no pretensions whatever to originate anything It can do whatever we know how to
Résolution de problèmes en IA: Les algorithmes de recherche
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 à
LES algorithmes de tri Et de recherche
LES algorithmes de tri Et de recherche A Le tri d’un tableau : I Introduction : Le tri est une opération qui consiste à répartir ou organiser une collection d’objets selon un ordre déterminé Dans le domaine de l’informatique, il existe plusieurs méthodes de tri (algorithmes) Dans ce
INF4230 – Intelligence Artificielle Algorithmes de recherche
Relation entre les joueurs •Dans un jeu, des joueurs peuvent être : –Coopératifs •Ils veulent atteindre le même but –En compétition direct (avec adversaires) •Un gain pour les uns est une perte pour les autres •Cas particulier : les jeux à somme nulle (zero-sum games) –Jeux d’éhes, de dame, ti -tac-toe, Connect5, etc
Intelligence Artificielle Recherche
Algorithmes de recherche en IA Strat egie de recherche Les di erents attributs des n˙uds sont initialis es par la fonction Expand Une strat egie de recherche est d e nie parl’ordre dans lequel les n˙uds sont d evelopp es, i e , la fonction Insert-Fn Une strat egie s’ evalue en fonction de 4 dimensions :
Quelques Algorithmes simples - IRIF
les algorithmes babyloniens pour r esoudre par exemple des equations), et plus "r ecemment" a Al-Khw^arizm^ (lui aussi a v ecu en Perse, a Bagdad, mais vers 900 apr es J esus Christ) qui a donn e son nom a l’algorithmique
Intelligence Artificielle – TD 2 ALGORITHMES DE RECHERCHE EN IA
Exercice 4 - Considérez un espace de recherche dans lequel l’état initial est 1 et la fonction successeur pour un nœud n retourne deux états contenant les entiers 2n et 2n+1 1 Dessiner la partie de l’espace de recherche contenant les nœuds de 1 à 15 2 Supposer que le but soit 11
Algorithmique: algorithmes sur les arbres binaires
8 Recherche d’une cl e dans un arbre binaire de recherche: Nous allons maintenant etudier un algorithme permettant de rechercher une cl e de valeur k dans un arbre binaire de recherche Si k est bien pr esent dans l’arbre binaire de recherche, l’algorithme renvoie vrai, dans le cas contraire, il renvoie faux
Structures de donn ees et algorithmes Projet 2: arbres
Il s’agit d’impl ementer un arbre binaire de recherche g en erique; les cl es et les valeurs associ ees sont de type const void* Dans le cadre du projet, les cl es seront soit des r eels (latitude et longitude), soit des entiers (code de Morton) Les valeurs seront toujours un type reprenant la ville et ses coordonn ees (City)
[PDF] Recherche de célébrité ANGLAIS
[PDF] Recherche de chansons parlant de la ségregation
[PDF] Recherche de cinq textes argumentatifs sur la guerre
[PDF] recherche de correction
[PDF] Recherche de définitions
[PDF] Recherche de devoir physique-chimie
[PDF] recherche de document sur l'art nouveau
[PDF] recherche de document sur l'art nouveau
[PDF] Recherche de figures de style dans un extrait du texte "Le reflet" de Didier Daeninckx
[PDF] Recherche de francaise
[PDF] Recherche de l'Absolu, Honoré de Balzac
[PDF] Recherche de l'ensemble de définition et du sens de variation d'une fonction donnée par une formule
[PDF] recherche de l'équation
[PDF] Recherche de la biographie d'un auteur sur internet
Intelligence Artificielle
Recherche
Bruno Bouzy
http://web.mi.parisdescartes.fr/~bouzy bruno.bouzy@parisdescartes.frLicence 3 Informatique
UFR Mathématiques et Informatique
Université Paris Descartes
Algorithmes de recherche en IA
Algorithmes de recherche en IA
Agents avec objectifs explicites
Les dierents types de probleme
Exemples de problemes
Algorithme de recherche de base (recherche aveugle)4 / 46Intelligence articielle
NAlgorithmes de recherche en IA
Algorithmes de recherche en IA
Agents avec objectifs explicites
Les dierents types de probleme
Exemples de problemes
Algorithme de recherche de base (recherche aveugle)5 / 46Intelligence articielle
NAlgorithmes de recherche en IA
Agent avec des objectifs explicites
6 / 46Intelligence articielle
NAlgorithmes de recherche en IA
Exemple de probleme: le voyage en
RoumanieAradZerind
TimisoaraOradea
Sibiu LugojMehadia
Dobreta
CraiovaRimnicu VilceaFagaras
PitestiBucharest
GiurgiuUrziceni
Hirsova
EforieVasluiLasiNeamt
7511871
140151
11170
75
12080
14699
13897211
101908598
801429287
7 / 46Intelligence articielle
NAlgorithmes de recherche en IA
Algorithmes de recherche en IA
Agents avec objectifs explicites
Les dierents types de probleme
Exemples de problemes
Algorithme de recherche de base (recherche aveugle)8 / 46Intelligence articielle
NAlgorithmes de recherche en IA
Les dierents types de problemes
Deterministe, completement observable!probleme a un seul etatL'agent sait exactement dans quel etat il est et dans quel etat il sera
La solution est une sequence d'actions
Non-observable!probleme sans possibilite de percevoir l'environnementL'agent n'a aucune idee d'ou il est reellement
La solution est une sequence d'actions
Non-deterministe ou partiellement observable!probleme dans lesquels il faut gerer des eventualitesLes perceptions fournissent de nouvelles informations sur l'etat courant Souvent les phases de recherche et d'execution sont entrelacees L'expace d'etats est inconnu!probleme d'exploration9 / 46Intelligence articielle NAlgorithmes de recherche en IA
Exemple : Le monde de l'aspirateur
Probleme deterministe completement observableEtat initial : #5Etat nal : #8
Solution :hdroite,aspirei10 / 46Intelligence articielle NAlgorithmes de recherche en IA
Exemple : Le monde de l'aspirateur
Probleme deterministe non observableEtats initiaux :f#1, #2, #3, #4, #5, #6, #7, #8gSolution pourf#1, #3, #5, #7g: haspire,droite,aspireiSolution pourf#2, #4 #6, #8g: hgauche,aspire,droite,aspirei11 / 46Intelligence articielle NAlgorithmes de recherche en IA
Exemple : Le monde de l'aspirateur
Probleme non deterministe partiellement observableNon-deterministe : aspirer ne garantit pas que le sol soit proprePartiellement observable : on ne sait pas si le sol a droite est propre )Etats initiaux :f#5, #7gSolution : hdroite, si sol sale alorsaspirei12 / 46Intelligence articielle NAlgorithmes de recherche en IA
Les problemes deterministes et com-
pletement observablesUnp roblemed eterministee tc ompletementob servablee std enip ar: 1. u netat initialpar exemple,\a Arad" 2.u nensemble d'actionsou unefonction de transition,succ(x) :par exemple,succ(Arad) =fZerind,Timisoara,Sibiug
3. u ntest de terminaisonpour savoir si le but est atteindexplicite, e.g.,\a Bucharest" implicite, e.g.,\verier mat au echec" 4. u nco^ut(additif)par exemple la somme des distances, le nombre d'actions executees, etc.par exemple,c(x;a;y) est le co^ut d'une transition,c(x;a;y)0Unes olutione stu nes equenced 'actionsp artantd el' etati nitiale tme nant
au but.13 / 46Intelligence articielle
NAlgorithmes de recherche en IA
L'espace d'etats
Lemonde reel est trop complexepour ^etre modeliseL'espace de recherche modelise unev ueab straiteet sim plieed um onde
reelUnetat abstraitrepresente un ensemble d'etats reelsUneaction abstraiterepresente une combinaison complexe d'actions
reellespar exemple,\Arad!Zerind"represente un ensemble de routes possibles, de detours, d'arr^ets, etc.Une action abstraite doit ^etre une simplication par rapport a une action reelleUnesolution abstraitecorrespond a un ensemble de chemins qui sont solutions dans le monde reel.14 / 46Intelligence articielle
NAlgorithmes de recherche en IA
Algorithmes de recherche en IA
Agents avec objectifs explicites
Les dierents types de probleme
Exemples de problemes
Algorithme de recherche de base (recherche aveugle)15 / 46Intelligence articielle
NAlgorithmes de recherche en IA
Exemple : Espace d'etats du monde de
l'aspirateurR L SS SS R L R L R L S SS S L L LLR R RREtats?sol sale ou propre, position de l'aspirateurActions?droite, gauche, aspireTest du but?les deux pieces doivent ^etre propresCo^ut du chemin?1 par action16 / 46Intelligence articielle
NAlgorithmes de recherche en IA
Exemple : Le jeu du taquin
Etats?les positions des piecesActions?deplacement droite, gauche, haut, basTest du but?etat but donneCo^ut du chemin?1 par deplacement17 / 46Intelligence articielle
NAlgorithmes de recherche en IA
Exemple : Le robot assembleur
Etats?coordonnees du robot, angles, position de l'objet a assembler...Actions?deplacements continusTest du but?objet completement assembleCo^ut du chemin?le temps d'assemblage18 / 46Intelligence articielle
NAlgorithmes de recherche en IA
Exemple de problemes reels
Recherche de parcours
Itineraires automatiques, guidage routier, planication de routes aeriennes, routage sur les reseaux informatiques, ...RobotiqueAssemblage automatique, navigation autonome, ...
Planication et ordonnancement
Horaires, organisation de t^aches, allocation de ressources, ...19 / 46Intelligence articielle
NAlgorithmes de recherche en IA
Algorithmes de recherche en IA
Agents avec objectifs explicites
Les dierents types de probleme
Exemples de problemes
Algorithme de recherche de base (recherche aveugle)20 / 46Intelligence articielle
NAlgorithmes de recherche en IA
Algorithme de recherche de base
(recherche aveugle)Idee de baseRecherche hors ligne
, i.e. exploration de l'espace d'etats en generant des successeurs d'etats deja generes (developper des etats)Generation d'una rbred er echerche On s'arr^ete lorsqu'on a choisi de developper un nud qui est un etat nal21 / 46Intelligence articielle
NAlgorithmes de recherche en IA
Exemple : arbre de recherche
Arad22 / 46Intelligence articielle
NAlgorithmes de recherche en IA
Exemple : arbre de recherche
SibiuZerindTimisoaraArad
22 / 46Intelligence articielle
NAlgorithmes de recherche en IA
Exemple : arbre de recherche
AradFagarasOradeaRimnicu VilceaSibiuZerindTimisoaraArad22 / 46Intelligence articielle
NAlgorithmes de recherche en IA
Implemetation des algorithmes de
rechercheStructure de donneesnudqui contientetat parent enfant profondeurco^ut du chemin (noteg(x))Expandcree de nouveaux nudsInsertAllinsere de nouveaux nuds dans la liste a traiter23 / 46Intelligence articielle
NAlgorithmes de recherche en IA
Algorithme de recherche dans les arbres
24 / 46Intelligence articielle
NAlgorithmes de recherche en IA
Etats vs Nuds
Un etat es tu nere presentationd 'unec ongurationp hysiqued umo nde Un n ud e stu nes tructured ed onneesq uies tpa rtiein tegrantede l 'arbre de recherche et qui inclue :l'etat le parent, i.e. le nud pere l'action realisee pour obtenir l'etat contenu dans le nudle co^utg(x) pour atteindre l'etat contenu dans le nuddepuis l'etat initialla profondeur du nud, i.e., la distance entre le nud et la racine de l'arbre
25 / 46Intelligence articielle
NAlgorithmes de recherche en IA
Strategie de recherche
Lesdierents attributs des nudssont initialises par la fonctionExpandUnestrategie de rechercheest denie parl'o rdred ansle quell esn uds
sont developpes ,i. e.,l afo nctionInsert-FnUne strategie s'evalue en fonction de 4 dimensions : lacompletude: est ce que cette strategie trouve toujours une solution sielle exise ?lacomplexite en temps: le nombre de nuds creeslacomplexite en memoire: le nombre maximum de nuds en memoirel'optimalite: est ce que la strategie trouve toujours la solution la moins
co^uteuse ?26 / 46Intelligence articielle NAlgorithmes de recherche en IA
Strategie de recherche
La complexite en temps et en memoire se mesure en termes de : b: lefacteur maximum de branchementde l'arbre de recherche, i.e., lenombre maximum de ls des nuds de l'arbre de recherched: laprofondeur de la solution la moins co^uteusem: laprofondeur maximale de l'arbre de recherche
!attention peut ^etre127 / 46Intelligence articielle NAlgorithmes de recherche en IA
Strategies de recherche non-informees
(aveugles)Less trategiesd ere cherchen on-informeesu tilisents eulementle s informations disponibles dans le problemeIl existe plusieurs strategies :Recherche en largeur d'abord
Recherche en co^ut uniforme
Recherche en profondeur d'abord
Recherche en profondeur limitee
Recherche iterative en profondeur
28 / 46Intelligence articielle
NAlgorithmes de recherche en IA
Recherche en largeur d'abord
La fonctionInsert-Fnajoute les successeurs en n de listefringe= [A]A29 / 46Intelligence articielle
NAlgorithmes de recherche en IA
Recherche en largeur d'abord
La fonctionInsert-Fnajoute les successeurs en n de listefringe= [B;C]BCA29 / 46Intelligence articielle
NAlgorithmes de recherche en IA
Recherche en largeur d'abord
La fonctionInsert-Fnajoute les successeurs en n de listefringe= [C;D;E]DEBCA29 / 46Intelligence articielle
NAlgorithmes de recherche en IA
Recherche en largeur d'abord
La fonctionInsert-Fnajoute les successeurs en n de listefringe= [D;E;F;G]DEFGBCA29 / 46Intelligence articielle
NAlgorithmes de recherche en IA
Recherche en largeur d'abord
La fonctionInsert-Fnajoute les successeurs en n de listefringe= [E;F;G]DEFGBCA29 / 46Intelligence articielle
NAlgorithmes de recherche en IA
Exemple de probleme: le voyage en
RoumanieAradZerind
TimisoaraOradea
Sibiu LugojMehadia
Dobreta
CraiovaRimnicu VilceaFagaras
PitestiBucharest
GiurgiuUrziceni
Hirsova
EforieVasluiLasiNeamt
7511871
140151
11170
75
12080
14699
13897211
101908598
801429287
30 / 46Intelligence articielle
NAlgorithmes de recherche en IA
Recherche en largeur d'abord
Complet, sibest niComplexite en temps :
1 +b+b2+b3+:::+bd+ (bd+1b) =O(bd+1)Complexite en espace :O(bd+1) (garde tous les nuds en memoire)Optimale si co^ut = 1 pour chaque pas, mais non optimale dans le cas
general )L'espace est le plus gros probleme31 / 46Intelligence articielle NAlgorithmes de recherche en IA
Recherche en largeur d'abord
b= 1010000 nuds par seconde1000 octets de memoire pour un nuds
ProfondeurNudsTempsMemoire
810931 heures1 Teraoctet, 1024 Go
12101335 ans10 Petaoctets, 1024 Teraoctet
32 / 46Intelligence articielle
NAlgorithmes de recherche en IA
Recherche en co^ut uniforme
La fonctionInsert-Fnajoute les nuds dans l'ordre du co^utg(x)fringe= [(S;0)]SA B CG1 15 5105 5S, 0
33 / 46Intelligence articielle
NAlgorithmes de recherche en IA
Recherche en co^ut uniforme
La fonctionInsert-Fnajoute les nuds dans l'ordre du co^utg(x)fringe= [(A;1);(C;5);(B;15)]SA B CG1 15 5105
5A, 1B, 15C, 5S, 0
33 / 46Intelligence articielle
NAlgorithmes de recherche en IA
Recherche en co^ut uniforme
La fonctionInsert-Fnajoute les nuds dans l'ordre du co^utg(x)fringe= [(C;5);(G;11);(B;15)]SA B CG1 15 5105 5
G, 11A, 1B, 15C, 5S, 0
33 / 46Intelligence articielle
NAlgorithmes de recherche en IA
Recherche en co^ut uniforme
La fonctionInsert-Fnajoute les nuds dans l'ordre du co^utg(x)fringe= [(G;10);(G;11);(B;15)]SA B CG1 15 5105 5
G, 11G, 10A, 1B, 15C, 5S, 0
33 / 46Intelligence articielle
NAlgorithmes de recherche en IA
Recherche en co^ut uniforme
La fonctionInsert-Fnajoute les nuds dans l'ordre du co^utg(x)fringe= [(G;11);(B;15)]SA B CG1 15 5105 5
G, 11G, 10A, 1B, 15C, 5S, 0
33 / 46Intelligence articielle
NAlgorithmes de recherche en IA
Recherche en co^ut uniforme
Equivalent a la largeur d'abord si le co^ut est toujours le m^eme Complet si le co^ut de chaque pas est strictement superieur a 0 Complexite en temps : nombre de nuds pour lesquelsgC, ouCest le co^ut de la solution optimaleComplexite en espace : idem que la complexite en temps Optimale car les nuds sont developpes en fonction deg34 / 46Intelligence articielle NAlgorithmes de recherche en IA
Recherche en profondeur d'abord
La fonctionInsert-Fnajoute les successeurs en debut de listefringe= [A]A35 / 46Intelligence articielle
NAlgorithmes de recherche en IA
Recherche en profondeur d'abord
La fonctionInsert-Fnajoute les successeurs en debut de listefringe= [B;C]BCA35 / 46Intelligence articielle
NAlgorithmes de recherche en IA
Recherche en profondeur d'abord
La fonctionInsert-Fnajoute les successeurs en debut de listefringe= [D;E;C]DEBCA35 / 46Intelligence articielle
NAlgorithmes de recherche en IA
Recherche en profondeur d'abord
La fonctionInsert-Fnajoute les successeurs en debut de listefringe= [H;I;E;C]DE HIBCA35 / 46Intelligence articielle
NAlgorithmes de recherche en IA
Recherche en profondeur d'abord
La fonctionInsert-Fnajoute les successeurs en debut de listefringe= [I;E;C]DE HIBCA35 / 46Intelligence articielle
NAlgorithmes de recherche en IA
Recherche en profondeur d'abord
La fonctionInsert-Fnajoute les successeurs en debut de listefringe= [E;C]DE HIBCA35 / 46Intelligence articielle
NAlgorithmes de recherche en IA
Recherche en profondeur d'abord
La fonctionInsert-Fnajoute les successeurs en debut de listefringe= [J;K;C]DEHIJKBCA
35 / 46Intelligence articielle
NAlgorithmes de recherche en IA
Recherche en profondeur d'abord
La fonctionInsert-Fnajoute les successeurs en debut de listefringe= [K;C]DEHIJKBCA
35 / 46Intelligence articielle
NAlgorithmes de recherche en IA
Recherche en profondeur d'abord
La fonctionInsert-Fnajoute les successeurs en debut de listefringe= [C]DEHIJKBCA
35 / 46Intelligence articielle
NAlgorithmes de recherche en IA
Recherche en profondeur d'abord
La fonctionInsert-Fnajoute les successeurs en debut de listefringe= [F;G]DEFGHIJKBCA
35 / 46Intelligence articielle
NAlgorithmes de recherche en IA
Recherche en profondeur d'abord
La fonctionInsert-Fnajoute les successeurs en debut de listefringe= [G]DEFGHIJKBCA
35 / 46Intelligence articielle
NAlgorithmes de recherche en IA
Recherche en profondeur d'abord
La fonctionInsert-Fnajoute les successeurs en debut de listefringe= []DEFGHIJKBCA
35 / 46Intelligence articielle
NAlgorithmes de recherche en IA
Recherche en profondeur d'abord
Non complet dans les espaces d'etats innis ou avec boucle Il est possible d'ajouter un test pour detecter les repetitionsComplexite en temps :O(bm)Tres mauvais simest beaucoup plus grand quebComplexite en espace :O(bm)Lineaire!