mihaispr
Administrator
 Inregistrat: acum 18 ani
Postari: 2142
|
|
Sinteza pt.examenul de IA
Termeni de baza IA pt.rezolvarea unei probleme date:
1. Date – constau în material brut, fapte, simboluri, numere, cuvinte, poze fără un înţeles de sine stătător, neintegrate într-un context, fără relaţii cu alte date sau obiecte. Ele se pot obţine în urma unor experimente, sondaje etc.
2. Informaţii – prin prelucrarea datelor şi găsirea relaţiilor dintre acestea se obţin informaţii care au un înţeles şi sunt integrate într-un context. Datele organizate şi prezentate într-un mod sistematic pentru a sublinia sensul acestor date devin informaţii. Pe scurt informaţiile sunt date prelucrate. Informaţiile se prezintă sub formă de rapoarte, statistici, diagrame etc.
3. Cunoştinţele - sunt colecţii de date, informaţii, adevăruri şi principii învăţate, acumulate de-a lungul timpului. Informaţiile despre un subiect reţinute şi înţelese şi care pot
fi folosite în luarea de decizii, formează judecăţi şi opinii devin cunoştinţe. Cu alte cuvinte, cunoştinţele apar în momentul utilizării informaţiei
Baza de date
-cuprinde informatiile organizate într-o forma particulara, legata de algoritmul folosit si
pentru a-l servi pe acesta
Adancimea nodului
- numarul de noduri prin care s-a
trecut de la nodul radacina pana la nodul curent;
Solutia initiala:
-reprezinta configuratia initiala a problemei. Se mai numeste si starea curenta;
Solutia finala:
-reprezinta solutia/configuratia finala a problemei
Spatiul starilor:
-contine toate configuratiile posibile ale obiectelor relevante (si poate si unele imposibile). Practic sunt toate configuratiile posibile si cele care conduc la solutie si cele care nu conduc la solutie.
Euristica (heuristica)
-este o metoda ce se bazeaza pe reguli derivate din
experienta, introducând în multe situatii un grad de incertitudine.
IA (Inteligenta artificiala)
-este o ramura a stiintei calculatoarelor ce studiaza realizarea unor tehnici de
programare performante, care sa permita rezolvarea unor sarcini complexe.
Învatarea este privita în IA ca fiind procesul prin care oamenii si calculatoarele îsi
îmbogatesc cunostintele si îsi perfectioneaza activitatea.
Strategii de cautare în spatiul starilor
Unul dintre cele mai utilizate modele de rezolvare a problemelor este prin reprezentarea căutării sub forma unui graf orientat în care nodurile sunt stări succesive în rezolvare iar arcele corespund tranziţiilor sau operatorilor legali ce pot fi aplicaţi pentru trecerea dintr-o stare în alta.
Cautarea solutiilor în spatiul starilor
Pentru a construi o descrierea unei probleme rezolvate prin reprezentare în spaţiul stărilor trebuie parcurse urmatoarele etape:
1) Se defineste spatiul starilor care contine toate configuratiile posibile ale obiectelor relevante (si poate si unele imposibile). Spatiul se poate defini explicit prin indicarea tuturor stărilor (acesta fiind un caz particular şi rar întâlnit în practică ) sau implicit prin indicarea transformărilor care generează o nouă stare dintr-o stare dată.
2) Se specifica una sau mai multe stari din spatiu care descriu situatii posibile de la care poate porni procesul de rezolvare a problemei (starea iniţială ) .
3) Se specifica una sau mai multe stari care ar fi acceptabile ca solutii ale problemei. Aceste stari se numesc stari scop (sau stari finale sau scopuri).
4) Se specifica un set de reguli care descriu actiunile (operatorii) disponibile şi care definesc tranziţiile sau transformările între stări.
Strategii de cautare
Exista 2 tipuri de strategii de cautare neinformate si informate
Din categoria strategiilor de cautare neinformate fac parte: strategia de cautare pe nivel, adancime limitata,cost uniform, adancime cu nivel iterativ si bidirectionala.
Din categoria strategiilor de cautare informate fac parte: strategia A*,strategia AO*, strategia BF(best first care este o generalizare a strategiilor pe nivel si in adancime).
Strategia de cautare pe nivel
Strategia de căutare pe nivel (în lăţime, breadth-first search) este o strategie de căutare
neinformată.
Strategia de căutare pe nivel începe expandarea cu nodul rădăcină, apoi expandează toate
nodurile generate de rădăcină şi continuă similar expandarea cu toţi succesorii acestora etc.
Orice nod este expandat pt.a genera stari succesoare. Daca starile succesoare de pe un anumit nivel sunt egale cu starea tinta atunci e gasita solutia si adaugata in caz contrar nu este adaugata.
FRONTIERA- lista implementata sub forma de coada (lista=vector alocat dinamic) ce contine nodurile evaluate
TERITORIU- lista implementata sub forma de coada (lista=vector alocat dinamic) ce contine nodurile expandate
Strategia de cautare pe nivel incepe cu expandarea nodului radacina, apoi expandeaza toate nodurile generate de radacina si continua expandarea cu toti succesorii acestora.
Implementarea strategiei de cautare pe nivel se realizeaza particularizand strategia generala de cautare prin implementarea listelor FRONTIERA si TERITORIU de tip coada( coada este de tip FIFO –primul nod din coada este primul scos)
Caracteristici
Căutarea pe nivel este completă.
Căutarea pe nivel este optimală.
Complexitatea strategiei este exponenţială. (asta inseamna ca daca arborele de cautare are o structura complexa el va gasi solutia mai repede)
Criterii de caracterizare a unei strategii de cautare in spatiul starilor
Completitudine:
-daca garanteaza o solutie in cazul in care aceasta exista
Optimalitate:
-daca gaseste o solutie optima (reprezinta cea mai buna cale de rezolvare a problemei)
Complexitatea:
-este de 2 categorii spatiu si timp
Complexitatea în spaţiu
-se referă la volumul de memorie necesar calculelor ( cat spatiu de memorie este necesar pentru a realiza cautarea solutiei)
Complexitatea în timp
-se referă la timpul necesar efectuării calculelor, ambele fiind exprimate ca funcţii de n, unde n este mărimea datelor de intrare. ( in cat timp se gaseste o solutie)
In continuare este prezentat un exemplu al structurii unui arbore de cautare asupra caruia vom aplica strategia de cautare pe nivel:
Nodul a1 are succesorii notati a1.1 si a1.2.
Nodul a2 are succesorii notati a2.1 si a2.2
Nodul a3 in acest caz nu are succesori.
Algoritm pseudocod:
1. iniţializează listele FRONTIERA ←{Si} şi TERITORIU ←{}
2. dacă FRONTIERA={} atunci
întoarce INSUCCES /*nu există soluţie*/
3. elimină primul nod S din FRONTIERA şi inserează-l în TERITORIU
4. expandează nodul S
4.1. generează toţi succesorii direcţi Sj ai nodului S
4.2. pentru fiecare succesor Sj (1≤j≤n) al lui S execută
4.2.1. stabileşte legătura Sj → Suzz
4.2.2. dacă Sj este stare finală atunci
i. soluţia este (Sj, S, ..., Si)
ii. întoarce SUCCES /* a fost găsită soluţia */
4.2.3. dacă Sj ≠ toate stările anterior generate în
soluţia parţială curentă atunci
inserează Sj în FRONTIERA, la sfârşit
5. repetă de la pasul 2
sfârşit
Cum functioneaza strategia de cautare pe nivel pt.acest exemplu:
Nodul radacina nu este cel tinta, prin urmare deci vor fi generate stari succesoare de la nodul radacina.Fiecare
din aceste stari succesoare vor fi luate din agenda si vor fi comparate cu tinta daca sunt egale cu scopul final
(tinta) vor fi stocate in SolutionsFound de tip ArrayList. In cazul in care un nod de exemplu de pe nivelul2 este
diferit de scopul final(tinta) acesta va fi expandat pentru a crea stari succesoare pana va fi egal cu tinta
si abia atunci va fi adaugat in agenda.
In concluzie solutiile pot fi gasite pe nivele diferite in arborele de cautare.
Prima solutie sa spunem ca a fost gasita. Urmatoarele solutii vor fi comparata cu solutia gasita pe nivelul
respectiv si daca sunt mai mici sau egale sunt stocate ca solutii optimale valide. Doar atunci cand sunt gasite
solutii la un nivel superior strategia de cautare stie cum sa-si gaseasca toate solutiile optimale.Cand se
intampla acest lucru strategia de cautare pe nivel se opreste si solutiile optimale sunt afisate.
Algoritmul pleaca din nodul radacina si intra pe nodul a1
Pasul1: pleaca din nodul radacina numit Root
Pasul2: Ajunge pe nivelul 2 si intra pe nodul a1
Pasul3: Cauta solutii pe nivelul2
Pasul4: expandeaza nodul a2 (succesorii lui sunt nodurile a2.1 si a2.2)
Pasul5: Expandarea nodulului a3 nu mai are loc deoarece observam ca nu are stari succesoare
Expandarea unui nod- se realizeaza pt.a determina stari succesoare.
Obs. O solutie intr-un arbore de cautare in cadrul strategiei pe nivel poate fi gasita pe orice nivel.
Concluzie:
Strategia pe nivel este completa, optimala iar complexitatea timp si spatiu este exponentiala. (asta inseamna ca daca arborele de cautare are o structura complexa el va gasi solutia mai repede)
Strategia de căutare în adâncime limitată
Strategia de căutare în adâncime limitată (depth-first search) este o strategie de căutare
neinformată.
Strategia expandează întotdeauna ultimul nod adăugat arborelui (aflat pe nivelul cel mai
adânc). Căutarea revine pe nivelele anterioare numai atunci când s-a blocat (a apărut un nod
care nu e nodul scop şi care nu poate fi expandat sau s-a ajuns la adâncimea maximă
impusă .
Implementarea strategiei de căutare pe nivel se realizează particularizând strategia generală
de căutare prin implementarea listei FRONTIERA sub formă de stivă.
Algoritm in pseudocod
1. iniţializează listele FRONTIERA ←{Si} şi TERITORIU ←{}
2. dacă FRONTIERA={} atunci
întoarce INSUCCES /*nu există soluţie*/
3. elimină primul nod S din FRONTIERA şi inserează-l în TERITORIU
4. daca adancime(S) = Hmax atunci repeta de la pasul 2
4. expandează nodul S
4.1. generează toţi succesorii direcţi Sj ai nodului S
4.2. pentru fiecare succesor Sj (1≤j≤n) al lui S execută
4.2.1. stabileşte legătura Sj → S
4.2.2. dacă Sj este stare finală atunci
i. soluţia este (Sj, S, ..., Si)
ii. întoarce SUCCES /* a fost găsită soluţia */
4.2.3. dacă Sj ≠ toate stările anterior generate în
soluţia parţială curentă atunci
inserează Sj în FRONTIERA, la inceput
5. repetă de la pasul 2
sfârşit
Dezavantajul căutării este posibilitatea blocării într-o cale greşit aleasă.
Caracteristici
Căutarea nu este completă.
Căutarea nu este optimală.
Complexitatea timp este exponenţială, iar complexitatea spaţiu este polinomială
In continuare este prezentat un exemplu al structurii unui arbore de cautare asupra caruia vom aplica strategia de cautare pe adancime:
Am luat acelasi arbore de cautare.
Cum functioneaza strategia de cautare pe in adancime pt.acest exemplu ilustrat in printscreen-ul de mai sus:
Fie arborele de cautare de mai sus avand 3 nivele.
Pasul1: Pleaca din radacina se duce in nodul a1 si apoi in a1.1 si vede dk a gasit solutia
prima data
Pasul2: Revine in radacina
Pasul3: Pleaca pe traseul Root a1 a1.1
Pasul4: Pleaca pe traseul Root,a2,a2.1
Pasul5: Pleaca pe traseul Root,a2,a2.2
Pasul6: Revine in radacina
Pasul7: Pleaca pe traseul Root,a3 si atat deoarece a3 nu are descendenti
Strategia de cost uniform
Aceasta modifică strategia de căutare pe nivel pentru a găsi soluţia de cost minim (care nu
întotdeauna este şi soluţia cu adâncimea minimă. Prin urmare se va expanda mai întâi nodul
cu cost minim din FRONTIERA.
Căutarea pe nivel este căutarea de cost uniform cu cost(S)=Adâncime (S).
Căutarea de cost uniform găseşte soluţia cea mai ieftină dacă este îndeplinită condiţia:
- costul unei căi nu scade de-a lungul acesteia: cost(succesor(S))≥cost(S), pentru orice
nod S.
Exista 2 modalitati de definire a costului unui arbore solutie:
- Costul suma- suma costurilor tuturor arcelor din arbore
- Cosul maxim- suma costurilor de-a lungul caii celei mai costisitoare intre radacina si un nod terminal
Strategia de cautare cu nivel iterativ
Complexitatea spatiu este exponentiala complexitatea timp liniara.
Caracteristici
Căutarea este completă.
Căutarea este optimală.
Complexitatea timp si spatiu este exponenţială.
Strategii de cautare informate
Strategia A*
Strategia de căutare A* este o strategie de căutare informată care încearcă reducerea
numărului de noduri generate din spaţiul de căutare, pe baza unor anumite criterii cum sunt
euristicile.
Acest obiectiv include şi problema găsirii căii spre soluţie care presupune aplicarea unui
număr minim de operatori.
Strategia de căutare A* începe expandarea cu nodul rădăcină, generează toţi succesorii
acestui nod şi calculează funcţia euristică specifică fiecăruia. Apoi expandează acel succesor
a cărei funcţie euristică are valoarea minimă şi continuă similar expandarea cu toţi succesorii
acestuia etc.
Funcţii euristice
După cum sugerează şi numele, euristicile nu garantează găsirea unei soluţii, ci sunt
determinate de experienţa specialiştilor în rezolvarea clasei de probleme.
În stategia de căutare A* funcţia de evaluare euristică este o funcţie aditivă:
f(S) = g(S) + h(S),
unde:
g(S) – reprezintă costul soluţiei parţiale (Si, ..., S)
h(S) – estimata distanţei de la starea curentă la starea scop (S,..., Sf)
Si – starea iniţială
S – starea curentă
Sf – starea finală (scop)
Funcţia h(S) trebuie definită de către programator, ea fiind specifică fiecărei probleme în
parte.
Algoritm
1. iniţializează listele FRONTIERA ←{Si} şi TERITORIU ←{}
2. calculeaza f(Si) şi asociază această valoare nodului Si
3. dacă FRONTIERA={} atunci
întoarce INSUCCES /*nu există soluţie*/
4. selectează din FRONTIERA un nod S pentru care f(S) este minimă
5. elimină nodul S din FRONTIERA şi inserează-l în TERITORIU
6. dacă S este starea finală atunci
6.1. construieşte soluţia(S,..., Si), prin trasarea căii de-a
lungul pointer-ilor de la scop înapoi la starea iniţială, Si
6.2 întoarce SUCCES /* s-a găsit soluţia problemei */
7. expandează nodul S
7.1. generează toţi succesorii direcţi Sj ai nodului S
7.2. pentru fiecare succesor Sj (1≤j≤n) al lui S execută
7.2.1. calculează f(Sj) = g(S) + cost_arc(S, Sj) + h(Sj)
şi asociază valoarea lui Sj
7.2.2. stabileşte legătura fiu – părinte Sj -> S, prin
ataşarea unui pointer de la Sj înapoi la S
7.2.3 dacă Sj ≠ toate stările anterior generate în
soluţia parţială curentă atunci
introduce Sj în FRONTIERA
7.2.4 altfel
i. fie S’j copia lui Sj din FRONTIERA sau TERITORIU
ii. dacă g(Sj) < g(S’j) atunci
* transformă legătura S’j -> predecesor(S’j) în
legătura S’j -> S
* înlocuieşte f(S’j) asociată lui S’j cu f(Sj) (se
modifică doar g)
dacă S’j ∈ TERITORIU atunci
*elimină S’j din TERITORIU şi inserează-l în
FRONTIERA
iii. ignoră nodul Sj
8. repetă de la pasul 3
sfârşit
Caracteristici
Strategia A* este completă şi optimală dacă funcţia h este euristică admisibilă, adică
nu supraestimează niciodată costul atingerii scopului.
Funcţia g(S) reprezintă costul drumului parcurs de la starea iniţială până la starea curentă S.
daca sunt indeplinite urmat conditii:
h = admisibil (funct admisibila)
cost_arc(S,S') > ct unde ct > 0
atunci alg este admisibil => este complet si optimal si cu complexitate mare dar depinde de prb.
Algoritm pseudocod A*:
1. iniţializează listele FRONTIERA ←{Si} şi TERITORIU ←{}
2. calculeaza f(Si) şi asociază această valoare nodului Si
3. dacă FRONTIERA={} atunci
întoarce INSUCCES /*nu există soluţie*/
4. selectează din FRONTIERA un nod S pentru care f(S) este minimă
5. elimină nodul S din FRONTIERA şi inserează-l în TERITORIU
6. dacă S este starea finală atunci
6.1. construieşte soluţia(S,..., Si), prin trasarea căii de-a
lungul pointer-ilor de la scop înapoi la starea iniţială, Si
6.2 întoarce SUCCES /* s-a găsit soluţia problemei */
7. expandează nodul S
7.1. generează toţi succesorii direcţi Sj ai nodului S
7.2. pentru fiecare succesor Sj (1≤j≤n) al lui S execută
7.2.1. calculează f(Sj) = g(S) + cost_arc(S, Sj) + h(Sj)
şi asociază valoarea lui Sj
7.2.2. stabileşte legătura fiu – părinte Sj -> S, prin
ataşarea unui pointer de la Sj înapoi la S
7.2.3 dacă Sj ≠ toate stările anterior generate în
soluţia parţială curentă atunci
introduce Sj în FRONTIERA
7.2.4 altfel
i. fie S’j copia lui Sj din FRONTIERA sau TERITORIU
ii. dacă g(Sj) < g(S’j) atunci
* transformă legătura S’j -> predecesor(S’j) în
legătura S’j -> S
* înlocuieşte f(S’j) asociată lui S’j cu f(Sj) (se
modifică doar g)
dacă S’j ∈ TERITORIU atunci
*elimină S’j din TERITORIU şi inserează-l în
FRONTIERA
iii. ignoră nodul Sj
8. repetă de la pasul 3
sfârşit
Alg. AO*
-reprezinta o strategie de cautare informata si este folosita in cazul grafurilor SI/SAU.
daca sunt indeplinite urmat conditii:
f(s)<=W(s)
cost_arc(S(k mic0,S(kmic +1)) >= ct unde ct > 0
daca sint indeplinite atunci => alg optimal
|
|
