inteligenta artificiala: strategii de cautare

105
Inteligenţă artificială 2. Strategii de căutare Florin Leon Universitatea Tehnică „Gheorghe Asachi” din Iaşi Facultatea de Automatică şi Calculatoare http://florinleon.byethost24.com/curs_ia.htm Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

Upload: enrollinfo

Post on 26-Jun-2015

831 views

Category:

Documents


12 download

DESCRIPTION

Inteligenta artificiala2. Strategii de cautareFlorin LeonUniversitatea Tehnica „Gh. Asachi” Iaşi Facultatea de Automatică şi Calculatoare http://florinleon.byethost24.com/curs_ia.htmFlorin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htmStrategii de căutare1. 2. 3. 4. Rezolvarea problemelor prin căutare Căutarea neinformată (oarbă) Căutarea informată (euristică) Concluzii2Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htmS

TRANSCRIPT

Page 1: Inteligenta artificiala: Strategii de cautare

Inteligenţă artificială

2. Strategii de căutare Florin Leon

Universitatea Tehnică „Gheorghe Asachi” din Iaşi

Facultatea de Automatică şi Calculatoare

http://florinleon.byethost24.com/curs_ia.htm

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

Page 2: Inteligenta artificiala: Strategii de cautare

2

Strategii de căutare

1. Rezolvarea problemelor prin căutare

2. Căutarea neinformată (oarbă)

3. Căutarea informată (euristică)

4. Concluzii

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

Page 3: Inteligenta artificiala: Strategii de cautare

3

Strategii de căutare

1. Rezolvarea problemelor prin căutare

2. Căutarea neinformată (oarbă)

3. Căutarea informată (euristică)

4. Concluzii

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

Page 4: Inteligenta artificiala: Strategii de cautare

4

Probleme de căutare

15 puzzle Turnurile din Hanoi

Labirinturi 8 regine Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

Page 5: Inteligenta artificiala: Strategii de cautare

5

Probleme de căutare reale

Planificare Găsirea rutelor

Programarea telescoapelor Navigarea roboţilor militari Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

Page 6: Inteligenta artificiala: Strategii de cautare

6

Alte aplicaţii

Găsirea rutelor

Rezervarea biletelor pentru avioane, trenuri etc.

Reţele de calculatoare

Distribuţia coletelor poştale

Asemănătoare problemei comis-voiajorului

Proiectarea instalaţiilor, VLSI

Proiectarea cablurilor şi ţevilor într-o clădire, într-o maşină

Conectarea pinilor circuitelor electronice, cu scopul de a minimiza aria şi de a maximiza viteza prin minimizarea lungimii conexiunilor

Crearea medicamentelor

Găsirea substanţelor celor mai potrivite care permit substanţei active să se cupleze la zona dorită

Jocuri video

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

Page 7: Inteligenta artificiala: Strategii de cautare

7

Componentele unei probleme de căutare

Starea iniţială

Starea scop

O mulţime de operatori

Funcţia de evaluare – pentru căutarea informată

Cât de departe este fiecare stare de starea scop

Conţine cunoştinţe despre fiecare problemă în parte

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

Page 8: Inteligenta artificiala: Strategii de cautare

8

Formalizarea unei probleme de căutare

Q este o mulţime finită de stări

S Q este o mulţime nevidă de stări iniţiale

G Q este o mulţime nevidă de stări scop

succs : Q (Q) reprezintă mulţimea de stări care pot fi atinse din starea s într-un singur pas

Funcţia primeşte o singură stare ca argument şi returnează o mulţime de stări ca rezultat

cost : Q2 R+ reprezintă costul de a ajunge din starea s în starea s’

Funcţia primeşte 2 stări şi returnează un număr pozitiv

cost(s,s’ ) este definită doar când s’ succs(s)

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

Page 9: Inteligenta artificiala: Strategii de cautare

9

Definiţii

Spaţiu de căutare (spaţiul problemei)

Mulţimea tuturor stărilor care pot fi atinse prin aplicarea operatorilor disponibili

Soluţie

Seria de operatori care transformă starea iniţială într-o stare scop

Metodă de rezolvare a unei probleme

O procedură pentru găsirea unei soluţii

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

Page 10: Inteligenta artificiala: Strategii de cautare

10

Rezolvarea unei probleme prin căutare

Stare

iniţială

Stare

scop

Spaţiul de căutare

(spaţiul problemei)

