Diapositive 1 - ESIEE Paris

Diapositive 1 - ESIEE Paris

PR3602 Rsolution de problmes en intelligence artificielle : les algorithmes A* Quest-ce que lintelligence ? Quest-ce que lintelligence ? Quest-ce que lintelligence ? Quest-ce que lintelligence ? Quest-ce que lintelligence ? On qualifie dintelligent un comportement qui vise apporter une solution optimale un problme Quest-ce que lintelligence ? On qualifie dintelligent un comportement qui vise apporter une solution optimale

un problme, ou une bonne solution en un temps acceptable Notion dheuristique Dans le dictionnaire, ladjectif euristique ou heuristique (du grec heuriskin, trouver do le fameux Eurka ! dArchimde), signifie qui facilite la dcouverte, qui a une utilit dans la recherche (scientifique ou autre) . Un exemple : le problme des 8 reines Un exemple : le problme des 8 reines Une solution Un exemple : le problme des 8 reines

Supposons quon ait russi placer 3 reines Un exemple : le problme des 8 reines O placer la quatrime ? Un exemple : le problme des 8 reines Les possibilits Un exemple : le problme des 8 reines 1re stratgie : recherche aveugle 2me

stratgie : recherche avec heuristique Un exemple : le problme des 8 reines valuons les possibilits Un exemple : le problme des 8 reines valuons les possibilits Un exemple : le problme des 8 reines 7 valuons les possibilits

Un exemple : le problme des 8 reines 7 valuons les possibilits Un exemple : le problme des 8 reines 7 valuons les possibilits Un exemple : le problme des 8 reines 7 11

valuons les possibilits Un exemple : le problme des 8 reines 7 7 8 8 6 9 7 11

6 7 9 9 7 8 8 7 valuons les possibilits 2 me

exemple Le voyageur de commerce Le voyageur de commerce Donnes : un rseau R = (E, , c) E = {1, , n} (n villes) y (x) sil y a une route directe de x y c(x,y) = cot pour se rendre de x y Problme : trouver un circuit dans R passant une fois et une seule par chaque ville (circuit hamiltonien), de cot minimum Cest un problme NP-difficile ! P=NP? Soit L un problme de dcision L est dans P sil peut tre rsolu par un

algorithme de complexit polynomiale (en O(nk)) L est dans NP (nondeterministic polynomial time) si lon peut vrifier en temps polynomial quune instance donne en est solution L est NP-difficile si tout problme dans NP peut tre rduit L par une transformation de cot polynomial L est NP-complet sil est dans NP et sil est NP-difficile Note : tout ceci reste informel NP-difficile NP-difficile

NP-complet NP P = NP = NP-complet P P NP P = NP 3 me exemple : jeu du taquin 3

me exemple : jeu du taquin Donnes : Situation de dpart D Mouvements autoriss 8 3 1 6 4 7

1 Situation darrive A 2 2 7 7 5 3 4 6 5 2

8 1 7 3 4 6 5 Problme : passer de D A par une suite de mouvements autoriss de longueur minimale Graphe de rsolution de problme 2 8 3 1 6 4 7 5

2 8 3 1 6 4 7 5 2 8 3 6 4 1 7 5 2 8 3 6 4 1 7 5 8 3 2 6 4 1 7 5 8 3 2 1 4 7 6 5 2 8 3 1

4 7 6 5 2 8 3 1 4 7 6 5 2 8 3 7 1 4 6 5 2 3 1 8 4 7 6 5 2 3 1 8 4 7 6 5 2 3 1 8 4 7 6 5

2 8 3 1 6 4 7 5 2 8 3 1 4 7 6 5 2 8 1 4 3 7 6 5 2 8 3 1 4 5 7 6 2 8 3 1 6 7 5 4 2 8 1 6 3 7 5 4

2 8 3 1 6 7 5 4 Procdure Recherche avec graphe Rfrence : Principes dintelligence artificielle Nils J. Nilsson d 283 1 164 75 4 283 164 7 5

283 2 1 4 765 283 3 164 75 283 64 175 M {1,2,3} Question Question:: comment comment rordonner rordonnerla laliste

liste OUVERT OUVERT?? {4} OUVERT FERME n (d) () () (d) d (1,2,3) (2,3) (d,1) 1 (2,3,4) Rordonner la liste OUVERT

Par ordre de profondeur dcroissante (stratgie en profondeur dabord ) Par ordre de profondeur croissante (stratgie en largeur dabord ) Selon une heuristique ou fonction dvaluation Largeur dabord Profondeur dabord Rordonner la liste OUVERT Par ordre de profondeur dcroissante (stratgie en profondeur

dabord ) Par ordre de profondeur croissante (stratgie en largeur dabord ) Selon une heuristique ou fonction dvaluation STRATEGIE STRATEGIES STRATEGIES AVEUGLES AVEUGLES STRATEGIE INFORMEE INFORMEE Rordonner la liste OUVERT Principe de la stratgie informe :

