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