Soluţie

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

Page 11: Inteligenta artificiala: Strategii de cautare

11

Soluţia

O soluţie este o cale care leagă nodul iniţial de oricare din nodurile scop

I

G

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

Page 12: Inteligenta artificiala: Strategii de cautare

12

Soluţia

O soluţie este o cale care leagă nodul iniţial de oricare din nodurile scop

Costul căii este suma costurilor arcelor care formează calea

O soluţie optimă este soluţia de cost minim

Unele probleme nu au soluţie!

I

G

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

Page 13: Inteligenta artificiala: Strategii de cautare

13

Existenţa soluţiei

12 14 11

15 10

13 9 5 6 7 8

4 3 2 1

12 15 11

14 10

13 9 5 6 7 8

4 3 2 1

?

1000 $

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

Page 14: Inteligenta artificiala: Strategii de cautare

14

Dimensiunea spaţiului de căutare

8-puzzle 9! = 362.880 stări

15-puzzle 16! 2 · 1013 stări

24-puzzle 25! 1025 stări

Doar jumătate din aceste stări pot fi atinse dintr-o stare dată

Dar într-o abordare simplă acest lucru nu se cunoaşte dinainte

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

Page 15: Inteligenta artificiala: Strategii de cautare

15

Căutarea în spaţiul problemei

Deseori construirea unei reprezentări complete a grafului de căutare nu este fezabilă sau este prea costisitoare

Algoritmul de rezolvare trebuie să construiască soluţia prin explorarea unei porţiuni restrânse a grafului

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

Page 16: Inteligenta artificiala: Strategii de cautare

16

Căutarea în spaţiul problemei

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

Page 17: Inteligenta artificiala: Strategii de cautare

17

Căutarea în spaţiul problemei

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

Page 18: Inteligenta artificiala: Strategii de cautare

18

Căutarea în spaţiul problemei

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

Page 19: Inteligenta artificiala: Strategii de cautare

19

Căutarea în spaţiul problemei

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

Page 20: Inteligenta artificiala: Strategii de cautare

20

Căutarea în spaţiul problemei

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

Page 21: Inteligenta artificiala: Strategii de cautare

21

Căutarea în spaţiul problemei

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

Page 22: Inteligenta artificiala: Strategii de cautare

22

Reprezentarea

Care este spaţiul problemei?

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

Page 23: Inteligenta artificiala: Strategii de cautare

23

Costul unui pas orizontal / vertical = 1 Costul unui pas diagonal = 2

Abordarea 1

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

Page 24: Inteligenta artificiala: Strategii de cautare

24

Soluţia optimă

Această cale este cea mai scurtă în spaţiul discretizat, dar nu şi în spaţiul iniţial continuu

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

Page 25: Inteligenta artificiala: Strategii de cautare

25

Abordarea 2

Costul unui pas: lungimea segmentului

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

Page 26: Inteligenta artificiala: Strategii de cautare

26

Abordarea 2

Costul unui pas: lungimea segmentului

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

Page 27: Inteligenta artificiala: Strategii de cautare

27

Soluţia

Cea mai scurtă cale în acest spaţiu este cea mai scurtă şi în spaţiul iniţial

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

Page 28: Inteligenta artificiala: Strategii de cautare

28

Misionarii şi canibalii

3 misionari, 3 canibali, 1 barcă

Barca poate duce 2 persoane

Dacă sunt mai mulţi canibali decât misionari, îi mănâncă

5 operatori: 1C, 1M, 2C, 2M, CM

Alternativă: persoanele individuale (27 de operatori)

Reprezentare: numărul de persoane pe primul mal şi barca

Starea iniţială: (3, 3, 1)

Starea scop: (0, 0, 0)

O reprezentare mai bună reduce spaţiul de căutare

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

Page 29: Inteligenta artificiala: Strategii de cautare

29

Presupuneri

Mediul este static

Mediul este discret (sau discretizabil)

Mediul este accesibil (observabil)

Mediul este determinist

Multe din aceste presupuneri pot fi înlăturate şi căutarea tot rămâne o metodă importantă de rezolvare a problemelor

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

Page 30: Inteligenta artificiala: Strategii de cautare

30

Noduri şi stări

Un nod este o structură de date în program

O stare este o configuraţie a problemei

Un nod are:

Stare

Nod părinte

Operatorul care a fost aplicat pentru a-l genera