on a intrt choisir en priorit un sommet ayant la plus grande probabilit de se trouver sur un chemin menant au but Question Question :: comment comment estimer estimer cette cette probabilit probabilit ?? Fonction dvaluation A chaque sommet du graphe G dvelopp, elle associe un rel positif Elle dpend du domaine dapplication et du problme rsoudre Question Question :: trouver trouver une

une bonne bonne fonction fonction dvaluation dvaluation pour pour le le problme problme du du taquin taquin Fonction dvaluation Pour tout sommet n : f(n) = w(n) + p(n) Avec : w(n) = nombre de cases mal places p(n) = profondeur du sommet n dans G M

OUVERT FERME (s) () n s M OUVERT FERME n (s) () () (s) s s M {a,b,c}

OUVERT FERME n (s) () () (s) s (a,b,c) (b,a,c) s a b c M OUVERT

(s) () {a,b,c} (a,b,c) (b,a,c) (a,c) FERME () (s) s n s a (s,b) b b

c M OUVERT (s) () {a,b,c} (a,b,c) (b,a,c) (a,c) {d,e,f} (a,c,d,e,f) (d,e,a,c,f) FERME () (s) (s,b) s

n s a b c d e f b M OUVERT (s) ()

{a,b,c} (a,b,c) (b,a,c) (a,c) {d,e,f} (a,c,d,e,f) (d,e,a,c,f) (e,a,c,f) FERME () (s) (s,b) (s,b,d) s n s a b

c d e f b d M OUVERT (s) () {a,b,c} (a,b,c) (b,a,c) (a,c) {d,e,f} (a,c,d,e,f) (d,e,a,c,f)

(e,a,c,f) {g,h} (e,a,c,f,g,h) (e,a,c,f,g,h) FERME () (s) (s,b) (s,b,d) s n s a b c

d e f b d g h M OUVERT (s) () {a,b,c} (a,b,c) (b,a,c) (a,c)

{d,e,f} (a,c,d,e,f) (d,e,a,c,f) (e,a,c,f) {g,h} (e,a,c,f,g,h) (e,a,c,f,g,h) (a,c,f,g,h) FERME () (s) (s,b) s n s a b

c d e f b (s,b,d) d (s,b,d,e) e g h

M OUVERT (s) () {a,b,c} (a,b,c) (b,a,c) (a,c) {d,e,f} (a,c,d,e,f) (d,e,a,c,f) (e,a,c,f) {g,h} (e,a,c,f,g,h) (e,a,c,f,g,h) (a,c,f,g,h) {i,j} (a,c,f,g,h,i,j) (i,a,c,f,g,h,j) FERME

() (s) (s,b) s n s a b c d e f i

j b (s,b,d) d (s,b,d,e) e g h M OUVERT (s)

() {a,b,c} (a,b,c) (b,a,c) (a,c) {d,e,f} (a,c,d,e,f) (d,e,a,c,f) (e,a,c,f) {g,h} (e,a,c,f,g,h) (e,a,c,f,g,h) (a,c,f,g,h) {i,j} (a,c,f,g,h,i,j) (i,a,c,f,g,h,j) (a,c,f,g,h,j) FERME () (s) (s,b)

s n s a b c d e f i j b

(s,b,d) d (s,b,d,e) e (s,b,d,e,i) i g h M OUVERT FERME (s)

() () (s) {a,b,c} (a,b,c) (b,a,c) (a,c) (s,b) {d,e,f} (a,c,d,e,f) (d,e,a,c,f) (e,a,c,f) (s,b,d) {g,h} (e,a,c,f,g,h) (e,a,c,f,g,h) (a,c,f,g,h) (s,b,d,e) {i,j} (a,c,f,g,h,i,j) (i,a,c,f,g,h,j) (a,c,f,g,h,j) (s,b,d,e,i) {k} (a,c,f,g,h,j,k)

(k,a,c,f,g,h,j) s n s a b c d e f i j

b d e g h i k M OUVERT FERME (s) () () (s) {a,b,c} (a,b,c) (b,a,c)

(a,c) (s,b) {d,e,f} (a,c,d,e,f) (d,e,a,c,f) (e,a,c,f) (s,b,d) {g,h} (e,a,c,f,g,h) (e,a,c,f,g,h) (a,c,f,g,h) (s,b,d,e) {i,j} (a,c,f,g,h,i,j) (i,a,c,f,g,h,j) (a,c,f,g,h,j) (s,b,d,e,i) {k} (a,c,f,g,h,j,k) (k,a,c,f,g,h,j) (a,c,f,g,h,j) (s,b,d,e,i,k) s

