Prezentare Capitolul 1 Sisteme Expert

10.04.2011 1

Cap. 1. Sisteme expert

O definiţie a sistemelor expert

Sistemele expert – SE constituie o clasă particulară de sisteme informatice bazate pe inteligenţa artificială, având ca scop reproducerea cu ajutorul calculatorului a cunoştinţelor şi raţionamentelor experţilor umani.

Edward Feigenbaum de la Stanford University, considerat părintele sistemelor expert, defineşte SE ca fiind: “programe concepute pentru a raţiona în scopulrezolvării problemelor dificile pentru care, în mod obişnuit, se cere o expertiză umană considerabilă”.

10.04.2011 2


Un expert uman este o persoană care posedă cunoştinţe temeinice într-un anumit domeniu, un specialist de înaltă clasă, care poate efectua o expertiză în acel domeniu.Expertul poate rezolva probleme ale domeniului, pe care

alţii nu le pot rezolva deloc sau în mod eficient. El trebuie să fie capabil să îndeplinească următoarele sarcini:

să formuleze precis problema pe baza datelor puse la dispoziţie;să determine soluţia corectă;să explice soluţia şi paşii necesari pentru obţinerea ei;să acorde asistenţă pentru implementarea soluţiei într-un domeniu particular.

10.04.2011 3


Din punct de vedere funcţional, un sistem expert poate fi definit ca un program care se bazează pe o bază de cunoştinţe pentru a realiza anumite sarcini, uneori dificile, pe care de regulă le rezolvă un expert uman din domeniul respectiv.

În concluzie, un SE este un program inteligent care utilizează cunoştinţe, fapte şi tehnici de raţionament pentru a rezolva probleme care în mod normal necesită cunoştinţele experţilor umani.

10.04.2011 4


Observaţii:

Performanţele programului inteligent depind de:“bogăţia” bazei de cunoştinţe;organizarea acestora, care să permită rezolvarea problemei într-un timp rezonabil.

Spre deosebire de majoritatea programelor clasice de calcul, care cer informaţii complete pentru rezolvarea problemei sau luarea deciziilor, sistemele expert sunt proiectate să găsească soluţia pe baza datelor disponibile, adesea incomplete, la fel ca un expert uman.

10.04.2011 5


SE sunt sisteme de prelucrare automată a datelor conţinute într-o bază largă de date care pe lângă elementele clasice de prelucrare, conţin:

baza de cunoştinţe alcătuită din reguli şi fapte;elementele necesare manipulării cunoştinţelor sub forma mecanismului de inferenţă;elementele necesare achiziţionării şi implementării de noi cunoştinţe;componenta explicativă.

10.04.2011 6


Asemănător expertului uman care, bazându-se pe cunoştinţele acumulate, prin raţionamentul propriu ajunge la anumite concluzii, un SE se bazează pe cunoştinţele înglobate în baza de cunoştinţe şi pe mecanismul de inferenţă care are funcţia de a lua decizii în urma unor raţionamente logice.Raţionamentul este o înlănţuire de judecăţi (propoziţii) în care plecând de la anumite cunoştinţe, consemnate într-un număr de propoziţii numite premise sau fapte iniţiale, se ajunge la o nouă cunoştinţă – exprimată printr-o nouă propoziţie numită concluzie. Raţionamentul este corect dacă şi numai dacă concluzia este consecinţa logică a premiselor.

Raţionamentul poate fi definit şi ca o înlănţuire de reprezentări simbolice care trebuie să conducă la atingerea unui scop: a demonstra, a convinge, a elucida, a decide, a explica etc.

10.04.2011 7


SE implică următoarele caracteristici:reprezentări simbolice;inferenţă simbolică;căutare euristică,

Acestea le diferenţiază în mod esenţial de sistemele informatice convenţionale (procedurale) de prelucrare care folosesc date şi algoritmi cunoscuţi apriori pentru rezolvarea problemelor.

Metodele de rezolvare folosite de SE nu sunt proceduri matematice sau procesoare de date, ci tehnici de raţionament calitativ sau tehnici euristice, care leagă elemente între ele prin reguli de judecată precum şi prin legi şi definiţii teoretice.

10.04.2011 8


Diferenţele dintre un program de calcul analitic şi un SE:sistemul expert foloseşte datele din baza de date filtrate printr-un set de cunoştinţe, înmagazinate în baza de cunoştinţe, care sunt independente de algoritmul de rezolvare utilizat;algoritmul de căutare a soluţiei, denumit motor de inferenţă, nu mai este de tip iterativ, ca în cazul programelor analitice, ci de tip convergent;datorită delimitării nete dintre elementele componente (baza de date, baza de cunoştinţe, motorul de inferenţă) un SE poate fi modificat cu uşurinţă prin simpla adăugare sau eliminare de reguli; conceperea unui SE este un proces linear, realizat prin discuţii repetate cu experţi umani pentru dezvoltarea bazei de cunoştinţe;toate operaţiile logice şi matematice care se succed în găsirea unui răspuns se aduc la cunoştinţa utilizatorului printr-un modul explicativ independent numit “interfaţa cu utilizatorul”.

10.04.2011 9


Caracteristicile care califică un program dreptsistem expert

lucrează la un nivel expert de competenţă; foloseşte un mecanism de inferenţă pentru a realiza deducţiile;expertiza efectuată se bazează exclusiv pe cunoştinţe special dobândite;programarea lui implică descrierea şi reprezentarea cunoştinţelor unor experţi în domeniu, cunoştinţe ce sunt păstrate în baze de date specifice, numite baze de cunoştinţe, în scopul utilizării ulterioare.

10.04.2011 10


Avantaje ale utilizării sistemelor expert

1. aria de aplicabilitate cuprinde numeroase domenii de activitate mergând de la arhitectură, arheologie, bănci, comerţ, educaţie, până la ingineria sistemelor şi medicină;

2. disponibilitatea crescută, expertiza devenind accesibilă pe orice calculator adecvat: spre deosebire de expertul uman, SE este disponibil în orice moment şi nu este afectat de emotivitate, factori de stres etc.;

3. reducerea costului, explicabilă în corelaţie cu cele menţionate la punctul anterior, dar şi cu evoluţia preţului sistemelor de calcul;

4. permanenţa, rezultată din faptul că, spre deosebire de experţii umani, SE nu au o viaţă limitată;

5. reducerea riscurilor prin incorporarea în sisteme de comandă a roboţilor industriali utilizaţi în medii periculoase pentru om;

10.04.2011 11


Avantaje ale utilizării sistemelor expert

6. creştrea calităţii, prin obţinerea unei expertize complete a domeniului, ceea ce expertul uman nu realizează întotdeauna;

7. posibilitatea de explicare în detaliu a soluţiei obţinute pentru creşterea gradului de încredere al utilizatorului;

8. rapiditatea, în sensul că pe sisteme hardware şi software adecvate se pot obţine performanţe de timp mult mai bune comparativ cu cele ale experţilor umani;

9. păstrarea în siguranţă a cunoştinţelor: marile firme şi-au constituit sisteme expert pentru a fi afectate într-o mai mică măsură de plecarea unor experţi umani;

10. contribuţia la răspândirea cunoştinţelor din domeniu: un utilizator poate rula programul pentru mai multe probleme, de la simplu la complex, şi urmărind soluţiile şi explicaţiile date de SE se poate autoinstrui în domeniul respectiv.

10.04.2011 12


Arhitectura unui SE

Mediu ded ezvo ltare

Inginer decunoşt inţe

Memo riea d elucru

Fapte dinamice

Uti lizator

E xpert îndomeniu

Baza dedate

Regu liselecţionate

A cţiuniConcluzii

Da te

Baza decunoşt inţe

Reg uli

Fap teSelectare

reg uli şi fapte

Moto r de in ferenţă

Ach

iziţi

e de

cunoşt

inţe

10.04.2011 13


Componentele unui SE se grupează în:1. Componente de bază care alcătuiesc nucleul SE