Adâncime

Cost (al căii parcurse din starea iniţială)

Două noduri diferite pot conţine aceeaşi stare!

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

Page 31: Inteligenta artificiala: Strategii de cautare

31

Frontiera arborelui de căutare

Frontiera (engl. fringe) este mulţimea tuturor nodurilor care nu au fost încă expandate

1

2 3 4 5 6

7 8

1

2 3 4 5 6

7 8

1

2 3 4 5 6

7 8

1 3 5 6

8

1 3

4

5 6 7

8 2 4 7

2

1

2 3 4 5 6

7 8

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

Page 32: Inteligenta artificiala: Strategii de cautare

32

Strategia de căutare

Frontiera este implementată ca o listă

Ordonarea nodurilor în frontieră defineşte strategia de căutare

De exemplu tratarea listei ca o coadă sau ca o stivă

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

Page 33: Inteligenta artificiala: Strategii de cautare

33

Măsuri de performanţă

Completitudine

Un algoritm este complet dacă găseşte o soluţie atunci când există una

Dar dacă nu există o soluţie?

Optimalitate

Un algoritm este optim dacă returnează o soluţie de cost minim când problema are soluţii

Complexitate

Măsoară timpul şi volumul de memorie necesare algoritmului

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

Page 34: Inteligenta artificiala: Strategii de cautare

34

Strategii de căutare

1. Rezolvarea problemelor prin căutare

2. Căutarea neinformată (oarbă)

3. Căutarea informată (euristică)

4. Concluzii

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

Page 35: Inteligenta artificiala: Strategii de cautare

35

Căutarea neinformată

Raţionamentul constă în explorarea alternativelor

Căutarea în lăţime (engl. breadth-first search)

Căutarea bidirecţională

Căutarea în adâncime (engl. depth-first search)

Căutarea limitată în adâncime (engl. depth-limited search)

Căutarea iterativă în adâncime (engl. iterative deepening search)

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

Page 36: Inteligenta artificiala: Strategii de cautare

36

Căutarea în lăţime

Nodurile noi sunt inserate la sfârşitul frontierei (lista e o coadă)

FRONTIERA = (1)

2 3

4 5

1

6 7

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

Page 37: Inteligenta artificiala: Strategii de cautare

37

Căutarea în lăţime

Nodurile noi sunt inserate la sfârşitul frontierei

FRONTIERA = (2, 3)

2 3

4 5

1

6 7

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

Page 38: Inteligenta artificiala: Strategii de cautare

38

Căutarea în lăţime

Nodurile noi sunt inserate la sfârşitul frontierei

FRONTIERA = (3, 4, 5)

2 3

4 5

1

6 7

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

Page 39: Inteligenta artificiala: Strategii de cautare

39

Căutarea în lăţime

Nodurile noi sunt inserate la sfârşitul frontierei

FRONTIERA = (4, 5, 6, 7)

2 3

4 5

1

6 7

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

Page 40: Inteligenta artificiala: Strategii de cautare

40

Parametri importanţi

Numărul maxim de succesori ai oricărei stări

Factorul de ramificare (engl. branching factor) b al arborelui de căutare

Lungimea minimă (≠ cost) a căii între starea iniţială şi o stare scop

Adâncimea (engl. depth) d a celui mai superficial nod scop din arborele de căutare

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

Page 41: Inteligenta artificiala: Strategii de cautare

41

Evaluarea performanţelor

Căutarea în lăţime este:

Completă

Optimă dacă un pas are costul 1

Numărul de noduri generate (cazul cel mai defavorabil)

1 + b + b2 + … + bd = (bd+1-1)/(b-1) = O(bd)

Complexitatea de timp şi de spaţiu este O(bd)

Numărul de noduri generate (cazul cel mai favorabil)

1 + b + b2 + … + bd-1 + 1 = 1+(bd-1)/(b-1) = O(bd-1)

Nu este o diferenţă foarte mare, performanţele sunt destul de predictibile

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

Page 42: Inteligenta artificiala: Strategii de cautare

42

Notă

Căutarea în lăţime poate rula la infinit dacă:

Problema nu are soluţii şi spaţiul de căutare este infinit

sau

Stările pot fi revizitate de mai multe ori

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

Page 43: Inteligenta artificiala: Strategii de cautare

43

Căutarea bidirecţională

Două frontiere: FRONT1 şi FRONT2