n s a b c d e f i j b d e

g h i k k M OUVERT FERME (s) () () (s) {a,b,c} (a,b,c) (b,a,c) (a,c) (s,b) {d,e,f} (a,c,d,e,f)

(d,e,a,c,f) (e,a,c,f) (s,b,d) {g,h} (e,a,c,f,g,h) (e,a,c,f,g,h) (a,c,f,g,h) (s,b,d,e) {i,j} (a,c,f,g,h,i,j) (i,a,c,f,g,h,j) (a,c,f,g,h,j) (s,b,d,e,i) {k} (a,c,f,g,h,j,k) (k,a,c,f,g,h,j) (a,c,f,g,h,j) (s,b,d,e,i,k) {l,m} (a,c,f,g,h, j,l,m) (l,a,c,f,g,h, j,m)

s n s a b c d e f i j b

d e g h i k k l m OUVERT FERME n (s) () () (s) s

{a,b,c} (a,b,c) (b,a,c) (a,c) (s,b) b {d,e,f} (a,c,d,e,f) (d,e,a,c,f) (e,a,c,f) (s,b,d) d {g,h} (e,a,c,f,g,h) (e,a,c,f,g,h) (a,c,f,g,h) (s,b,d,e) e {i,j} (a,c,f,g,h,i,j) (i,a,c,f,g,h,j) (a,c,f,g,h,j) (s,b,d,e,i) i {k}

(a,c,f,g,h,j,k) (k,a,c,f,g,h,j) (a,c,f,g,h,j) (s,b,d,e,i,k) k {l,m} (a,c,f,g,h, j,l,m) (l,a,c,f,g,h, j,m) (a,c,f,g,h, (s,b,d,e,i,k,l) l j,m) s M g a b

c d e f i j h k l m 283

164 7 5 283 14 765 2 3 184 765 283 14 765 283 16 754 283 83

83 283 23 23 28 283 28 283 6 4 264 214 714 184 184 143 145 163 1 6 175 175 765 65 765 765 765 76 754 754 Exploration en largeur Exploration en profondeur

Recently Viewed Presentations

  • NSF Briefing on Gender Differences Report (NSF Grant No. 0336796)

    NSF Briefing on Gender Differences Report (NSF Grant No. 0336796)

    Clock stoppers had a lower chance of promotion to associate professor (about 80%) at any time (given that they had not been promoted until then) than those who did not stop the clock. Everything else being equal, however, stopping-the-clock did...
  • Graphing Exercise - Moore Public Schools

    Graphing Exercise - Moore Public Schools

    Graph time on the horizontal axis and the distance Carlos has traveled on the vertical axis. Sheet 4 - Interpreting Graphs. The Mount Southington Ski area claims its lift travels 400 feet per minute and is 2000 feet long. The...
  • Terminating Franchisees for Fraud or Abandonment: Practical Considerations

    Terminating Franchisees for Fraud or Abandonment: Practical Considerations

    Repudiatory conduct is established if it is such as to "convey to a reasonable person, in the situation of the other party, renunciation either of the contract as a whole or of a fundamental obligation under it." (See Mr Rental...
  • History of Medieval Drama - Cuyamaca College

    History of Medieval Drama - Cuyamaca College

    History of Medieval Drama From Roman Spectacle to Miracle, Morality and Mystery Plays Roman Times EVERYMAN Themes: Way to Salvation, Death, Worldly Encumbrances, The Sacraments, Priesthood, Power of the Church, Grace & Works.
  • Graduate Orientation - David R. Cheriton School of Computer ...

    Graduate Orientation - David R. Cheriton School of Computer ...

    You are required to apply for OGS and NSERC if you hold an RA and are eligible (average over85%) CheritonScholarships Open to all Ph.D. students within program limits
  • School Dude - Fitchburg State University

    School Dude - Fitchburg State University

    School Dude's Work Order Request System Here is the MySchoolBuilding.com login page for Fitchburg State College where you as a Requestor will enter yourself into the system.
  • Representing data

    Representing data

    What type of graph would you use when graphing... Different salaries of careers in science? Funding for NASA over the years? Percentage of pollutants from humans in Lake Okeechobee?
  • Whats New in Social Studies? August 15, 2013

    Whats New in Social Studies? August 15, 2013

    CHS (HS #1) Other factors… In 2011-12 levels were combined. ... Test banks posted to intranet for use in classroom instruction, quizzes and unit tests. Process of benchmarking. Establish the pacing guide. Create the test. Post test to Achievement Series,...