Date post: | 12-Jul-2015 |
Category: |
Documents |
Upload: | pop-ciprian |
View: | 513 times |
Download: | 1 times |
5/11/2018 Inteligenta_artificiala - slidepdf.com
http://slidepdf.com/reader/full/inteligentaartificiala 1/53
Lucian SASU
5/11/2018 Inteligenta_artificiala - slidepdf.com
http://slidepdf.com/reader/full/inteligentaartificiala 2/53
5/11/2018 Inteligenta_artificiala - slidepdf.com
http://slidepdf.com/reader/full/inteligentaartificiala 3/53
Cuprins
1 Definitii. Rezolvarea problemelor prin ci'lutare
1.1 Definitii . . . . . . . . . . . . . . . . . . . . . .
1.1.1 Sisteme care actioneaza precum oamenii
1.1.2 Sisteme care gandesc ca oamenii .
1.1.3 Sisteme care gandesc rational .
1.1.4 Sisteme care actioneaza rational1.2 Fundamentele inteligentei artificiale ..
1.3 Starea actuala .
1.4 Rezolvarea de probleme de catre agent!
1.5 Formularea unei probleme ....
1.6 Exemple de probleme de cautare ..
1.6.1 Probleme "de jucarie"
1.6.2 Probleme "din lumea reala"
1.7 Cautarea solutiei . . . . . . . . . .
1.8 Masurarea performantelor aigoritmilor de cautare
1.9 Rezumat .1.10 Teste de autoevaluare .
1.10.1 Intrebari .
1.10.2 Teste grila ...
7
7
7
7
8
88
8
8
9
9
9
9
10
10
1212
12
12
2 Strategii de cautare neinforrnat.a
2.1 Cautarea "mai intai in latime" .
2.2 Cautarea dupa costul uniform .
2.3 Cautarea "mai intai in adancime"
2.4 Cautarea cu adancime limitata
2.5 Cautarea "mai intai in adancime" cu adancire iterativa
2.6 Cautare bidirectional a . .2.7 Problema starilor duplicat
2.8 Rezumat........
2.9 Teste de autoevaluare .
2.9.1 Intrebari .
2.9.2 Teste grila
15
15
15
16
16
16
17
17
18
18
18
19
3 Cautare inforrnat.a
3.1 Strategii de cautare informata
3.2 Cautarea euristica lacoma
3.3 Algoritmul A* ..3.4 Variatii ale lui A*
21
21
21
22
23
3
5/11/2018 Inteligenta_artificiala - slidepdf.com
http://slidepdf.com/reader/full/inteligentaartificiala 4/53
4 CUPRINS
3.5
3.6
Functii euristice . . . . . . . . . . . . . . . . . . . . .
Algoritmi de cautare locala §i probleme de optimizare
3.6.1 Cautarea prin metoda ascensiunii
3.6.2 Recoacerea simulata . . . . . . .
3.6.3 Algoritmi genetici .
3.6.4 Cautare locala in spatii continue.Rezumat .
Teste de autoevaluare .
3.8.1 Intrebari :
3.8.2 Teste grila . . .
23
24
25
26
26
2828
29
29
29
3.7
3.8
4 Probleme de satisfacere a constrangerflor
4.1 Probleme de satisfacere a constrangerilor .
4.2 Cautare backtracking pentru PSC . . . . .
4.2.1 Ordonarea valorilor §i a variabilelor
4.2.2 Propagarea informatiilor prin constrangeri
4.3 Cautare locala pentru PSC .
4.4 Rezumat...... . .
4.5 Teste de autoevaluare .
4.5.1 Intrebari :
4.5.2 Teste grila
31
31
32
32
33
34
34
34
34
34
5 Agent! logici
5.1 Motivatie .
5.2 Agenti bazati pe cunoastere
5.3 Logica ~ '~
5.4 Logica propozitionala .
5.4.1 Sintaxa .
5.4.2 Semantica...
5.4.3 Inferenta....
5.4.4 Echivalenta, validitate §i satisfiabilitate
5.5 Tipare de rationament in logic a propozitionala .
5.5.1 Rezolutia .
5.6 Forma normala conjunctiva
5.7 ~lgoritmul de rezolutic . . .
5.8 Inlantuirea inainte §i inapoi
5.9 Inforenta propozitionalii efectiva .5.9.1 Algoritm bazat pe backtracking
5.9.2 Algoritm bazat pe cautare locala
5.10 Rezumat . . . . . . . .
5.11 Teste de autoevaluare .
5.11.1 Intrebari .
5.11.2 Teste grila .
37
37
37
37
3838
39
39
40
41
41
42
42
43
4445
45
45
46
46
46
A Indicatii §i raspunsuri
A.1 Indicatii §i raspunsuri pentru capitolul 1
A.1.1 Raspunsuri la intrebari . . . . . .
A.1.2 Raspunsuri pentru testele grila
A.2 Indicatii si raspunsuri pentru capitolul 2
49
49
49
49
49
5/11/2018 Inteligenta_artificiala - slidepdf.com
http://slidepdf.com/reader/full/inteligentaartificiala 5/53
CUPRINS 5
A.2.1 Raspunsuri la intrebari .
A.2.2 Raspnnsuri pentru testele grila .
A.3 Indicatii si raspunsuri pentru capitolul 3
A.3.1 Raspunsuri la intrebari .
A.3.2 Raspunsuri pentru testele grila .
A.4 Indicatii §i raspunsuri pentru capitolul 4A.4.1 Raspunsuri pentru testele grila .
A.5 Indicatii §i raspunsuri pentru capitolul 5
A.5.1 Raspunsuri pentru testele grila
Bibliografie . . . . . . . . . . . . . . . . . . .
49
50
50
50
51
5151
51
52
53
5/11/2018 Inteligenta_artificiala - slidepdf.com
http://slidepdf.com/reader/full/inteligentaartificiala 6/53
6 CUPRINS
5/11/2018 Inteligenta_artificiala - slidepdf.com
http://slidepdf.com/reader/full/inteligentaartificiala 7/53
Capitolul 1
Definit ii. Rezolvarea problernelor
prin cautare
Obiective
Seprezinta cateva definitii pentru domeniul Inteligentei artificiale (celepatru abordari]
precum §i care sunt fundamentele sale, respectiv lista disciplinelor care au contribuit la
dezvoltarea domeniului.
Sunt prezentate §iurrnatoarele: notiunea de problema de cautare; notiunea de arbore
de cautare, nod; schita a unui algoritm de cautare in arborele de cautare
1.1 Definitii
Dam cateva definitii care au fost formulate de-a lungul timpului in diverse lucrari.Exista patru tipuri de abordari pentru sistemele cu inteligenta artificiala: sisteme care
gandesc precum oamenii, sisteme care gandesc rational, sisteme care actioneaza precum
oamenii, sisteme care actioneaza rational.
1.1.1 Sisteme care act.ioneaza precum oamenii
Deflnit.ia 1 Arta creiirii de masini care indeplinesc functii ce necesiiii inteligenta atunci
ciirul sunt indeplinite de ciiire oameni.
Deflnitia 2 Studiul asupra cum se poate ca un calculator sa [acii lucruri la care, pentru
moment, oamenii sunt mai buni.
Testul Turing, propus de catre Alan Turing in 1950 a fost conceput pentru a da 0
definitie operationala a inteligentei. Testul care trebuie trecut de catre un sistem inteligent
consta in a pune un omin imposibilitate de a decide daca interlocutorul (sistemul artificial)
este om sau nu.
1.1.2 Sisteme care gandesc ca oamenii
Deflni'[ia 3 Efortul provocator de a face calculatoarele sa gandeasca f. .. } masuii cu
minte, in sens literal.
Deflnitta 4 [AutomatizareaJ aciuniiiiilor pe care le asociem cu giindirea umanii, actuniiiii
precum luarea deciziilor, rezolvarea problemelor, invatareaf. .. }
7
5/11/2018 Inteligenta_artificiala - slidepdf.com
http://slidepdf.com/reader/full/inteligentaartificiala 8/53
8 CAPITOLUL 1. DEFINITII. REZOLVAREA PROBLEMELOR PRIN CAUTARE
1.1.3 Sisteme care gaudesc rational
Dcflnitia 5 Siudiul [aculiiitilor meniale pe baza utilizarii modelelor compuiaiionole.
Deflnrtia 6 Studiui calculelor care fac posibile percepiia, raiionamentul, aciionarea.
Aceasta abordare se bazeaza pe maturizarea domeniului numit "logica" in secolul al
19-1ea ~ introducerea de notatii si silogisme care permit redactarea unor enunturi §i relatii
intre diferite obiecte,
1.1.4 Sisteme care actioneaza rational
Definitia 7 Inteliqenia computaiionalii este studiul design-ului agentilor inteligenti.
Definitia 8 IA [. .. j se preocupii de comportamentul inteligent in artifacte.
1.2 Fundamentele inteligentei artificiale
Prezentam succint 0 list a a disciplinelor care au contribuie la dezvoltarea IA este: filo-
zofia, matematica, stiintele economice, neurostiinta, psihologia, ingineria calculatoarelor,
lingvistica.
1.3 Starea actuala
Unde este de folos IA? 0 Esta neexhaustiva este data mai jos:
• planificare autonoma
• jocuri
• control autonom
• diagnostic
• robotica
• intelegerea limbajului §i rezolvarea problemelor
1.4 Rezolvarea de probleme de catre agenti
Sa presupunem ca un agent inteligent are de rezolvat 0 problema: cum anume se poate
ajunge din Arad in Bucuresti (figura 1.4 este 0 harta simplificata a Rornaniei), folosind
drept cai de comunicatie §oselele din Romania.
Pasii care trebuie urrnati in rezolvarea unei probleme sunt:
1. formularea problemei
2. cautarea solutiei
3. executarea
5/11/2018 Inteligenta_artificiala - slidepdf.com
http://slidepdf.com/reader/full/inteligentaartificiala 9/53
1.5. FORMULAREA UNEI PROBLEME 9
Figura 1.1: 0 harta simplificata a Romanieij l]
1.5 Formularea unei probleme
o problema poate fi abstractizata precum mai jos, prin intermediul a patru atribute.
1. Siarea ini1iala.
2. 0descriere a aciisuiilor pe care le poate indeplini agentul. Acestea se pot formaliza
sub forma de operatori sau a unei [uncii: succesor
3. Testul de scop - determina daca 0stare este stare scop, adica 0 stare in care problemase considera a fi rezolvata.
4. 0 functie de cost a ciiii care asigneaza 0 valoare numerica fiecarei cai.
o solutie este 0 succesiune de actiuni care permite agentului rezolvarea problemei, iar
o solutio optima este una in care costul solutiei este minim posibil.
1.6 Exemple de probleme de cautare
1.6.1 Probleme "de jucarie"1. Problema puzzle-ului: se cia 0 matrice de n linii §i tot atatea coloane; in fiecare
celula se afia un singur numar de la 1 la n2- 1, nu exista doua celule care sa contina
acelasi numar, iar una din celule este goala.
2. Problema reginelor pe tabla de sah: dandu-se 0 tabla de sah de n linii §i tot atatea
coloane, sa se determine 0pozitionare a regineIor astfeI incat sa nu se atace reciproc.
1.6.2 Probleme "din lumea reala"
1. Problema determinarii rutei: acest tip de problema apare intr-o varietate de aplicatii,
precum crearea unui itinerar bazat pe zboruri cu avionul, planificarea operatiilor mil-
itare, rut.are in retele de calculatoare, etc. Trebui« insa considerate posibilitati]« (§i
5/11/2018 Inteligenta_artificiala - slidepdf.com
http://slidepdf.com/reader/full/inteligentaartificiala 10/53
10 CAPITOLUL 1. DEFINITII. REZOLVAREA PROBLEMELOR PRIN CAUTARE
probabilitatilc) de apar itie a unor evenimente nedorite precum anularea/Intarzierea
unor zboruri.
2. Problema comis-voiajorului - 0 persoana trebuie sa faca un tur al unei multirni de
erase, fara a trece de doua ori prin acelasi loc, cu revenire in Iocatia initiala §i cu
un cost al drumului minim.
3. Dispunerea circuitelor VLSI1
4. Roboti software pentru cautarea pe Internet.
1.7 Cautarea soltrtiei
Rezolvarea problemei este facuta prin cautare in spatiul starilor. Tehnicile de cautare
prezentate in acest capitol §i in capitolul 2 folosesc un arbore de cautare care are drept
didacina un nod corespunzand starii initials a problemei, iar nodurile sunt generate pebaza actiunilor permise din starea curenta,
Considerand cate 0stare 1a un moment dat, vom proceda astfel: testam sa vedem daca
starea curenta este stare scop; dadi da, oprim cautarea, construim solutia §i 0 raportarrr'.
Daca raspunsul este insa negativ, at unci se va expanda starea curenta pe baza functiei
succesor, obtinand un nou set de stari. Modul de alegere a nodu1ui deterrnina strategia
de cautare,
Arborele de cautare este format din noduri; un nod consta din urmatoarele compo-
nente:
• Stare: starea caruia iicorespunde nodul curent
• Nod-Parinte: nodul din arborele de cautare care a generat nodul curent
• Actiune: actiunea care a fost aplicata nodului parinte pentru a produce nodul
curent
• Costul-caii: costul cumulat al actiunilor care due de la nodul initial la nodul
curent;
• Adancime: numarul de pasi de-a lungul caii de la nodul initial
Nodurile care au fost obtinute prin expandarea altora, dar nu au fost la randul lorexpandate (altfel zis: noduri frunza in arborele de cautare construit pana la momentul
curent) sunt mentinute intr-o eclectic numita colectieNoduri.
Forma general a a algoritmului de cautare este data in figura 1.2.
1.8 Masurarea performantelor algoritmilor de cautare
Pentru algoritmii care urrneaza a fi discutati, evaluarea se va face prin prisma urmatoarelor
patru caracteristici:
1VLSI: Very Large Scale Integration, crearea de circuite integrate prin combinarea de tranzistoare.2De remarcat dl, nu ne propunem determinarea tuturor sau rnacar a mai multor solutii, ci doar a
primeia pe care algoritrnul de cautare 0 descopera,
5/11/2018 Inteligenta_artificiala - slidepdf.com
http://slidepdf.com/reader/full/inteligentaartificiala 11/53
1.8. MASURAREA PERFORMANTELOR ALGORITMILOR DE CAUTARE 11
functie Caut ar e-in-arh ore(problema, colectieNoduri) returneaza 0 solutie sau esuarec ol e eti e No du ri - in s e re az a( c re ea za -n od tsta re -in itia l a [p ro b1 e ma ]), e ole eti e No du ri)
eicleaaa
daea e 0 1 eetieN oduri este goal a
atunei retumeaza esuare
sfa rsi t d ae a
nod - scoate-primul ( co l ee ti eNoduri )
daca te st-se op (p roblem a , sta re [nod ])
atunei retumeaza solutie(nod)
sfa rs i t d ae a
col e eti eNoduri - ins ereaza-toate (e xp an de az a(n od , p ro ble m a ), c ol e eti e No du ri)sfarsi t cicleaza
functie Expandeaza(nod, pr obl em a) returneaza un set de noduri
succe sori - set vi d
pentru fiecare (aetiu ne, stareN ou a) in fu netie-su eceso r(pro blem a, stare [no d]) exe cuta
s -un nodnou
nod-parinte[s] - nod
aetiune[ s] - actiune
starers] - stareN oua
costul-cai i
[s] - e o stul-caii [nod] + costu l-p asu lu i (s ta re [nod ], a ctiu ne , s ta reN oua)adaneime[ s] - adaneime[nod] + 1adauga s 1 a su cce so ri
sf a rsi t p en tru
returneaza suecesori
functie Solutie(nod) returneaza 0 Iista ordonata de nnduri
drumNodur i -Iista vida
cicleaza
adauga nod l a inceputul lui drum Noduri
d ac a p arin te [n od ] =nimi e
atunci returneaza d ru mN o duri
altfel nod - parinte[nod]
sf arsi t d ae a
sfarsi t cicleaza
Figura 1.2: Algoritmul general de cautare.
5/11/2018 Inteligenta_artificiala - slidepdf.com
http://slidepdf.com/reader/full/inteligentaartificiala 12/53
12 CAPITOLUL 1. DEFINITII. REZOLVAREA PROBLEMELOR PRIN CAUTARE
• Completitudinea - un algoritm de cautare este complet daca se garanteaza di gase§tc
solutia problemei, in cazul in care aceasta exista;
• Optimalitatea - un algoritm este optim daca solutia gasita este eu eost al diU optim;
• Complexitatea in timp
• Complexitatea in spaiiu.
Cele doua cornplexitati se cuantifica prin intermediul notatiei O. Complexitatea in
timp este masurata relativ la numarul de noduri generate in decursul explorarii, iar com-
plexitatea de memorie este numarul maxim de noduri ce trebuie sa fie memorat pana la
rezolvare.
1.9 Rezumat
S-au dat mai multe definitii domeniului "Inteligenta artificiala" , in functie abordarile
existente. Tendinta actuala este de a descoperi principiile care stau Ia baza actionarii
inteligente.
Pentru problemele de cautare s-a dat 0 formulare generala, bazata pe starea initiala,
descrierea actiunilor, test de scop §ifunctie de cost. Cautarea solutiei se face prin gener-
area starilor care pot fi obtinute prin plecarea de la starea initiald §iefectuarea de actiuni
conform functiei succesor. Exista un algoritm general de cautare pe un arbore, prin a
carui particularizare se obtin diferite metode de cautare.
Criteriile de performanta pentru compararea diferitelor variante sunt: completitudinea,
optimalitatea, complexitatea in timp §i complexit.atea in spatiu.
1.10 Teste de autoevaluare
1.10.1 Int.rebari
1. In ce tip de abordare de definire a domeniului se incadreaza testul Turing?
2. Care este domeniul pe baza caruia se sprijina abordarea prin "gandire rationale"?
3. Care sunt pasii pentru rezolvarea unei probleme?
4. Care sunt componentele unui nod din arborele de cautare?
1.10.2 Teste grila
Raspundeti la urmatoarele intrebari, alegand variantele corecte.
1. Domeniul numit "logica " este definitoriu pentru care abordare a sistemelor in-
teligente?
(a) sisteme care gandesc precum oamenii
(b) sisteme care gandesc rational
(c) sisteme care actioneaza precum oamenii
5/11/2018 Inteligenta_artificiala - slidepdf.com
http://slidepdf.com/reader/full/inteligentaartificiala 13/53
1.10. TESTE DE AUTOEVALUARE 13
(d) sisteme care actioneaza rational
2. Functia succesor este folosita pentru a descrie:
(a) starea din care se pomeste cautarea
(b) actiunile §istartle in care se ajunge pe baza lor(c) scopul problemei
(d) costul caii
3. Daca un algoritm de catare determina intotdeauna solutia (cand aceasta exista)
atunci e1se numeste:
(a) comp1et
(b) optim
(c) complex
4. Factorul de ramificare este:
(a) numarul maxim de succesori ai oricarui nod dinarborele de cautare
(b) adancimea celui mai put in adanc nod solutio
(c) lungimea maxima a oricarei cai in arborele de cautare
5/11/2018 Inteligenta_artificiala - slidepdf.com
http://slidepdf.com/reader/full/inteligentaartificiala 14/53
14 CAPITOLUL 1. DEFINITII. REZOLVAREA PROBLEMELOR PRIN CAUTARE
5/11/2018 Inteligenta_artificiala - slidepdf.com
http://slidepdf.com/reader/full/inteligentaartificiala 15/53
Capitolul 2
Strategii de cautare neinforrnata
Obiective
Capitolul prezinta cateva strategii de cautare neinformata, impreuna cu discutia prob-lemelor legate de complexitate, optimalitate, completitudine. Cautarile sunt sistematice
§i se deosebesc intre ele prin strategia de alegere a nodurilor ce urmeaza sa fie expandate.
2.1 Cautarea "rnai Intai in latime"
Cautarea "mai intai in latime" are ca particularitate folosirea structurii de date de
tip coada in cadrul functiei Cautare-in-arbore din sectiunea 1.7. Nodul de start este
expand at , apoi copiii acestui nod sunt expandati, apoi copiii copiilor, etc. Functia
Cautare-in-arbore va fi apelata cu parametrul colectieNoduri initializat cu 0 coada
goala.
Sepoate vedea faptul ca dad plecand de la nodul initial se poate ajunge la nodul final
prin urmarirea actiunilor date de functia succesor, atunci functia va duce mai devreme
sau mai tarziu la descoperirea lui.
Algoritmul este optimal doar daca functia de cost a caii este nedescrescatoare fata de
numarul de arce (adancimea nodului). Acest lucru se intampiEi, de exemplu, daca costul
fiecarei actiuni este egal cu aceasi cantitate constanta.
Complexitatile (atat in timp cat §i in spatiu] nu sunt incurajatoare. Ca atare, acest
tip de explorare nu se foloseste in practica decat pentru probleme de dimensiuni foarte
mici.
2.2 Cautarea dupa costul uniform
Pentru cazul in care eostul diii nu este nedescrescator fata de adancimea nodului,
strategia de alegere pentru algortimul de cautare "mai intai in l3,time" poate sa ra.teze
gasirea caii optime. Se poate insa corecta acest aspect daca la fiecare pas se alege nu cel
mai putin adanc nod neexpandat, ci nodul neexpandat cu eostul dii eel mai mic. Acest
lucru se poate face dad colectia de noduri este mentinuta nu ca 0 coada normala, ci ca
o coada de prioritati.
Astfel, cautarea dupa costul uniform descopera caile cu cost minim. Dad eostulfiecarui pas (actiuni) este cel putin egal cu 0 constants e > 0, atunci cautarea este atat
completa cat §i optima.
15
5/11/2018 Inteligenta_artificiala - slidepdf.com
http://slidepdf.com/reader/full/inteligentaartificiala 16/53
16 CAPITOLUL 2. STRATEGII DE cA UTARE NEINFORMATA
Cornplexitatea in timp §i spatiu nu mai poate fi caracterizata de adancimea nodului;
in schimb este implicat costul solutiei optime, C*. Cornplexitatea de timp §i spatiu este
o ( b 1 + [ C : * l ) ; complexitatea data este deseori mai mare decat 0 ( b d + l ) .
2.3 Caut area "mai Intai in adancime"
Cautarea "mai intai in adancirne" va alege pentru expandare "eel mai adanc" nod
din arbore care nu a fost expandat. Colectia de noduri neexpandate din algoritmul
Cautare-in-arbore se poate implementa ca 0 stiva.
Necesarul de memorie pentru acest algoritm este deosebit de modest: dad factorul
de ramificare este b §i lungimea maxima unei cai este m, atunci numarul de noduri ce
trebuie retinute in colectieNoduri este 1+ b - m, deci comp1exitatea este O(b · m ).
Exista 0 varianta §imai redusa ca necesar de memorie bazat pe acest tip de cautare;
algoritmul este cunoscut sub numele de "backtracking" §i are particularitatea ca nu face
expandarea tuturor nodurilor copil pentru nodul ce se expandeaza, ci doar a unui copil.
Complexitatea in spatiu este O(m) . Mai mult, se poate doar mentine nodul curent (daca
pasul inapoi, de la copil spre piirinte este usor de refacut ) §iatunci complexitatea in spatiu
este 0(1) - memorie constanta ocupata, indiferent de dimensiunile problemei.
Problema cu acest tip de cautare este dl poate sa parcurga un numar mare de arce
pana la gasirea nodului solutio, dad ordinea de a1egerea nodurilor este "neinspirata".
Mai mult chiar, poate sa caute la nesfarsit in arbore, daca nu se face evitarea starilor
duplicat. Ramane insa de remarcat compexitatea de memorie ceruta: liniara,
2.4 Cautarea eu adancimc limit.ata
Cautarea "mai intai in adancime'' din sectiunea 2.3 are un mare atu: foloseste extrem
de putina memorie, Dar are §i un dezavantaj major, posibilitatea de a cauta la infinit
in arbore. Acest dezavantaj este eliminat simplu: vom 1imita adancimea maxima la care
poate sa coboare explorarea in arbore. Yom folosi deci un parametrul l (numar intreg)
reprezentand adancimea max~made explorare. Nodurile de la adancimea l sunt tratate ca
§icum nu ar avea succesori. Insa acest algoritm mai introduce un tip de rezultat: tajere,
pentru cazul in care avem d > liar cautarea epuizeaza toate nodurile din subarborele de
adancime l; in acest caz nu se poate spune ca see§ueaza, pentru ca 0adancime de cautare
mai mare ar fi perrnis gasirea nodu1ui scop (§i deci problema s-ar fi putut rezolva).
Algoritmu1 nu este complet daca l < d ; pentru l > d cautarea poate sa nu fie nicimacar optima. Complexit.atea in timp este OW) , iar cea in spatiu O(b · l) (mostenite
arnandoua de la parcurgerea "mai intai in adancime"). Ceea ce este insa de remarcat e
ca nu mai avem rise de cautare infinita datorata ciclurilor (vizitari! repetate a acelorasi
stari). Impreuna cu consumu1 dememorie redus ne fac sa speram ca problema de cautare
devine rezolvabila cu cerinte de memorie rezonabile.
2.5 Cautarea "mai Intai in adancime" eu adancire
it.erat.ivii
Problema necunoasterii apriorice a adancimii la care sa se fad cautarea este tratabila
prin urrnatoarea strategic: se dau valori succesive lui l incepand ell 0, din ce in cemai mari
5/11/2018 Inteligenta_artificiala - slidepdf.com
http://slidepdf.com/reader/full/inteligentaartificiala 17/53
2.6. CAUTARE BIDIRECTIONALA 17
pana cerezultatul este de tip esuare sau solutie. Gasirea solutiei inseamna deterrninarea
nodului solutio cel mai putin adanc, Variant a de algoritm combina partile bune ale
cautarii in adancime §i in latime: memorie necesara mica §i respectiv, completitudine
§i optimalitate pentru cazul in care functia de cost a caii este nedescrescatoare fata de
numarul de arce pentru cale.
2.6 Cautare bid irectionala
Cautarea bidirectionala se bazeaza pe strategia: se incep simultan doua cautari, atilt
dinspre nodul de start spre scop cat §i invers. Daca se produce "intalnirea" celor doua
cautari (§iin acest caz punctul comun celor doua parcurgeri este la distanta d/2 dintre
cele doua noduri de pornire), atunci complexitatea in timp este O (b d/2 + bd/2) =O (b d
/2),
care este mult mai mic dedit O (b d).
La fiecare expand are de nod se verifica daca acesta nu a fost cumva at ins de cautareadin sens contrar. Daca da, atunci solutia (secventa de actiuni care duce dinspre nodul
de start spre cel de scop) se reface pe baza drumurilor construite spre nodul comun,
Deterrninarea faptului ca un nod se gase§te intr-o lista de noduri se face in timp constant,
daca se foloseste 0 tabela de dispersie. Dar tocmai faptul ca necesarul de memorie este
O (b d/2) face acest algoritm sa nu poata fi aplicat in practica. In rest insa, algoritmul este
complet §ioptimal daca fiecare din cele dona cautari este efectuata prin parcurgere "mai
intai in latime" (§idesigur, cu ipoteza suplimentara ceruta de algoritmul mentionat). Alte
variante de combinare pot face algoritmul neoptim sau incomplet.
2.7 Problema st.ar ilor duplicat
Algoritmul general de cautare nu evita explorarea in mod repetat a acelorasi stari
(deci obtinerea de noduri diferite, dar pentru care starile corepsunzatoare au mai fost
vizitate anterior). Acest lucru face ca, de exemplu, explorarea in adancime sa poata sa
nu determine solutie, cu toate ca una exista. Pentru ceilalti algoritmi vizitarea repetat.a
a unor stari se traduce prin ineficienta.
Detectarea se face prin cautarea starii nodului ce urrneaza a fi expandat in lista starilor
care au fost deja expandate. Daca un algoritm evita starile duplicat, atunci poate fi vazut
ca 0 cautare in graf (recunoastem c a exista ciclul Arad-Sibiu-Arad, dar il evitam ).
Algoritrnul este dat in figura 2.1 §i foloseste 0 multime a starilor deja vizitate numit.a
stari Vechi. Algoritmul nou obtinut se numeste Cautare-in-graf.
Algoritmul Cautare-in-graf nu pune probleme in privinta completitudinii; complex-
itatea in tirnp §i spatiu sunt proportionale cu numarul starilor distincte, iar asta poate sa
fie rnult mai mic decat O (b d). Remarcam insa ca pentru cautarea "mai intai in adancime"
sau cu adancime limitata, datorita mentinerii acestei liste de noduri vechi, necesarul de
memorie nu mai este Iiniar.
In ceea ce priveste optimalitatea, lucrurile stau astfel: algoritmul va elimina noua
cale descoperita catre 0 stare care a mai fost intalnita inainte. Deoarece prima cale
descoperita s-ar putea sa fie suboptimala, rezulta ca nu se poate garanta optimalitatea
solutiei determinate. Acest aspect poate fi corectat.
5/11/2018 Inteligenta_artificiala - slidepdf.com
http://slidepdf.com/reader/full/inteligentaartificiala 18/53
18 CAPITOLUL 2. STRATEGII DE CAUTARE NEINFORMATA
functie Cautare-in-graf(problema, colectieNoduri) r eturneaz a0 solutie sau esuare
stari Vechi ~ mul tim e vida
col ecti eNoduri ~ ins ereaza( creeaza-nod( stare-initial a[probl ema D , col ecti eNoduri)
ci cleaza
daca c 0 1 ectieNoduri este goal a
atun ci re tum eaza esuaresfarsi t dac a
nod ~ scoate-prirnul (col ecti eNoduri)
daca test-scop(problema, stare[nod])
atunci returneaza solutie(nod)
sfarsi t dac a
daca stare[nod] nu este in stariVechi
atunci
adauga stare[nod] la stariVechi
col ecti e'Noduri ~ insereaza-toate (expandeaza(nod, problema), col ecti eNoduri)
sfarsi t dacasfarsi t cicleaza
Figura 2.1: Algoritmul de cautare in graf.
2.8 Rezumat
Pornind de la algoritmul general al cautarii pe arbore, se obtin cateva strategii de re-
zolvare, in prima faza prin particularizarea structurii de date asociate colectiei de noduri,
apoi prin modificarea comportamentului algoritmilor precedenti. Algoritmii rezultati
sunt: cautarea "mai intai in latime" , cautarea dupa costul uniform, cautarea "mai intai inadancime" , cautarea cu adancime limitata, cautarea "mai intai in adancime" cu adancire
iterativa, cautare bidirectionala. Pentru fiecare se studiaza optimalitatea, completi-
tudinea, complexitatea in timp §imemorie. Una din problemele mari este complexitatea
de memorie, care limiteaza aplicabilitatea in practica a unora dintre algoritmi. Cel mai
bun algoritm de explorare neinformata pentru cazul in care nu este cunoscuta adancimea
solutiei este cautarea "rnai intai in adancime'' cu adancire iterativa,
Evitarea starilor duplicat trebuie luata in considerare, iar folosirea unei structuri de
date eficiente pentru mentinerea starilor care au fost deja obtinute duce la reducerea
timpului de lucru, dar poate sacrifica optimalitatea solutiilor obtinute.
2.9 Teste de autoevaluare
2.9.1 Int.rebart
1. Ce este specific strategiei de cautare prin parcurgere "mai int.ai in latime"?
2. Ce este specific strategiei de cautare dupa costul uniform?
3. Ce este specific strategiei de cautare prin parcurgere "mai int.ai in adancime"?
4. Care este complexitatea de memorie a algoritrnului de cautare prin parcurgere "maiintai in adancime"? Cum este ea fata de complexitatea dememorie pentru strategia
de cautare prin parcurgere "mai intai in latime"?
5/11/2018 Inteligenta_artificiala - slidepdf.com
http://slidepdf.com/reader/full/inteligentaartificiala 19/53
2.9. TESTE DE AUTOEVALUARE 19
5. Explicati diferenta dintre algoritmul parcurgerii pe graf ~i eel al parcurgerii pe ar-
bore.
2.9.2 Teste grila
Raspundeti la urmatoarele intrebari, alegand variantele eoreete.
1. Tipul de date utilizat pentru colectieNoduri la algoritmul de cautare prin par-
curgere "mai intai in latime" este:
(a) stiva
(b) coada
(e) arbore
(d) coada de prioritati
2. Tipul de date utilizat pentru colectieNoduri la algoritmul de cautare dupa costuluniform:
(a) stiva
(b) coada
(e) arb ore
(d) coada de prioritati
3. Algoritmul de cautare prin pareurgere "mai Intai in latime" este garantat optimal
(a) adevarat
(b) fals
4. Algoritmul de cautare dupa costul uniform este garantat optimal:
(a) adevarat
(b) fals
5. Algoritmul de cautare prin parcurgere "mai intai in adancime" este:
(a) optimal
(b) eomplet
(e) niei optimal, niei eomplet
6. Care este algoritmul de cautare neinformata preferat, atunci cand nu se cunoaste
adancimea nodului solutio?
(a) cautarea "mai int.ai in latime"
(b) cautarea "mai intai in adancime'
(c) cautarea "mai intai in adancime'' eu adancire iterativa
(d) cautare dupa costul uniform
7. Cautarea bidirectionala are complexitate de memorie liniara:
5/11/2018 Inteligenta_artificiala - slidepdf.com
http://slidepdf.com/reader/full/inteligentaartificiala 20/53
20 CAPITOLUL 2. STRATEGII DE CAUTARE NEINFORMATA
(a) adevarat
(b) fals
8. Evitarea starilor duplicat poate reduce numarul de noduri de Ia forma exponentiala
la forma polinomiala:
(a) adevarat
(b) fals
5/11/2018 Inteligenta_artificiala - slidepdf.com
http://slidepdf.com/reader/full/inteligentaartificiala 21/53
Capitolul 3
Cautare inforrnata
Obiective
Algoritmii discutati in capitolu12 efectueaza 0explorare sistematica a spatiului starilor.Capitolul acesta contine 0 descriere a unor strategii de cautare euristica. Pentru anumite
variante §iipoteze destul de generale, unii algoritmi garanteaza gasirea unei solutii optime.
De asemenea sunt introdusi algoritmi de cautare locala §ioptimizare.
Dupa parcurgerea capitolului studentul va putea sa: defineasca euristica folosita pen-
tru acesti tip de algoritmi, exemplifice executia acestor algoritmi pe cateva probleme, sa
enunte conditiile in care A* duce la determinarea solutiei optime, aplice un algoritm de
cautare locala §i optimizare.
3.1 Strategii de cautare inforrnata
Strategiile euristice prezentate in acest capitol pornesc de la 0 idee simpla: ce s-ar
intampla daca s-ar explora intr-o directie care pare mai promitatoare pentru rezolvarea
problemei? am putea astfel sa evitam explorarea unor noduri care au 0 §ansa mica de
aju~gere in nodul scop, cu efect benefic asupra complexitatii in timp §i spatiu.
In cazul problemelor de cautare formalizate in capitolull, vorn considera pentru fiecare
nod n sansa lui de a duce spre un nod scop. Concret, pentru fiecare nod n se calculeaza
o [unciie de eooluare f(n). Nodul cu cea mai mica valoare a acestei functii este ales
pentru expandare, deoarece f estimeaza efortul de ajungere la solutio prin nodul curent.Ca atare, algoritmul de cautare pe arbore poate fi folosit cu 0modificare minora: lista de
noduri colectieNoduri trebuie sa fie organizata ca 0 coada de prioritati.Exista 0 clasa intreaga de algoritmi bazati pe aceasta idee. 0 componenta comuna
a acestor algoritmi este 0 [unciie eurisiicii notata traditional, cu h( n). h( n) reprezinta
costul estirnat al celei mai scurte cai (ca secventa de actiuni) dintre nodul curent §i un
nod scop.
De exemplu, pentru problema drumului din Arad inBucuresti putem sa vedem aceasta
functie ca fiind distanta pe drum drept de la oricare oras catre Bucuresti,
3.2 Cautarea eur ist.ica lacoma
Cautarea euristica lacoma alege pentru expandare nodul care are valoarea calculate
pentru functia h cea mai mica. AIHel spus, avem f(n) = h(n).
2 1
5/11/2018 Inteligenta_artificiala - slidepdf.com
http://slidepdf.com/reader/full/inteligentaartificiala 22/53
22 CAPITOLUL 3. CAUTARE INFORMATA
Putem observa ca minimizarea lui h poate duce la cautare neadecvata, ciclare daca nu
se evita starile repetate; daca se evita, atunci se poate descoperi uneori calea optima.
Concluzia pentru acest algoritm: ineomplet, neoptim, complexitate in timp §i spatiu
O(bm), unde m este adancimea maxima a unui drum in arborele de cautare,
3.3 Algoritmul A*Cea mal cunoscuta forma a acestor algoritmi euristici de cautare este algoritmul A*,
pentru care funtia f (n ) este data ca:
f(n) = g(n) + h(n)
unde g(n) este costul real al drumului de la nodul de start la nodul n iar h(n) este (preeum
anterior) costul estimat al celei mai bune eai de la nodul n la un nod scop. Avem deci c af(n) este costul estimat al celei mai bune eai de la nodul de start la un nod scop, drum ee
treee prin n. Pentru cateva conditii impuse lui h se obtine ca algoritmul A* este optim §i
complet; in practica, rezultatele obtinute sunt foarte bune, prin cornparatie eu strategiile
de cautare de tip neinformat.
Vomconsidera functii h care sunt euristici admisibile, adica h(n) niciodata nu supraes-
t.imeaza costul unei solutii de la nodul n la nod scop. Prin natura lor, acest tip de functii
sunt optimiste.
Un exemplu de functie euristica admisibila este cea care estimeaza efortul de ajungere
din nodu1 n in Bucuresti ca fiind distanta pe drum drept de la n 1aBucuresti. Este evident
c a orice ruta s-ar alege, ea nu poate avea cost mai mic decat costu1 drumului drept.
A vern urrnatoarea propozitie:
Propozitla1Dacii olqoritmui A * se termuui, aiunci nodul scop la care s-a aj1tns are
cost optim.
Daca se foloseste algoritmul Cautare-pe-Graf in locul algoritmului Cautare-pe-Arbore,
rezultatul de mai sus nu este valabil. Problema cu aceast.a abordare este ca se poate astfel
ca a prima ajungere intr-o anumita stare sa se faca eu cun cost suboptimal, iar urmatoarele
drumuri care conduc la aceeasi stare sunt neglijate, chiar daca ar duce la imbunatatirea
costului pentru acea stare.
Exista doua solutii care se pot aplica. Prima consta in mentinerea caii care are costul
eel rnai bun. Se poate scrie asemenea algoritrn, chiar daca este mai complex (presupune
de exemplu ca sa se modifice §i costurile nodurilor care sunt descendenti ai nodurilor cu
cost imbunatatit}, A doua solutio cere ca sa ne asiguram c a prima cale care duce Ia 0
anumita stare este intotdeauna cu cost optim, ca atare putem neglija drumurile ulterioare
care due la aceeasi stare. Vom detalia in cele ce urrneaza care sunt conditiile care trebuie
sa fie indeplinite de catre h pentru a aplica aceasta varianta.
Definitfa 9 0 [unciie h se numeste consisteniii dacii peniru orice nod n §i orice succesor
n' qenetai de 0 aciiune a avem co':
h(n) ::;c(n, a, n') + h(n')
o functie consistent a semai numeste §imonototui. Pentru problema drumului Arad-
Bucuresti, functia euristica data de distanta pe drum drept de la orasul curent la Bucuresti
este de asemenea §i consistenta. Se poate arata ca daca h este rnonotona, atunci valorile
lui f de-a lungul unui drum sunt nedescrescatoare, Sepoate demonstra ca:
5/11/2018 Inteligenta_artificiala - slidepdf.com
http://slidepdf.com/reader/full/inteligentaartificiala 23/53
3.4. VARIATII ALE LUI A * 23
Teorema 1 Docii h este consisientii, atunci A * folosind fl1,nctia Cautare-pe-Graj este
optimal.
Fie C* costul solutiei optime. Se mai poate arata ca:
• A* expandeaza toate nodurile cu f (n ) < C*;
• se poate ca A* sa expandeze cateva noduri care au f (n) =C* inainte ca sa expandeze
nod scop.
Sa notam ca A* nu expandeaza noduri n cu f (n ) > C*, de exemplu nodul aferent orasuluiTimisoara. Algoritmul este complet, daca nu cumva sunt infinit de multe noduri n care
au f(n) ::; f (G). Este §i optimal; mai mult decat at at , este optimal eficient pentru orice
functie euristica data - adica nici un alt algoritm optimal nu garanteaza expandarea unui
numar mai mic de noduri decat A*, poate cu exceptia celor cu f (n ) =C*.Exist.a totusi 0 problema: numarul de noduri care au fU < C* creste exponential cu
Iungimea solutiei. De muite ori algoritmul epuizeaza toata memoria pusa la dispozitie,
inainte de ca timpul pus la dispozitie sa se scurga.
3.4 Var iafii ale lui A*
Exista cateva variatii ale algoritmului A* , recent obtinute, care determina solutia
optima cu un necesar de memorie neprohibitiv. Primul dintre ele este Recursive best-
first search (RBFS) care are complexitate de memorie liniara, dar suferii de regenerarea
excesiva a nodurilor. Practic, acest algoritm sufera din faptul ca foloseste prea putina
memorie.
Algoritmii MA* (Memory-bounded A*) §i SMA* (Simplified memory-bounded A*)
Yin sa corecteze problema, ei folosind toata memoria care Ii se pune la dispozitie, Algo-
ritmul este complet daca solutia poate fi atinsa cu memoria data; este optimal in aceeasi
conditio, iar daca memoria pusa la dispozitie este prea putina, atunci va returna cea mai
buna solutie (suboptimala) pe care a putut-o descoperi. Pe de alta parte, insii, 0problema
poate deveni intratabila datorita complexitatiide timp crescute.
3.5 Funcfii euristice
Vomstudia functii euristice pentru problema puzzle-ului (a sevedea definitia problemei
de la pagina 9). Pentru un puzzle de 3x3, factorul mediu de ramificare este 3 (4 noduri
descendonte daca spatiul este la mijloc, 2 noduri descendente daca spatiul este intr-un
colt, 3 noduri altfel). Numarul mediu de mutari pentru rezolvare este de 22; 0 cautare
exhaustive ar cere vizitarea a 322 adica aproximativ 3, 1.1010 stari. Prin eliminarea starilor
duplicat problema s-ar reduce la 9!/2=181.440 stiiri distincte. Numarul este acceptabil,
dar pentru un puzzle de 4x4, un calcul asemanator duce la aproximativ 1013 stari distincte.
Ca atare, ne intrebam ce funtie euristica am putea folosi §i cat de buna este ea.
Cele mai populare euristici sunt:
• h1 - numarul de piese pozitionate gresit. h1 este 0 euristica admisibila, deoarece
este dar ca orice casuta cu pozitionare gre§ita trebuie s a suporte eel putin 0mutate.
5/11/2018 Inteligenta_artificiala - slidepdf.com
http://slidepdf.com/reader/full/inteligentaartificiala 24/53
24 CAPITOLUL 3. CAUTARE INFORMATA
• h2 - suma distantelor dintre pozitiile actuale §i cele din starea finala a pieselor.
Deoarece piesele se pot misca doar pe orizontala §iverticala, nu vom folosi distanta
euclidiana - preeum in problema drumului de la Arad la Sibiu - ei distanta L1 (sau
distanta Manhattan):
Din nou se observa di este 0 euristica admisibila, deoarece pentru mutarea unei
piese la pozitia corecta se fac eel putin mutarile pe orizontala §ipe verticala.
o modalitate de a caracteriza calitatea unei euristici este factorul efectiv de ramificare,
b", Daca numarul de noduri pentru 0 instanta particulara a unei probleme este N, atunci
b * se defineste ca factorul de ramifieare (nu neaparat numar intreg) pentru care un arbore
uniform de adancime d contine eele N noduri. De exemplu, daca A* descopera solutiala adancime 5 cu 52 de noduri, atunci b " ~ 1.92. Scopul este de a obtine un factor de
ramificare cat mai apropiat de 1.
Daca exista mai multe euristici ne putem pune problema daca e vreuna mai buna
decat celelalte, Pentru h I §i h2, de pilda, avemca h2(n) 2 h1(n ), 'lin . Se arataca este de
preferat a se cauta functii euristice care sa aibe valori cat mai rnari, dar sa ramana inca
admisibile (sub valoarea reala).
Ceseintampla cand avemmai multe euristici, dar niciuna nu domina pe toate celelelate
(adica: avem h I, h2 ' ... , b -« §i exista i, j, 1 :::;i, j :::;m ii = j pentru care exista x, y astfel
incat h dx) :::; h j(x) dar hdy ) > hj(y))? Putem eonsidera funtia h definitapunctual ca:
care domina pe toate celelalte.o alta metoda de obtinere a euristicilor este de a pleca de la subprobleme ale problemei
initiale, De exemplu, putem sa ne concentram atentia doar asupra unora din piesele de pe
puzzle, pe care incercam sa le aducem la pozitia corecta, in timp ce celelate pot ajunge in
orice pozitie. Pentru multo cazuri, rezultatul este mai bun dedit daca se foloseste distanta
Manhattan.
3.6 Algoritmi de caut.are locala §i problome de opt! ....
mizare
Algoritmii precedenti fac 0cautare mai mult sau mai putin sistematica pentru a de-
scoperi daca un nod scop poate fi ajuns plecand de la nodul initial. Cand acest lucru se
intarnpla, se reconstituie calea dintre nodul de start §inodul scop.
De multe ori, insa, secventa de pasi care duce din stares initiala in starea finala
este irelevanta. De exemplu, pentru problema reginelor pe tabla de sah (aectiunea 1.6.1,
pagina 9) nu ne intereseaza cum s-a ajuns la plasarea acestor regine, ci doar dispunerea
lor efectiva pe tabla de sah.
Cautarea locala foloseste doar 0 singura stare, cea curenta - ceea ce din start inseamna
ca memoria consumata este redusa; mutarile se fac doar in stare vecina cu cea curenta,
iar caile urrnate nu sememoreaza. Pe langa cantitatea mica de memorie ceruta (de obiceio cantitate constanta), se pot aborda §i probleme unde cautarea sistematica san chiar
euristica nu sunt fezabile (de exemplu probleme pe spatii continue).
5/11/2018 Inteligenta_artificiala - slidepdf.com
http://slidepdf.com/reader/full/inteligentaartificiala 25/53
3.6. ALGORITMI DE CAUTARE LOCALA §I PROBLEME DE OPTIMTZARE 25
De asernenea, se pot folosi algoritmii prezentati in aceasta sectiune §i pentru cazul
problemelor de optimizare, unde sa da 0 funtie obiectiv. Desi nu totdeauna solutiile
obtinute sunt optime, rezultatele se obtin de regula foarte aproape de optim.
Precum la metodele de cautare prezentate anterior, in acest context un algoritm de
cautare este:
• complet, daca intotdeauna gase§te un scop (cu conditia ca acesta sa existe);
• optimal, daca gase§te un optim local
Vomconsidera profilul functiei obiectiv (figura 3.1); dorim ca pentru functia reprezen-
tata sa determinam care este maximul.
Functia obiect iv
global
Figura 3.1: Profilul unei functii obiectiv; se doreste maximizarea ei. Punctul marcat pe
grafic reprezinta pozitia curenta, pentru care 0miscare in sus duce la imbunatatirea valorii
curente.
3.6.1 Cautarea prin metoda ascensiunii
Metoda ascensiunii se bazeaza pe 0 idee simpla: incearca sa modifici pozitia curenta
printr-o deplasare mica, astfel incat sa seproduca 0 imbunatatire a valorii functiei obiectiv.
Pentru profilul reprezentat in figura 3.1, unde se doreste maximizarea valorii functiei,
miscarea punctului de pe grafic se face inspre stanga.Algoritmul nu construieste un arbore de cautare, iar cautarea actiunii urmatoare nu
se face mai departs de vecinul imediat. Metoda se mai numeste §i cautare localii la-
coma. Algoritmul se termina atunci cand se ajunge intr-un optim, care poate fi local.
Ciiutarea vecinului se face in proximitate, "salturi" prea mari ar putea duce la ratarea
unor configuratii cu valoarea buna.
Strategia se poate folosi pentru problema darnelor pe 0 tabla de sah (a se vedea
sectiunea 1.6.1, pagina 9). Pentru fiecare patrat se calculeaza care ar fi numarul total de
atacuri de pe tabla de sah care are rezulta dupa plasarea reginei de pe coloana respect iva
in acel patrat. Evident, dorim sa determinam configuratia in care numarul de atacuri este
minim, ideal O. Daca pentru 0 stare (dispunere a reginelor) oarecare exista mai multe
"celemai bune mutari" se poate alege aleator oricare dintre ele.
Problemele pe care are algoritmul bazat pe ascensiune sunt:
5/11/2018 Inteligenta_artificiala - slidepdf.com
http://slidepdf.com/reader/full/inteligentaartificiala 26/53
26 CAPITOLUL 3. CAUTARE INFORMATA
1. maximelc locale: un maxim local este un varf care este mai inalt dedit punetele
situate intr-o vecinatate a lui, dar este mai mie decat maximul global.
2. zona plata: o.zona plata este 0 regiune din spatiulstarilor in care functia de evaluare
este constanta.
3. ereste - rezulta in secventii de maxime locale pentru care directia corecta este dificil
de ales.
Pentru problema celor opt regine, cautarea prin ascensiune duce la un optim local in
86% din cazuri; rezolvare cu functia de cost nula se atinge doar in 14% din cazuri,
Algoritmul, asa cum a fost enuntat, se opreste atuncicand ajunge in zona de platou
sau de coama. Pentru coama, insa, daca s-ar permite cautarea pe zona plata, s-ar putea
ajunge din nou la 0 situatie de urcus. 0 variants a algoritmului este cea in care se permit
pasi laterali pe zona plata. Pentru a preveni plimbarea la infinit pe un platou, se poate
impune 0 limit a a numarului de pasi suecesivi care pastreaza valoarea functiei obiectiv.
De exemplu, daca se stabileste aceasta lirnita la 100, pentru problema damelor se gaseste
rezolvare corecta in 94% din cazuri.
De asemenea mai exists varianta ascensiunii stochastice: dintr-un punet se alege prob-
abilist panta pe care se face urcarea; eu cat pant a este mai abrupt a , cu atat este mairnare
sansa de alegere a ei ca directie urrnatoare.
Algoritmii descrisi pana acum sunt incompleti - ei nu gasesc solutia mereu, deoarece
se blocheaza in optime locale. Ascensiunea cu repornire aleatoare stabileste puncte de
plecare aleator in spatiul starilor. Abordarea duce la un algoritm eare este eomplet eu 0
probabilitate ce tinde catre 1, din motivul c a repornirile aleatoare pot duee la alegerea unuinod de start corespunzator unui nod scop. Daca procentul de succes pentru 0 problema
este p, atunci este nevoie de lip reporniri.
Problemele din lumea reala deseori au un profil al functiei obiectiv cu maxime §i
minime multiple, "indesate" pe domeniul de definitie; algorimul cautarii prin aseensiune
duce, de regula, intr-un maxim local suficient de bun pentru tipul de ealeul eonsumat.
3.6.2 Recoacerea simulata
Un algoritm de cautare prin ascensiune este ineomplet, deoareee se poate eantona
intr-un mimim local. Ar fide dorit sapermitem algoritmului sa efectueze rni§diri §i intr-o
directie nefavorabila, in speranta c a va permite iesirea dintr-un minim local.
Algoritmul pentru minimizarea unei functii are ca principal a trasatura: daca mutarea
curenta duce intr-o situatie ell valoarea mai mica, atunci seaccepta; daca noua situatie este
mai defavorabila, atunci se accept a 0mutate cu 0 anumita probabilitate. Probabilitatea
scade exponential eu lipsa de calitate a noii configuratii §i cu "temperatura" (variabila)
curenta, Planificarea care apare ca parametu al algoritmului este 0 functie descrescatoare
fata de timp.
3.6.3 Algoritrni genetici
Sunt inspirati din principiile evolutionismului darwinian, care incearca sa explice
evolntia vietuitoarelor pe pamant. Seporneste cu 0 populatie -initiaIa, care este supusa
apoi unui sir de procese de tipul:
5/11/2018 Inteligenta_artificiala - slidepdf.com
http://slidepdf.com/reader/full/inteligentaartificiala 27/53
3.6. ALGORITMI DE CAUTARE LOCALA $I PROBLEME DE OPTIl\IfIZARE 27
felt)perturbare
x
Figura 3.2: Algoritmul coacerii simulate. Perturbarile vor permite scoaterea bilei din
minimele locale.
1. selectie: indivizii care sunt cei mai adecvati (fata de valoarea functiei ce se vrea
optimizata) sunt favorizati sa apara de mai multe ori intr-o populatie noua fata de
indivizii mai putin perforrnanti;
2. incrucisare: are loc un schimb de gene intre perechi de parinti, forrnandu-se copii;
acestia se presupune ca mostenesc §i combina performantele parintilor.
3. mutatie: se efectueaza niste modificari minore asupra materialului genetic existent.
Rolul mediului este preluat de catre functia scop. Vom detalia algoritmul pentru
maximizarea unei functii f : [ a , b ] =? R~ . Indivizii care alcatuiesc popolatia se numesc
cromozomi §i sunt alcatuiti din gene.
Pas 1. Crearea unei populatii initfalo de cromozomi. Seconsider a rnai multe val-
ori pentru variabila x E [ a , b ] . Numarul acestor valori (numit dimensiunea populatiei)
este dat ca parametrul al algoritmului, NR. Toate valorile sunt cuantificate prin
cromozomi care sunt siruri de k biti (un bit se mai numeste §i gena), k fiind alt
parametru de intrare. Generarea celor N R crornozomi se face aleator, prin setarea
fiecarei gene la valoarea 0 sau 1, la intamplare, Se obtine astfel 0 populatie initiala
fermata din cromozomii Cl, ... , CNR. Fiecare cromozom C (adica sir de k biti) va
produce un numar x ( c ) din intervalul [ a , b ].
Pas 2. Evolutia populatlei. In acest pas se obtin generatii succesive plecand de la
populatia initiala. Operatorii sunt selectia, irnperecherea (crosssover, incrucisarea)
§i mutatia.
Pas 2.1. Selectia, Pentru fiecare cromozom din popnlatie se calculeaza functia
obiectiv. Se face 0seletie care favorizeaza aparitia mai deasa a crornozomilor
cu valoare mare §i defavorizeaza cromozomii rnai putin performanti.
Pas 2.2. Incrucisarea. Se aleg aleator cromozornii care iau parte la procesul de
imperechere. Crornozomii alesi se incruciseaza astfel: primul select at cu al
doilea select at , al 3-lea cu al 4-lea, etc. Incrucisarea inseamna schirnbul de
gene intre parinti §i obtinerea de doi cromozomi copii care inlocuiesc parintii
in noua populatie.
5/11/2018 Inteligenta_artificiala - slidepdf.com
http://slidepdf.com/reader/full/inteligentaartificiala 28/53
28 CAPITOLUL 3. CAUTARE INFORMATA
Pas 2.3. Mutatia. Populatiei obtinute ise aplica operator de rnutatie.care duce la
modificarea aleatoare a genelor din cromozomi, cu 0 anumita probabilitate.
Populatia obtinuta in pasu12 reia ciclul de evolutie. Dupa ce se executa cateva astfel de
evolutii (sau numar de generatii, parametru al programului), se raporteaza valoarea celui
mai bun cromozom din ultima generatie, sau se foloseste strategia elitist a: se returneazaeel mai bun individ al tuturor generatiilor.
3.6.4 Cautare locala in spat.ii continue
Algoritmii de cautare prezentati pana acum functioneaza intr-un univers discret §i in
care functia succesor returneaza un set finit de pasi care pot fi efectuati dintr-o stare
oarecare. Cele mai multe probleme, insa, sunt de tip continuu §i deci posibilitatile de
alegere a urmatorilor pasi sunt infinite.
Pentru 0 functie reala demai multe variable f(xI,' .. ,xn), maximul se regaseste printre
punctele x =(XI,"" xn ) pentru care \7 f(x) =0, undo:
(o f of)
\7 f(x) = OXI"'" O X n
Pentru multe probleme, eel mai bun algoritm este bazat pe metoda Newton-Raphson,
folosita pentru deterrninarea radacinilor ecuatiilor de forma g ( x) =0 ( g fiind functie de 0
singurii variabila). Se calculeazs 0 noua estimare a lui x prin:
g(x)x+-x---
g'(x)
Pentru a gasi un maxim al lui f (funtie de mai multe variabile) urmatoarea valoarea a lui
x se determina astfel:
x +- x - Hjl(X)\7 f(x)
unde H f ( x ) este matricea hessiana, cu H i j - 02f / O X i O X j . Totusi, inversarea matricilor
este computational intensiva pentru un numar mare de variabile.
3.7 Rezumat
Cautarea inforrnata incearca sa evite explorarea sistematica a spatiului starilor. 0
directie este reprezentatta de folosirea de algoritmi de cautare care folosesc 0 euristica
de diretionare a cautarii (cel mai proeminent exemplu fiind algoritmul A*), iar cea de-a
doua este folosirea unor algoritrni de cautare locala, care nu mai pot garanta determinarea
gasirea solutiei, dar in practica due 1arezultate foarte bune.
Algoritmii de cautare locala (metoda ascensiunii §ivariantele ei, recoacerea simulate
§i algoritrnii genetici) folosesc extrem de putina rnemorie si sunt utili pentru rezo1varea
problemelor in care solutia este deterrninarea unei stari care satisface anumite cerinte, dar
modul in care se ajunge la acea stare este neimportant. Ei lucreaza cu functii obiectiv ce
trebuie optimizate; nu se garanteaza gasirea unui optirn absolut, dar fie sansa de a ajungeintr-un asemnea optirn este foarte mare, fie rezultatul deterrninat este foarte bun pentru
cat tirnp de calcu1li se aloca.
5/11/2018 Inteligenta_artificiala - slidepdf.com
http://slidepdf.com/reader/full/inteligentaartificiala 29/53
3.8. TESTE DEAUTOEVALUARE 29
3.8 Teste de autoevaluare
3.8.1 Intrcbari
1. Care este structura de date cea mai potrivita pentru.rnentinerea colectiei de noduri
din care se alege urmatorul expand at , pentru algoritmul A*?
2. Explicati de -ce la .algoritmul A* fara evitareastarilor repetat noduri corespunzand
starii Arad pot avea doua valori distincte.
3. Explicati de ce pentru 0problema de minimizare a costului caii, euristicile dominante
sunt mai bune.
4. Explicati de cein algorrtrnul din sectiunea 3.6.3 populatia rama,ne mereu cu acelasi
numar de cromozomi. .
3.8.2 Teste grilaRaspundeti la urmatoarele intrebari, alegand variantele eoreete.
1. Algoritmul de cautare euristicalacoma este optim
(a) adevarat
(b) fals
2. Algoritmul de cautare euristica lacoma este complet (considerati c a nu se face
evitarea starHor repetat)
(a) adevarat
(b) fals
3. Algoritmul A * expandeaza §i noduri avand eostul (valoarea functiei 1) mai mare
.decat costul solutiei optime:
(a) adevarat
(b) fals
4. Dandu-se 0 colectie de funtii euristice, nu se poate construi 0 functie euristica
domin(-l,nta peste oricare din familia. data:
(a) adevarat
(b) fals
5. Algoritmii de cautare locala nu sunt completi
(a) adevarat
(b) false
5/11/2018 Inteligenta_artificiala - slidepdf.com
http://slidepdf.com/reader/full/inteligentaartificiala 30/53
30 CAPITOLUL 3. CAYTARE INFORMATA
5/11/2018 Inteligenta_artificiala - slidepdf.com
http://slidepdf.com/reader/full/inteligentaartificiala 31/53
Capitolul4
Probleme·de satisfacere a
constranger ilor
Objective
Prezentul capitol trateaza probleme in care variabilele se supun unor restrictii impuse.
Spre deosebire de reprezentarile date la metodele de cautare din capitolele anterioare
(reprezentari care tin cont de particularitatile problemei pentru care se face cautarea
solutiei), problemele de satisfacere a constrangerilor au 0 forma mult mai generala. Eu-
risiticile prezentate sunt independente de probleme.
4.1 Probleme de satisfacere a const.rangerflor
o problema de satisfacere a constrangerilor (PSC) este definita ca un set de variabile
Xl, ... ,Xn §i un set de constrangeri C1, ... Cm. Fiecare variabila are un domeniu nevid
de valori Di, 0 constrangere se refera la un subset de variabile §iexprima conditii asupra
combinatiilor de valori pentru variabilele in discutie, 0 stare a problemei este 0 asignare
de forma {X i = Vi, Xj = Vj,' . . } . 0 stare in care valorile respect a orice restrictie Ck, 1 ::;
k ::; m senumeste consistenta sau legala. 0 solutie a problemei este 0 asignare consistent a
§i care da valori pentru fiecare variabila, Uneori este implicata §i 0 functie obiectiv care
trebuie optimizata.
Exemplu: dorim sa coloram harta regiunilor Australiei (figura 4.1) cu 3 culori, astfel
incat sa nu existe doua regiuni vecine care au aceasi culoare. Variabilele pot fi considerate
abrevierile pentru regiuni, respectiv: WA, NT, Q, NSW, V, SA, T, domeniul fiecarei
variabile este {rosu, verde, albastru}, iar restrictiile sepot exprima sub forma unoI' perechi
de forma X = 1 = Y unde X, YEW A, NT, Q, NSW, V,SA, T §i X, Y vecine pe harta,
Deseori se recurge la reprezentarea acestor restrictii sub forma de graf in care doua
variabile sunt legate printr-o muchie dacase supun unei constrangeri ..De exemplu, pentru
problema colorarii regiunilor se leaga prin muchii noduri reprezentand regiuni vecine (§i
care trebuie colorate diferit).
o PSC se poate formula in forma urrnatoare:
• stare iniliala: multimea vida, corespunzatoare lipsei de asignari de valori oricarei
variabile;
• funclie succesor: se asigneaza unei variabile ce nu are valoare data (numita variabila
31
5/11/2018 Inteligenta_artificiala - slidepdf.com
http://slidepdf.com/reader/full/inteligentaartificiala 32/53
32 . CAPITOLUL 4. PROBLEl'vfE DE SATISFACERE A CONSTRANGERILOR
>~ \
~~""1
INew South War
Figura 4.1: Regiuni din Australia.
libera) ovaloare din domeniul asociat, cuconditia ca asignarea nou obtinuta sa fie
consistenta (sa nu incalce restrictiile impuse):
• test scop: asignarea, curenta. este completa, nu mai exista. variabile Iibere
• costul caii: 0 constanta pentru fiecare asignare de variabila
Deoarece fiecare solutie.are toate cele.nvariabile cu valori asignate rezulta ci;\,adancimea
solutiei este n. Algoritmii folositi pentru rezolvarea acestui tip de probleme sunt cei de
cautare in adancime (adancimea se cunoaste, iar cicluri nu putem avea, deoarece la fiecare
pas consideram 0 alta variabila libera). De asemenea, algoritmii pentru cautare locala
dau rezu1tate bune,
4.2 Cautare backtracking pentru PSC
Formularea data pentru PSC (in special prezenta unei functii succesor) ne permite sa
speram ca putem trata PSC prin orice a1goritm de cautare de care dispunem. Totusi,
acest tip de probleme trebuie abordat cu 0 anumita schema de cautare.
Cautarea de tip backtracking este de fapt 0cautare de tip "mai intai in adancime" care
genereaza un singur nod descendent. Deoarece reprezentarea PSC este standardizata, ea
se poate aplica independent de specificul domeniului.
Fiind un algoritm de cautare neinforrnata, in practice ~l nu se comporti:l, bine pentru
probleme de dirnensiune mare. Existi; insa niste met ode generale care mareso eficientalor. Metodele reprezinta raspunsuri la urmatoarele intrebari:
1. Care variabila ar trebui luata in considerate la pasul curent., §i in ce ordine ar trebui
incercate valorile?
2. Care sunt irnplicatiile asignarii curente de valoare pentru 0 variabila. pentru alte
variabile ce inca nu au valori asociate?
4 . 2 . 1 Ordonarea valorilor §i a v.ariabilelor
Algoritrnul backtracking nu precizeaza cum anume se face select area de variabila. Se
poate, desigur, opta pentruo ordine fixa. Intuitiv, ar trebui sa consider am la fiecare pas
variabila care are cele rnai putme valori candidat.
5/11/2018 Inteligenta_artificiala - slidepdf.com
http://slidepdf.com/reader/full/inteligentaartificiala 33/53
4.2. CAUTARE BACKTRACKING PENTRU PSC 33
Stratcgia numita "valori rninime ramase" (VMR) decide alegerea variabilei care are cele
mai putine variante, astfel se incearca producerea unei esuari cat mai devreme posibil in
calea de cautare curenta, astfel ca sa se reteze caile care nu due la solutii. De exemplu,
daca avem 0 variabila care are 0 valori ramase, atunci algoritmul 0 va alege pe aceasta
§i se va detecta esuare. Acest lucru este corect, deoarece oricum mai devreme sau mai
tarziu se ajunge la imposibilitatea de a da valoare pentru variabila incauza, deci astfelse evita niste cautari care nu ar putea produce solutie.
In practica, aceasta strategie simpla duce la imbunatatiri ale vitezei de 3 pana la
3000 de ori. Se discuta in sectiunea 4.2.2 modul in care contorizarea numarului de valori
disponibile ramase se poate face eficient.
Euristic~ nu este utila la alegerea primei variabile, deoarece fiecare regiune poate avea
trei culori. Intr-un asemenea moment se foloseste euristica gradului care indica alegerea
acelei variabile care are cele mai multe contrangeri cu alte variabile fara valori asignate.
Notiunea de grad face aici referire la valori definite in teoria grafurilor. De exemplu,
pentru harta din figura 4.1 avem ca SA are gradul 5, alte variabile au valori 2, 3, O . Ca
atare, se va alege ca prima variabila SA (§i pasii urrnatori, cu aceeasi euristica due larezolvarea problemei fara a fi nevoie sa se revina). Strategia VMR este mult mai efectiva
decat aceasta, dar euristica gradului este utila la deciderea urmatorului pas intr-o situatie
de egalitate.
Odata ce s-a ales variabila pentru care se va da valoare trebuie determinat care este
ordinea de considerare a valorilor. Pentru asta se aplica strategia celei mai putin con-
strangatoarc valori, Concret, se prefera valorile care produc cele mai putine eliminari de
valori pentru alte varibile neasignate. Ideea este de a se lasa maximum de flexibilitate
(posibilitati) pentru alegerile urrnatoare. Evident, daca se cere generarea tuturor solutiilor
pentru PSC sau daca problema nu are nicio solutie, strategia este inutila.
4.2.2 Propagarea inforrnattilor prin constranger i
Pana acum algoritmul a considerat constrangerile pentru 0variabila doar cand ea era
aleasa pentru asignarea unei valori. Daca se iau in considerare aceste constrangeri mai
repede de acest moment, atunci se poate reduce foarte mult spatiul de cautare,
Verificare inainte
Ori de cate ori unei variabile X ise asigneaza 0 valoare, pentru fiecare variabila Y
care este conectata cu X printr-o restrictie se sterge din domeniullui Y valorile care suntinconsistente cu proaspata valoare a lui X. Este clar ca aoeasta verificare inainte face
pereche buna cu strategia VMR, pentru care urrnatoarele variabile luate in considerate
sunt SA §i NT. Verificarea inainte este un mod eficient de calcularea a informatiei de
care VMR are nevoie.
Propagarea constrangertlor
Cu toate ca verificarea inainte depisteaza inconsitente, ea nu le depisteaza pe toate.
Verificarea inainte nu este suficient de patrunzatoare in a detect a incompatibilitati. Propa-
garea constriinqeriior este un termen general, desemnand propagarea restrictiilor pentru
o variabila conform constrangerilor pentru alte variabile. Mai clar, propagam de la WA
§iQ la NT §iSA (precum la verificarea inainte), dar luam in considerate §iconstrangerea
5/11/2018 Inteligenta_artificiala - slidepdf.com
http://slidepdf.com/reader/full/inteligentaartificiala 34/53
34 CAPITOLUL 4. PROBLEME DE SATISFACERE A CONSTRANGERILOR
dintre NT §i SA pentru a detect a inconsitenta. Evident, dorim sa facem 0 asemenea
propagare de constrangeri cu efort computational cat mai mic.
Consistenia arcului este 0metoda rapida de propagate a constrangerilor care este ult
mai putemica decat verificarea inainte. Un arc se refera la 0 legatura directionata de la 0
variabila la alta. Date fiind doua variabile X §iY cu domeniile de valori aferente, un arc
de la X la Y este consistent daca pentru orice valoare din domeniullui X avem ca existamacar 0 valoarea compatibila (consistenta) in domeniullui Y.
Procesul de verificare a consistentei arcelor trebuie aplicat in mod repetat pana cand
nu mai exista inconsistente, Acest proces se poate face inainte de inceperea cautarii sau
dupa fiecare asignare de valoare. Ori de cate ori se face stergerea unei valori din domeniul
unei variabile X, trebuie verificate toate arcele de la variabile Y la X.
4.3 Cautare locala pentru PSC
Algoritmii de cautare locala se dovedesc a fi foarte eficienti in rezolvarea multor PSC.
Ei pornesc de la 0 asignare pentru toate variabilele iar functia succesor modifica valoarea
unei variabile la fiecare pas.
Cea mai evidenta euristica pentru selectarea valorii undei variabile este alegerea unei
valori care produce numarul minim de conflicte cu alte variabile - euristica conflicte-
minime.
Un alt avantaj al cautarii locale este ca permite cautarea unci solutii atunci cand
o parte din restrictii se schimba "pe loc". De exemplu, pentru 0 problema de planifi-
care a zborurilor, daca un aeroport devine indisponibil (accidente, conditii meteo) atunci
restrictia corespunzatoare poate fi usor introdusa §iplecand de la 0 planificare precedent a
se poate obtine una adecvata pentru situatia actuala in timp foarte scurt.
4.4 Rezumat
Problemele de satisfacere a constrangerilor se refera la situatiile in care pentru un set
de variabile se cere determinarea de valori care satisfac anumite restrictii, Metoda de
cautare este backtracking, dar algoritmul general poate fi imbunatatit prin folosirea unor
strategii independente de problema. Algoritmii de cautare locala sunt adecvati §i ei 11'1
rezolvarea de PSC.
4.5 Teste de autoevaluare
4.5.1 Int.rcbari
1. Prin ce se caracterizeaza 0 problema de satisfacere a constrangerilor?
2. Din ce motiv se foloseste cautarea in adancime pentru rezolvarea unei PSC?
3. Pe ce idee se bazeaza strategia valorilor minim ramase?
4.5.2 Teste grila
Raspundoti la urmatoarele intrebari, alegand variantele corecte.
5/11/2018 Inteligenta_artificiala - slidepdf.com
http://slidepdf.com/reader/full/inteligentaartificiala 35/53
4.5. TESTE DE AUTOEVALUARE 35
1. Algoritrnul de cautare folosit pentru rezolvarea unei PSC sebazeaza pe cautarea in:
(a) adancime
(b) latirne
(c) bidirectionala
2. Metode numita "verificare inainte" determina verificarea consistentei arcelor dintre
noduri:
(a) adevarat
(b) fals
5/11/2018 Inteligenta_artificiala - slidepdf.com
http://slidepdf.com/reader/full/inteligentaartificiala 36/53
36 CAPITOLUL 4. PROBLEME DE SATISFACERE A CONSTRANGERILOR
5/11/2018 Inteligenta_artificiala - slidepdf.com
http://slidepdf.com/reader/full/inteligentaartificiala 37/53
Capitolul 5
Agerrti logici
Obiective
Capitolul introduce agentii bazati pe cunoastere. Conceptele care-se discuta suntreprezentarea cunoasterii §i procesele de rationare - preocupari centrale ale inteligentei
artificiale.
Dupa parcurgerea capitolului studentul va putea sa explice care sunt aspectele care
definesc 0 logica, sa defineasca deductia, sa formuleze enunturi conform sintaxei din logica
propozitionala, sa foloseasca algoritmii prezontati pentru a efectua inferente.
5.1 Mct.ivatle
Spre deosebire de agentii care aplica metode1e de cautare prezentate in capitolele
anterioare, agentii logiei beneficiaza de cunoastere exprirnata in cele mai variate forme,
combinand §i recombinand informatia pentru a raspunde unor scopuri diverse. In plus,
cunoasterea §i rationarea de asemenea joaca un rol crucial in lucrul cu medii partial
observabi1e. Un agent bazat pe cunoastere poate sa produca noi cunostinte pe baza
cunostinielor generale §i a percepiiilor.
Un alt motiv pentru care se studiaza agentii bazati pe cunoastere este flexibilitatea
produselor rezu1tate. Astfel de agenti sunt in stare sa accepte noi sarcini §i sa castige
rapid noi competente prin invatare sau prin descoperire de noi informatii,
Principalul mod in care se abordeaza agentii logici este bazat pe logica (propozitionala,
apoi de ordinul intai).
5.2 Agenti bazat ipe cunoastere
Component a centrala a unui agent este baza de cunostinte (BC), adica un set de
enunturi care fac parte din domeniu1 de lucru al agentului. Fiecare enun] este exprimat
intr+un limbaj numit limbaj de reprezentare a cunostintelor §i reprezinta niste asertiuni
despre lume.
5.3 Logica
Sectiunea prezenta contine generalitati despre reprezentari logice si rationament. De-
talile sunt specifice logicilor concrete ce se studiaza (logica propozitiilor, logica predi-
37
5/11/2018 Inteligenta_artificiala - slidepdf.com
http://slidepdf.com/reader/full/inteligentaartificiala 38/53
38 CAPITOLUL 5 . AGENTI LOGICI
catelor, logica temporala, logica fuzzy).
Orice logica trebuie sa clarifice doua aspecte: sintaxa §i semantica. Sintaxa reprezinta
o specificate a ceea ce este corect exprimat in logica respective §i se poate reprezenta sub
forma de diagrame sau propozitii folosind simboluri.
Semantica defineste in general semnificatia unui enunt. In cadrul logicii ea permite
stabilirea unei valori de adevar pentru un enunt care este corect formulat din punct devedere sintactic. Mai mult, sernantica trebuie sa specifice valoarea de adevar pentru fiecare
enunt fata de fiecare lume posibila; de exemplu, a > b este adevarata pentru a =3 §i
b = 2, dar falsa pentru a = b =4.
a "lume posibila" (set de valori atasat variabilelor ) se va numi de acum inainte model
§i vom spune ca m este un model al lui a daca a este adevarata in lumea m.
Rationamentul logic (sau deductia, adica partea de interes major intr-o logica) reprezinta
modul in care se poate deduce un enunt dintr-un altul. Definitia forrnala a deductiei este:
Deflrritla 10 Spun em cii din 0: se deduce (3 §i noiiim. 0: 1 = j3 dacii in orice model al
enuntului 0: avem cii §i f J este adevrat.
Aceasta metoda deverificare a posibilitatii de deducere senumeste algoritmul verificarii
modelelor. Vom dezvolta mai multi algoritmi de dcdutie; daca avem un astfel de algoritm
i, atunci vom serie a I = i f J §i vom citi "(3 este dedus (sau derivat) din a prin i" sau "i 11
deriveaza pe f J din a" .
Un algoritm inferential se nurneste temeinic' daca obtine numai enunturi care sunt
derivabile din baza de cunostinte. Este evident c a algoritmul de verificare a modeleloreste temeinie.
a alta proprietate pentru un algoritm inferential este cea de completitudine - daca
poate sa deduca toate enunturile care sunt derivabile din baza de cunostinte. a examinaresistematica in cazul unei probleme in care rnultimea de concluzii posibile este finita duce,
evident, la un algoritm complet; proprietatea este insa esentiala pentru problemele in care
multimea concluziilor posibile este infinita,
5.4 Logica propozttionala
5.4.1 Sintaxa
Enunturile atornice din logica propozifionala'' sunt elemente sintactice indivizibile.
Fiecare simbol corespunde unei propozitii care poate sa fie adevarata sau falsa, Existe,
doua simboluri propozitionale cu semnificatii fixate: Adevarat este propozitia tot timpuladevaratasi Fals este propozrtia tot timpul falsa.
Enunturile complexe sunt compuse din propozitii simple folosind conectorii logici. Cei
cinci conectori sunt:
1. ' (non) - 0 propozitie precum ,A este negarea lui A. Un literal este fie un enunt
atomic (literal pozitiv), fie negarea a unuia (literal negativ),
2. 1\ (§i) - 0 propozitie formata din doua propozitii legate prin 1\ precum A 1\ B se
numeste cotijuuiie.
3. V (sau) - 0 propozitie ce foloseste V , precum A vB, se numeste disfunctie.
1In limba engleza, in original: sound.
2Nurnita §i logica booleana
5/11/2018 Inteligenta_artificiala - slidepdf.com
http://slidepdf.com/reader/full/inteligentaartificiala 39/53
5.4. LOGICA PROPOZITIONALA 39
4. = > (implidi) 0 propozitie precum A = > B se numeste implicatie. Premise sau
antecedentul implicatiei este A, iar concluzia sau consecventul este B.
5. < = ? (echivalent, daca §inurnai daca) - propozitia A < = ? B semai numeste biconditionala.
5.4.2 SemanticaSemantica defineste reguli pentru determinarea valorii de adevar a propozitiilor relativ
la un model concreto In logica propozitionala un model reprezinta valorile de adevar ale
simbolurilor propozitionale. De exemplu, daca avem propozitiile H,2, P2,2, P3,1, atunci
un model posibil este m = {PI,2 = f als, P2,2 = adevarat, P3,1= adevarat}.
Calculul valorii de adevar se face recursiv, deoarece orice propozitie este alcatuita din
propozitii atomice §iconectori. Pentru inceput, trebuie sa se determine valoarea de adevar
a unei propozitii atomice:
• Adevarat are valoarea de adevar "adevarat" pentru oriee model; Fals are valoarea
de adevar "fals" pentru orice model;
• valoarea de adevar a unei unui simbol propositional trebuie sa rezulte din modelul
curent.
Pentru propozitiile compuse se foloseste tabela de adevar (data in tabelul 5.1) care
arata cum se calculeaza valoarea propozitiei plecand de la elementele care 0 forrneaza.
Pe baza celor de mai sus se poate scrie 0 functie (Este- Adevar at ) care stabileste daca
valoarea de adevar a unei expresii s, plecand de la un model dat m este adearat.
p q - , p p A q p V q p = > q p < = ? q
adevarat adevarat fals adevarat adevarat adevarat adevarat
adevarat fals fals fals adevarat fals fals
fals adevarat adevarat fals adevarat adevarat fals
fals fals adevarat fals fals adevarat adevarat
Tabela 5.1: Tabela de adevsr pentrulogica propozitionala.
S-a spus anterior c a 0baza de cunostinte este 0multime de enunturi, Dat fiind modul
de calcul al valorii de adevar pentru 0 conjuntie, se poate spune ca 0 BC de forma 001,
... , an se poate scrie ca: al 1\ ... A an.
5.4.3 Inferenta
Scopul unei inferente este de a detemina daca BC F a. Primul algoritm pe care il
dam se bazeaza pe implement area direct a a definitiei 10: se enumera toate modelele §ise
verifica daca a este adevarata in toate modelele in care BC estc adevarata. Pentru logica
propozitionala, multimea tuturor modelelor se obtine dand toate combinatiile de valori
de adevar pentru sirnbolurile propozitionale.
Figura 5.1 contine un algoritm general pentru a determina daca se poate deduce a din
BC. Este 0cautare de tip backtracking; algoritmul este temeinic, deoarece implementeaza
direct definitia; este de asemenea §i complet deoarece se termina pentru orice baza de
cunostinte §ia, numarul de modele fiind finit.Complexitatea algoritmului este dictata de n, numarul de sirnboluri. Complexitatea
in timp este O(2n) iar cea in spatiu este O(n) , deoarece avem 0 cautare de tipul "mai
5/11/2018 Inteligenta_artificiala - slidepdf.com
http://slidepdf.com/reader/full/inteligentaartificiala 40/53
40 CAPITOLUL 5. AGENT'! LOGICI
functie TA-dednctie(BC, £ 1 . ) returneaza adevarat san f'als
intrari: BC, 0 baz a de cunostinte formulata in logiea prop ozitional a
a" interogarea, 0 propozitie in logi ca bool eana
simboluri -- 0 lista de simboluri propozitional e in BC si a
returneaza TA-Verifiea-Toate(BC, a, simboluri, [])
fnnctie TA-Verifiea- Toate(BC, £ 1 . , simb oluri, model) r etnrneaza adevar at san falsdaca Este-Goal a(simbol uri)
atunei daca Este-Adevarat(BC, model)
atunei returneaza Este-Adevarattn, model)
altfel r eturneaz a adevarat
sfarsit daca
altfel
P-prim ul(sim boluri); rest-rest(sim boluri)
returneaza TA-Verifiea-Toate(BC, a" rest, Extinde(p, adevarat, model» si
TA-Verifiea-Toate(BC, a" rest, Extinde(P, fals, model)
Figura 5.1: Algoritm de dcductie bazat pe construirea tabelei de adevar.
intai in adancime". Vom prezenta algoritmi care in practica sunt mult mai eficienti, dar
pentru toti algoritmii inferentiali cunoscuti exist a un cel mai defavorabil caz care duce la
complexitate exponentials,
5.4.4 Echivalenta, validitate si satisfiabilitate
Conceptele urmatoare sunt folosite in alti algoritmi care urmeaza a fi prezentati.
Primul concept este legat de echioolenia loqicii; notata cu simbolul = . Doua propozitiiex§i 1 3 sunt echivalente daca sunt adevarate in aceleasi modele. Se poate vedea de exempluca P 1\ Q este echivalenta cu Q!\ P (se verifica pe tabela de adevar).
o definitie alternativa a echivalentei este: ex 1 3 dad §i numai daca exF 1 3 §i 1 3 F ex.Tabelul 5.2 contine echivalcntele logice standard.
(ex1\ ( 3 )
(exV ( 3 )
((ex1\ ( 3 ) IVy)
((exV ( 3 ) V,),(,ex)
(ex=? ( 3 )(ex=? ( 3 )
(ex¢'} ( 3 )
,(ex 1\ ( 3 )
,(ex VfJ)
(ex1\ ( 1 3 V ,))
(exV (fi 1\ ,))
( 1 3 1\ ex) comutativitatea lui 1\
( 1 3 V ex) comutativitatea lui V
(ex1\ ( 1 3 1\ ,)) asociativitatea lui 1\
(exV ( 1 3 V ,)) asociativitatea lui V
exeliminarea dublei negatii
(,{3 =? ,ex) contrapozitie(,0: V ( 3 ) eliminarea implicatiei
((0: =? ( 3 ) 1\ ( 1 3 =? ex)) eliminarea biconditionala
(,0: V , ( 3 ) de Morgan
(--'0:1\ - , , 1 3 ) de Morgan
( ( 0 : 1 \ ( 3 ) V (ex1\ ,)) distributivitatea lui 1\ asupra lui V
((0: V ( 3 ) 1 \ (exV,)) distributivitatea lui V asupra lui 1\
Tabela 5.2: Echivalente logice standard.
Al doilea concept este validitatea. 0 propozitie este valida daca este adevarata in orice
model", Conceptul este util pentru urmatoare teoremii de deductie:
30 astfel de propozitie se mai numeste §i tautologie.
5/11/2018 Inteligenta_artificiala - slidepdf.com
http://slidepdf.com/reader/full/inteligentaartificiala 41/53
5.5. TIPARE DE RATIONAMENT iN LOGICA PROPOZITIONALA 41
Teorema2 Peuiru orice propoziiii a §i /3,aevem eli C l:p (3 dacii ii i numai dacii propoziiia
a :::}3 este valida.
Ultimul concept este satisfiabilitatea. 0propezitie este satisfiabila daca ~inumai daea
este adevarata in eel putin un model. Daca a este adevarata intr -un model m, atunci
spunem ca m satisface a, sau ca m este un model allui a.A verifica daca (3 se poate deduce din a (adica daca a :::}3) este echivalent cu a vedea
daca a /\ ,(3 este nesatisifiabila - de fapt regasim procedeul demonstratiei prin reducere
1aabsurd.
5.5 Tiparc de ra~ionament in logica propozrtionala
Prezentam tiparele standard care pot fi aplicate pentru a deriva noi propozitii; aceste
tipare se mai numesc ~i reguli de inferenta.
Cea mai cunoscuta regula se numeste Modus Ponens §i are forma:
a:::} (3 , a
(3
adica: daca din a se poate deduce (3 §istirn ca a este adevaratti, atunci §i(3 este adevarata.
Alta regula este eliminarea lui §i care spune c a dintr-o conjunctie oricare din terrneni
poate sa fie dedus:
Cl:/\(3
a
De asemenea, oricare din echivalentele din tabelul 5.2 pot fi folosite ca reguH de
inferenta; de exemp1u echivalenta pentru eliminarea biconditionala duce la dona regulide inferenta:
Deoarece inferenta in logica propozitionala este NP-completa, s-ar putea spune ca 0
cautare de demonstratie nu poate sa fiemai eficienta dedit enumerarea modelelor. In prac-
tics insa, gasirea unei demonstratii este mult mai eficienta, deoarece se evita propozitiile
irelevante, indiferent de cate sunt.
5.5.1 RezolutiaIn mod evident, regulile de inferenta expuse anterior sunt temeinice; nu este insa
evident daca sunt §i complete, adica ele perrnite deducerea a orice poate fi demonstrat
pornind de la 0baza de cunostinte. Aplicarea unui algoritm de cautare care este complet
avand drept pasi urmatori regulile de inferenta nu garanteaza obtinerea unui mecan-
ism inferential complet. De exemplu, daca regula eliminarii biconditionals nu ar fi fost
prezenta, atunci concluzia din demonstratia anterioara nu s-ar fi putut dovedi.
Introducem osingura regula de inferenta, numita rezotutie care produce un algoritm
de inferenta cornplet, daca este folosit in conjunctie cu un algoritm de cautare cornplet.
Regula rezoluiiei unit ate se serie formalizat astfel:
5/11/2018 Inteligenta_artificiala - slidepdf.com
http://slidepdf.com/reader/full/inteligentaartificiala 42/53
42 CAPITOLUL 5. AGENTI LOGICI
unde fiecare Z · este un literal iar l' i §i m sunt literali complementari (uuul este negarea
celuilalt). Deci regula rezolutiei unitate preia 0 clauza (0 disjunctie de literali) §i un
literal §i produce 0 noua clauza.
Regula de mai sus admite 0 generalizare imediate:
adica se pleaca de la doua clauze §ise ajunge 1auna noua in care avem toti literalii clauzelor
initiale, mai putin cei doi termeni care sunt complementari. Desigur, se presupune ca se
aplica §i factorizare, adica 0 expresie de forma A V A V ... este redusa la A.
Este usor de vazut c a regula de rezolutie este temeinica. Se poate arata, de aseme-
nea, ca orice a1goritm complet de cautare care aplica doar regula de rezolutie poate sa
demonstreze orice concluzie care se poate demonstra plecand de la 0 baza de cunostinte
in logica propozitionala,
Exista totusi un aspect practic care trebuie mentionat: daca se da de exernplu propozitia
A adevarata, metoda rezolutiei nu poate sa deduca automat ca §i A V Beste adevarata.
Mai general, rezolutia poate fi folosita pentru a confirm a sau infirm a orice propozitie, dar
nu poate sa genereze singura toate propozitiile care pot fi deduse pornind de la baza de
cunotinte.
5.6 Forma norrnala conjunctiva
Regula de rezolutie se aplica numai disjunctiilor de literali, deci s-ar parea ca se aplica
doar bazelor de cunotinte §i interogarilor care constaudin.ascrnenca forme. Se poate ara,ta
c a orice expresie din logica propozitionala poate fi rescrisa sub forma unei conjunctii dedisjuntii, asa numita forma normolii conjunctiva (FNC).
5.7 Algoritmul de rczohrtio
Procedurile de inferenta bazate pe rezolutie lucreaza pe principiul reducerii la absurd,
adica pentru a arata c a BC F 0:, aratam ca (BC /\ ,0:) este nesatisfiabila.
Algoritmul este aratat in figura 5.2. Primul pas este de a converti BC /\ ,0: in FNC.
Apoi, pentru fiecare pereche care contine literali complementari se produce 0 noua clauza,
care este adaugate la setul de clauze, daca nu este deja prezenta. Procesul se repeta pana
cand se intampla una din:
1. nu exist a noi clauze care sa fie adaugata la setul de clauze; in acest caz din BC nu
se poate deduce 0:;
2. doua clauze produc clauza vida, caz in care din BC se poate deduce 0:.
Clauza vida. este echivalenta cu Fals, deoarece 0 clauza este adevarata daca §i numai
daca eel putin un termen al ei este adevarat; nefiind cazul, inseamna ca FNC data de
BC /\ ,0: evolueaza la un enunt care contine conjuntie cu Fals, deci valoarea de adevar
este fals.
Se defineste inchiderea rezolutiva a unei propozitii aflate in FNC ca fiind setul tuturor
clauzelor care se obtin din aplicarea repetata a regulii de rezolutie peste propozitie sau
5/11/2018 Inteligenta_artificiala - slidepdf.com
http://slidepdf.com/reader/full/inteligentaartificiala 43/53
5.8. iNLANTUIREA iNAINTE $I iNAPOI 43
functie LP-Rezolutie(BC, a) returneaza adevar at sau fals
intrare: B C, 0 baza de cunostinte in logi ca propoziti onala
1 1 . , inter ogarea, exprimata in 1ogica propozi tional a
clauze+-setul de clause in mc pentru BC f\ a
nou-O
cicleaza
pentru fiecare Ci,q in clause executarezolventi -LP-Rezolva(Ci, q)daca rezolventi contine clauza vi da
atunci returneaza adevarat
sfarsit daca
nou - nou uezolventi
sfarsit pen tru
daca nou c ; ; c 1 auze
atunci returneaza f'als
sfarsit daca
cl auze - clauzeUou
sfarsit cicleaza
Figura 5.2: Algoritm de rezolutie pentru logica propozitionala. Functia LP-Rezolva
returneaza setul de clauze care se obtine prin combinarea celor doua intrari.
clauze derivate din ea. Acesta multime este finitii, deoarece numarul de combinatii in
disjuntii al unui set finit de simboluri este finit (se aplica §i factorizarea).
Completitudinea este data de teorema:
Teorema 3 (Teorema de rezolutie, [1]) Dacii un set de clauze este nesatisfiabilJ atunci
inchiderea rezolutiva a acestor clauze coniine clauza vida.
5.8 Inlantuirea inainte §i inapoi
De multe ori, bazele de cunostinte din lumea reala con tin clauze intr-o forma partie-
ulara numita clauzii Horn. 0 clauza Horn este 0 disjuntie de literali in care cel mult un
literal are forma pozitiva. De exemplu, -,A V -,B V C.
Restrictia poate parea cam dura, dar:
1. Fiecare clauza Horn poate fi scrisa ca 0 irnplicatie a carei premisa este 0conjuntie cu
literali pozitivi §i drept concluzie un singur literal pozitiv. De exemplu, -,AV -,B V C
este echivalenta eu A 1\ B :;:::}. Aceasta din urrna forma este extrem de naturala,
motiv pentru care clauzele Horn se regasesc atat de usor in bazele de cunostinte,
Ele sunt element fundamental al domeniului numit Programare logica.
Daca 0 clauza Horn nu contine nici un literal pozitiv (de exemplu: -,AV -,B), at unci
se poate scrie echivalent -,A V -,B V Fals §i apoi ea A 1\ B :;:::}als.
2. Inferentele eu clauze Horn pot fi facute cu doi algoritmi extrem de naturali, inH1ntuirea
inainte §i inlantuirea inapoi.
3. Algoritmii de deductie care folosesc clauze Horn este liniar in dimensiunea BC.
Algoritmul de inlantuire inainte LP-Inlantuirelnainte (Be, q) determina daca un
simbol propozitional q poate fi dedus din baza de cunstinte aflate in forma Horn. Daca
5/11/2018 Inteligenta_artificiala - slidepdf.com
http://slidepdf.com/reader/full/inteligentaartificiala 44/53
4 4 CAPITOLUL 5. AGENTI LOGICI
premisele unei implicatii sunt cunoscute ca adevarate, atunci concluzia implicatiei este
adevarata §i este adaugata la baza de cunostinte. Procedeul se repets pana cand fie se
deduce q, fie nu semai poate adannga niciun simbol propozitional nou 1aBe. A1goritmu1
este dat in figura 5.3.
functie LP-htlantuireInainte{BC, q) returneaza adevarat san falsintrari: BC, baza de eunostinte eu propozitii exprimate in forma Horn
q, interogarea, un symbol propozitional
variabile locale: eontor, 0 tabela indexata dupa clauze, initial numarul de premise pentru
fiecare clauza
inferat, 0 tabel a indexata dupa simboluri , fiecare intrare eu val oarea initi ala
fa l s
agenda, 0 li sta de simboluri, initial simbolurile din BC eunoseute ca avand
valcarea adevarat
cat timp agenda nu este goala
p-Extrage(agenda)
daeap = q
atunei returneaza adevarat
sfarsit daca
daca inferat[p [=fal s
inf erat[p] = adevarat
pentru fiecare c 1 auza Hom e in care apare premi sa p
eontor[ c) = contor[ e] - 1daea eontor[ c) = 0
atunei Adauga(eap(e), agenda)
sfarsit daea
sfarsit pentru
sfarsit pentrusfarsit cat timp
Figura 5.3: Algoritmul de inlantuire inainte,
Inlantuirea inainte este temeinica, deoareee reprezinta apliearea rcpetata a regulii
Mo~us Ponens, Este de asemenea §i un algoritm comp1et (a se vedea [1]).
Inlantuirea inainte este un exemplu de rationarnent condus de date, adica al unui
rationament in care demonstrarea unei concluzii se face pornind dinspre ipoteze. Spre
deosebire de regula rezolutiei, poate fi folosita pentru a genera 0 lista de concluzii care
pot Afideduse plecand de la 0 baza de cunostinte.
Inlantuirea inapoi porneste dinspre interogare spre baza de cunostinte, Daca se cere
a se demonstra ca q este adevarata, se verifica prima data daca se stie deja valoarea de
adevar a lui q; daca nu se cunoaste, atunci se gasesc toate implicatiile care il produc pe
q. Daca se poate demonstra c a premisele unci astfel de implicatii sunt toate adevarate,atunci §i q este adevarata. Procesul de rationament este unul directionat de scop.
De multe ori, costul unei inlantuiri inapoi este mult mai mic decat dimensiunea bazei
de cunostinte (desi 0 implement are eficienta are costul liniar, in eel mai defavorabil caz).
5.9 Infercnta propozitfonala efectiva
Descriem aid doua variante de algoritmi eficienti pentru inferenta propozitionala
bazate pe verificarea de modele: unul este bazat pe cautare backtracking, altu1 pleaca
5/11/2018 Inteligenta_artificiala - slidepdf.com
http://slidepdf.com/reader/full/inteligentaartificiala 45/53
5.10. REZUMAT 45
de la cautare prin metoda ascensiunii.
Ambele metode verifica satisifiabilitatea, adica determinarea unui model (valori pentru
variabile) astfel incat sa se verifice 0 anumita valoare de adevar. Atat backtracking cat §i
cautarea locala rezolva aceste probleme, dar primul este un algoritm determinist, exact,
pe cand al doilea poate sa duca la rezultate incorecte.
5.9.1 Algoritm bazat pe backtracking
Algoritmul, datorat lui Davis §i Putnam plead de la 0 propozitie in forma normala
conjunctiva. Precum cautarea backtracking (sectiunea 4.2) §i metoda TA-deductie (figura
5.1), este 0 enumerare a modelelor, dar cu urrnatoarele imbunatatiri:
• terminate rapida: algoritmul detecteaza dad 0 propozitie este adevarata sau falsii,
chiar dad modelul este partial completat. 0 clauza este adevarata dad un literal
este adevarat, chiar daca ceilalti literali nu au valoare de adevar fixata. Similar, 0
conjuntie de clauze este falsa dad 0 clauza este falsa, indiferent de valorile celorlalte
clauze.
• Euristica simbolurilor pure: un simbol este pur daca apare ell acelasi semn in fieeare
clauza. Este usor de vazut ca daca 0 propozitie are un model, atunci acesta are
proprietatea ca simbolul pur are valoarea adevarat.
• Strategia clauzei unitate: 0 clauza unitate este 0 clauza cu un singur literal. In
contextul algoritmului, inseamna §i 0 clauza unde toti literalii, mai putin unul, au
valoare fals. Strategia clauzei unitate asigneaza valori unor asemenea simboluri
inainte de a se apnea de altele. 0 astfel de set are de variabila poate de asemenea
sa duca la alte clauze unitate.
5.9.2 Algoritm bazat pe cautare locala
Algoritmii de cautare locala pot fi aplicati direct problemelor de satisfiabilitate, daca
se da 0 functie de evaluare adecvata, Se alege de regula numarul de clauze nesatisfacute.
Algoritmii de acest tip schimba la fiecare pas valoarea unei variabile; pentru a iesi din
minimele locale se folosesc diferite variante de aleatoritivitate.
Unul din cei mai simpli §i mai eficienti algoritmi rezultati se numeste WalkSat (figura
5.4). La fiecare iteratie algoritmul alege 0 clauza nesatisfacuta §i alege aleator care dintre
variabile sa i§i schimbe valoarea, Alegerea variabilei se face aleator, fie:
• se alege variabila care minimizeaza numarul de clauze nesatisfacute, sau
• se alege simbolul aleator
Dad algoritmul returneaza un model, atunci acest model satisface clauzele. Daca insa
se returneaza esuare, atunci nu se poate §ti sigur daca expresia este nesatisfiabila sau ar
trebui ca algoritmul sa fie lasat sa ruleze mai mult (§i nici cat de mult).
5.10 Rezumat
Agentii logici beneficiaza de cunoastere exprirnata in cele mai variate forme, com-
binand §i recombinand inforrnatia pentru a raspunde unor scopuri diverse. In plus,
5/11/2018 Inteligenta_artificiala - slidepdf.com
http://slidepdf.com/reader/full/inteligentaartificiala 46/53
4 6 CAPITOLUL 5. AGENTI LOGICI
functie WalkSat (clauze, p, maxSchimbari) returneaza model pentru dame san esuare
intrari: clauze, un set de cl auze in logica propozitionala
p, probabilitatea de a alege 0miscare de tip al eator
maxSchim bari, nurnarul de schim bari de variabile inainte de a renunta
model -0 asignare al eatoare de adevarat/fals pentru simbolurile din cl auze
pentru i=11a maxSchimbari
daca mode1ul sati sface clauzel eatunci retuneaza m odelul
sfarsit daca
clauze - 0 clauza aleasa aleator care este falsa in model
cu probabilitateap schimba valoareain model a unui sibol ales din clauza
al tfel schimba val oarea unui simbol care m aximizeaza numarul de clauze satisfacute
sfarsi t pentru
returne aza esuare
Figura 5.4: Algoritmul Walks at pentru verificarea satisfiabilitatii unui set de clauze.
cunoasterea §i rationarea de asemenea joaca un rol crucial in lucrul cu medii partial
observabile.
Logica booleana este un caz particular de logica, beneficiind deci sintaxa §i semantica
proprii. Exista algoritmi de inferenta asociati, pornind de la implementarea naiva, trecand
prin tiparele de retionarnent dezvoltate ca legi ale gandirii §i ajungand la algoritmi bazati
pe proces de rezolu ctie. De asemenea exist a forme eficiente ale acestor algoritmi folositi
pentru bazele de cunostinte care se regasesc in practica, §i anume inlantuirea inainte §i
mapoi,
Diferite eursitici implementate pe un schelet de catare de tip backtracking (algoritm
determinit) §i algoritmi basati pe cautare locals (procedeu nedeterminist) due la algoritmi
care se pot utiliza practic pentru probleme legate de procesul inferential.
5.11 Teste de autoevaluare
5.11.1 Intrebari
1. Ce anume trebuie sa posede 0 logica?
2. Cum functioneaza mecanismul de rezolutie?
3. Pentru ce cazuri se pot folosi algoritmii de inlantuire inainte §i inapoi?
5.11.2 Teste grila
Raspundeti la urrnatoarele intrebari, alegand variantele corecte.
1. Pentru expresia AAB, daca A are valoarea Fals, atunci intreaga expresie are valoarea
de adevar:
(a) adevarat
(b) fals
(c) depinde de valoarea de adevar a lui B
5/11/2018 Inteligenta_artificiala - slidepdf.com
http://slidepdf.com/reader/full/inteligentaartificiala 47/53
5.11. TESTE DEAUTOEVALUARE 4 7
2. Pentru expresia Av B, daca A are valoarea Fals, atunci intreaga expresie arevaloarea
de adevar:
(a) adevarat
(b) fals
(c) depinde de valoarea de adevar a lui B
5/11/2018 Inteligenta_artificiala - slidepdf.com
http://slidepdf.com/reader/full/inteligentaartificiala 48/53
48 CAPITOLUL 5. AGENTI LOGICI
5/11/2018 Inteligenta_artificiala - slidepdf.com
http://slidepdf.com/reader/full/inteligentaartificiala 49/53
Anexa A
Indicati! §i raspunsur! pentru testele
de autoevaluare
A.I Indicatii §i raspunsur! pentru capitolul 1
A.1.1 Raspunsur'i la intrebari
1. Testu1Turing, urmarind reproducerea comportamentu1ui uman, este parte a viziunii
"sisteme care actioneaza precum oamenii". Desi atragatoare §i cea mai raspandita
reprezentare a inteligentei artificiale, 1a ora actuala nu mai este prioritate pentru
cercetare.
2. Logica, §tiinta care forrnalizeaza 1egile gandirii este piatra de teme1ie a abordarii
agentilor logici.
3. Pasii care trebuie urrnati in rezo1varea unei probleme sunt:
(a) formularea problemei
(b) cautarea solutiei - aici se folosesc a1goritmi decautare specifici
(c) executarea - pe baza solutiei ce expliciteaza actiunile ce trebuie executate
4. Starea, referinta catre nodul parinte, actiunea, costul caii, adancimea.
A.1.2 Raspunsurt pentru testele grila
1. b
2. b
3. a
4. a
A.2 Irrdicat.ii §i raspunaur ipentru capitolul 2
A.2.1 Raspunsuri la irrtrebar-i
1. Cautarea "mai inUi,iin latime" foloseste ca §i colectie pentru stoc~rea nodurilor
care sunt descoperite prin explorare, dar inca neexpandate, 0 coada. In acest fel de
49
5/11/2018 Inteligenta_artificiala - slidepdf.com
http://slidepdf.com/reader/full/inteligentaartificiala 50/53
50 ANEXA A. INDICA TIl $1RASPUNSURI
fiecare data se alege spre expand are eel mai veehi nod ramas in colectia de noduri;
expandarea se faee dupa adancimea crescatoare a nodurilor.
2. Cautarea dupa eostul uniform alege spre expandare nodul care are costul caii cel
rnai mic; colectia de noduri este organizata ca 0 coada de prioritati; algoritmul este
optim, spre deosebire de cautarea "mai intai in latime".
3. Cautarea "mai intai in adancime" foloseste ca §icolectie pentru stocarea nodurilor
care sunt descoperite prin explorare, dar inca neexpandate 0 stiva. In acest fel
de fiecare data se alege spre expandare cel mai recent nod introdus in colectia de
noduri.
4. Complexitatea de memorie a algoritmului de cautare prin parcurgere "mai intai in
adancime" este O(bm) , deci polinorniala. Pentru strategia de cautare prin parcurg-
ere "mai intai in Iatime" complexitatea este exponentiala: O (b d), mult mai mare
decat pentru cautarea prin parcurgere "mai intai in adancime".
5. Parcurgerea pe graf evita crearea unor noduri care ar avea drept stare una din starile
ce au fost deja atinse, prin verificarea starii nodului care urmeaza a fi expandat fata
de 0 coletie de stari. Algoritmul parcurgerii pe graf mai utilizeaza deci 0 colectie
suplimentara; trebuie luat in considerare sporul de viteza obtinut (san chiar faptul
c a 0 cautare in adancime se poate transforrna din algoritm incomplet in complet),
precum §i efortul necesar pentru mentinere caracterului optim al solutiei gasite.
A.2.2 Raspunsur ipentru testele grila
1. b
2. d
3. b
4. a
5. c
6. c
7. b
8. a
A.3 Irrdicat.ii §i rasptrnsur'i pentru capitolul 3
A.3.1 Raspunsuri la Intrebari
1. Coada de prioritati; desigur, trebuie ca pentru oricare dona noduri sa fie definite
relatia de "<" (mai mic) pentru a §ti care este ordinea de mentinere a nodurilorin colectie. Ordinea a dona noduri coincide cu ordinea data de valorile functiei fpentru nodurile respective.
5/11/2018 Inteligenta_artificiala - slidepdf.com
http://slidepdf.com/reader/full/inteligentaartificiala 51/53
A.4. INDICA TIl $1RASPUNSURI PENTRU CAPITOLUL 4 51
2. Fie dona noduri Arad corespunzatoare drumului Arad - Sibiu - Arad. Pentru
primul nod Arad, functia 9 are valoarea 0 (este chiar nodul de plecare), pe cand
pentru al doilea functia 9 are ca valoare distanta Arad-Sibiu plus distant a Sibiu-
Arad. Functia hare aceeasi valoare pentru ambele noduri, deci in total valoarea
functiei j pe cele dona noduri este diferita.
3. Din cauza ca A* expandeaza fiecare nod care are j(n) < C* (echivalent: h(n) <
C* - g ( n)), rezulta ca orice nod expandat pentru functia h2 este sigur expand at §i
pentru functia b.
4. Pasul de seletie aduna exact atatia elemente cat existau in populatia initiala. La
incrucisare copiii i§i inlocuiesc parintii, iar mutatia nu adaugii §inu extrage indivizi
din populatie.
A.3.2 Raspunstrri pentru testele grila
1. b
2. b
3. b
4. b
5. a
A.4 Indicatii §i raspunsuri pentru capitolul 4
1. 0 psc presupune existenta unui set de variabile, cu domenii de valori asociate §i
pentru care se dau conditii ce trebuie satisfacute de valorile variabilelor.
2. Cautarea in adancirne este adecvata pentru rezolvarea unei PSC deoarece adancimea
solutiei se cunoaste iar cicluri nu pot exista.
3. Strategia valorilor minim ramase incearca sa produca cat mai devreme 0 esuare in
procesul de cautare, prin alegerea variabilei pentru care se va considera valoarea ca
fiind variabila pentru care exista cele mai putine variante de alegere de valori.
AA.l Raspunsuri pentru testele grila
1. a
2. b
A.5 Indicatii §i raspunsurf pentru capitolul 5
1. Pentru0
logica trebuie sa se defineasca sintaxa (specificare a modului in carese pot formula enunturi cu sens) §i semantica (modalitate prin care se stabileste
semnificatia unui enunt ).
5/11/2018 Inteligenta_artificiala - slidepdf.com
http://slidepdf.com/reader/full/inteligentaartificiala 52/53
52 ANEXA A. INDICA TIl $1 RAsPUNSURI
2. Se face reducerea a doi termeni care au forme complement are in dona expresii scrise
ca disjunctii,
3. Daca baza de cunostint,e este data sub forma de clauze Horn, atunci se pot folosi
algoritmii enuntati,
A.5.l Raspunsur'i pentru testele gr ila
1. b
2. c.
5/11/2018 Inteligenta_artificiala - slidepdf.com
http://slidepdf.com/reader/full/inteligentaartificiala 53/53
Bibliografie
[1] Artificial Intelligence. A Modern Approach, Prentice Hall, Stuart Russel, Peter Norvig,
2nd edition, 2003
[2] Principiile inteligentei artificiale, Editura Albastra, D. Dumitrescu, 2004
[3] Pattern Classification, editia a doua, Ed. Wiley-Interscience, Richard O. Duda, Peter
E. Hart, David G. Stork, 2000
[4] Genetic Algorithms + Data Structures = Evolution Programs, Ed. Springer-Verlag,
Zbigniew Michalewicz, 1998
[5] Machine Learning, Ed. McGraw-Hill, Tom Mitchell, 1997
[6] Neural Networks. A comprehensive foundation, Ed. Prentice Hall, Simon Haykin, 1999
53