Complexitatea de timp şi spaţiu este O(bd/2) O(bd) dacă ambii arbori au acelaşi factor de ramificare b

s

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

Page 44: Inteligenta artificiala: Strategii de cautare

44

Căutarea în adâncime

Nodurile noi sunt inserate la începutul frontierei (lista e o stivă)

1

2 3

4 5

FRONTIERA = (1)

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

Page 45: Inteligenta artificiala: Strategii de cautare

45

Căutarea în adâncime

Nodurile noi sunt inserate la începutul frontierei

1

2 3

4 5

FRONTIERA = (2, 3)

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

Page 46: Inteligenta artificiala: Strategii de cautare

46

Căutarea în adâncime

Nodurile noi sunt inserate la începutul frontierei

1

2 3

4 5

FRONTIERA = (4, 5, 3)

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

Page 47: Inteligenta artificiala: Strategii de cautare

47

Căutarea în adâncime

Nodurile noi sunt inserate la începutul frontierei

1

2 3

4 5

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

Page 48: Inteligenta artificiala: Strategii de cautare

48

Căutarea în adâncime

Nodurile noi sunt inserate la începutul frontierei

1

2 3

4 5

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

Page 49: Inteligenta artificiala: Strategii de cautare

49

Căutarea în adâncime

Nodurile noi sunt inserate la începutul frontierei

1

2 3

4 5

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

Page 50: Inteligenta artificiala: Strategii de cautare

50

Căutarea în adâncime

Nodurile noi sunt inserate la începutul frontierei

1

2 3

4 5

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

Page 51: Inteligenta artificiala: Strategii de cautare

51

Căutarea în adâncime

Nodurile noi sunt inserate la începutul frontierei

1

2 3

4 5

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

Page 52: Inteligenta artificiala: Strategii de cautare

52

Căutarea în adâncime

Nodurile noi sunt inserate la începutul frontierei

1

2 3

4 5

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

Page 53: Inteligenta artificiala: Strategii de cautare

53

Căutarea în adâncime

Nodurile noi sunt inserate la începutul frontierei

1

2 3

4 5

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

Page 54: Inteligenta artificiala: Strategii de cautare

54

Căutarea în adâncime

Nodurile noi sunt inserate la începutul frontierei

1

2 3

4 5

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

Page 55: Inteligenta artificiala: Strategii de cautare

55

Evaluarea performanţelor

b: factorul de ramificare d: adâncimea celui mai superficial nod scop m: adâncimea arborelui de căutare Căutarea în adâncime:

Nu este completă Nu este optimă

Cazul cel mai favorabil Complexitatea de timp şi de spaţiu este O(d) – extrem de rapid

Cazul mediu Complexitatea de timp este similară cu a căutării în lăţime: O(bd) De obicei, DFS este mai rapid decât BFS

Cazul cel mai defavorabil Complexitatea de timp este O(bm) – căutarea este lentă Complexitatea de spaţiu este O(b ∙ m) – excelentă

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

Page 56: Inteligenta artificiala: Strategii de cautare

56

Căutarea limitată în adâncime

Căutare în adâncime cu limitarea la k niveluri

Sub această adâncime nodurile nu mai sunt expandate

Situaţii posibile:

Găsirea unei soluţii

Eşec (nu există soluţie)

Căutare incompletă (nu există soluţie pe nivelurile considerate)

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

Page 57: Inteligenta artificiala: Strategii de cautare

57

Căutarea iterativă în adâncime

Combină avantajele căutărilor în lăţime şi adâncime

Ideea de bază: pentru k = 0, 1, 2, …

Realizează căutare limitată în adâncime pentru limita k

Generează nodurile cu adâncime k

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

Page 58: Inteligenta artificiala: Strategii de cautare

58

Căutarea iterativă în adâncime

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

Page 59: Inteligenta artificiala: Strategii de cautare

59

Căutarea iterativă în adâncime

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

Page 60: Inteligenta artificiala: Strategii de cautare

60

Căutarea iterativă în adâncime

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

Page 61: Inteligenta artificiala: Strategii de cautare

61

Evaluarea performanţelor

Căutarea iterativă în adâncime este: Completă

Optimă dacă un pas are costul 1

Cazul cel mai defavorabil Complexitatea de timp:

(d+1) ∙ (1) + d ∙ b + (d-1) ∙ b2 + … + (1) ∙ bd = O(bd)

