[PDF] [PDF] Intelligence Artificielle Recherche - Université Paris Cité





Previous PDF Next PDF



6.3.1 Parcours en profondeur itératif 6.3.2 Parcours en profondeur

Université Paris Diderot – LI0436 – 08/09. Ch6. Les arbres. 6.3.1 Parcours en profondeur itératif procedure Parcours(A); var X : sommet ;.



Cours 3: Arbres. Parcours.

Parcourir en profondeur. Parcours en profondeur d'abord: ? on parcourt récursivement. Voici un algorithme générique itératif de parcours d'arbre.



Algorithmes de recherche

Parcours aveugles non informés : profondeur largeur. Parcours informés. Caractéristiques de la recherche en profondeur itérative. Complète.



Arbres et récursivité

Jul 1 2020 1.4 Fonctions récursives et parcours d'arbre ... De même que pour le parcours en profondeur itératif



Intelligence Artificielle Recherche

Recherche de parcours la profondeur du nœud i.e.



Travaux Pratiques no2

Parcours en profondeur itératif. Le parcours en profondeur des arbres doit se faire récursivement pour supprimer la récursivité



Parcours dun graphe

Apr 1 2013 A savoir. A la suite de cette séance



HE01LI – 15/16 def Parcours(A) : 0 X - Université Paris Diderot

Université Paris Diderot – HE01LI – 15/16. Ch5. Recherche de motifs def Parcours(A) : Figure 5.3: Parcours en profondeur itératif



Chapitre 3 : Exploration dun graphe - Algorithmique de graphes

3 Parcours en profondeur (DFS). Prolongement d'une chaˆ?ne élémentaire (appelé racine) la suite d'ensembles définie itérativement comme.



TD 6 Arbres binaires 1 Exercices

Nov 10 2005 Donner l'algorithme itératif de parcours en ordre préfixe d'un Arbre ... des parcours en profondeur d'un Arbre binaire (on suppose que.



[PDF] 631 Parcours en profondeur itératif

Université Paris Diderot – LI0436 – 08/09 Ch6 Les arbres 6 3 1 Parcours en profondeur itératif procedure Parcours(A); var X : sommet ;



[PDF] Algorithmique des graphes - Cours 4 – Parcours en profondeur

Parcours en profondeur : le principe Exploration d'un graphe donné par un agent mobile Il peut se déplacer d'un sommet au voisin en suivant une arête les



[PDF] Parcours de graphes [gp] - Algorithmique - Unisciel

Le parcours en profondeur dit aussi par sondage L'algorithme étant récursif la version itérative équivalente utilisera une pile Exemple



[PDF] Parcours en profondeur et recherche de circuits - UFR SEGMI

Analysons la complexité dans le pire des cas de cette détection de circuit: la boucle pour comporte au maximum m (nombre d'arcs) itérations Pour chacune on 



[PDF] Parcours de graphes - IGM

parcours principaux pour les graphes sont les parcours en profondeur et en largeur Ce cha- pitre couvre les algorithmes correspondants ainsi que des 



[PDF] Première partie : Algorithmique avancée pour les graphes - CNRS

Une façon naïve de déterminer les différentes SCC d'un graphe consiste à faire un parcours (en largeur ou en profondeur) à partir de chacun des sommets du 



[PDF] Algorithmes de recherche - Irif

Parcours aveugles non informés : profondeur largeur Parcours informés Caractéristiques de la recherche en profondeur itérative Complète



[PDF] Parcours dun arbre binaire

Parcours d'un arbre binaire Un arbre binaire est un arbre avec racine dans lequel tout noeud a au plus deux fils : un éventuel fils



[PDF] Cours 3: Arbres Parcours - LIX-polytechnique

Parcours en profondeur d'abord: ? on parcourt récursivement Mais il reste trois possibilités ? Préfixe: traiter la racine parcourir le sous-arbre 



[PDF] Intelligence Artificielle Recherche - Université Paris Cité

Recherche de parcours la profondeur du nœud i e la distance entre le nœud et la racine de l'arbre Recherche iterative en profondeur

  • Quelle est la différence entre le parcours préfixe et le parcours Post-fixé ?

    Parcours préfixe : on traite la racine, puis le sous-arbre gauche, puis le sous-arbre droit. Parcours infixe : on traite le sous-arbre gauche, puis la racine, puis le sous-arbre droit. Parcours postfixe : on traite le sous-arbre gauche, puis le sous-arbre droit, puis la racine.

  • Comment faire un parcours en largeur ?

    Un parcours en largeur débute à partir d'un nœud source. Puis il liste tous les voisins de la source, pour ensuite les explorer un par un. Ce mode de fonctionnement utilise donc une file dans laquelle il prend le premier sommet et place en dernier ses voisins non encore explorés.
  • 2.2 Parcours de graphes
    2. ils ne poss?nt pas de cycle : il n'est donc possible d'aller de la racine à un sommet arbitraire v que par un seul chemin ; 3. La preuve de cette affirmation est laissée en exercice.

Intelligence Artificielle

Recherche

Bruno Bouzy

http://web.mi.parisdescartes.fr/~bouzy bruno.bouzy@parisdescartes.fr

Licence 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

N

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)

