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

  • Unit 1, Week 1

    Unit 1, Week 1

    Ask: What is an antonym of collective? Context Clue: "The league had one collective goal: All members wanted to improve bicycling conditions" (Bike Ride, Anyone?, pg 398). Unit 4 Week 2 adept Key Words Define: Someone adept is highly skilled....
  • Aucun titre de diapositive

    Aucun titre de diapositive

    They cool the planet, help regulate the seasons, recharge groundwater, restore soil fertility and stop erosion, regenerate the ozone layer, bind atmospheric carbon dioxide, and purify the toxins we put everywhere. ... A high amount of tannic and gallic acids...
  • Understanding Solid Figures A Mini Lesson by Diana

    Understanding Solid Figures A Mini Lesson by Diana

    A solid figure whose ends are congruent, parallel polygons, and whose sides are rectangles is a prism. These are prisms. Practice counting vertices: Remember to count the vertices that you can't see. 8 0 4 Practice counting faces: 6 Remember...
  • MSc - CD4040 - Internet and Web Research Topics

    MSc - CD4040 - Internet and Web Research Topics

    This tutorial is intended to describe the relationship between 802.11 and other LANs, and to describe some of the details of its operation. It is assumed that the audience is familiar with serial data communications, the use of LANs and...
  • Suprtool Module 0 - Robelle

    Suprtool Module 0 - Robelle

    Objectives of this course Learn what Suprtool can do for you Learn the basic commands, variations, options, and syntax Learn advanced techniques Apply what you've just learned; get hands-on experience Basic Modules Module 1 - Introduction to Suprtool Module 2...
  • Management Sciences New Graduate Student Orientation

    Management Sciences New Graduate Student Orientation

    Phil Bezaire, [email protected], TC 3112. Application Requirements. Application Deadline . to Lisa Hendel by December 1, 2016. Students must have: min. 80% average . ... Management Sciences New Graduate Student Orientation Last modified by:
  • EARLY AMERICAN THEATRE 1700s  Civil War Starting in

    EARLY AMERICAN THEATRE 1700s Civil War Starting in

    By this artifice, the dramatist seeks to engage the audience's recently refreshed sense of fear or moral disapproval, while simultaneously maintaining the posture that the drama so produced is timely and socially engaged. Action melodrama is another type of melodrama...
  • 2010 Alabama Course of Study: Mathematics

    2010 Alabama Course of Study: Mathematics

    English Language ArtsCourse of Study OverviewK-5. Session 2 . I would like to welcome you to the third webinar for the 2010 ELA COS overview.We are still in phase one of this process. In the first webinar all K-12 administrators...