Comparabilă cu a căutării în lăţime, puţin mai lentă din cauza repetiţiilor

Complexitatea de spaţiu: O(b ∙ d) Comparabilă cu a căutării în adâncime, foarte bună

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

Page 62: Inteligenta artificiala: Strategii de cautare

62

Compararea performanţelor

Trei probleme (în ordine crescătoare a complexităţii):

15-puzzle: b = 2,13

Cubul Rubik: b = 13,5

Şah: b = 35 (nu este o problemă de căutare de tipul celorlalte, e un joc, vezi cursul 3)

Timpul şi spaţiul de prelucrare

1 milion de noduri pe secundă

100 octeţi pe nod

Tabelele următoare prezintă cazurile cele mai defavorabile

Pentru analiza cazurilor celor mai favorabile:

tw: cel mai defavorabil, tb: cel mai favorabil

Căutare în lăţime (BFS), bidirecţională tw / tb b

Căutare iterativă în adâncime (IDS) tw / tb b/2

Căutare în adâncime (DFS) tw este exponenţial, tb este liniar

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

Page 63: Inteligenta artificiala: Strategii de cautare

63

15-puzzle: b = 2,13

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

Page 64: Inteligenta artificiala: Strategii de cautare

64

Cubul Rubik: b = 13,5

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

Page 65: Inteligenta artificiala: Strategii de cautare

65

Şah: b = 35

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

Page 66: Inteligenta artificiala: Strategii de cautare

66

Evitarea repetării stărilor

Evitarea întoarcerii în starea din care tocmai s-a plecat

Starea fiului este identică cu starea părintelui

Evitarea căilor cu bucle

Starea unui nod este identică cu starea unui nod de pe calea din starea iniţială

Evitarea stărilor generate anterior

Necesită memorarea tuturor stărilor generate: complexitate de spaţiu posibil O(bd)

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

Page 67: Inteligenta artificiala: Strategii de cautare

67

Strategii de căutare

1. Rezolvarea problemelor prin căutare

2. Căutarea neinformată (oarbă)

3. Căutarea informată (euristică)

4. Concluzii

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

Page 68: Inteligenta artificiala: Strategii de cautare

68

Căutarea informată (euristică)

Factorii de ramificare mari sunt o problemă serioasă

Trebuie găsită o modalitate de a reduce numărul de noduri vizitate

Metodele de căutare euristică încearcă alegerea „inteligentă” a nodurilor care trebuie expandate

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

Page 69: Inteligenta artificiala: Strategii de cautare

69

Euristică

εὑρίσκειν = a găsi, evrika = am găsit

O euristică este o metodă care furnizează rapid o soluţie, nu neapărat optimă

Este deci o metodă aproximativă, spre deosebire de un algoritm exact optim

Deşi nu garantează găsirea soluţiei optime, metodele euristice funcţionează de obicei (foarte) bine

Chiar dacă nu găsesc soluţia optimă, găsesc de cele mai multe ori o soluţie acceptabilă

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

Page 70: Inteligenta artificiala: Strategii de cautare

70

Strategii neinformate vs. Strategii informate

Strategiile neinformate (oarbe) Nu exploatează semnificaţiile stărilor pentru a ordona

nodurile din frontieră

Exploatează doar poziţiile nodurilor în arbore

Tratează toate problemele la fel

Strategiile informate (euristice) Ordonează nodurile frontierei în funcţie de semnificaţiile

stărilor

Cele mai „promiţătoare” noduri sunt plasate la începutul frontierei

Utilizează cunoştinţele specifice fiecărei probleme

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

Page 71: Inteligenta artificiala: Strategii de cautare

71

Căutarea Best-First

Evaluează cât de bun este un nod

Utilizează o funcţie de evaluare f care atribuie fiecărui nod n un număr real f(n) 0

f(n) este un cost estimat

Cu cât este mai mic f(n), cu atât este mai bun nodul n

Căutarea Best-First sortează frontiera în ordinea crescătoare a lui f

Pentru f egale, se decide aleatoriu

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

Page 72: Inteligenta artificiala: Strategii de cautare

Definirea lui f

72

Funcţii utilizate în general g(n) este costul căii de la nodul iniţial la n

Este cunoscută

h(n) este estimarea costului căii de la n la un nod scop Este o estimare euristică

Căutarea de cost uniform (neinformată) f(n) = g(n)

Căutarea Greedy f(n) = h(n)