5 / 46Intelligence articielle

N

Algorithmes de recherche en IA

Agent avec des objectifs explicites

6 / 46Intelligence articielle

N

Algorithmes de recherche en IA

Exemple de probleme: le voyage en

RoumanieAradZerind

TimisoaraOradea

Sibiu Lugoj

Mehadia

Dobreta

CraiovaRimnicu VilceaFagaras

PitestiBucharest

GiurgiuUrziceni

Hirsova

EforieVasluiLasiNeamt

75
11871

140151

111
70
75
12080
14699

13897211

101

908598

801429287

7 / 46Intelligence articielle

N

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)

8 / 46Intelligence articielle

N

Algorithmes 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 N

Algorithmes de recherche en IA

Exemple : Le monde de l'aspirateur

Probleme deterministe completement observableEtat initial : #5

Etat nal : #8

Solution :hdroite,aspirei10 / 46Intelligence articielle N

Algorithmes 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 N

Algorithmes 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 N

Algorithmes 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

N

Algorithmes 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

N

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)

15 / 46Intelligence articielle

N

Algorithmes 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 R

REtats?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

N

Algorithmes 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

N

Algorithmes 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

N

Algorithmes de recherche en IA

Exemple de problemes reels

Recherche de parcours

Itineraires automatiques, guidage routier, planication de routes aeriennes, routage sur les reseaux informatiques, ...Robotique

Assemblage automatique, navigation autonome, ...

Planication et ordonnancement

Horaires, organisation de t^aches, allocation de ressources, ...

19 / 46Intelligence articielle

N

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)

20 / 46Intelligence articielle

N

Algorithmes de recherche en IA

Algorithme de recherche de base

(recherche aveugle)Idee de base

Recherche 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 nal

21 / 46Intelligence articielle

N

Algorithmes de recherche en IA

Exemple : arbre de recherche

Arad

22 / 46Intelligence articielle

N

Algorithmes de recherche en IA

Exemple : arbre de recherche

SibiuZerindTimisoaraArad

22 / 46Intelligence articielle

N

Algorithmes de recherche en IA

Exemple : arbre de recherche

AradFagarasOradeaRimnicu VilceaSibiuZerindTimisoaraArad

22 / 46Intelligence articielle

N

Algorithmes de recherche en IA

Implemetation des algorithmes de

rechercheStructure de donneesnudqui contientetat parent enfant profondeur

co^ut du chemin (noteg(x))Expandcree de nouveaux nudsInsertAllinsere de nouveaux nuds dans la liste a traiter23 / 46Intelligence articielle

N

Algorithmes de recherche en IA

Algorithme de recherche dans les arbres

24 / 46Intelligence articielle

N

Algorithmes 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 nud

le 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

N

Algorithmes 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 si

elle 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 N

Algorithmes 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., le

nombre 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 N

Algorithmes 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

N

Algorithmes de recherche en IA

Recherche en largeur d'abord

La fonctionInsert-Fnajoute les successeurs en n de listefringe= [A]A

29 / 46Intelligence articielle

N

Algorithmes de recherche en IA

Recherche en largeur d'abord

La fonctionInsert-Fnajoute les successeurs en n de listefringe= [B;C]BCA

29 / 46Intelligence articielle

N

Algorithmes de recherche en IA

Recherche en largeur d'abord

La fonctionInsert-Fnajoute les successeurs en n de listefringe= [C;D;E]DEBCA

29 / 46Intelligence articielle

N

Algorithmes de recherche en IA

Recherche en largeur d'abord

La fonctionInsert-Fnajoute les successeurs en n de listefringe= [D;E;F;G]DEFGBCA

29 / 46Intelligence articielle

N

Algorithmes de recherche en IA

Recherche en largeur d'abord

La fonctionInsert-Fnajoute les successeurs en n de listefringe= [E;F;G]DEFGBCA

29 / 46Intelligence articielle

N

Algorithmes de recherche en IA

Exemple de probleme: le voyage en

RoumanieAradZerind

TimisoaraOradea

Sibiu Lugoj

Mehadia

Dobreta

CraiovaRimnicu VilceaFagaras

PitestiBucharest

GiurgiuUrziceni

Hirsova

EforieVasluiLasiNeamt

75
11871

140151

111
70
75
12080
14699

13897211

101

908598

801429287

30 / 46Intelligence articielle

N

Algorithmes 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 N

Algorithmes de recherche en IA

Recherche en largeur d'abord

b= 1010000 nuds par seconde

