prezentare ai cursuri 1-8
DESCRIPTION
Inteligenta artificialaTRANSCRIPT
Outline Inteligenta Computationala si Cunoasterea Rezolvarea de probleme Obiecte si termeni in Prolog Algoritmi de cautare
Cuprins I
1 Inteligenta Computationala si CunoastereaCe este Inteligenta Artificiala?Agentii si mediul inconjuratorReprezentare si rationamentAplicatii
2 Rezolvarea de problemeTehnici fuzzyRezolvarea problemeiFormularea problemeiProbleme si solutii bine definiteMasurarea performantei in rezolvarea problemelorAlgoritmi de cautare
3 Obiecte si termeni in PrologUnificarea(Matching)Liste
Inteligenta Artificiala 2/58
Outline Inteligenta Computationala si Cunoasterea Rezolvarea de probleme Obiecte si termeni in Prolog Algoritmi de cautare
Cuprins II
4 Algoritmi de cautareCautarea neinformata
Breadth-firstDepth-firstIterative deepeningCautarea bidirectionala
Cautarea informataBest-firstAlgoritmul A*Algoritmul IDA*Concluzii finale
Inteligenta Artificiala 3/58
Outline Inteligenta Computationala si Cunoasterea Rezolvarea de probleme Obiecte si termeni in Prolog Algoritmi de cautare
Cuprins
1 Inteligenta Computationala si CunoastereaCe este Inteligenta Artificiala?Agentii si mediul inconjuratorReprezentare si rationamentAplicatii
2 Rezolvarea de problemeTehnici fuzzyRezolvarea problemeiFormularea problemeiProbleme si solutii bine definiteMasurarea performantei in rezolvarea problemelorAlgoritmi de cautare
3 Obiecte si termeni in PrologUnificarea(Matching)Liste
4 Algoritmi de cautareCautarea neinformata
Breadth-firstDepth-firstIterative deepeningCautarea bidirectionala
Cautarea informataBest-firstAlgoritmul A*Algoritmul IDA*Concluzii finale
Inteligenta Artificiala 4/58
Outline Inteligenta Computationala si Cunoasterea Rezolvarea de probleme Obiecte si termeni in Prolog Algoritmi de cautare
Ce este Inteligenta Artificiala?
Studiul designului agent, ilor inteligent, i (progamelor).Agent - ceva ce act, ioneaza ın interiorul unui mediu (viermi, caini,avioane, oameni, organizat, ii, societatea).Agent Inteligent - sistem ce act, ioneaza inteligent:
ceea ce face este corespunzator propriilor scopuri
e flexibil la modificarile mediului ınconjurator s, i al scopurilor
ınvat, a din experient, a
face alegerile potrivite t, inand cont de limitarile perceptuale s, icomputat, iile finite
Inteligenta Artificiala 5/58
Outline Inteligenta Computationala si Cunoasterea Rezolvarea de probleme Obiecte si termeni in Prolog Algoritmi de cautare
Ce este Inteligenta Artificiala?
Scopul Inteligent,ei Computat, ionale - ınt, elegerea principiilor ce staula baza posibilelor comportamente inteligente ın sistemele naturalesau artificiale.Scopul Ingineresc - specificarea metodelor pentru designulartefactelor utile, inteligente.Artificial Intelligence - numele stabilit pentru domeniul Inteligent,eiComputat, ionale.Scopul Inteligent,ei Artificiale - ınt, elegerea sistemelor inteligentereale (naturale sau sintetice) prin sintetizarea lor.Metodologia - designul, construct, ia s, i experimentul cu sistemelecomputat, ionale ce realizeaza taskuri vazute drept inteligente.Inteligent,a computat, ionala apart, ine s, tiint, elor cognitive pentru caconfera instrumente pentru construct, ia inteligent, ei mai degrabadecat studiul comportamentului agent, ilor inteligent, i.
Inteligenta Artificiala 6/58
Outline Inteligenta Computationala si Cunoasterea Rezolvarea de probleme Obiecte si termeni in Prolog Algoritmi de cautare
Agentii si mediul inconjurator
Agentul cuprinde percept, ia, rat, ionamentul s, i act, iunea.
�����
������������
������������������� ��������
�����������������������������
������������ ���������������
�� �� ��������������������� ���
���������� �����
Inteligenta Artificiala 7/58
Outline Inteligenta Computationala si Cunoasterea Rezolvarea de probleme Obiecte si termeni in Prolog Algoritmi de cautare
Agentii si mediul inconjurator
Pentru fiecare agent se specifica:
forma intrarilor
act, iunile
Lumea - agentul ın mediul ınconjurator (ce poate include s, i alt, iagent, i).Starea interna - codifica convingeri despre mediu s, i sine.Agentul poate avea:
scopuri de atins
modalitat, i de act, iune ın mediul ınconjurator pentru atingereascopurilor
modalitat, i de modificare a convingerilor prin:
rat, ionamentpercept, ieınvat, are
Inteligenta Artificiala 8/58
Outline Inteligenta Computationala si Cunoasterea Rezolvarea de probleme Obiecte si termeni in Prolog Algoritmi de cautare
Agentii si mediul inconjurator
Legatura dintre agent s, i mediu:
�����
����������
�����
����
�������
������
Inteligenta Artificiala 9/58
Outline Inteligenta Computationala si Cunoasterea Rezolvarea de probleme Obiecte si termeni in Prolog Algoritmi de cautare
Reprezentare si rationament
Presupusele probleme raman:
achizit, ionarea s, i reprezentarea cunos, tint, elor
modalitat, i de utilizare a cunos, tint, elor pentru a raspunde laıntrebari s, i a rezolva probleme
Concluzie - vom folosi sisteme de reprezentare s, i rat, ionament(RRS: representation and reasoning systems):
limbaj de comunicare cu calculatorul
modalitatea de a da un ınt, eles (sens) limbajului
proceduri de a calcula raspunsuri pentru inputuri date asociatelimbajului
Limbajul poate fi:
low-level: Fortron, C++ sau Lisp
limbaje naturale: Engleza
Inteligenta Artificiala 10/58
Outline Inteligenta Computationala si Cunoasterea Rezolvarea de probleme Obiecte si termeni in Prolog Algoritmi de cautare
Reprezentare si rationament
Reprezentari:
lumea poate fi descrisa ın termeni de indivizi s, i relat, ia dintreaces, tia (ca ın logica sau ın limbajul natural). Aces, tia pot ficoncret, i sau abstract, i.
pentru fiecare sarcina sau domeniu se identifica indivizispecifici s, i relat, iile ce pot fi folosite pentru a exprima ce esteadevarat ın legatura cu lumea considerata
Cateva atribute asupra mediului ınconjurator pot fi:
ın totalitate
part, ial observabil
Deci starea mediului ınconjurator poate fi:
total observabila
part, ial observabila
Inteligenta Artificiala 11/58
Outline Inteligenta Computationala si Cunoasterea Rezolvarea de probleme Obiecte si termeni in Prolog Algoritmi de cautare
Reprezentare si rationament
Agentul Inteligent poate fi:
deterministic - act, iunile agentului determina unic ies, irea
stocastic - ies, irea (rezultatul) nu este neaparat acelas, i
discret - spat, iul act, iunilor este finit
continuu - spat, iul act, iunilor este infinit
benign
adversarial - mediul ınconjurator reprezentand adversarul
Inteligenta Artificiala 12/58
Outline Inteligenta Computationala si Cunoasterea Rezolvarea de probleme Obiecte si termeni in Prolog Algoritmi de cautare
Aplicatii
Domenii:
robotica
jocuri
finant, e
medicina (diagnosticare)
ınt, elegerea s, i interpretarea webului (Microsoft, Google)
Inteligenta Artificiala 13/58
Outline Inteligenta Computationala si Cunoasterea Rezolvarea de probleme Obiecte si termeni in Prolog Algoritmi de cautare
Aplicatii
La nivelul abstract, exista 4 sarcini:
1 modelarea mediului - robotul trebuie sa poata modelamediul si propriile capacitat, i
2 rat, ionament evident/percept, ie - robotul trebuie sadetermine ce altceva se mai gas, es, te ın mediul ınconjuratorbazandu-se pe informat, iile de simt,
3 act, iunea - fiind dat un model al lumii s, i scopul, sarcina estede a determina ce trebuie facut.
4 ınvat, are din experient, a anterioara - ınvat, area:
a. despre cum este un anumit mediu ınconjuratorb. informat, iilor generale (cum funct, ioneaza de fapt senzorii
robotului)c. de a rezolva problemele mai eficient
Sarcinile interact, ioneaza ıntre ele s, i nu pot fi studiate separat.
Inteligenta Artificiala 14/58
Outline Inteligenta Computationala si Cunoasterea Rezolvarea de probleme Obiecte si termeni in Prolog Algoritmi de cautare
Cuprins
1 Inteligenta Computationala si CunoastereaCe este Inteligenta Artificiala?Agentii si mediul inconjuratorReprezentare si rationamentAplicatii
2 Rezolvarea de problemeTehnici fuzzyRezolvarea problemeiFormularea problemeiProbleme si solutii bine definiteMasurarea performantei in rezolvarea problemelorAlgoritmi de cautare
3 Obiecte si termeni in PrologUnificarea(Matching)Liste
4 Algoritmi de cautareCautarea neinformata
Breadth-firstDepth-firstIterative deepeningCautarea bidirectionala
Cautarea informataBest-firstAlgoritmul A*Algoritmul IDA*Concluzii finale
Inteligenta Artificiala 15/58
Outline Inteligenta Computationala si Cunoasterea Rezolvarea de probleme Obiecte si termeni in Prolog Algoritmi de cautare
Tehnici fuzzy
Programele se numesc agent, i program (funct, ii ce implementeazaun agent).Inteligent,a Artificiala proiecteaza programe agent, i ce realizeazatransformarea de la percept, ia mediului ınconjurator prin senzori laact, iune prin efectori (actuatori).
Agentul act, ioneaza prin stabilirea unor t, eluri/scopuri s, i ia deciziicare sa duca la ındeplinirea acestora.
Scopul s, i mult, imea tuturor modalitat, ilor de atingere ascopului, altcatuiesc problema.
Procesul de explorare a ceea ce pot face aceste modalitat, i senumes, te cautare.
Inteligenta Artificiala 16/58
Outline Inteligenta Computationala si Cunoasterea Rezolvarea de probleme Obiecte si termeni in Prolog Algoritmi de cautare
Rezolvarea problemei
Pas IProcesul de rezolvare a problemei consta ın formularea scopuluibazat pe situat, ia curenta.Scopul ={stari ale universului | acele stari ın care scopul este satisf acut} ={s1, s2...sn}
Act, iunile pot fi privite ca generand tranzit, ii ıntre stari aleuniversului. Agentul va trebui sa afle ce act, iuni ıl conduc la o stareın care scopul este satisfacut.
Procesul deciziei asupra act, iunilor s, i starilor care trebuie luate ınconsiderare reprezinta formulare problemei.
Inteligenta Artificiala 17/58
Outline Inteligenta Computationala si Cunoasterea Rezolvarea de probleme Obiecte si termeni in Prolog Algoritmi de cautare
Rezolvarea problemei
Pas IIUn agent care are la dispozit, ie mai multe opt, iuni imediate, trebuiesa decida ce sa faca examinand diferinte secvent, e de act, iuniposibile, urmand sa o aleaga pe cea mai buna. Procesul deexaminare a unei asemenea succesiuni de act, iuni se numes, tecautare.Un algoritm de cautare
primes, te ca intrare o problema
ıntoarce o solut, ie sub forma unor succesiuni de act, iuni
Pas III - faza de execut, ieAgentul pe care ıl programam realizeaza 3 act, iuni:
formuleaza
cauta
executa
Inteligenta Artificiala 18/58
Outline Inteligenta Computationala si Cunoasterea Rezolvarea de probleme Obiecte si termeni in Prolog Algoritmi de cautare
Formularea problemei
Depinde de tipul de problema care exista:
Problema cu o stare unica
Problema cu stari multiple
Problema de contingent, a
Problema de explorare
Inteligenta Artificiala 19/58
Outline Inteligenta Computationala si Cunoasterea Rezolvarea de probleme Obiecte si termeni in Prolog Algoritmi de cautare
Probleme si solutii bine definite
1. Probleme cu o singura stare
Elementele de baza ale definirii unei probleme sunt starile s, iact, iunile.
Din punct de vedere formal, pentru a le defini e nevoie de:
starea init, iala ın care agentul s, tie ca se afla
mult, imea act, iunilor posibile, disponibile agentului
O problema se defines, te prin:
starea init, iala
mult, imea operatorilor
testul scop
funct, ia de cost a unui drum
Inteligenta Artificiala 20/58
Outline Inteligenta Computationala si Cunoasterea Rezolvarea de probleme Obiecte si termeni in Prolog Algoritmi de cautare
Probleme si solutii bine definite
2. Probleme cu stari multiple cont, in:
o mult, ime de stari init, iale
o mult, ime de operatori specificand ın cazul fiecarei act, iunimult, imea de stari ın care se ajunge plecand din orice stare data
un test scop
funct, ia de cost a unui drum
Un operator se aplica unei mult, imi de stari prin reunirearezultatelor aplicarii operatorului fiecarei stari din mult, ime.
Un drum leaga mult, imi de stari, iar o solut, ie este un drum careconduce la o mult, ime de stari tip scop.
Spat, iul de stari, aici, este ınlocuit de spat, iul mult, imii de stari.
Inteligenta Artificiala 21/58
Outline Inteligenta Computationala si Cunoasterea Rezolvarea de probleme Obiecte si termeni in Prolog Algoritmi de cautare
Masurarea performantei in rezolvarea problemelor
Eficacitatea unei cautari poate fi masurata:
daca se gases, te o solut, ie
daca s-a gasit o solut, ie buna (cu un cost scazut al drumului)
prin pret, ul cautarii asociat timpului calculator s, i al memorieinecesare pentru gasirea de solut, ii
Inteligenta Artificiala 22/58
Outline Inteligenta Computationala si Cunoasterea Rezolvarea de probleme Obiecte si termeni in Prolog Algoritmi de cautare
Masurarea performantei in rezolvarea problemelor
Costul total al cautarii este format din ınsumarea costului drumuluis, i cel al cautarii.
Aplicarea unui operator asupra unei stari curente, generand omult, ime de stari se numes, te extinderea starii.
Strategia de cautare determina alegerea referitoare la starea la caretrebuie extinsa prima.
O stare reprezinta o configurat, ie a lumii ınconjuratoare.
Un nod este o structura de date.
Se numes, te frontiera colect, ia de noduri care as, teapta sa fie extinse.
Inteligenta Artificiala 23/58
Outline Inteligenta Computationala si Cunoasterea Rezolvarea de probleme Obiecte si termeni in Prolog Algoritmi de cautare
Masurarea performantei in rezolvarea problemelor
Urmatorul nod din frontiera care trebuie extins este selectat decatre strategia de cautare, care se evalueaza dupa urmatoarelepatru criterii:
completitudine
complexitatea timpului
complexitatea spat, iului
optimalitate
Inteligenta Artificiala 24/58
Outline Inteligenta Computationala si Cunoasterea Rezolvarea de probleme Obiecte si termeni in Prolog Algoritmi de cautare
Masurarea performantei in rezolvarea problemelor
Tehnicile pentru rezolvarea de probleme funct, ioneaza candurmatoarele condit, ii sunt adevarate:
domeniul este ın totalitate observabil
domeniul este ın totalitate cunoscut
domeniul este ın totalitate discret
domeniul este ın totalitate determinist
domeniul este ın totalitate static
Inteligenta Artificiala 25/58
Outline Inteligenta Computationala si Cunoasterea Rezolvarea de probleme Obiecte si termeni in Prolog Algoritmi de cautare
Algoritmi de cautare
I. Cautarea neinformata (cautarea oarba - blind search)
Breadth-first (cautarea ın lat, ime)
Depth-first (cautarea ın adancime)
Iterative deepening (cautarea iterativa)
Cautarea bidirect, ionala
II. Cautarea informata (euristica - descoperiri de fapte noi pecare le valorificam din mers)
Best-first
Algoritmul A∗
Algoritmul IDA∗ (iterative deepening A∗)
III. Jocurile ca problema de cautare - de 2 persoane
Algoritmul Minmax
Algoritmul Alpha-Beta
Inteligenta Artificiala 26/58
Outline Inteligenta Computationala si Cunoasterea Rezolvarea de probleme Obiecte si termeni in Prolog Algoritmi de cautare
Cuprins
1 Inteligenta Computationala si CunoastereaCe este Inteligenta Artificiala?Agentii si mediul inconjuratorReprezentare si rationamentAplicatii
2 Rezolvarea de problemeTehnici fuzzyRezolvarea problemeiFormularea problemeiProbleme si solutii bine definiteMasurarea performantei in rezolvarea problemelorAlgoritmi de cautare
3 Obiecte si termeni in PrologUnificarea(Matching)Liste
4 Algoritmi de cautareCautarea neinformata
Breadth-firstDepth-firstIterative deepeningCautarea bidirectionala
Cautarea informataBest-firstAlgoritmul A*Algoritmul IDA*Concluzii finale
Inteligenta Artificiala 27/58
Outline Inteligenta Computationala si Cunoasterea Rezolvarea de probleme Obiecte si termeni in Prolog Algoritmi de cautare
Obiecte si termeni in Prolog
Exista trei tipuri de clauze:
faptele
regulile
ıntrebarile
Obiectele sunt:
simpleconstante
numereatomi
variabile
structuri
Inteligenta Artificiala 28/58
Outline Inteligenta Computationala si Cunoasterea Rezolvarea de probleme Obiecte si termeni in Prolog Algoritmi de cautare
Obiecte si termeni in Prolog
O structura este o colect, ie de date sau obiecte, grupate ıntr-unsingur obiect s, i se defines, te cu ajutorul unui functor (Numefunctor(Argument1,Argument2...Argumentn) ). Se numes, tefunctor principal ıntregul functor.
Exemplu: data(22,martie,2012)
����
�� ������ ��
Figura : Arborele asociat structurii ”data”
O structura e bine definita de functorul principal s, i aritate(numarul de argumente).Inteligenta Artificiala 29/58
Outline Inteligenta Computationala si Cunoasterea Rezolvarea de probleme Obiecte si termeni in Prolog Algoritmi de cautare
Unificarea(Matching)
O mult, ime Θ care are urmatoarea forma:Θ = {(Xi ,Ti )i=1,n | Xi variabil , Ti termen, ∀ i 6= j ,Xi 6= Xj} senumes, te substitut, ie.Daca T este termen Prolog s, i Θ o substitut, ie, atunci vom nota cuT Θ ınlocuirea simultana a tuturor variabilelor Xi cu Ti .De exemplu:T = f (X , g(a,Y ), h(X ,Y ,Z ))Θ = {(X , g(Z , c), (Y ,P(x)), (Z , c ′)}T Θ = f (g(Z , c), g(a,P(x)), h(g(Z , c)),P(x), c ′)
Inteligenta Artificiala 30/58
Outline Inteligenta Computationala si Cunoasterea Rezolvarea de probleme Obiecte si termeni in Prolog Algoritmi de cautare
Unificarea(Matching)
Definitii:
un termen T se numes, te complet instant, iat daca nu cont, inevariabile.
T1 reprezinta instant, ierea lui T2 daca ∃ Θ o substitut, ie astfelıncat T1 = T2Θ
un termen T1 unifica cu un T2 daca ∃ Θ o substitut, ie astfelıncat T1Θ = T2Θ⇒ Θ se numes, te unificator
Reguli de unificare:
doi atomi unifica daca sunt identici
o variabila unifica cu orice
doua structuri unifica daca au acelas, i functor principal s, iaceeas, i aritate (f (1, 2, x) 6= f (1, 2, 3, 4) pentru ca nu auaceeas, i aritate)
Inteligenta Artificiala 31/58
Outline Inteligenta Computationala si Cunoasterea Rezolvarea de probleme Obiecte si termeni in Prolog Algoritmi de cautare
Unificarea(Matching)
Exemple:
T1 = f (X , a) s, i T2 = f (b,Y ), daca ∃Θ astfel ıncatT1Θ = T2Θ, atunci Θ = {(X , b), (Y , a)} s, iT1Θ = f (b, a) = T2Θ
T1 = X T2 = g(f (Y ,Z ), a)Θ = {X , g(f (Y ,Z ), a)}Θ = {(Y , b), (Z , c), (X , g(f (Y ,Z ), a))}In Prolog predicatul ”=” ne spune daca cei doi termeniunifica, atunci programul ıntoarce substitut, ia generala.
?− x = f (x)T1 = x , T2 = f (x)Θ = {(x , f (x))}T1Θ = f (x)T2Θ = f (f (x))
Inteligenta Artificiala 32/58
Outline Inteligenta Computationala si Cunoasterea Rezolvarea de probleme Obiecte si termeni in Prolog Algoritmi de cautare
Liste
O lista este o secvent, a de oricate obiecte ([Ion,Ana,Maria,Elena]).Exista doua tipuri de liste:
lista vida ([])
lista nevida ([H|T ] - unde H - head s, i T - tail)
Inteligenta Artificiala 33/58
Outline Inteligenta Computationala si Cunoasterea Rezolvarea de probleme Obiecte si termeni in Prolog Algoritmi de cautare
Liste
[1, 2, 3] = [1|[2, 3]] = [1, 2|[3]] = [1, 2, 3|[]][H|T ]⇔ •(H,T )
[1, 2, 3] = •(1, •(2, •(3, [])))
baiat(adrian, 20)baiat(gabi , 25)baiat(dragos, 30)baiat(adrian, 15)membru(X , L) - true daca X ∈ L; false daca X /∈ L
Inteligenta Artificiala 34/58
Outline Inteligenta Computationala si Cunoasterea Rezolvarea de probleme Obiecte si termeni in Prolog Algoritmi de cautare
Liste
In lucrul cu listele ∃ trei predicate:
bagof (X ,P, L)Comanda ?− bagof (X , baiat(X , 20), L). va afis, a:L = [adrian].Comanda ?− bagof (X , baiat(X ,Y ), L). va afis, a:Y = 20, L = [adrian];Y = 25, L = [gabi ];Comanda ?− bagof (X ,Y ˆbaiat(X ,Y ), L). va afis, a:L = [adrian, gabi , dragos, adrian];
setof (X ,P, L)Comanda ?− setof (X ,Y ˆbaiat(X ,Y ), L) va afis, a:L = [adrian, dragos, gabi ]
findall(X ,P, L).Comanda findall(X , baiat(X , 35), L) va afis, a: L = []
Inteligenta Artificiala 35/58
Outline Inteligenta Computationala si Cunoasterea Rezolvarea de probleme Obiecte si termeni in Prolog Algoritmi de cautare
Cuprins
1 Inteligenta Computationala si CunoastereaCe este Inteligenta Artificiala?Agentii si mediul inconjuratorReprezentare si rationamentAplicatii
2 Rezolvarea de problemeTehnici fuzzyRezolvarea problemeiFormularea problemeiProbleme si solutii bine definiteMasurarea performantei in rezolvarea problemelorAlgoritmi de cautare
3 Obiecte si termeni in PrologUnificarea(Matching)Liste
4 Algoritmi de cautareCautarea neinformata
Breadth-firstDepth-firstIterative deepeningCautarea bidirectionala
Cautarea informataBest-firstAlgoritmul A*Algoritmul IDA*Concluzii finale
Inteligenta Artificiala 36/58
Outline Inteligenta Computationala si Cunoasterea Rezolvarea de probleme Obiecte si termeni in Prolog Algoritmi de cautare
Cautarea neinformata
(cautarea oarba - blind search)
Strategiile nu det, in nicio informat, ie despre numarul de pas, isau despre costul drumului de la starea curenta la starea scop.
Tot ceea ce agentul poate face este sa distinga o stare scop deo stare care nu este scop.
Inteligenta Artificiala 37/58
Outline Inteligenta Computationala si Cunoasterea Rezolvarea de probleme Obiecte si termeni in Prolog Algoritmi de cautare
Breadth-first: Metodologie
se extinde ıntai nodul radacina, apoi toate nodurile generatede acesta, apoi succesorii lor, etc.
vom folosi o structura de date de tip coada care plaseazastarile nou generate la sfars, itul cozii, dupa starile generateanterior
daca exista o solut, ie, aceasta strategie o va gasi
daca exista mai multe solut, ii, se va gasi mai ıntai nodul scopcel mai put, in adanc
cautarea este completa s, i optima cu condit, ia ca costuldrumurilor sa fie funct, ie descrescatoare de adancimea nodului.
Inteligenta Artificiala 38/58
Outline Inteligenta Computationala si Cunoasterea Rezolvarea de probleme Obiecte si termeni in Prolog Algoritmi de cautare
Breadth-first: Algoritm
Pas 1: creaza o variabila numita ListaNoduri s, i se seteaza lastarea init, iala
Pas 2: pana la gasirea unei solut, ii (stare scop) sau pana candListaNoduri devine vida, executa:
Pas 2.1: ınlatura primul element din ListaNoduri ; ıl numim E .Daca ListaNoduri e vida, atunci STOPPas 2.2: pentru fiecare nod ın care fiecare regula se potrives, tecu starea descrisa ın E , executa:
Pas 2.2.1: aplica regula pentru a genera o noua starePas 2.2.2: daca noua stare e o stare scop, atunci ıntoarceaceeas, i stare s, i STOPPas 2.2.3: altfel, adauga noua stare la sfars, itul lui ListaNoduri
Inteligenta Artificiala 39/58
Outline Inteligenta Computationala si Cunoasterea Rezolvarea de probleme Obiecte si termeni in Prolog Algoritmi de cautare
Breadth-first: Exemplu
Example
Consideram f s, i j nodurile scop. Ordinea parcurgerii: a, b, c , d , e, f
Pas 1: [[a]] - plecam de la radacina
Pas 2: se genereaza extensii ale lui a: [[b, a], [c , a]]
Pas 3: se ınlatura [b, a] s, i se genereaza extensiile sale:[[c , a], [d , b, a], [e, b, a]]
Pas 4: [[d , b, a], [e, b, a], [f , c , a], [g , c , a]]
La pas, ii urmatori mult, imea de candidat, i devine:[[f , c , a], [g , c , a], [h, c , b, a], [i , e, b, a], [j , e, b, a]].Algoritmul scoate ca solut, ie drumul [f , c , a] ce cont, ine nodul scopf .
Inteligenta Artificiala 40/58
Outline Inteligenta Computationala si Cunoasterea Rezolvarea de probleme Obiecte si termeni in Prolog Algoritmi de cautare
Breadth-first: Complexitate
complexitate exponentiala a timpului
complexitate exponentiala a spatiului
Inteligenta Artificiala 41/58
Outline Inteligenta Computationala si Cunoasterea Rezolvarea de probleme Obiecte si termeni in Prolog Algoritmi de cautare
Depth-first: Metodologie
ıntotdeauna se extinde unul din nodurile aflate la nivelul celmai adanc ın arbore.
implementarea se face cu o structura de date de tip coada ceplaseaza starile nou generate ın fat, a cozii
necesitat, ile de memorie sunt foarte mici
strategia nu este nici completa, nici optimala s, i trebuie evitataın cazul arborilor de cautare de adancimi foarte mari
Inteligenta Artificiala 42/58
Outline Inteligenta Computationala si Cunoasterea Rezolvarea de probleme Obiecte si termeni in Prolog Algoritmi de cautare
Depth-first: Algoritm
1 declaram fapte de tipul scop(j) = true. Apelamrezolva(N, [N]) : −scop(N).
2 rezolva(N, [N|Sol1]) : −s(N,N1), rezolva(N1, Sol1), unde sreprezinta predicatul ce defines, te succesorii
3 apeleaza ?− rezolva(a, Sol)
Pentru ımbunatat, irea programului trebuie inserat un mecanism dedetectare a ciclurilor.
Inteligenta Artificiala 43/58
Outline Inteligenta Computationala si Cunoasterea Rezolvarea de probleme Obiecte si termeni in Prolog Algoritmi de cautare
Iterative deepening
strategia evita problema stabilirii unei adancimi optime la caretrebuie cautata solut, ia prin testarea tuturor limitelor deadancime posibile
combina beneficiile de la Breadth-First s, i Depth-First:
din BF este optima s, i completadin DF consuma doar o cantitate mica de memorie, cerint, a dememorie fiind liniara
ordinea extinderii starilor e similara cu cea de la BF, doar caanumite stari sunt extinse de mai multe ori, numarul findechivalent cu cel din BF
garanteaza gasirea nodului scop de la adancimea minima,daca scopul poate fi gasit
Inteligenta Artificiala 44/58
Outline Inteligenta Computationala si Cunoasterea Rezolvarea de probleme Obiecte si termeni in Prolog Algoritmi de cautare
Iterative deepening: Implementare in Prolog
Procedura: path(Nod1,Nod2,Drum), unde variabila Drumsemnifica un drum aciclic ıntre Nod1 s, i Nod2 ın spat, iul de stari.Definirea procedurii path:
path(Nod ,Nod , [Nod ]).
path(PrimNod ,UltimNod , [UltimNod |Drum]) :−path(PrimNod ,PenultimNod ,Drum),succesor(PenultimNod ,UltimNod), notmembru(UltimNod ,Drum).
Observat, ie: Relat, ia de succesor(X ,Y ) va reprezenta un spat, iu alstarilor. Daca exista s, i costuri asociate mis, carilor, atunci predicatuldevine: succesor(X ,Y ,Cost), unde Cost este costul unei deplasari.
Inteligenta Artificiala 45/58
Outline Inteligenta Computationala si Cunoasterea Rezolvarea de probleme Obiecte si termeni in Prolog Algoritmi de cautare
Iterative deepening
Avantajul metodei: put, ina memorie. La orice moment alexecut, iei necesitat, ile de spat, iu se reduc la un singur drumıntre nodul de ınceput al cautarii s, i nodul curent.
Dezavantajul metodei: la fiecare iterat, ie, drumurilecalculate anterior sunt recalculate, fiind extinse pana la o noualimita de adancime.
Inteligenta Artificiala 46/58
Outline Inteligenta Computationala si Cunoasterea Rezolvarea de probleme Obiecte si termeni in Prolog Algoritmi de cautare
Cautarea bidirectionala
Ideea algoritmului este cautarea simultana atat ınainte, cat s, iınapoi, cu oprire acolo unde cele doua cautari se ıntalnesc
1 cautarea ınapoi plecand de la scop presupune generareasuccesiva a predecesorilor
2 trebuie aleasa o metoda eficienta de a testa fiecare nod noupentru a vedea daca acesta apare ın arborele de cautare alceleilalte jumatat, i ın care se cauta
3 trebuie decis tipul de cautare ce se efectueaza ın fiecarejumatate
4 pentru ca cele doua cautari sa se ıntalneasca, nodurilecorespunzatoare a cel put, in una dintre jumatat, i, trebuiememorate ın ıntregime, la fel ca la BF.
Inteligenta Artificiala 47/58
Outline Inteligenta Computationala si Cunoasterea Rezolvarea de probleme Obiecte si termeni in Prolog Algoritmi de cautare
Cautarea informata
Se utilizeaza informat, ia despre spat, iul de stari.
Se folosesc cunos, tint, e specifice problemei s, i se rezolvproblemele de optimizare.
Inteligenta Artificiala 48/58
Outline Inteligenta Computationala si Cunoasterea Rezolvarea de probleme Obiecte si termeni in Prolog Algoritmi de cautare
Best-first
Cautarea euristica de baza este de tip best-first
Idei de baza:1 se presupune existent, a unei funct, ii euristice de evaluare (f ).2 se extinde nodul care are cea mai mica valoare a lui f (n), unde
n reprezinta nodul.3 procesul se ıncheie atunci cand urmatorul nod ce trebuie extins
este un nod scop
Putem fi indus, i ın eroare de o euristica extrem deoptimista?
Inteligenta Artificiala 49/58
Outline Inteligenta Computationala si Cunoasterea Rezolvarea de probleme Obiecte si termeni in Prolog Algoritmi de cautare
Best-first: Algoritm I
Algoritmul general de cautare bazat pe grafuri:GRAPHSEARCH permite o cautarea neinformata sau euristica
Pas 1: creeaza arborele de cautare Tr ce consta numai din nodul destart n0. Plaseaza deci pe n0 ıntr-o lista ordonata numitaOPEN
Pas 2: creeaza o lista CLOSED init, ial vidaPas 3: daca OPEN = ∅([ ]) atunci exit cu es, ecPas 4: daca OPEN 6= [ ] atunci selecteaza primul nod din lista OPEN,
ıl eliminam din ea s, i ıl includem ın CLOSED. Numim acestnod n
Pas 5: daca n este un nod scop, atunci algoritmul se ıncheie cu succes.Solut, ia este obt, inuta prin urmarea ın sens invers a unui drumde-a lungul arcelor (create la Pasul 6) din arborele Tr de la nla n0
Inteligenta Artificiala 50/58
Outline Inteligenta Computationala si Cunoasterea Rezolvarea de probleme Obiecte si termeni in Prolog Algoritmi de cautare
Best-first: Algoritm II
Pas 6: extinde nodul n, generand o mult, ime M de succesori. M seinclude ın Tr ca succesori ai lui n prin creearea de arce de la nla fiecare membru al lui M
Pas 7: reordoneaza OPEN fie ın concordant, a cu un plan arbitrar, fieın mod euristic
Pas 8: mergi la Pas 3
Obervat, ie:Pentru cautarea de tip best-first, OPEN se reordoneaza ınfunct, ie de meritele euristice ale nodurilor.
Inteligenta Artificiala 51/58
Outline Inteligenta Computationala si Cunoasterea Rezolvarea de probleme Obiecte si termeni in Prolog Algoritmi de cautare
Algoritmul A*
Cel mai cunoscut algoritm euristic (best-first) ın carereordonarea de la Pasul 7 se face ın funct, ie de valoricrescatoare pentru f .
A∗ foloses, te euristica f = h + g
Inteligenta Artificiala 52/58
Outline Inteligenta Computationala si Cunoasterea Rezolvarea de probleme Obiecte si termeni in Prolog Algoritmi de cautare
Algoritmul A*: Admisibilitate
A∗ garanteaza gasirea unui drum optim (de cost minim) la un scop(cand acesta exista), daca sunt ındeplinite urmatoarele condit, ii:
1 orice nod al grafului care admite succesori trebuie sa aiba unnumar finit de succesori
2 toate arcele din graf au costuri mai mari decat o cantitateε > 0
3 pentru toate nodurile din arborele de cautare trebuieındeplinita condit, ia: h(n) ≤ h(n). O astfel de funct, ie h senumes, te estimator optimist
Inteligenta Artificiala 53/58
Outline Inteligenta Computationala si Cunoasterea Rezolvarea de probleme Obiecte si termeni in Prolog Algoritmi de cautare
Algoritmul A*: Optimalitate
FieG1 o stare scop optimala cu un cost al drumului f ∗
G2 o stare scop suboptimala (dar tot scop)
}⇒
g(G2) > f ∗.
Daca presupunem ca A∗ selecteaza G2 pentruextindere (G2 stare scop), cautarea se poate ıncheia cusolut, ia suboptimala?
Inteligenta Artificiala 54/58
Outline Inteligenta Computationala si Cunoasterea Rezolvarea de probleme Obiecte si termeni in Prolog Algoritmi de cautare
Algoritmul A*: Completitudine
Din faptul ca A∗ extinde noduri ın ordinea crescatoare a valorilorlui f , putem deduce ca, ın final, va exista o extindere care conducela o stare scop, mai put, in cand numarul de noduri este foarte mare(tinde catre inf).
Cand exista un numar infinit de noduri?
Inteligenta Artificiala 55/58
Outline Inteligenta Computationala si Cunoasterea Rezolvarea de probleme Obiecte si termeni in Prolog Algoritmi de cautare
Algoritmul A*: Complexitate
Cres, tere subexponent, iala: |h(n)− h∗(n)| ≤ O(log h∗(n)), undeprimul termen reprezinta adevaratul cost pentru a ajunge de la n lascop.
Inteligenta Artificiala 56/58
Outline Inteligenta Computationala si Cunoasterea Rezolvarea de probleme Obiecte si termeni in Prolog Algoritmi de cautare
Algoritmul IDA*
Este o extensie logica a algoritmului iterative deepeningsearch, care foloses, te, ın plus, informat, ia euristica.
Fiecare iterat, ie extinde toate nodurile din interiorul conturuluideterminat de costul f curent, dupa care se trece la conturulurmator. Cum se termina cautarea ın interiorul unui contur, sedeclans, eaza o noua iterat, ie, folosind un cost nou f .
Este complet s, i optim cu aceleas, i amendamente ca s, i A∗.
Inteligenta Artificiala 57/58
Outline Inteligenta Computationala si Cunoasterea Rezolvarea de probleme Obiecte si termeni in Prolog Algoritmi de cautare
Concluzii finale
Cand nodurile sunt ordonate, cand nodul cel mai bine evaluateste primul extins, strategia se numes, te cautare de tipBest-first.O cautare tip best-first ce foloses, te pe h pentru selectareaurmatorului nod ce va fi extins se numes, te cautare de tipGreedy.Cautarea de tip best-first care foloses, te o funct, ie f de evaluares, i o funct, ie h admisibila se numes, te cautare de tip A∗, care eoptima s, i completa.Pentru a folosi algoritmul A∗ ın rezolvarea unei problemeconcrete, trebuie definite:
un spat, iu al starilorun predicat scopo funct, ie euristica adecvata fiecarei probleme
Algoritmul de tip IDA∗ ınlatura neajunsurile legate deproblema spat, iului mare de memorie folosit fara a sacrificaoptimalitatea sau completitudinea.Inteligenta Artificiala 58/58
Outline Inteligenta Computationala si Cunoasterea Rezolvarea de probleme Obiecte si termeni in Prolog Algoritmi de cautare
Concluzii finale
Cand nodurile sunt ordonate, cand nodul cel mai bine evaluateste primul extins, strategia se numes, te cautare de tipBest-first.O cautare tip best-first ce foloses, te pe h pentru selectareaurmatorului nod ce va fi extins se numes, te cautare de tipGreedy.Cautarea de tip best-first care foloses, te o funct, ie f de evaluares, i o funct, ie h admisibila se numes, te cautare de tip A∗, care eoptima s, i completa.Pentru a folosi algoritmul A∗ ın rezolvarea unei problemeconcrete, trebuie definite:
un spat, iu al starilorun predicat scopo funct, ie euristica adecvata fiecarei probleme
Algoritmul de tip IDA∗ ınlatura neajunsurile legate deproblema spat, iului mare de memorie folosit fara a sacrificaoptimalitatea sau completitudinea.Inteligenta Artificiala 58/58
Outline Inteligenta Computationala si Cunoasterea Rezolvarea de probleme Obiecte si termeni in Prolog Algoritmi de cautare
Concluzii finale
Cand nodurile sunt ordonate, cand nodul cel mai bine evaluateste primul extins, strategia se numes, te cautare de tipBest-first.O cautare tip best-first ce foloses, te pe h pentru selectareaurmatorului nod ce va fi extins se numes, te cautare de tipGreedy.Cautarea de tip best-first care foloses, te o funct, ie f de evaluares, i o funct, ie h admisibila se numes, te cautare de tip A∗, care eoptima s, i completa.Pentru a folosi algoritmul A∗ ın rezolvarea unei problemeconcrete, trebuie definite:
un spat, iu al starilorun predicat scopo funct, ie euristica adecvata fiecarei probleme
Algoritmul de tip IDA∗ ınlatura neajunsurile legate deproblema spat, iului mare de memorie folosit fara a sacrificaoptimalitatea sau completitudinea.Inteligenta Artificiala 58/58
Outline Inteligenta Computationala si Cunoasterea Rezolvarea de probleme Obiecte si termeni in Prolog Algoritmi de cautare
Concluzii finale
Cand nodurile sunt ordonate, cand nodul cel mai bine evaluateste primul extins, strategia se numes, te cautare de tipBest-first.O cautare tip best-first ce foloses, te pe h pentru selectareaurmatorului nod ce va fi extins se numes, te cautare de tipGreedy.Cautarea de tip best-first care foloses, te o funct, ie f de evaluares, i o funct, ie h admisibila se numes, te cautare de tip A∗, care eoptima s, i completa.Pentru a folosi algoritmul A∗ ın rezolvarea unei problemeconcrete, trebuie definite:
un spat, iu al starilorun predicat scopo funct, ie euristica adecvata fiecarei probleme
Algoritmul de tip IDA∗ ınlatura neajunsurile legate deproblema spat, iului mare de memorie folosit fara a sacrificaoptimalitatea sau completitudinea.Inteligenta Artificiala 58/58
Outline Inteligenta Computationala si Cunoasterea Rezolvarea de probleme Obiecte si termeni in Prolog Algoritmi de cautare
Concluzii finale
Cand nodurile sunt ordonate, cand nodul cel mai bine evaluateste primul extins, strategia se numes, te cautare de tipBest-first.O cautare tip best-first ce foloses, te pe h pentru selectareaurmatorului nod ce va fi extins se numes, te cautare de tipGreedy.Cautarea de tip best-first care foloses, te o funct, ie f de evaluares, i o funct, ie h admisibila se numes, te cautare de tip A∗, care eoptima s, i completa.Pentru a folosi algoritmul A∗ ın rezolvarea unei problemeconcrete, trebuie definite:
un spat, iu al starilorun predicat scopo funct, ie euristica adecvata fiecarei probleme
Algoritmul de tip IDA∗ ınlatura neajunsurile legate deproblema spat, iului mare de memorie folosit fara a sacrificaoptimalitatea sau completitudinea.Inteligenta Artificiala 58/58
Outline Inteligenta Computationala si Cunoasterea Rezolvarea de probleme Obiecte si termeni in Prolog Algoritmi de cautare
Concluzii finale
Cand nodurile sunt ordonate, cand nodul cel mai bine evaluateste primul extins, strategia se numes, te cautare de tipBest-first.O cautare tip best-first ce foloses, te pe h pentru selectareaurmatorului nod ce va fi extins se numes, te cautare de tipGreedy.Cautarea de tip best-first care foloses, te o funct, ie f de evaluares, i o funct, ie h admisibila se numes, te cautare de tip A∗, care eoptima s, i completa.Pentru a folosi algoritmul A∗ ın rezolvarea unei problemeconcrete, trebuie definite:
un spat, iu al starilorun predicat scopo funct, ie euristica adecvata fiecarei probleme
Algoritmul de tip IDA∗ ınlatura neajunsurile legate deproblema spat, iului mare de memorie folosit fara a sacrificaoptimalitatea sau completitudinea.Inteligenta Artificiala 58/58
Outline Inteligenta Computationala si Cunoasterea Rezolvarea de probleme Obiecte si termeni in Prolog Algoritmi de cautare
Concluzii finale
Cand nodurile sunt ordonate, cand nodul cel mai bine evaluateste primul extins, strategia se numes, te cautare de tipBest-first.O cautare tip best-first ce foloses, te pe h pentru selectareaurmatorului nod ce va fi extins se numes, te cautare de tipGreedy.Cautarea de tip best-first care foloses, te o funct, ie f de evaluares, i o funct, ie h admisibila se numes, te cautare de tip A∗, care eoptima s, i completa.Pentru a folosi algoritmul A∗ ın rezolvarea unei problemeconcrete, trebuie definite:
un spat, iu al starilorun predicat scopo funct, ie euristica adecvata fiecarei probleme
Algoritmul de tip IDA∗ ınlatura neajunsurile legate deproblema spat, iului mare de memorie folosit fara a sacrificaoptimalitatea sau completitudinea.Inteligenta Artificiala 58/58
Outline Inteligenta Computationala si Cunoasterea Rezolvarea de probleme Obiecte si termeni in Prolog Algoritmi de cautare
Concluzii finale
Cand nodurile sunt ordonate, cand nodul cel mai bine evaluateste primul extins, strategia se numes, te cautare de tipBest-first.O cautare tip best-first ce foloses, te pe h pentru selectareaurmatorului nod ce va fi extins se numes, te cautare de tipGreedy.Cautarea de tip best-first care foloses, te o funct, ie f de evaluares, i o funct, ie h admisibila se numes, te cautare de tip A∗, care eoptima s, i completa.Pentru a folosi algoritmul A∗ ın rezolvarea unei problemeconcrete, trebuie definite:
un spat, iu al starilorun predicat scopo funct, ie euristica adecvata fiecarei probleme
Algoritmul de tip IDA∗ ınlatura neajunsurile legate deproblema spat, iului mare de memorie folosit fara a sacrificaoptimalitatea sau completitudinea.Inteligenta Artificiala 58/58