Căutarea A* f(n) = g(n) + h(n)

Reuneşte ideile căutărilor de cost uniform şi greedy

Problema principală: găsirea celei mai bune funcţii h

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

Page 73: Inteligenta artificiala: Strategii de cautare

73

Calitatea căutării este dată de h

Când h = costul până la scop

Sunt expandate doar nodurile de pe calea corectă

Se găseşte soluţia optimă

Când h < costul până la scop

Sunt expandate noduri suplimentare

Se găseşte soluţia optimă

Când h > costul până la scop

Soluţia optimă poate fi trecută cu vederea

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

Page 74: Inteligenta artificiala: Strategii de cautare

74

Exemplu: căutarea Greedy

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

Page 75: Inteligenta artificiala: Strategii de cautare

75 Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

Page 76: Inteligenta artificiala: Strategii de cautare

76

Căutarea Greedy

Iaşi – Făgăraş: prin Piatra Neamţ

Dacă se permite revizitarea stărilor, buclă infinită

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

Page 77: Inteligenta artificiala: Strategii de cautare

77

Performanţele căutării Greedy

Nu este optimă

Este incompletă dacă:

Nu se foloseşte o coadă de priorităţi iar succesorul cel mai promiţător este expandat direct

Aceasta este abordarea cea mai utilizată

Nodurile sunt adăugate la începutul cozii de priorităţi (~ căutare în adâncime) iar euristica este constantă (de exemplu euristica naivă: h = 0)

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

Page 78: Inteligenta artificiala: Strategii de cautare

78

Fie h*(n) costul căii optime de la n la un nod scop

Funcţia euristică h(n) este admisibilă dacă: 0 h(n) h*(n)

Dacă G este scop, atunci h(G) = 0

O funcţie euristică admisibilă este întotdeauna optimistă (niciodată nu supraestimează)

Euristici admisibile

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

Page 79: Inteligenta artificiala: Strategii de cautare

79

Căutarea A*

Unul din cei mai populari algoritmi de IA

f(n) = g(n) + h(n), unde:

g(n) = costul celei mai bune căi găsite până la n

h(n) = o funcţie euristică admisibilă

Presupunem că: n, n’, : cost(n, n’) > 0

Între două noduri diferite există întotdeauna un cost pozitiv

Căile infinite au cost infinit

Foloseşte 2 liste: OPEN şi CLOSED

Mulţimea nodurilor din lista OPEN reprezintă frontiera, iar cele din lista CLOSED interiorul zonelor vizitate

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

Page 80: Inteligenta artificiala: Strategii de cautare

80

Greedy şi A*

f(n) = g(n) + h(n)

f(B) = 15 + 20 + 30 = 65

f(C) = 15 +10 + 35 = 60

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

Page 81: Inteligenta artificiala: Strategii de cautare

Algoritmul A*: pseudocod

81 Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

Page 82: Inteligenta artificiala: Strategii de cautare

82 Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

Page 83: Inteligenta artificiala: Strategii de cautare

83

Revizitarea stărilor

Euristica h este admisibilă

Într-o situaţie reală, nodul cu h = 1 ar putea fi lângă scop, dar despărţit de acesta de un obstacol

c = 1

100

2 1

2

h = 100

0

90

1

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

Page 84: Inteligenta artificiala: Strategii de cautare

84

Revizitarea stărilor

c = 1

100

2 1

2

h = 100

0

90

1

104

4+90

f = 1+100 2+1

?

Dacă eliminăm acest nod, algoritmul expandează nodul scop vecin şi returnează o soluţie sub-optimă

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

Page 85: Inteligenta artificiala: Strategii de cautare

85

1

100

2 1

2

100

0

90

1

104

4+90

1+100 2+1

2+90

102

Dacă nu eliminăm nodurile care revizitează stările, căutarea se termină cu soluţia optimă

Revizitarea stărilor

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

Page 86: Inteligenta artificiala: Strategii de cautare

86

1

100

2 1

2

100

0

90

1

Noduri introduse, noduri scoase în/din coada de priorităţi

Cum funcţionează A*

B(101), C(3)

C(3), B(101) – sortată după f

B(101), D(94)

D(94), B(101) – sortată după f

B(101), E(104)

E(104), D(92)

D(92), E(104) – sortată după f

E(104), E(102)

E(102), E(104) – sortată după f

Scop: E(102)

A