1000 octets de memoire pour un nuds

ProfondeurNudsTempsMemoire

810

931 heures1 Teraoctet, 1024 Go

1210

1335 ans10 Petaoctets, 1024 Teraoctet

32 / 46Intelligence articielle

N

Algorithmes 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 510
5 5S, 0

33 / 46Intelligence articielle

N

Algorithmes 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 510
5

5A, 1B, 15C, 5S, 0

33 / 46Intelligence articielle

N

Algorithmes 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 510
5 5

G, 11A, 1B, 15C, 5S, 0

33 / 46Intelligence articielle

N

Algorithmes 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 510
5 5

G, 11G, 10A, 1B, 15C, 5S, 0

33 / 46Intelligence articielle

N

Algorithmes 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 510
5 5

G, 11G, 10A, 1B, 15C, 5S, 0

33 / 46Intelligence articielle

N

Algorithmes 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 N

Algorithmes de recherche en IA

Recherche en profondeur d'abord

La fonctionInsert-Fnajoute les successeurs en debut de listefringe= [A]A

35 / 46Intelligence articielle

N

Algorithmes de recherche en IA

Recherche en profondeur d'abord

La fonctionInsert-Fnajoute les successeurs en debut de listefringe= [B;C]BCA

35 / 46Intelligence articielle

N

Algorithmes de recherche en IA

Recherche en profondeur d'abord

La fonctionInsert-Fnajoute les successeurs en debut de listefringe= [D;E;C]DEBCA

35 / 46Intelligence articielle

N

Algorithmes de recherche en IA

Recherche en profondeur d'abord

La fonctionInsert-Fnajoute les successeurs en debut de listefringe= [H;I;E;C]DE HIBCA

35 / 46Intelligence articielle

N

Algorithmes de recherche en IA

Recherche en profondeur d'abord

La fonctionInsert-Fnajoute les successeurs en debut de listefringe= [I;E;C]DE HIBCA

35 / 46Intelligence articielle

N

Algorithmes de recherche en IA

Recherche en profondeur d'abord

La fonctionInsert-Fnajoute les successeurs en debut de listefringe= [E;C]DE HIBCA

35 / 46Intelligence articielle

N

Algorithmes de recherche en IA

Recherche en profondeur d'abord

La fonctionInsert-Fnajoute les successeurs en debut de listefringe= [J;K;C]DE

HIJKBCA

35 / 46Intelligence articielle

N

Algorithmes de recherche en IA

Recherche en profondeur d'abord

La fonctionInsert-Fnajoute les successeurs en debut de listefringe= [K;C]DE

HIJKBCA

35 / 46Intelligence articielle

N

Algorithmes de recherche en IA

Recherche en profondeur d'abord

La fonctionInsert-Fnajoute les successeurs en debut de listefringe= [C]DE

HIJKBCA

35 / 46Intelligence articielle

N

Algorithmes de recherche en IA

Recherche en profondeur d'abord

La fonctionInsert-Fnajoute les successeurs en debut de listefringe= [F;G]DEFG

HIJKBCA

35 / 46Intelligence articielle

N

Algorithmes de recherche en IA

Recherche en profondeur d'abord

La fonctionInsert-Fnajoute les successeurs en debut de listefringe= [G]DEFG

HIJKBCA

35 / 46Intelligence articielle

N

Algorithmes de recherche en IA

Recherche en profondeur d'abord

La fonctionInsert-Fnajoute les successeurs en debut de listefringe= []DEFG

HIJKBCA

35 / 46Intelligence articielle

N

Algorithmes 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 repetitions

Complexite en temps :O(bm)Tres mauvais simest beaucoup plus grand quebComplexite en espace :O(bm)Lineaire!

Non optimale

36 / 46Intelligence articielle

N

Algorithmes de recherche en IA

Recherche en profondeur limitee

Algorithme de recherche en profondeur d'abord, mais avec une limitelsur la profondeurLes nuds de profondeurln'ont pas de successeursExemple pourl= 2A

37 / 46Intelligence articielle

N

Algorithmes de recherche en IA

Recherche en profondeur limitee

Algorithme de recherche en profondeur d'abord, mais avec une limitelsurquotesdbs_dbs44.pdfusesText_44
[PDF] algorithme parcours en profondeur python

[PDF] parcours en largeur graphe java

[PDF] conflit de puissance définition

[PDF] parcours lecture acces pas cher

[PDF] parcours lecture pdf

[PDF] parcours lecture le petit chaperon rouge

[PDF] parcours lecture acces avis

[PDF] parcours lecture occasion

[PDF] coexistence pacifique cours

[PDF] archives militaire en ligne

[PDF] livret militaire en ligne

[PDF] la coexistence pacifique de 1953 ? 1962 pdf

[PDF] cornière catnic

[PDF] corniere galva pour brique

[PDF] corniere pour linteau brique