baza de cunoştinţe; baza de date; motorul de inferenţe. (inferenţă = operaţie logică de trecere de la un enunţ la altul şi în care ultimul enunţ este dedus din primul )

2. Componente complementaremodulul de achiziţionare de cunoştinţe; interfaţa cu inginerul de aplicaţie (expertul); interfaţa cu inginerul de cunoştinţe;interfaţa cu utilizatorul; module de grafică şi de calcul.

10.04.2011 14


Baza de cunoştinţe – BC

cuprinde o colecţie de cunoştinţe relevante despre un anumit domeniu şi este constituită din reguli şi fapte.

Regulile se referă la operaţiile ce pot fi efectuate asupra obiectelor conţinute în baza de date. Ele se schimbă mai rar şi în esenţă constituie un ansamblu complet şi necontradictoriu de cunoştinţe necesare rezolvării unei probleme.

Faptele reprezintă partea dinamică a bazei de cunoştinţe şi au rolul de a reprezenta starea obiectelor la un moment dat.

10.04.2011 15


Reprezentarea cunoştinţelor

Reprezentarea cunoştinţelor se poate realiza prin:

regulile de producţie;reţele semantice;structuri împachetate sau frame–uri;obiecte;logica propoziţională sau a predicatelor

10.04.2011 16


Reguli de producţie

Reprezentarea cunoştinţelor sub forma regulilor de producţie este specifică sistemelor de producţie şi este foarte potrivită pentru raţionamente.

Într-un sistem de producţie cunoştinţele sunt de natură procedurală şi se împart în următoarele componente:

cunoştinţe declarative sau factuale, grupate sub forma unor structuri de date memorate într-o colecţie denumită context;cunoştinţe procedurale reprezentate sub forma unor perechi de tipul condiţie –acţiune, denumite reguli de producţie, memorate în baza de reguli;cunoştinţe strategice sau de control, reprezentate sub forma unor reguli care sprijină decizia în procesul de soluţionare al problemei.

10.04.2011 17


Structura generală a unei reguli de producţie este:< partea de condiţie > → < partea de acţiune >

şi este interpretată astfel: “DACĂ < partea de condiţie > este îndeplinită,

ATUNCI se poate executa < partea de acţiune >”.

Partea de condiţie, denumită şi premisă, este constituită din propoziţii logice care trebuie să fie verificate pentru ca regula să poată fi aplicată.

Partea acţiune corespunde declanşării unei concluzii sau a unei noi ipoteze.

10.04.2011 18


Avantajele regulilor de producţiemodularitatea proprie a fiecărei reguli – orice regulă poate fi considerată ca o entitate structurală independentă de celelalte ceea ce conferă o uşoară întreţinere a bazei de reguli;modularitate în realizarea formalismului de rezolvare a problemei regulile putând fi asimilate cu un ansamblu de constituenţi elementari, care se adună şi se combină pentru a forma un răspuns la problema studiată;caracterul natural de exprimare ;accesibilitatea bazei de reguli, dată de facilitatea şi uniformitatea structurii utilizate pentru reprezentarea cunoştinţelor.

10.04.2011 19


Dezavantajele regulilor de producţieimposibilitatea de a prevedea o desfăşurare optimă pentru o secvenţă de acţiuni;

ordinea în care sunt aplicate regulile potenţial aplicabile influenţează concluzia obţinută.

10.04.2011 20


Reţele semanticeSunt structuri destinate reprezentării cunoştinţelor sub forma unui graf complex alcătuit din noduri şi arce. Nodurile reţelei/grafului sunt utilizate pentru a reprezenta obiecte, concepte, atribute, stări, evenimente etc. Arcele reprezintă relaţiile existente între obiectele ataşate nodurilor reţelei semantice şi sunt de două tipuri:

ISA – is a (este un); AKO – a kind of (un fel de).

Reţelele semantice, respectiv grafurile corespunzătoare, pot fi organizate ierarhic ceea ce permite moştenirea unor atribute de la tipurile generale la cele particulare.

10.04.2011 21


Structuri împachetate (frame-uri).

O structură este un grup de atribute ce descriu un obiect dat. Fiecare atribut este stocat într-un slot (compartiment ) care conţine valoarea/valorile ataşate. Folosirea structurilor permite reprezentarea cunoştinţelor în blocuri de date, fiecare bloc fiind prezentat printr-un slot sau compartiment. Structurile reprezentând diverse obiecte pot fi înzestrate cu proprietatea de moştenire, pe baza căreia se generează legături ierarhice între acestea. Prin urmare, ele pot fi reprezentate sub forma unui arbore.

10.04.2011 22


Reprezentarea orientată pe obiecte

Constituie un pas superior în reprezentarea datelor.

Caracteristica principală a reprezentării orientată pe obiecte este aceea că unifică, într–o aceeaşi unitate structurală numită "obiect", datele şi funcţiile sau metodele care acţionează asupra lor.

Din punct de vedere al tehnicii de programare tipurile structurilor amintite se definesc cu ajutorul conceptului de clasă, iar obiecte cu care operează programul sunt instaţieri ale claselor.

10.04.2011 23


Logica predicatelor

Oferă un mijloc de exprimare a aserţiunilor (aserţiune = enunţ care este dat ca adevărat ) şi un cadru formal pentru realizarea de inferenţe bazate pe manipularea sintatică a formulelor logice.

O bază de cunoştinţe este constituită exclusiv dintr-o mulţime de formule care descriu universul problemelor de rezolvat numit şi universul de discurs.

10.04.2011 24


Utilizarea logicii predicatelor pentru reprezentarea cunoştinţelor rezultă din posibilitatea obţinerii de noi rezultate folosind reguli de inferenţă precum:

modus ponens;modus tollens;rezoluţia etc.

Logica permite exprimarea relativ naturală a unor fapte, fiind lipsită de ambiguităţi: este un sistem formal care oferă rigoare şi claritate semantică.Avantajele oferite de rigoare şi claritate constituie în acelaşi timp dezavantaje în reprezentarea cunoştinţelor şi realizarea expertizei deoarece omul, în general, nu este atât de riguros, raţionamentele sale fiind adesea mult mai suple.

10.04.2011 25


Nu există o organizare între diferitele elemente care alcătuiesc baza de cunoştinţe. Obiectele manipulate nu au o reprezentare proprie; ele există doar prin intermediul formulelor care sunt diseminate în baza de cunoştinţe (este caracteristica formalismului relaţional, opus celui obiectual.

Pe măsură ce baza de cunoştinţe se dezvoltă, lipsa de organizare generează probleme vizând coerenţa utilizării sale.

Modelarea cunoştinţelor în logica de ordinul întâi nu este întotdeauna uşor de realizat.

Pentru eliminarea dezavantajelor şi extinderea câmpului de aplicaţii al logicii s-au dezvoltat aşa numitele logici neclasicecum ar fi logicile multivalente, logicile de incertitudine, logicile modale, logicile fuzzy etc.

10.04.2011 26


Consideraţii vizând reprezentarea cunoştinţelor

În dezvoltarea aplicaţiilor practice de tip SE, pentru reprezentarea cunoştinţelor se au în vedere următoareleaspecte:

regulile de producţie sunt foarte adecvate pentru dezvoltarea raţionamentelor;frame-urile (cadrele), încadrate eventual în reţele semantice, sunt adecvate pentru stocarea şi manipularea eficientă a cunoştinţelor;reprezentarea orientată pe obiecte, prin proprietăţi precum încapsularea, moştenirea şi polimorfismul, asigură o elasticitate mărită în elaborarea SE.

10.04.2011 27


În afara inferenţelor folosind cunoştinţele calitative, pentru rezolvarea problemelor din viaţa reală sunt necesare şi calcule numerice. Cantitatea de calcule poate fi foarte mică în unele cazuri şi destul de mare în altele.

Necesitatea ca un sistem expert să fie capabil să apeleze programede calcul procedural.

Acestea formează o parte a bazei de cunoştinţe şi se numesc cunoştinţe cantitative. Ele pot fi reprezentate ca funcţii sau programe scrise în limbaje de programare de nivel înalt cum ar fi Fortran sau C.

În acest conrext, cele mai multe shell-uri de dezvoltare a sistemelor expert furnizează facilităţi de reprezentare atât a cunoştinţelor calitative (prin reguli, structuri etc.), cât şi a cunoştinţelor cntitative prin funcţii scrise în limbaje procedurale.

10.04.2011 28

Cap. 1. Sisteme expertBaza de fapte – BF

Constituie partea dinamică a sistemelor bazate pe cunoştinţe şi conţine informaţii relative la domeniul de aplicaţie studiat. Faptele sunt date normale de tip:

închis–deschis pentru un echipament de comutaţie;o alarmă de ieşire din funcţiune a unui echipament;o valoare sau o mărime fizică aflată în afara limitelor admisibile etc.

Ele se modifică pe măsură ce stările obiectelor cărora le sunt asociate se schimbă (de exemplu datorită unor avarii, efectuării unor manevre, schimbării configuraţiei de funcţionare a unei reţele etc.).

10.04.2011 29


Un fapt are o reprezentare de forma:<Obiect>, <Relaţie>, <Valoare>

<Obiectul> reprezintă, de exemplu, un echipament a cărui stare poate fi stabilită printr–o semnalizare, verificare sau, mai general, deducţie logică;

<Relaţie> corespunde unei relaţii existente între obiecte sau între un obiect şi diferitele stări în care acesta se poate afla;

<Valoare> reprezintă cuantificarea stării obiectului la un moment dat.

Exemplu: < Întreruptorul I7 > < Este în poziţia > < Închis >

10.04.2011 30


În funcţie de domeniul de aplicare, sistemul expert are la dispoziţie un anumit număr de fapte, care descriu stări sau dau informaţii de tip cantitativ. O parte din datele din baza de fapte sunt introduse cu ajutorul dialogului om–maşină, în timp ce altă parte este încărcată automat prin citirea lor dintr-o bază de date.

Prin analogie cu programele de calcul convenţionale, faptele reprezintă ” datele ” problemei. În arhitectura SE ele, alături de unele date numerice aferente modelului problemei abordate, ” baza de date ”.

10.04.2011 31


Motorul de inferenţă – MI

Este un program general care implementează mecanismul prin care se construiesc raţionamentele.

Pornind de la faptele iniţiale ( datele de intrare ale problemei ), MI are ca sarcină exploatarea regulilor şi generarea răspunsurilor la întrebările puse de utilizatori în scopul determinării soluţiei problemei analizate.

10.04.2011 32


În acest sens, cu regulile existente în baza de cunoştinţe se construiesc arbori de inferenţă sau de căutare care au ca noduri premisele/condiţiile, iar ca ramuri arcele care conectează diferitele premise. Există diverse procedee sau mecanisme de inferenţă care traversează acest arbore în sensuri diferite, conceptul de “CĂUTARE” fiind unul esenţial în programele de IA.Cele mai cunoscute metode de inferenţă sunt:

înlănţuirea înainte - este un proces de inferenţă deductiv, condus de date;înlănţuirea înpoi - este un proces de inferenţă inductiv, condus de scop;înlănţuirea hibridă - este un proces de inferenţă care combină inducţia înainte şi inducţia înapoi.

10.04.2011 33


Principiul de funcţionare al MI.

Reguli

Sistem achizi ie de dateţ

UtilizatorFapte

Motor de inferenţe

reguli aplicabile

Reguli

Regulă

Alteacþiuni

Selectare

Folosind baza de cunoştinţe (faptele şi regulile), MI construieşte dinamic raţionamentele alegând regulile ce vor fi aplicate şi ordinea de înlănţuire a acestora până când se ajunge la scopul propus.

10.04.2011 34


Ciclul de bază al motorului de inferenţă

Este independent de modul de raţionament utilizat şi comportă patru etape:

SELECŢIA: în această etapă se extrag din baza de reguli şi din baza de fapte elementele care caracterizează subdomeniul de rezolvare a problemei. Această etapă este necesară atunci când baza de cunoştinţe este mare, încercând să acopere mai multe domenii ale cunoaşterii.

Reguli posibile Faptele selecţionate

10.04.2011 35


FILTRAJUL ( pattern matching ) constă în compararea premiselor regulilor selecţionate anterior cu faptele ce caracterizează problema de rezolvat, pentru a determina submulţimea regulilor declanşabile. În urma acestei etape pot rezulta:

o regulă aplicabilă care este declanşată pentru a genera noi fapte;nici o regulă aplicabilă: s-a ajuns într-o stare de eşec pe care SE o semnalează, iar utilizatorul va trebui să răspundă la o serie de întrebări în scopul datelormai multe reguli aplicabile: s-a generat o stare conflictuală care trebuie rezolvată.

10.04.2011 36


REZOLVAREA CONFLICTELOR este necesară atunci când din etapa de filtraj au rezultat mai multe reguli declanşabile şi trebuie aleasă una pentru a fi executată. Pentru aceasta se utilizează diverse criterii dintre care se amintesc:

prima regulă din listă; regula cu cel mai mare număr de fapte în premisă; regula cea mai des utilizată.

De alegerea făcută în această etapă depind performanţele MI. Este dificil de indicat unul sau altul dintre criterii. Alegerea depinde de contextul în care se găseşte baza de cunoştinţe în momentul respectiv.

10.04.2011 37


EXECUŢIA REGULII SELECTATE constă în adăugarea uneia sau mai multor fapte în “baza de fapte”ca o consecinţă a aplicării regulii respective. Este posibil ca în această etapă să se facă apel şi la proceduri externe ( acces la baze de date, calcul tabelar sau la proceduri de calcul scrise în limbaje de nivel înalt ) sau la întrebări puse utilizatorului.

Pentru rezolvarea unei probleme MI execută mai multe cicluri de bază şi se opreşte în funcţie de modul de raţionament utilizat.

10.04.2011 38


Baza de reguli (BR)

Reguliposibile

SELEC IEŢ

Baza de fapte (BF)

Fapteselec ionateţ

FILTRAJ

Regulideclan abileş

REZOLVARECONFLICTE

Regulire inuteţ

EXECU IEREGULI

Ţ

10.04.2011 39


Module complementare

Modulul de achiziţie de cunoştinţe - realizează transferul cunoştinţelor de la experţii în domeniu către sistemul expert

10.04.2011 40


Extragerea cunoştinţelor de la un expert uman cu ajutorul unor mijloace specifice sau prin metoda interviurilor este un proces eterogen, numit ingineria cunoaşterii şi constă în:

Identificare: definirea corectă a problemei şi determinarea caracteristicilor sale;Conceptualizare: determinarea conceptelor care să sprijine reprezentarea cunoştinţelor;Formalizare: alegerea unor metode de reprezentare a cunoştinţelor şi a mecanismului de inferenţă; Implementare: reprezentarea propriu-zisă a cunoştinţelor în formalismul ales;Testare: verificarea cunoştinţelor şi validarea sistemului.

10.04.2011 41


Interfaţa cu utilizatorul: Este partea din program care permite utilizatorului:

să pună întrebări sistemului expert;să introducă noi informaţii; să primească diferite recomandări de la SE.

Aprecierea utilizatorului asupra unui sistem expert depinde în mare măsură de asemănarea între modul de reprezentare a informaţiilor de către SE şi modelul pe care utilizatorul îl are în “mintea sa” despre problema care se rezolvă.

10.04.2011 42


Modulul explicativ SE trebuie să aibă capacitatea de a furniza explicaţii operatorului în legătură cu raţionamentul folosit pentru a ajunge la o anumită recomandare sau decizie. Cu cât sunt mai explicit reprezentate cunoştinţele în baza de cunoştinţe, cu atât este mai eficient procesul explicativ, deoarece cunoştinţele şi metodele de utilizare a acestora sunt elemente fundamentale.

10.04.2011 43


STRATEGII DE CĂUTARE A SOLUŢIEI

Consideraţii generaleProblemele care pot fi rezolvate folosind tehnici ale IA sunt probleme complex computaţionaleDeterminarea soluţiei se face prin deplasarea în spaţiul de definiţie al problemei denumit şi spaţiul de căutare sau universul problemei de rezolvat. Spaţiul de căutare este constituit dintr-un număr foarte mare de stări, fiecare descriind o situaţie posibilă; datorită restricţiilor problemei, o parte dintre stări sunt stări interzise în care nu se poate ajunge niciodată.

10.04.2011 44


Concluzie: rezolvarea problemelor poate fi văzută ca un proces de identificare sau de construire a unui obiect având anumite caracteristici şi care reprezintă soluţia problemeiAceastă activitate implică existenţa următoarelor elemente:

O structură simbolică care să poată reprezenta descrierea iniţială a problemei si fiecare obiect candidat la soluţie (este structura folosită pentru reprezentarea cunoştinţelor)O mulţime de instrumente computaţionale capabile să transforme descrierea unui obiect (structură simbolică) într-o nouă descriere în scopul de a investiga sistematic toţi candidaţii la soluţie. Aceste instrumente sunt constituite din operatorii de transformare sau regulile de producţie

10.04.2011 45


O strategie de control care să indice ordinea de aplicare a transformărilor astfel încât soluţia problemei să fie găsită cât mai repede.

Procesul de determinarea a soluţiei porneşte dintr-o stare iniţială Si cunoscută şi, prin aplicarea unor reguli (operatori de transformare) care permit trecerea dintr-o stare în altă stare, se urmăreşte ajungerea într-o stare finală Sf care constituie soluţia sau o soluţie a problemei de rezolvatDeci soluţia problemei se obţine printr-un proces de căutare şi nu prin aplicarea unei secvenţe de transformări specificate dinainte.

10.04.2011 46


În procesul de căutare se utilizează grafuri: fiecare stare este reprezentată printr-un nod, iar operatorii de transformare prin arce. Definirea unei probleme de căutare se face folosind următorul formalism:

D este mulţimea stărilor sau universul problemei;T – mulţimea transformărilor;

O soluţie a problemei P, notată T*, este o secvenţă de transformări cu următoarea proprietate:

( ) ( )Ti fP S D S D= ∈ ⎯⎯→ ∈

( )( )( )* * *2 1...f n iS t t t S=

10.04.2011 47


Algoritmul generic de căutare

1. Stabileşte starea/stările iniţială/iniţiale Si2. Stabileşte starea curentă 3. Repetă

3.1. Selectează un operator de transformare t posibil de aplicat stării curente Sc

3.2. Aplică operatorul t asupra stării si obţine o nouă stare

3.3. Stabileşte până când Sc este stare finală

4. Sfârşit.

c iS S←

( )'cS t S=

'cS S←

10.04.2011 48


Observaţii:Algoritmul este nedeterminist deoarece pasul 3.1 nu specifică cum se selectează operatorul sau transformarea t de aplicat. Selectarea transformărilor si memorarea transformărilor efectuate constituie strategia de control. Strategia de control trebuie să fie sistematică, adică trebuie să satisfacă următoarele cerinţe:

să prezinte proprietatea de completitudine, adică să garantează faptul că strategia produce soluţia, dacă aceasta există; să asigure protecţie împotriva ineficienţei prelucrărilor repetate

Altfel spus:nu lasă nici o piatră neîntoarsă;nu întoarce nici o piatră de mai multe ori.

10.04.2011 49


EXEMPLU

Se consideră un sistem aflat în starea iniţială caracterizată de proprietăţile P1, P2 şi P3.

Sistemul evoluează prin adăugarea de noi proprietăţi conform următoarelor transformări sau reguli:

t1: DACĂ (P1 ŞI P2) ATUNCI P4t2: DACĂ (P2 ŞI P3) ATUNCI P5t3: DACĂ (P1 ŞI P4) ATUNCI P6t4: DACĂ (P5 ŞI P6) ATUNCI P7t5: DACĂ (P2 ŞI P5) ATUNCI P7

10.04.2011 50


Evoluţia sistemului are loc respectând convenţia: dacă între starea iniţială şi starea curentă s-a aplicat o anumită secvenţă de transformări, atunci niciuna dintre transformările folosite nu mai poate fi aplicată stării curente.

Se cere să se stabilească secvenţa de transformări ce conduce sistemul în starea finală care conţine proprietatea P7.

10.04.2011 51

Cap. 1. Sisteme expertSecvenţa de transformări şi soluţii posibile

{ }{ }

*7 1 2 5*8 2 1 5

, ,

, ,

T t t t

T t t t

=

= P , 1 P , P2 3

P , 1 P , P ,P , P , P ,

P

2 3

4 5 6

7

P , 1 P ,P ,P ,P , P

2 3

4 5 7

P , 1 P ,P ,P , P , P

2 3

4 5 6

P , 1 P ,P ,P ,P

2 3

4 5

P , 1 P ,P ,P

2 3

4

P , 1 P ,P ,P

2 3

5

P , 1 P ,P ,P , P

2 3

5 7

P , 1 P , P ,P , P

2 3

4 6

t1

t1

t2

t2

t2

t3

t3

t4

t5

t5

t5

{ }{ }{ }

*1 1 2 3 4*2 2 1 3 4*3 1 3 2 4

, , ,

, , ,

, , ,

T t t t t

T t t t t

T t t t t

=

=

=

{ }{ }{ }

*4 1 2 3 5*5 2 1 3 5*6 1 3 2 5

, , ,

, , ,

, , ,

T t t t t

T t t t t

T t t t t

=

=

=

{ }*9 2 5,T t t=

10.04.2011 52


Acest exemplu evidenţiază următoarele aspecte:O parte dintre soluţii conţin aceleaşi transformări, dar în succesiuni diferite. Acest fapt implică revenirea în stări deja explorate şi apariţia unor bucle în graful de căutare. Dacă se elimină buclele rezultă patru soluţii posibile:

{ }*1 1 2 3 4, , ,T t t t t= { }*

4 1 2 3 5, , ,T t t t t=

{ }*7 1 2 5, ,T t t t= { }*

9 2 5,T t t=

Numărul transformărilor utilizate diferă de la o soluţie la alta, existând posibilitatea obţinerii soluţiei printr-un nr. minim de transformări.

10.04.2011 53


Observaţii:Comportarea programelor de inteligentă artificială poate fi caracterizată ca un proces de căutare în care diverse transformări aplicabile universului problemei sunt încercate până se determina soluţia problemei. În general, pentru a determina soluţia este necesară evaluarea unui număr mare de stări intermediare (obiecte candidate la soluţie), iar folosirea căutării exhaustive este exclusă.Informaţia euristică joacă un rol foarte important în cadrul procesului de căutare contribuind la reducerea numărului de stări investigate pentru obţinerea soluţiei şi creşterea eficienţei procesului de rezolvare. Informaţia euristică este reprezentată printr-o funcţie euristică asociată fiecărei stări, care estimează cât de promiţătoare este acea stare din punct de vedere al avansului spre soluţie. Funcţiile euristice depind şi se stabilesc pe baza cunoştinţelor specifice problemei sau clasei de probleme de rezolvat.

10.04.2011 54


Reprezentarea soluţiei problemeiReprezentarea soluţiei problemei

Reprezentarea soluţieiproblemei prinspaţiul stărilor

Reprezentarea soluţieiproblemei prinspaţiul stărilor

Reprezentarea soluţieiproblemei prin

grafuri SI / SAU

Reprezentarea soluţieiproblemei prin

grafuri SI / SAU

( ), ,i fS O S ( ), ,i eS O P

10.04.2011 55


Reprezentarea soluţiei problemei prin spaţiul stărilorSpaţiul de căutare are forma unui graf orientat în care nodurile sunt identificate prin stări, iar arcele reprezintă aplicarea unor operatori pentru a transforma o stare în altă stareReprezentarea este formată din tripletul (Si,O, Sf) în care:

Si este starea iniţială;O - mulţimea de operatorilor aplicabili stărilor universului

problemei pentru a ajunge în noi stări: in fiecare stare dată, numai o parte din operatori pot fi aplicaţi;

Sf - mulţimea stărilor finale; aceasta poate fi constituită din una sau mai multe stări.

10.04.2011 56


Prin urmare, în această reprezentare, o soluţie a problemei este o secvenţa de operatori care transformă starea iniţială în starea finală şi reprezintă o cale între aceste două stări în graf. Iniţial graful spaţiului de căutare este specificat implicit de reprezentare prin tripletul (Si, O, Sf ). Pe măsură ce procesul de căutare a soluţiei avansează o parte din acest graf devine explicită. Porţiunea din graful spaţiului de căutare astfel construită reprezintă partea explorată a spaţiului de căutare.

10.04.2011 57

Cap. 1. Sisteme expertExemplu: Problema comis voiajorului

A

B

E

D

C

7

106

10

10

136

7

5

9

(a) Harta oraselor de parcurs

{A}

{A,B} {A,C} {A,D} {A,E}

7 6 10 13

... ... ...5{A,C,D}

{A,C,D,E}

6

(b) O portiune din spatiul de cautare a solutiei

Generarea tuturor traseelor posibile şi compararea costurilor asociate pentru a găsi traseul optim este un proces ineficient din punct de vedere computaţional, mai ales în cazul unui număr mare de oraşe. De aceea, pentru rezolvarea acestei probleme se face apel la tehnicile euristice de căutare.

10.04.2011 58


Există probleme care pot fi rezolvate printr-o tehnică numită descompunerea problemei în subprobleme.

Caracteristica acestei clase de probleme este aceea că problema pusă de un obiect candidat la soluţie este văzută ca o conjuncţie de subprobleme care pot fi rezolvate independent unele de altele.

Reprezentarea soluţiei problemei prin grafuri SI/SAU

10.04.2011 59


Mecanismul de rezolvare a problemelor din această clasă constă în :

descompunerea problemei iniţiale în subproblemele care trebuie rezolvate;descompunerea subproblemelor în alte subprobleme;continuarea procesului până când se obţine o descompunere a problemei iniţiale in subprobleme elementare a căror rezolvare este cunoscută.

Spaţiul de căutare al unei astfel de rezolvări a problemei are forma unui graf SI/SAU. Acesta este un caz particular al unui hipergraf.

10.04.2011 60


Definiţie: o reprezentare a soluţiei problemei prin grafuri SI/SAU este formată din tripletul (Si , O , Pe) în care:

Si este descrierea stării iniţiale;O – mulţimea operatorilor de transformare care

descompun problema în subprobleme; Pe – mulţimea de probleme elementare.

Observaţie: mulţimea operatorilor conţine operatori aplicabili stărilor universului problemei pentru a genera noi stări; în fiecare stare dată, numai o parte din operatori pot fi aplicaţi.

10.04.2011 61


Reguli pentru generarea grafurilor SI/SAU

R1 Fiecare nod reprezintă fie o singură problemă, fie o mulţime de probleme ce trebuie rezolvate.

R2 Un nod care reprezintă o singură problemă nu are descendenţi. Problema este fie o problemă elementară, fie o problemă neelementară care nu se mai poate descompune în alte subprobleme.

R3 Nodurile care reprezintă mulţimea de subprobleme în care s-a descompus o problemă prin aplicarea unui operator de descompunere se numesc noduri SI.

R4 Nodurile ce reprezintă descompuneri alternative ale unei probleme în subprobleme se numesc noduri SAU. Aceste noduri au ca descendenţi noduri SI.

10.04.2011 62


Exemplu de graf SI/SAU

Nod SAU

Noduri SI

Noduri SAU

10.04.2011 63


Într-un graf SI/SAU există două tipuri de noduri: noduri rezolvate noduri nerezolvabile:

Un nod este rezolvat dacă:este un nod terminal etichetat cu o problemă elementară;este un nod SI, iar toţi succesorii lui sunt noduri rezolvate;este un nod SAU si cel puţin un succesor al acestuia este nod rezolvat.

Un nod este nerezolvabil dacă:este un nod terminal etichetat cu o problemă neelementară care nu se mai poate descompune în subprobleme;este un nod SI cu cel puţin un succesor nerezolvabil;este un nod SAU cu toţi succesorii nerezolvabili.

10.04.2011 64

Concluzie O problemă are soluţie dacă există o secvenţă de operatori care fac ca nodul corespunzătordescrierii iniţiale a problemei să devină nod rezolvat.

Exemplu. Problema turnurilor din HanoiSe cere să se mute n=3 discuri de pe tija A pe tija C,

utilizând tija intermediară B cu restricţia ca un disc să fie aşezat fie pe o tija liberă, fie peste un disc de o dimensiune mai mare decât el.

10.04.2011 65


A B C A B C

(a) Stare initiala (b) Stare finala

Mulţimea operatorilor de descompunere este formată dintr-un singur operator, cu trei componente şi anume:

mută n-1=2 discuri de pe tija i pe tija j, utilizând tija k;mută un disc de pe tija i pe tija k;mută n-1=2 discuri de pe tija j pe tija k, utilizând tija i.

Singura problema elementară este aceea de a muta un singur disc de peo tijă pe o altă tijă respectând restricţia problemei.Problema având un singur operator de descompunere, spaţiul de căutare va conţine numai noduri probleme elementare şi noduri SI.

10.04.2011 66


n = 3A la C

n = 2 n = 2

n = 1

A la B

A la C

B la C

n = 1A la C

n = 1A la B

n = 1C la B

n = 1B la A

n = 1B la C

n = 1A la C

(c) Arborele SI/SAU de descompunere in subprobleme

O - operator de descompunere

10.04.2011 67


Observaţii vizând soluţionarea problemelor de IA

Orice problemă poate fi solutionată prin ambele metode de reprezentare analizate. Totuşi, pentru o anumităproblemă este mai adecvată o reprezentare sau alta.Anumite probleme conduc în mod natural la o reprezentare a solutiei prin spatiul starilor, asa cum este problema comis voiajorului, problema mozaicului de 8 numere, problema celor 8 regine etc. O astfel de rezolvare corespunde unui rationament direct pentru a solutiona problema sau unui control condus de date.

10.04.2011 68


Alte probleme, cum ar fi problema turnurilor din Hanoi,problema cintaririi monezilor, conduc in mod natural la o rezolvare prin descompunerea problemei în subprobleme. O astfel de rezolvare corespunde unui rationament invers pentru rezolvarea problemei sau unui control condus de scopuri.

10.04.2011 69


Pentru alegerea unei strategii de căutare trebuie să se ţină cont de:

Completitudinea strategiei – stabileşte dacă strategia asigură sau nu găsirea soluţiei în cazul în care aceasta există.Optimalitatea soluţiei – este dată de capacitatea strategiei de a obţine o soluţie optimală, suboptimală sau pur si simplu o soluţie.Complexitatea strategiei – se referă la complexitatea exprimată în timp de calcul şi memorie (efort computaţional) a algoritmului utilizat.

Strategii de căutare de bază

10.04.2011 70


Caracterizarea unei strategii de căutare se poate face după două criterii:C1: capacitatea mecanismului de rezolvare de a reveni

într-o stare intermediară anterioară:Strategii de căutare irevocabile;Strategii de căutare tentative.

C2: după cantitatea de informaţie folosită la găsirea soluţiei:

Strategii de căutare neinformateStrategii de căutare informate

10.04.2011 71


Strategii de căutare irevocabile.Principiul: Un operator aplicabil este selectat şi aplicat unei stări pentru a

obţine o nouă stare, iar starea anterioară este uitată (nu este memorată) şi, prin urmare, nu se mai poate reveni în ea .

Exemplu: strategia de căutare a alpinistului. se bazează pe criterii de optim local;asemănător unui alpinist care doreşte sa ajungă repede pe vârful unui munte, strategia alege starea următoare de nivel maxim pe baza unei funcţii de evaluare a stărilor;strategia este irevocabilă deoarece pentru o stare curentă, după generarea stărilor următoare şi alegerea stării de nivel maxim ca noua stare curentă, celelalte stări sunt uitate. Deci nu se mai poate reveni într-una din stările anterioare stării curente sau într-una din alternativele stării curente. strategia alpinistului, deşi simplă si puţin consumatoare de memorie, prezintă o serie de limitări ca de exemplu blocarea intr-un maxim local fără a putea obţine maximul global.

10.04.2011 72


Strategii de căutare tentative

Principiul: La aplicarea unui operator starea curentă este memorată astfel încânt procesul de căutare să poată reveni ulterior în stările anterioare stării curente.

Dacă starea anterioară la care se poate reveni în timpul căutării se află numai pe calea curentă între starea iniţială si starea finală, strategia de căutare este o strategie tentativă de tip "backtracking". Aceasta este, de exemplu, strategia utilizata de limbajul Prolog.

Dacă starea anterioară în care se poate reveni se află pe orice cale deja parcursă în expandarea spaţiului de căutare, strategia este de căutare tentativă generală pe grafuri.

10.04.2011 73


Strategii de căutare neinformate.

Principiul: Considerarea stărilor următoare de inspectat se face după o ordine arbitrară, anterior stabilită.

inspectează sistematic toate stările spaţiului de căutare până în momentul găsirii stării finale.

Cele mai importante strategii de acest fel sunt: căutarea pe nivel sau căutarea în lăţime;căutarea in adâncime.

10.04.2011 74


Strategii de căutare informatePrincipiul: Considerarea stărilor următoare de inspectat se face

după criterii euristice. Strategia foloseşte o funcţie de evaluare a situaţiei globale sau locale care indică starea următoare cea mai promiţătoare din punct de vedere al avansului spre soluţie.Strategiile de căutare euristice încearcă reducerea numărului de stări din spaţiul de căutare inspectate până la atingerea stării finale, pe baza diverselor criterii, cum ar fi funcţiile euristice. Exemple: strategia alpinistului, strategia de căutare "best-first", algoritmul A* si algoritmul AO*. Algoritmii A* si AO* urmăresc în principal, pe lângă reducerea numărului de stări inspectate, găsirea soluţiei optime.

10.04.2011 75


Costul computaţional

Costul computaţional total al unui program de rezolvare a problemelor de IA depinde de locul unde se situează strategia de control în spectrul neinformat/informat şi are două componente:

costul aplicării operatorilor, sau costul parcurgerii spaţiului de căutare între starea iniţială si starea finală;

costul controlului, sau costul evaluării si selecţiei celei mai promiţătoare stări următoare.

10.04.2011 76


Grad deinformare

CostComputational

Cost total

Cost control(cost evaluare stari)Cost parcurgere

(cost aplicareoperatori)

Neinformat Informat

10.04.2011 77


Observaţii:O strategie de căutare complet neinformată implică:

un cost redus al controlului;un cost ridicat al parcurgerii spaţiului de căutare deoarece necesită aplicarea unui număr mare de operatori înaintea găsirii unei soluţii.

O strategie de control complet informată despre domeniul problemei implică:

un cost ridicat al controlului deoarece poate necesita calcule complicate pentru evaluarea meritului stărilor;un cost minim de parcurgere a spaţiului de căutare datorita numărului redus de operatori aplicaţi până la găsirea soluţiei.

Există un grad optim de informare pentru care costul total este minim.

10.04.2011 78


În funcţie de aplicaţie, proiectantul programului trebuie să încerce determinarea celei mai bune variante de pondere a costurilor.

Obţinerea unui cost computaţional optim este un aspect esenţial deoarece problemele de căutare sunt probleme de complexitate timp exponenţială.

10.04.2011 79

Cap. 1. Sisteme expertCăutări neinformate în spaţiul stărilor

Formularea problemeiSe consideră:

un graf definit implicit prin mulţimea operatorilor asociaţi arcelor ;nodul sau mulţimea de noduri ce definesc starea iniţială Si, adică condiţiile iniţiale ale problemei de rezolvat ;nodul sau mulţimea de noduri ce definesc starea finală , adică obiectivele sau cerinţele problemei .

Pentru rezolvarea problemei este necesar să se găsească o cale între starea iniţială şi starea finală. Un proces de căutare

10.04.2011 80


După cum s-a prezentat, principiul care se află la baza algoritmului generic de căutare constă în explorarea incrementală a căilor ce pornesc din nodurile aferente stării iniţiale şi foloseşte noţiunea de frontieră pentru a delimita nodurile explorate de cele care nu au fost încă explorate.

În parcurgerea spaţiului de căutare un nod poate fi:necunoscut - nodul aparţine părţii neexplorate a spaţiului de căutare;evaluat - nodul este cunoscut dar fie nu se cunoaşte nici un succesor al lui, fie se cunosc numai o parte dintre aceştia;expandat - nodul este cunoscut si, in plus, se cunosc toţi succesorii lui

10.04.2011 81


Expandarea unui nod înseamnă generarea tuturor succesorilor săi, adică aplicarea tuturor operatorilor legali stării curente Sc aferentă nodului.

În procesul de căutare se vor folosi doua liste:

LF – lista frontieră care conţine nodurile evaluate, adică frontiera spaţiului de căutare parcurs (explicitat) spre partea necunoscută a acestuia;

LT – lista teritoriu care conţine nodurilor expandate, adică partea cunoscută a spaţiului de căutare.

10.04.2011 82


STRATEGII DE CĂUTARE DE BAZĂcăutare pe nivel şi căutarea în adâncime

Ipoteze:Spaţiul de căutare este arbore, adică între starea iniţială şi cea finală există o cale unică. Rezultă că toate stările generate pe parcursul căutării sunt unice, adică nu au mai fost generate anterior.

La fiecare expandare a unui nod se stabileşte o legătură de la fiecare nod succesor la nodul expandat. In momentul descoperirii nodului stare finală aceste legaturi permit reconstruirea caii spre soluţie.

10.04.2011 83


Definiţie: într-o reprezentare a soluţiei problemei prin spaţiul stărilor adâncimea unui nod se defineşte astfel:

în care Sp este predecesorul stării curente Sc.

Ad( )=0iS unde Si este nodul stare iniţială;

Ad( )=Ad( )+1c pS S

10.04.2011 84


Căutarea pe nivel sau în lăţime

este o strategie de căutare care expandează stările următoare în ordinea apropierii faţă de nodul stare iniţială Si.

tratează lista frontieră LF folosind o strategie de tipul FIFO (First In First Out).

Nodul din frontieră care se elimină este primul din listă, iar succesorii săi sunt adăugaţi la sfârşitul listei.

10.04.2011 85


Algoritmul strategiei căutării pe nivel în spaţiul stărilor

1. Creează listele LF ←{Si} si LT ←{}2. DACĂ LF ={} ATUNCI întoarce INSUCCES /* nu există soluţie */3. Elimină primul nod Sc din LF si-l inserează în LT4. Expandează nodul Sc

4.1. Generează toţi succesorii direcţi ai nodului Sc

4.2. Pentru fiecare succesor Sj ( 1 ≤ j ≤ m ) al lui Sc execută4.2.1. Stabileşte legătura Sj ← Sc 4.2.2. DACĂ Sj este stare finală ATUNCI:

i. soluţia este {Sj≡ Sf , Sc … Sj,}ii. întoarce SUCCES /* s-a găsit o soluţie */

4.2.3. Insereaza Sj în LF, la sfârşit5. repeta de la 2

10.04.2011 86


Exempluse consideră graful din figură în care nodul n1 reprezintă starea iniţială, iar nodul n10 starea finală.ordinea în care se explorează diversele căi în graful de căutare depinde de ordinea în care se generează şi se inserează în LF succesorii nodului expandat . În cele ce urmează considerăm că succesorii unui nod se generează în ordinea indicelui numeric.

n1

n2

n4

n8 n9 n10

n5 n6 n7

n3

10.04.2011 87


Pas 1. Iniţializări LF ←{n1} si LT ←{} Pas 2 . Elimină n1 din LF şi-l inserează în LT:

LF ={} si LT={n1} Pas 3. Generează succesorii lui n1 si-i inserează în LF:

LF ={n2 , n3} si LT={n1}Pas 4. Elimină n2 din LF şi-l inserează în LT:

LF ={n3} si LT={n1 , n2}Pas 5. Generează succesorii lui n2 si-i inserează în LF la sfârşit:

LF ={n3 , n4 , n5} si LT={n1 , n2}Pas 6. Elimină n3 din LF şi-l inserează în LT:

LF ={n4 , n5} si LT={n1 , n2 ,n3}Pas 7. Generează succesorii lui n3 si-i inserează în LF la sfârşit:

LF ={n4 , n5 , n6 , n7} si LT={n1 , n2 ,n3}

10.04.2011 88


Pas 8. Elimină n4 din LF şi-l inserează în LT:LF ={n5 , n6 , n7} si LT={n1 , n2 , n3 , n4}Obs. Deoarece n4 nu are succesori, nu se adaugă alte noduri în lista LF.

Pas 9. Elimină n5 din LF şi-l inserează în LT:LF ={n6 , n7} si LT={n1 , n2 , n3 , n4 , n5}

Pas 10. Generează succesorii lui n5 şi-i inserează în LF la sfârşit: LF ={n6 , n7 , n8 , n9} si LT={n1 , n2 , n3 , n4 , n5}

Pas 11. Elimină n6 din LF şi-l inserează în LT: LF ={n7 , n8 , n9} si LT={n1 , n2 , n3 , n4 , n5 , n6}

Obs. Deoarece n6 nu are succesori, LF nu se modifică. Pas 12. Elimină n7 din LF şi-l inserează în LT:

LF ={n8 , n9} si LT={n1 , n2 , n3 , n4 , n5 , n6 , n7}Pas 13. Generează succesorii lui n7 şi-i inserează în LF la sfârşit:

LF ={n8 , n9 , n10} si LT={n1 , n2 , n3 , n4 , n5 , n6 , n7}

10.04.2011 89


Deoarece nodul final n10 a apărut în frontieră, se consideră procesul de căutare încheiat şi se specifică soluţia: {n10 , n7 , n3 , n1}

Observaţii:

Căutarea poate fi uneori lungă şi complex computaţională din punct de vedere al spaţiului de memorie utilizat deoarece pentru fiecare nivel sunt generate toate stările succesoare posibile.

Cu toate acestea, strategia de căutare pe nivel garantează găsirea soluţiei, în cazul în care aceasta există şi, în plus, găseşte cel mai scurt drum spre soluţie în termenii numărului de tranziţii de stări executate.

10.04.2011 90


Căutarea în adâncimeeste strategia cea mai frecvent utilizată în aplicaţiile practice;

expandează stările cel mai recent generate, adică nodurile din lista LF cu adâncimea cea mai mare;

această strategie parcurge o cale de la starea iniţială până la o stare ce poate fi starea finală sau care nu mai are nici un succesor. În acest ultim caz se aplică mecanismul backtracking revenindu-se pe nivelurile anterioare şi se încearcă explorarea altor căi posibile.

lista frontieră LF este tratată ca o stivă folosind o tehnică de tipul LIFO (Last In First Out).

10.04.2011 91


Observaţii:Strategia căutării în adâncime nu garantează obţinerea unei soluţii a problemei, chiar în cazul în care aceasta există.

O astfel de situaţie poate să apară în cazul unui spaţiu de căutare infinit iar ramura pe care s-a plecat în căutare nu conţine soluţia.

Pentru a evita intrarea într-o buclă infinită se introduce o limită maximă a adâncimii de căutare, AdMax. Dacă această limită a fost atinsă fără a se găsi soluţia, atunci strategia revine si inspectează stări de pe nivelurile inferioare lui AdMax dar aflate pe căi diferite.

Apare următorul dezavantaj: soluţia care s-ar găsi pe calea iniţială la o adâncime mai mare decât AdMax este pierdută.

Algoritmul căutării în adâncime prezintă avantajul generării unui număr de stări mai mic comparativ cu algoritmul căutării pe nivel.

10.04.2011 92


Algoritmul strategiei căutării în adâncime în spaţiul stărilor

1. Creează listele LF ←{Si} si LT ←{}2. DACĂ LF ={} ATUNCI întoarce INSUCCES /* nu există soluţie */3. Elimină primul nod Sc din LF si-l inserează în LT DACĂ Ad (Sc)=AdMax ATUNCI repetă de la 24. Expandează nodul Sc

4.1. Generează toţi succesorii direcţi ai nodului Sc

4.2. Pentru fiecare succesor Sj ( 1 ≤ j ≤ m ) al lui Sc execută4.2.1. Stabileşte legătura Sj ← Sc 4.2.2. DACĂ Sj este stare finală ATUNCI:

i. soluţia este {Sj≡ Sf , Sc … Sj,}ii. întoarce SUCCES /* s-a găsit o soluţie */

4.2.3. Insereaza Sj în LF, la început5. repeta de la 2

10.04.2011 93


Exempluse consideră graful din figură în care nodul n1 reprezintă starea iniţială, iar nodul n10 starea finală.ordinea în care se explorează diversele căi în graful de căutare depinde de ordinea în care se generează şi se inserează în LF succesorii nodului expandat . În cele ce urmează considerăm că succesorii unui nod se generează în ordinea indicelui numeric.

n1

n2

n4

n8 n9 n10

n5 n6 n7

n3

10.04.2011 94


Pas 1. Iniţializări LF ←{n1} si LT ←{} Pas 2 . Elimină n1 din LF şi-l inserează în LT:

LF ={} si LT={n1} Pas 3. Generează succesorii lui n1 si-i inserează în LF: conform convenţiei

adoptate se generează şi se introduce în listă n2 şi apoi n3: rezultă LF ={n3, n2} si LT={n1}

Pas 4. Elimină n3 din LF şi-l inserează în LT:LF ={n2} si LT={n1 , n3}

Pas 5. Generează succesorii lui n3 si-i inserează în LF la început:LF ={n7 , n6 , n2} si LT={n1 , n3}

Pas 6. Elimină n7 din LF şi-l inserează în LT:LF ={n6 , n2} si LT={n1 ,n3 , n7}

Pas 7. Generează succesorii lui n7 si-i inserează în LF la început: LF ={n10 , n6 , n2} si LT={n1 , n3 , n7 }

Deoarece nodul final n10 a apărut în frontieră, se consideră procesul de căutare încheiat şi se specifică soluţia: {n10 , n7 , n3 , n1}

10.04.2011 95


Algoritmul de căutare în adâncime cu nivel iterativ ( algoritmul lui Korf ).

elimină dezavantajele specifice celor două strategii de căutare de bază; algoritmul realizează la început o căutare în adâncime în spaţiul stărilor cu o adâncime maximă de căutare AdMax specificată. DACĂ starea finală nu a fost găsită, ATUNCI se reia căutarea în adâncime cu AdMax+1;continuă procesul până se găseşte solţia;la fiecare iteraţie algoritmul realizează o căutare în adâncime completă corespunzătoare valorii curente AdMax. între două iteraţii succesive nu se reţine nici o informaţie despre spaţiul de căutare. se garantează găsirea soluţiei, dacă aceasta există, precum şi a drumului cel mai scurt către soluţie

10.04.2011 96


În cazul în care spaţiul de căutare nu este un arbore, ci un graf oarecare, pentru a evita reconsiderarea unei stări analizate anterior, pasul de inserare a stării Sj în lista LF (pasul 4.2.3) se modifică astfel:

4.2.3‘ DACĂ ATUNCI inserează Sj în LF, la sfirsit respectiv la

început în funcţie de strategie.

jS LF LT∉ ∪

10.04.2011 97


Observaţii:Ambele tipuri de căutări realizează un raţionament direct, pornind în rezolvarea problemei de la starea iniţială si generând arborele de căutare a stării finale. Acest mod de abordare corespunde raţionamentului deductiv.Pentru rezolvarea anumitor probleme se poate proceda invers, executând strategiile începând din starea finală şi căutând starea iniţială. Acest mod de abordare corespunde raţionamentului inductiv.În anumite cazuri se poate utiliza o combinaţie între raţionamentul direct si cel invers, adică un raţionament bidirecţional în care se caută soluţia pornind simultan din starea iniţială si cea finală. În cazul acestei strategii, dacă se utilizează căutarea în adâncime există pericolul ca cei doi arbori generaţi simultan, unul pe calea directă şi celălalt pe calea inversă, să nu aibă noduri intermediare comune (să nu se întâlnească).

10.04.2011 98


Strategiile de căutare pe nivel si în adâncime pot fi uşor adaptate la căutarea soluţiei problemei în reprezentarea prin grafuri SI/SAU.

Diferenţa constă în criteriul de determinare a condiţiei de oprire. De această dată trebuie să se testeze dacă o mulţime de noduri formează un arbore SI/SAU soluţie. Impactul fiecărui nod nou generat trebuie propagat în arborele parţial construit pentru a determina dacă nodul problemă iniţială a devenit rezolvat.Algoritmele de căutare în grafuri SI/SAU trebuie să gestioneze, pe lângă

listele LF si LT, şi o structură de date care reprezintă arborele SI/SAU construit prin explicitatea spaţiului de căutare definit în mod implicit de reprezentare. O altă diferenţă constă în faptul că nodurile SI nu se introduc în listele LF şi LT deoarece ele nu corespund efectiv unor subprobleme, ci indică numai o mulţime de subprobleme care trebuie rezolvate. Aceste noduri sunt însă construite şi fac parte din porţiunea explicitată a spaţiului de căutare. Pe baza stării de rezolvat sau nerezolvabil a acestor noduri se poate decide când s-a obţinut arborele soluţie.

10.04.2011 99


Strategii de căutare euristică

Rezolvarea problemelor utilizând strategii de căutare neinformată prezintă dezavantajul că numărul de stări investigate pentru a găsi o soluţie poate ajunge prohibitiv de mare, chiar si pentru probleme relativ simple.

Necesitatea aplicării tehnicilor euristice de căutare.Acestea ţin seama de cât de aproape este fiecare nod al grafului de nodul corespunzător stării finale.

10.04.2011 100


Observaţie: cuvântul euristic(ă) provine din greaca veche şi are înţelesul “a descoperi”. Conform DEX “un procedeu euristic serveşte la descoperirea unor cunoştinţe noi”, respectiv defineşte o parte a ştiinţei care are ca obiect descoperirea de fapte noi.

În contextul problemelor de căutare, o tehnică euristică este o strategie folosită pentru a creşte eficienţa căutării, fără a garanta obţinerea soluţiei. Dezvoltarea unei tehnici euristice se face pe baza unor

aproximări raţionale;ipoteze simplificatoare;cunoştinţe specifice domeniului problemei.

10.04.2011 101


În acest context, cunoştinţele euristice pot fi utilizate pentru:

selectarea nodului următor de expandat în cursul căutării –selectarea nodului cel mai promiţător pentru obţinerea soluţiei;a decide care dintre succesorii nodului ce este expandat vor fi generaţi şi care nu – expandarea parţială a unui nod prin aplicarea numai a unui sbset de operatori dintre cei posibil de aplicat;eliminarea din spaţiul de căutare a anumitor noduri generate – retezarea arborelui de căutare

10.04.2011 102


Deşi o mare parte dintre tehnicile euristice cunoscute sunt tehnici cu aplicabilitate generală totuşi, pentru aplicarea lor cu succes la o problemă particulară, ele trebuie suprapuse peste euristica specifică problemei analizate.În acest sens, se defineşte o funcţie euristică care exprimă – cel mai adesea în formă numerică – cât de promiţătoare este o stare din spaţiul de căutare în procesul de identificare a soluţiei, adică cât de apropiată este starea respectivă de stare finală.

10.04.2011 103


Definirea unei funcţii euristice f implică utilizarea:

unei funcţii g evaluează costul deplasării din starea iniţială Si în starea curentă Sc;unei funcţii h estimează costul deplasării din starea curentă Sc în starea finală Sf;

Sf

Si

Sc

g( )Sc

h( )Sc

f( )Sc

10.04.2011 104


Observaţii :Dintre cele trei funcţii doar g poate fi evaluată precis, celelalte două fiind doar estimate şi de aceea se notează f* şih* , iar legătura dintre ele este dată de relaţia

O particularitate proprie tehnicilor euristice de căutare o reprezintă caracterul local al procesului decizional care determină o comportare nemonotonă a funcţiei h în spaţiul stărilor.

* *( ) ( ) ( )i f i c c ff S S g S S h S S→ = → + →

10.04.2011 105


Metoda căii spre obiectivPrincipiul metodei constă în alegerea acelor operatori care par să conducă la un obiectiv: soluţia problemei. La fiecare pas al procesului de căutare se evaluează diferenţele dintre starea curentă Sc şi starea finală Sf pe baza cărora se identifică un operator O1 ce ar permite trecerea directă din starea curentă în cea finală. Din păcate un astfel de operator fie nu există, fie nu poate fi aplicat. Se aplică principiul descompunerii problemei în subprobleme astfel:

se determină o stare intermediară S’c căreia i se poate aplica

operatorul identificat anterior şi în care se poate ajunge din starea curentă Sc prin aplicarea unui operator secundar .

10.04.2011 106


Metoda pasului optim (best – first)Strategia selectează pentru expandare cel mai bun nod din spaţiul de căutare generat folosind cunoştinţele euristice, adică o estimare a stării cu ajutorul unei funcţii euristice. Algoritmul de bază al metodei implică parcurgerea următoarelor etape:1. Calculul funcţiei euristice pentru toate nodurile din

nivelul curent (nodurile din frontieră)2. Selectarea nodului cu valoarea minimă/maximă a

funcţiei euristice3. Expandarea nodului selectat (generarea succesorilor

săi). Dacă unul dintre succesori este soluţia, atunci procesul de căutare se opreşte.

10.04.2011 107


Algoritmele A* şi AO*Folosesc pentru a evalua fiecare nod al frontierei o funcţie cost globală de tipul :

Caută o soluţie optimă a problemei. Algoritmul A* este specific reprezentării prin spaţiul stărilor, Algoritmul AO* este specific reprezentării prin grafuri SI/SAU.

* *( ) ( ) ( )i f i c c ff S S g S S h S S→ = → + →

10.04.2011 108


R1: DACĂ B ŞI D ŞI E → FR2: DACĂ D ŞI G → AR3: DACĂ C ŞI F → AR4: DACĂ B → XR5: DACĂ D → ER6: DACĂ A ŞI X → HR7: DACĂ C → DR8: DACĂ X ŞI C → AR9: DACĂ X ŞI B → D

B C

X

, , B C

X D

, ,

,

B C

X D

E

, ,

, ,

B C

X D

E F

, ,

, ,

,

B C

X D

E F

A

, ,

, ,

, ,

R7R8

R9

R5R8

R9

R1

R8R9

R3

R8R9

R6

R8R9

HR4R7

B C,

B C

X

, , B C

X A

, ,

, R7

R8

R9

R6R7

R9

R4R7B C,

H

H R6

R4

A

X B

G

DR2

C

F

R3 B

D

E

R7

R9

C

R5 DC

R8

verificatverificat

verificat

verificat

verificat

neverificat

inutil deoarece nu a fost verificat G

a

b

c

R7

R9

R1ŞI

ŞI

ŞI

ªI

SAU

SAU

ŞIambele subscopuritrebuie verificate

SAUuna sau alta dintrereguli poate fi aplicată

10.04.2011 109


MULŢUMESC PENTRU ATENŢIE !Urmează RNA !?!?

Date post:	05-Dec-2015
Category:	Documents
Upload:	marius-ibrean
View:	253 times
Download:	2 times

Prezentare Capitolul 1 Sisteme Expert

Documents