B C

D

E

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

Page 87: Inteligenta artificiala: Strategii de cautare

87

O euristică h este monotonă (sau consistentă) dacă:

n şi un fiu n’ al lui n:

h(n) cost(n, n’) + h(n’)

G un nod scop

h(G) = 0

O euristică monotonă este şi admisibilă

O euristică monotonă devine din ce în ce mai precisă cu cât înaintează în adâncimea arborelui de căutare

Euristici monotone

(inegalitatea în triunghi)

n

n’ h(n)

h(n’)

cost(n,n’)

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

Page 88: Inteligenta artificiala: Strategii de cautare

88

Euristici monotone

Dacă h este monotonă, oricând este deschis un nod, algoritmul A* garantează că a găsit o cale optimă către acesta

Nodurile închise nu mai sunt redeschise

În multe cazuri (dar nu întotdeauna), monotonia euristicii accelerează găsirea soluţiei

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

Page 89: Inteligenta artificiala: Strategii de cautare

Ecuaţia pathmax

Ecuaţia pathmax: la generarea unui nod fiu n’ al lui n

f(n’) = max( f(n), g(n’) + h(n’) )

În exemplul anterior: nodul D

f(D) = max( f(B), g(D) + h(D) ) = max( 101, 92 ) = 101

Ecuaţia pathmax face ca valorile lui f să fie monoton nedescrescătoare pe orice cale din arborele de căutare

Ecuaţia pathmax nu transformă o funcţie de cost f nemonotonă într-una monotonă

Dacă există mai multe căi prin care se poate ajunge la scop, valorile f pot rămâne nemonotone pentru căile netraversate încă

89 Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

Page 90: Inteligenta artificiala: Strategii de cautare

90

Caracteristici ale A*

A* este complet şi optim

Dacă nodurile care revizitează stările nu sunt eliminate

A* este eficient optim (engl. “optimally efficient”)

Niciun alt algoritm de acelaşi tip nu garantează expandarea unui număr mai mic de noduri

Este eficient optim doar dacă euristica este monotonă

Alţi algoritmi pot fi mai rapizi chiar dacă expandează mai multe noduri

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

Page 91: Inteligenta artificiala: Strategii de cautare

91

Complexitatea A*

Timp

Calitatea euristicii h scade timpul necesar

Cazul cel mai favorabil: h este perfectă, O(d)

Cazul cel mai defavorabil: h = 0, O(bd) ~ BFS

Spaţiu

Toate nodurile sunt memorate

Cazul cel mai defavorabil: O(nS)

nS este numărul de stări

A* are în general probleme de spaţiu înainte de a avea probleme de timp

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

Page 92: Inteligenta artificiala: Strategii de cautare

Cazul cel mai defavorabil

Exemplu de caz cel mai defavorabil pentru A* cu euristici inconsistente: familia Martelli – G5

O(2n) expandări de noduri pentru găsirea soluţiei

92 Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

Page 93: Inteligenta artificiala: Strategii de cautare

Optimizări

Optimizarea listelor

Căutarea celui mai bun nod, de fiecare dată, este ineficientă

Lista deschisă trebuie să fie o listă sortată sau un arbore heap

Lista închisă poate fi un hashtable

Optimizarea spaţiului de căutare

Cel mai simplu caz: “parent pruning” – evitarea expandării ca succesor a părintelui unui nod

93 Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

Page 94: Inteligenta artificiala: Strategii de cautare

94

Optimizări

Aplicarea pe grid, de exemplu pentru jocuri, este costisitoare

Există foarte multe stări dacă gridul este mare

Factor de ramificare mare: 4, 8 sau 6 pentru grid hexagonal

Multe căi au aceeaşi lungime. A* le poate explora pe toate

Se poate ajusta valoarea h în mod determinist, de exemplu se poate creşte cu 0,1%. A* va prefera expandarea nodurilor mai apropiate de scop

În general: h *= (1 + p), cu p < (costul minim al unui pas) / (lungimea aşteptată a celei mai lungi căi)

Alternativă: când valorile f sunt egale, se compară după valorile h

h poate fi mărită puţin, devenind neadmisibilă. Dacă funcţia rezultată h’ supraestimează rareori funcţia h* cu o valoare mai mare decât v, atunci algoritmul va găsi rareori o soluţie al cărei cost este mai mare cu v decât costul optim

