prezentare ai cursuri 1-8

65
Inteligenta Artificiala Morogan Luciana Academia Tehnica Militara 2 august 2012

Upload: lacramioara-mihaela

Post on 30-Nov-2015

41 views

Category:

Documents


1 download

DESCRIPTION

Inteligenta artificiala

TRANSCRIPT

Inteligenta Artificiala

Morogan Luciana

Academia Tehnica Militara

2 august 2012

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