Bazele Inteligentei Artificiale

Curs
9/10 (2 voturi)
Domeniu: Calculatoare
Conține 8 fișiere: doc
Pagini : 90 în total
Cuvinte : 31665
Mărime: 1.15MB (arhivat)
Cost: Gratis

Extras din document

In rezolvarea problemelor utilizind strategii de cautare neinformata numarul de stari investigate inainte de a gasi o solutie poate ajunge prohibitiv de mare, chiar si pentru probleme relativ simple, aparind deci explozia combinationala. Spatiul de cautare explorat poate fi redus prin aplicarea cunostintelor euristice despre problema. Acest capitol discuta modul in care informatia euristica poate fi utilizata in cautare pornind de la strategiile de baza si obtinind strategii de cautare euristica.

Cunostintele euristice pot fi folosite pentru a creste eficienta cautarii in trei moduri:

(1) Selectarea nodului urmator de expandat in cursul cautarii

(2) In cursul expandarii unui nod al spatiului de cautare se poate decide pe baza informatiilor euristice care dintre succesorii lui vor fi generati si care nu.

(3) Eliminarea din spatiul de cautare a anumitor noduri generate.

In acest curs se prezinta prima modalitate de utilizare a cunostintelor euristice pentru a alege nodul "cel mai promitator" pentru obtinerea solutiei. Al doilea mod de utilizare a euristicilor revine de fapt la expandarea partiala a unui nod prin aplicarea numai a unui subset de operatori dintre cei posibil de aplicat. O varianta a acestei tehnici este analiza bazata pe modalitati utilizata in programul General Problem Solver care alege operatorul cel mai potrivit pentru a avansa spre solutie, chiar daca nu este imediat aplicabil. Ulterior, se incearca atingerea unei stari in care operatorul poate fi aplicat, deci se incearca satisfacerea unui subscop. Al treilea mod de utilizare a euristicilor incearca eliminarea anumitor noduri pe baza deciziei daca aceste noduri pot face parte din solutie sau nu. Aceasta tehnica se numeste taierea arborelui de cautare.

3.3.1 Cautare informata de tip "best-first"

Ideea strategiei de cautare "best-first" este aceea de a selecta spre expandare cel mai bun nod din spatiul de cautare generat pe baza cunostintelor euristice, deci pe baza unei estimari. Calitatea unui nod, din punct de vedere al gasirii solutiei, poate fi estimata in diverse moduri. Se poate atribui nodului gradul de dificultate in solutionarea problemei reprezentata de acel nod. Se poate estima calitatea unei multimi de solutii candidate care contin acel nod, deci solutii partiale care contin o cale ce duce la acel nod. O a treia alternativa este aceea de a evalua cantitatea de informatie care poate fi obtinuta prin expandarea acelui nod si importanta acestei informatii in ghidarea procesului de cautare. In toate aceste cazuri calitatea unui nod este estimata de functia de evaluare euristica, notata w(n) pentru nodul n, care poate depinde de descrierea lui n, de descrierea scopului si de cunostinte suplimentare despre problema.

Una dintre cele mai simple strategii informate pentru modelul reprezentarii prin spatiul starilor, bazata pe un criteriu de optim local, este strategia de cautare a alpinistului, amintita anterior. Ideea acestei strategii este expandarea unui nod, inspectarea succesorilor acestuia si calculul valorilor functiei euristice pentru acesti succesori, apoi alegerea celui mai bun nod in functie de aceste valori. Toate celelalte noduri sint uitate, inclusiv nodul stare curenta, deci strategia este irevocabila. Simplitatea acestei strategii este platita de dezavantajele strategiei: posibilitatea de a pierde solutia, blocarea in maxime locale si inspectarea repetata a aceleiasi stari. Strategia este evident incompleta.

In cazul strategiilor tentative informate generale, selectia nodului cel mai promitator se face evaluind toate nodurile generate pina la un moment dat, indiferent de calea in arborele de cautare pe care se afla un nod. In continuare se prezinta un algoritm de cautare de tip "best-first" pentru reprezentarea solutiei problemei prin spatiul starilor. Se presupune ca spatiul de cautare este un graf si ca nodul selectat pentru expandare este cel care are cea mai mica valoare a functiei euristice w(n); Si este starea initiala.

Algoritm: Strategia de cautare "best-first" in spatiul starilor

1. Creaza listele si

2. Calculeaza si asociaza aceasta valoare nodului

Preview document

Bazele Inteligentei Artificiale - Pagina 1
Bazele Inteligentei Artificiale - Pagina 2
Bazele Inteligentei Artificiale - Pagina 3
Bazele Inteligentei Artificiale - Pagina 4
Bazele Inteligentei Artificiale - Pagina 5
Bazele Inteligentei Artificiale - Pagina 6
Bazele Inteligentei Artificiale - Pagina 7
Bazele Inteligentei Artificiale - Pagina 8
Bazele Inteligentei Artificiale - Pagina 9
Bazele Inteligentei Artificiale - Pagina 10
Bazele Inteligentei Artificiale - Pagina 11
Bazele Inteligentei Artificiale - Pagina 12
Bazele Inteligentei Artificiale - Pagina 13
Bazele Inteligentei Artificiale - Pagina 14
Bazele Inteligentei Artificiale - Pagina 15
Bazele Inteligentei Artificiale - Pagina 16
Bazele Inteligentei Artificiale - Pagina 17
Bazele Inteligentei Artificiale - Pagina 18
Bazele Inteligentei Artificiale - Pagina 19
Bazele Inteligentei Artificiale - Pagina 20
Bazele Inteligentei Artificiale - Pagina 21
Bazele Inteligentei Artificiale - Pagina 22
Bazele Inteligentei Artificiale - Pagina 23
Bazele Inteligentei Artificiale - Pagina 24
Bazele Inteligentei Artificiale - Pagina 25
Bazele Inteligentei Artificiale - Pagina 26
Bazele Inteligentei Artificiale - Pagina 27
Bazele Inteligentei Artificiale - Pagina 28
Bazele Inteligentei Artificiale - Pagina 29
Bazele Inteligentei Artificiale - Pagina 30
Bazele Inteligentei Artificiale - Pagina 31
Bazele Inteligentei Artificiale - Pagina 32
Bazele Inteligentei Artificiale - Pagina 33
Bazele Inteligentei Artificiale - Pagina 34
Bazele Inteligentei Artificiale - Pagina 35
Bazele Inteligentei Artificiale - Pagina 36
Bazele Inteligentei Artificiale - Pagina 37
Bazele Inteligentei Artificiale - Pagina 38
Bazele Inteligentei Artificiale - Pagina 39
Bazele Inteligentei Artificiale - Pagina 40
Bazele Inteligentei Artificiale - Pagina 41
Bazele Inteligentei Artificiale - Pagina 42
Bazele Inteligentei Artificiale - Pagina 43
Bazele Inteligentei Artificiale - Pagina 44
Bazele Inteligentei Artificiale - Pagina 45
Bazele Inteligentei Artificiale - Pagina 46
Bazele Inteligentei Artificiale - Pagina 47
Bazele Inteligentei Artificiale - Pagina 48
Bazele Inteligentei Artificiale - Pagina 49
Bazele Inteligentei Artificiale - Pagina 50
Bazele Inteligentei Artificiale - Pagina 51
Bazele Inteligentei Artificiale - Pagina 52
Bazele Inteligentei Artificiale - Pagina 53
Bazele Inteligentei Artificiale - Pagina 54
Bazele Inteligentei Artificiale - Pagina 55
Bazele Inteligentei Artificiale - Pagina 56
Bazele Inteligentei Artificiale - Pagina 57
Bazele Inteligentei Artificiale - Pagina 58
Bazele Inteligentei Artificiale - Pagina 59
Bazele Inteligentei Artificiale - Pagina 60
Bazele Inteligentei Artificiale - Pagina 61
Bazele Inteligentei Artificiale - Pagina 62
Bazele Inteligentei Artificiale - Pagina 63
Bazele Inteligentei Artificiale - Pagina 64
Bazele Inteligentei Artificiale - Pagina 65
Bazele Inteligentei Artificiale - Pagina 66
Bazele Inteligentei Artificiale - Pagina 67
Bazele Inteligentei Artificiale - Pagina 68
Bazele Inteligentei Artificiale - Pagina 69
Bazele Inteligentei Artificiale - Pagina 70
Bazele Inteligentei Artificiale - Pagina 71
Bazele Inteligentei Artificiale - Pagina 72
Bazele Inteligentei Artificiale - Pagina 73
Bazele Inteligentei Artificiale - Pagina 74
Bazele Inteligentei Artificiale - Pagina 75
Bazele Inteligentei Artificiale - Pagina 76
Bazele Inteligentei Artificiale - Pagina 77
Bazele Inteligentei Artificiale - Pagina 78
Bazele Inteligentei Artificiale - Pagina 79
Bazele Inteligentei Artificiale - Pagina 80
Bazele Inteligentei Artificiale - Pagina 81
Bazele Inteligentei Artificiale - Pagina 82
Bazele Inteligentei Artificiale - Pagina 83
Bazele Inteligentei Artificiale - Pagina 84
Bazele Inteligentei Artificiale - Pagina 85
Bazele Inteligentei Artificiale - Pagina 86
Bazele Inteligentei Artificiale - Pagina 87
Bazele Inteligentei Artificiale - Pagina 88
Bazele Inteligentei Artificiale - Pagina 89
Bazele Inteligentei Artificiale - Pagina 90
Bazele Inteligentei Artificiale - Pagina 91

Conținut arhivă zip

  • Bazele Inteligentei Artificiale
    • Curs_10.DOC
    • Curs_11.DOC
    • Curs_12.DOC
    • Curs_13.DOC
    • Curs_14.doc
    • Curs_9.DOC
    • C_BIA_6.DOC
    • C_BIA_7_Teoria_JOC.doc

Alții au mai descărcat și

Lucrul cu Numere Mari

De multe ori , in probleme, apar situatii cand este nevoie sa memoram numere intregi foarte mari (de ordinul sutelor de cifre), iar uneori trbuie...

Bridge - Cod Sursa in Limbaj CLIPS

În proiect este implementat un sistem expert în jocul de bridge. Acest sistem expert nu este adresat începatorilor în jocul de bridge, ci...

Curs IT

1. HARDWARE (HARD): Reprezinta totalitatea componentelor materiale ale unui sistem informatic. 2. SOFTWARE (SOFT): Reprezinta totalitatea...

Retele de Calculatoare

1. Calculatorul electronic De-a lungul istoriei,omenirea a folosit suporturi fizice pentru a-si exprima ideile,pentru a le vizualiza , a se putea...

Indrumator Laborator SDTP

Lucrarea nr. 1 Structura de arbore. Arbori generalizati 1. Scopul lucrarii este prezentarea structurii de arbore si a operatiilor de baza ce se...

Sisteme de Operare

Shell Unix Shell-ul este principala interfată de comunicare între utilizator si sistemul de operare. Desi, în mod intuitiv, shell-ul este...

Curs HTML

Curs – Programare WEB Curs – 1 Elemente de baza Pentru inceput sa descoperim originea abrevierii HTML - Hypertext Markup Language . Acest limbaj...

Ai nevoie de altceva?