Altă metodă pentru departajare: se preferă căile apropiate de linia dreaptă între starea iniţială şi scop

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

Page 95: Inteligenta artificiala: Strategii de cautare

Optimizări

A* ierarhic cvasi-optim (Near-Optimal Hierarchical Pathfinding, HPA*)

95 Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

Page 96: Inteligenta artificiala: Strategii de cautare

96

IDA*

Căutarea iterativă în adâncime A* (engl. Iterative Deepening A*)

Principiu similar cu acela al căutării iterative neinformate în adâncime

În loc de niveluri în arbore foloseşte contururi de cost ale funcţiei f

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

Page 97: Inteligenta artificiala: Strategii de cautare

97

Algoritmul IDA*: pseudocod

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

Page 98: Inteligenta artificiala: Strategii de cautare

Ecuaţia pathmax bidirecţională

Actualizarea dinspre părinţi spre fii

h(c) = max( h(c), h(p) – cost(p,c ) )

Actualizarea dinspre fii spre părinţi

h(p) = max( h(p), h(c) – cost(c, p) )

Regula poate elimina multe noduri care altfel ar fi generate şi chiar expandate (idee asemănătoare cu retezarea alfa-beta pentru jocuri, din cursul 3)

98 Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

Page 99: Inteligenta artificiala: Strategii de cautare

Exemplu

Să presupunem că pragul curent al IDA* este T = 2

Fără aplicarea regulii, atât parintele p şi fiul c2 sunt expandaţi f(p) = 0 + 2 = 2

f(c2) = 1 + 1 = 2

Cu regula BPMX: f(c1) = 1 + 5 = 6, IDA* îl va ignora

Se va actualiza h(p) = 4 şi deci f(p) = 0 + 4 = 4

IDA* va ignora nodul p şi nu va mai genera nodul c2

99 Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

Page 100: Inteligenta artificiala: Strategii de cautare

100

Crearea de euristici

O euristică admisibilă poate fi văzută drept costul soluţiei optime a unei probleme relaxate (prin eliminarea constrângerilor)

Pentru navigarea unui robot:

Distanţa Manhattan corespunde eliminării obstacolelor

Distanţa euclidiană corespunde eliminării obstacolelor şi a constrângerilor de mişcare pe grid

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

Page 101: Inteligenta artificiala: Strategii de cautare

Euristici pentru 8-puzzle (I)

101

Numărul de căsuţe diferite (fără a include spaţiul)

1 2 3

4 5 6

7 8

1 2 3

4 5 6

7 8

1 2 3

4 5 6

7 8

1 2 3

4 5 6

7 8

N N N

N N N

N D

Doar “8” este plasat diferit, deci funcţia euristică este evaluată la 1 Euristica ne spune că o soluţie ar putea fi găsită într-o mutare

Starea scop

Starea curentă

h(scrt) = 1

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

Page 102: Inteligenta artificiala: Strategii de cautare

Euristici pentru 8-puzzle (II)

102

Distanţa Manhattan (fără a include spaţiul)

Doar căsuţele “3”, “8” şi “1” sunt plasate greşit, deci funcţia euristică întoarce 8 Euristica ne spune că o soluţie ar putea fi găsită în cel puţin 8 mutări

3 2 8

4 5 6

7 1

1 2 3

4 5 6

7 8

Starea scop

Starea curentă

3 3

8

8

1

1

2 spaţii

3 spaţii

3 spaţii

Total 8 h(scrt) = 8

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

Page 103: Inteligenta artificiala: Strategii de cautare

103

Modalităţi suplimentare de alegere a funcţiei euristice

Abordarea maximă

h(n) = max( h1(n), …, hm(n) )

Abordarea statistică

De exemplu, dacă în 90% din cazuri când h(n) = 14, h*(n) = 18, atunci când valoarea lui h(n) este 14, returnăm 18

Complexitatea euristicii nu trebuie să afecteze eficienţa căutării

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

Page 104: Inteligenta artificiala: Strategii de cautare

104

IDS vs. A*

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

Page 105: Inteligenta artificiala: Strategii de cautare

105

Concluzii

Metodele de căutare sunt utile când:

Spaţiul de căutare este mic şi

Nu există alte tehnici disponibile sau

Dezvoltarea unei tehnici mai eficiente nu merită efortul

Spaţiul de căutare este mare şi

Nu există alte tehnici disponibile şi

Există euristici „bune” pentru problema considerată

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm