Studierea algoritmilor IAsi utilizarea acestora ˆn [614793]

MINISTERUL EDUCAT ¸ IEI, CERCET ˘ARII S ¸I INOV ˘ARII
UNIVERSITATEA DIN CRAIOV A
FACULTATEA DE S ¸TIINT ¸ E
LUCRARE DE DISERTAT ¸ IE
Studierea algoritmilor IAs¸i utilizarea acestora ˆn
dezvoltarea testelor online
Coordonator S ¸tiint ¸ific:
Lect.Univ.Dr. Claudiu Ionut ¸ POP ˆIRLAN
Student: [anonimizat] ¸a

Cuprins
1 Not ¸iuni Introductive 2
1.1 Introducere . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
2 Aplicat ¸ii IA 6
2.1 Domenii ˆın care este folosit ˘a IA . . . . . . . . . . . . . . . . . . . . . . . 6
2.2 Aplicat ¸ii de ultim ˘a or˘aˆın IA . . . . . . . . . . . . . . . . . . . . . . . . . 7
3 Agent ¸i inteligent ¸i s ¸i c ˘autare neinformat ˘a 10
3.1 Agent ¸i Inteligent ¸i . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
3.2 Agent ¸i de c ˘autare . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
3.3 C ˘autare neinformat ˘a . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
3.3.1 Breadth-first search (BFS) . . . . . . . . . . . . . . . . . . . . . . 17
3.3.2 Depth-first search (DFS) . . . . . . . . . . . . . . . . . . . . . . . 18
3.3.3 Uniform-cost search (UCS) . . . . . . . . . . . . . . . . . . . . . 19
4 C ˘autare euristic ˘a(informat ˘a) 21
4.1 Euristici s ¸i algoritmul de c ˘autare Greedy . . . . . . . . . . . . . . . . . . . 21
4.1.1 Best-first search . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
4.1.2 Greedy best-first search . . . . . . . . . . . . . . . . . . . . . . . . 23
4.1.3 A* (A-star)search . . . . . . . . . . . . . . . . . . . . . . . . . . 25
5 Preg ˘atirea mediului de dezvoltare 27
6 Prezentarea aplicat ¸iei 33
6.1 Prezentarea aplicat ¸iei . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
7 Concluzii 34
7.1 Sectiunea 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
7.2 Subcapitol . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
1

Capitolul 1
Not¸iuniIntroductive
1.1 Introducere
Ce este Inteligent ¸a Artificial ˘a?
Inteligent ¸a artificial ˘a este o s ¸tiint ¸ ˘a s ¸i tehnologia bazat ˘a pe discipline precum Informa-
tica, Biologia, Psihologia, Matematica s ¸i Ingineria. O orientare major ˘a a Inteligent ¸ei Arti-
ficiale este ˆın dezvoltarea funct ¸iilor pe calculator asociate cu inteligent ¸a uman ˘a, cum ar fi
rat ¸ionamentul, ˆınvatarea s ¸i rezolvarea problemelor.
Potrivit tat ˘alui inteligent ¸ei artificiale, John McCarthy, este ,, S ¸tiint ¸a s ¸i ingineria de a
face mas ¸ini inteligente, ˆın special programe informatice inteligente ”.
Inteligent ¸a Artificial ˘a este o modalitate de a face un calculator, un robot controlat de
calculator sau un software care s ˘a gˆandeasc ˘a inteligent, ˆın acelas ¸i mod ˆın care g ˆandesc
oamenii inteligent ¸i.
Inteligent ¸a artificial ˘a (IA) se realizeaz ˘a studiind modul ˆın care g ˆandes ¸te creierul uman
s ¸i cum oamenii ˆınvat ¸ ˘a, decid s ¸i lucreaz ˘aˆın timp ce ˆıncearc ˘a s˘a rezolve o problem ˘a s ¸i apoi
folosesc rezultatele acestui studiu ca baz ˘a pentru dezvoltarea de software s ¸i sisteme inteli-
gente.
De la inventarea computerelor sau a mas ¸inilor, capacitatea lor de a ˆındeplini diverse
sarcini a continuat s ˘a creasc ˘a exponent ¸ial. Oamenii au dezvoltat puterea sistemelor infor-
matice ˆın ceea ce privesc diversele lor domenii de lucru, viteza lor cresc ˘atoare s ¸i diminuarea
dimensiunii ˆın raport cu timpul.
O ramur ˘a a informaticii numit ˘a Inteligent ¸a Artificial ˘a urm ˘areste crearea calculatoarelor
sau a mas ¸inilor la fel de inteligente ca fiint ¸ele umane.
2

CAPITOLUL 1. INTRODUCERE 3
Filozofia Inteligent ¸ei artificiale (IA)
ˆIn timp ce exploateaz ˘a puterea sistemelor informatice, curiozitatea omului, ˆıl conduce
s˘a seˆıntrebe: ,, Poate o mas ¸in ˘a s˘a gˆandeasc ˘a s ¸i s ˘a se comporte ca oamenii?, ˆIn ce m ˘asur˘a
mas ¸inile inteligente vor face parte din viat ¸a oamenilor ?, Sunt oamenii capabili s ˘a constru-
iasc˘a mas ¸ini cu adev ˘arat inteligente s ¸i dac ˘a da, cum le vor controla ? etc. ,,.
Astfel, dezvoltarea IA a ˆınceput cu intent ¸ia de a crea inteligent ¸ ˘a similar ˘aˆın mas ¸inile pe
care le g ˘asim s ¸i le privim foarte mult la oameni.
Obiectivele Inteligent ¸ei artificiale (IA)
Pentru a crea sisteme de expert ¸i – Sistemele care manifest ˘a comportament inteligente,
ˆınvat ˘a, demonstreaz ˘a, explic ˘a s ¸i sf ˘atuiesc utilizatorii.
Implementarea inteligent ¸ei umane ˆın mas ¸ini – Crearea de sisteme care s ˘aˆınteleaga,
s˘a gˆandeasc ˘a, s˘aˆınvet ¸e s ¸i s ˘a se comporte ca oamenii.
Ce contribuie la realizarea Inteligent ¸ei artificiale?
Din urm ˘atoarele domenii, una sau mai multe zone pot contribui la construirea unui
sistem inteligent:

CAPITOLUL 1. INTRODUCERE 4
Diferent ¸ele principale dintre folosirea program ˘arii cu s ¸i f ˘ar˘a Inteligent ¸a artificial ˘a sunt:
Lipsa inteligent ¸ei artificiale:
– Un program de pe un calculator f ˘ar˘a Inteligent ¸ ˘a Artificial ˘a poate r ˘aspunde la ˆıntreb ˘arile
specifice pe care intent ¸ioneaz ˘a s˘a le rezolve.
– Modificarea programului duce la modificarea structurii sale.
– Modificarea nu este rapid ˘a s ¸i usoar ˘a. Aceasta poate duce la afectarea negativ ˘a a pro-
gramului.
Folosind inteligent ¸a artificial ˘a:
– Un program de pe un calculator cu Inteligent ¸ ˘a Artificial ˘a poate r ˘aspunde la ˆıntreb ˘arile
generice pe care intent ¸ioneaz ˘a s˘a le rezolve.
– Programele care cont ¸in Inteligent ¸a Artificial ˘a pot absorbi noi modific ˘ari prin punerea
ˆımpreunarea unor informat ¸ii extrem de independente. Prin urmare, putet ¸i modifica chiar s ¸i
o singur ˘a bucat ˘a de informat ¸ie a programului, f ˘ar˘a a afecta structura sa.
– Modificarea rapid ˘a s ¸i usoar ˘a a programului.
Inteligent ¸a este capacitatea unui sistem de a calcula, rat ¸iona, percepe relat ¸iile s ¸i analo-
giile, ˆınvat ¸ ˘a din experient ¸ ˘a, stocheaz ˘a s ¸i preia informat ¸ii din memorie, rezolv ˘a probleme,
ˆınt ¸elege ideile complexe, foloses ¸te fluent limba natural ˘a, clasific ˘a, generalizeaz ˘a s ¸i se adap-
teaz˘a la situat ¸ii noi.
Inteligent ¸a este de mai multe feluri: inteligent ¸a lingvistic, inteligent ¸a muzical ˘a, inteligent ¸a
de logic ˘a-matematic ˘a, inteligent ¸a fizico-kinestezic ˘a, inteligent ¸a spat ¸ial ˘a, inteligent ¸a inter-
personal ˘a etc. In acest caz putem spune ca o mas ¸in ˘a sau un sistem det ¸ine inteligent ¸a artifici-
al˘a atunci c ˆand este echipat cu cel put ¸in una din cele c ˆateva feluri de inteligent ¸ ˘a prezentate
mai sus.
Inteligent ¸a este intangibil ˘a. Este compus ˘a din :
Rat ¸ionamentul- Este setul de procese care ne permite s ˘a oferim o baz ˘a pentru jude-
cat˘a, luare de decizii s ¸i predict ¸ie.
ˆInv˘at ¸area – Este activitatea de a dob ˆandi cunos ¸tint ¸e sau pricepere prin studiere, prac-
ticare, ˆınv˘at ¸are sau experimentare de ceva.

CAPITOLUL 1. INTRODUCERE 5
Rezolvarea problemelor- Este procesul ˆın care cineva percepe s ¸i ˆıncearc ˘a s˘a ajung ˘a
la o solut ¸ie dorit ˘a dintr-o situat ¸ie actual ˘a, luˆand o cale blocat ˘a de obstacole cunoscute
sau necunoscute.
Percept ¸ia – Este procesul de dob ˆandire, interpretare, selectare s ¸i organizare a informat ¸iilor
senzoriale.
Inteligent ¸a lingvistic ˘a – Este abilitatea cuiva s ˘a foloseasc ˘a, s˘aˆınteleag ˘a, s˘a vorbeasc ˘a
s ¸i s˘a scrie ˆıntr-o anumit ˘a limb ˘a. Este important ˘aˆın comunicarea interpersonal ˘a.
Diferent ¸a dintre inteligent ¸a omului s ¸i a mas ¸inilor este aceea c ˘a:
-Oamenii percep ˆın funct ¸ie de modele, ˆın timp ce mas ¸inile percep prin seturi de reguli
s ¸i date.
-Oamenii stocheaz ˘a s ¸i is ¸i reamintesc anumite informat ¸ii dup ˘a modele, ˆın schimb mas ¸inile
o fac prin c ˘autarea algoritmilor. De exemplu, num ˘arul 40404040 este us ¸or de memorat, de
stocat s ¸i de rechemat deoarece modelul sau este simplu.
-Oamenii pot descoperi obiectul complet chiar dac ˘a o parte din el lipses ¸te sau acel
obiect este distorsionat, ˆın schimb mas ¸inile nu pot face acest lucru.
Domeniul Inteligent ¸ei Artificiale este clasificat ˆın sarcini formale, sarcini mundane
(obis ¸nuite) s ¸i sarcini expert. Oamenii ˆınvat ¸ ˘a lucruri mundane (obis ¸nuite) de la nas ¸tere. Ei
ˆınvat ¸ ˘a prin folosirea percept ¸iei, vorbirii, limbajului etc. Ei ˆınvat ¸ ˘a mai t ˆarziu sarcinile for-
male s ¸i sarcinile de experti, ˆın aceast ˘a ordine. Pentru oameni, sarcinile obis ¸nuite sunt cele
mai us ¸or de ˆınvat ¸at. Aceleas ¸i sarcini mundane(obis ¸nuite) au fost puse ˆın aplicare s ¸i pentru
mas ¸ini. Anterior, toate lucr ˘arile IA au fost concentrate ˆın domeniul sarcinilor obis ¸nuite.
Mai t ˆarziu, sa dovedit c ˘a mas ¸ina necesit ˘a mai multe cunos ¸tiint ¸e, o reprezentare com-
plex˘a a cunos ¸tiint ¸elor s ¸i algoritmi complicat ¸i pentru gestionarea sarcinilor banale. Acesta
este motivul pentru care IA lucreaz ˘a acum mai bine ˆın domeniul sarcinii expert, deoarece
domeniul de activitate al expert ¸ilor necesit ˘a cunos ¸tiint ¸e de specialitate, care pot fi mai us ¸or
de reprezentat s ¸i de manipulat.

Capitolul 2
Aplicat ¸iiIA
2.1 Domenii ˆın care este folosit ˘a IA
Inteligent ¸a Artificial ˘a a fost dominant ˘aˆın diverse domenii. Iat ˘a o scurt ˘a enumerare a c ˆatorva
din domeniile ˆın care este s ¸i va fi folosit ˘a Inteligent ¸a Artificial ˘a:
Gaming – Inteligent ¸a artificial ˘a joac ˘a un rol crucial ˆın jocurile strategice, cum ar fi
sahul, pokerul, tic-tac-toe etc., unde mas ¸ina poate s ˘a se g ˆandeasc ˘a la un num ˘ar mare
de pozit ¸ii posibile bazate pe cunos ¸tint ¸e euristice.
Procesarea limbajului natural – Este posibil s ˘a interact ¸ionat ¸i cu computerul care ˆınt ¸elege
limba natural ˘a vorbit ˘a de oameni.
Sisteme expert – Un sistem expert este format dintr-o colect ¸ie de programe s ¸i de
informat ¸ii specifice, cu ajutorul caror ˘a se poate purta un dialog om-computer, ˆın ceea
ce prives ¸te rezolvarea problemelor. Exist ˘a cateva aplicat ¸ii care integreaz ˘a informat ¸ii
despre mas ¸in ˘a, software s ¸i informat ¸ii speciale pentru a da rat ¸ionament s ¸i consiliere.
Acestea ofer ˘a explicat ¸ii s ¸i sfaturi utilizatorilor.
Sisteme de viziune – aceste sisteme ˆınt ¸eleg, interpreteaz ˘a s ¸iˆınt ¸elege intrarea vizual ˘a
pe computer. De exemplu:
-Un avion de spionaj face fotografii, care sunt folosite pentru a afla informat ¸ii spat ¸iale
sau h ˘art ¸i din anumite zone.
-Medicii folosesc un sistem de expertiz ˘a clinic ˘a pentru a diagnostica pacientul.
-Polit ¸ia foloses ¸te un software pe calculator care recunoas ¸te chipul criminalului cu por-
tretul stocat de c ˘atre medicul legist.
6

CAPITOLUL 2. APLICAT ¸ II IA 7
Recunoas ¸terea limbajului natural – Unele sisteme inteligente sunt capabile s ˘a asculte
s ¸i s˘aˆınt ¸eleag ˘a limba ˆın termeni de propozit ¸ii s ¸i de semnificat ¸ii, ˆın timp ce un om
vorbes ¸te cu el. Se poate descurca cu accente diferite, cu cuvinte de argou, cu zgomot
pe fundal, cu schimbarea zgomotului uman cauzat de frig, etc.
Recunoas ¸terea scrierii de m ˆan˘a – Software-ul de recunoas ¸tere a scrierii de m ˆan˘a
cites ¸te textul scris pe h ˆartie sau pe ecran de un stiloul(exemplu: stiloul pentru ta-
blete). Poate recunoas ¸te formele literelor s ¸i le convertes ¸te ˆın text editabil.
Robot ¸ii inteligent ¸i – Robot ¸ii sunt capabili s ˘aˆındeplineasc ˘a sarcini date de un om. Ei
au senzori pentru a detecta date fizice din lumea real ˘a, cum ar fi lumina, caldura, tem-
peratura, miscarea, sunetul, ciocnirea s ¸i presiunea. Ei au procesoare eficiente, senzori
multipli s ¸i memorie imens ˘a, pentru a expune inteligent ¸a. In plus, ei sunt capabili s ˘a
ˆınvet ¸e din gres ¸elile lor s ¸i se pot adapta noului mediu.
Agent ¸ii – sunt entit ˘at ¸i computerizate care act ¸ioneaz ˘aˆın locul unui operator uman,
adun ˆand informat ¸ii de pe Internet, trimit ¸ ˆand mesaje pe e-mail sau filtr ˆandu-le pe cele
primite. Des ¸i funct ¸ioneaz ˘a pe baza unor ,,cuvinte cheie” s ¸i sunt ˆınc˘aˆın cercetare,
agent ¸ii vor deveni foarte utili, fiind de ajutor utilizatorului ca acesta s ˘a gaseasc ˘a,
de exemplu, numai s ¸tirile sau articolele care ˆıl intereseaz ˘a, astfel scutindu-l de ore
ˆıntregi de navigare inutil ˘a pe Internet.
Ret ¸ele neuronale – sunt sisteme care simuleaz ˘a inteligent ¸a prin reconstruirea tipurilor
de conexiuni fizice care se afl ˘aˆın creierul biologic. Din cauza limitelor impuse de
tehnologie, num ˘arul acestor conexiuni este foarte mic, ˆın comparat ¸ie cu cele c ˆateva
zeci de miliarde de conexiuni din creierul uman;
2.2 Aplicat ¸ii de ultim ˘a or˘aˆın IA
S˘a discut ˘am acum despre unele dintre aplicat ¸iile de ultim ˘a or˘a din inteligent ¸a artificial ˘a. IA
atinge multe aspecte ale viet ¸ii noastre.
Prima aplicat ¸ie la care ne putem g ˆandi este recunoas ¸terea vocii, ˆın care avem asistent ¸i
virtuali cum ar fi Siri de la Apple, Echo din Amazon,Google Now sau Cortana de la
Microsoft. Aces ¸ti asistent ¸i virtuali sar ˆın ajutorul utilizatorului f ˘acˆand diverse lucruri
cum ar fi: trimiterea unui e-mail, efectuarea unei program ˘ari la doctor, g ˘asirea unui
restaurant, realizarea unei comenzi pizza sau a unei mas ¸ina Uber, va spune vremea s ¸i

CAPITOLUL 2. APLICAT ¸ II IA 8
multe altele. Deci, acest tip de tehnologie utilizeaz ˘a ret ¸ele neuronale profunde pentru
a trata limbajul natural, prin ˆınt ¸elegerea s ¸i recunoas ¸terea vocii. ˆInc˘a se fac progre-
se bune ˆın acest domeniu, dar deocamdat ˘a le putem folosi doar adres ˆandˆıntreb ˘ari
simple.
A doua aplicat ¸ie popular ˘a este recunoas ¸terea scrisului de m ˆan˘a. La mijlocul anilor
’90, USPS, US Postal Services au devenit foarte interesat ¸i de sortarea automat ˘a a
adreselor scrise manual s ¸i a codurilor zip de pe plicuri. P ˆan˘a la sf ˆars ¸itul anilor ’80,
Yann LeCun, care este un cercetator eminent, face o descoperire profund ˘a cu aju-
torul ret ¸elor neuronale s ¸i astfel a publicat o solut ¸ie utiliz ˆand ret ¸ele neuronale pentru
recunoas ¸terea cifrelor scrise manual pe un plic. Aceeas ¸i metoda a fost abordat ˘a s ¸i
prentru recunoas ¸terea cifrelor de pe un CEC ˆın mas ¸inile ATM, prin urmare at ˆat s ¸i
pentru ˆıntregul proces de recunoas ¸tere a codurilor pos ¸tale s ¸i a sumelor de dolari de
pe CEC-uri. Verific ˘arile fii astfel complet automatizate s ¸i efectiv astfel s-au salvat
milioane de dolari pentru societate.
A treia aplicat ¸ie popular ˘a a inteligent ¸ei artificiale care este utilizat ˘a cu succes de mili-
oane de oameni este traducerea automat ˘a. Traducerea mecanic ˘a cu ajutorul mas ¸inilor
a existat ˆınc˘a de la ˆınceputul inteligent ¸ei artificiale, iar motivat ¸ia istoric ˘a a reprezentat-
o guvernul american care a vrut sa traduc ˘a un text rus ˆın limba englez ˘a. Din p ˘acate,
primul sistem utilizat pentru ceea ce numim noi traducere mecanic ˘a sau corespondet ¸ ˘a
unu-la-unu a es ¸uat complet. Traducerea automat ˘a a trecut prin urcus ¸uri s ¸i cobor ˆas ¸uri.
Ast˘azi traducerea automat ˘a a devenit statistic ˘a s ¸i vorbim despre traducerea automat ˘a
a mas ¸inilor care utilizeaz ˘a o cantitate vast ˘a de texte traduse disponibile (exemple:
din punct de vedere online, avem acces la o mult ¸ime de texte de la guvern, s ¸tiri etc
publicate at ˆatˆın limba rom ˆan˘a, cˆat s ¸i ˆın alte limbi). Des ¸i exist ˘a loc de ˆımbun ˘at˘at ¸iri,
traducerea automat ˘a a f˘acut progrese semnificative, iar una din aplicat ¸iile online de
traducere pe care o folosim cu tot ¸ii este ceea Google (Google Translate), care ˆın
momentul actual se poate ocupa de peste 100 de limbi.
A patra aplicat ¸ie popular ˘a evident a inteligent ¸ei artificiale este robotica. Cunoas ¸tem
ast˘azi nis ¸te robot ¸i precum Nao s ¸i Asimo. ˆIn ultimii ani s-au f ˘acut progrese semnifi-
cative, robot ¸ii fiind important ¸i ˆın aplicat ¸ii cum ar fi chirurgia robotica etc.
A cincea aplicat ¸ie a inteligent ¸ei artificiale care ar putea s ˘a ne suprind ˘a este System
Recomander. Aceste sunt sisteme de recomandare cum ar fi sistemele de recoman-
dare Netflix sau sistemul de recomandare de la Amazon care foloses ¸te filtrarea co-
laborativ ˘a pentru a examina istoria achizit ¸iilor dumneavoastr ˘a s ¸i istoria altor client ¸i

CAPITOLUL 2. APLICAT ¸ II IA 9
pentru a putea face recomand ˘ari. De exemplu, dac ˘a cump ˘arat ¸i un computer, Amazon
ar putea sugera at ˆat persoanele care au fost interesate de acel produs sau chiar l-au
achizit ¸ionat, c ˆat s ¸i produse care pot fi cump ˘arate pentru computer (tastatur ˘a, mouse,
boxe etc.). Acesta este de fapt nucleul sistemelor de recomandare, adic ˘a s˘a utilizeze
date s ¸i s ˘aˆınvet ¸e de la ele s ˘a fac ˘a astfel de recomand ˘ari. Acest tip de sistem il pu-
tem reg ˘asi chiar ˆın e-mail. Exist ˘a un filtru de spam ˆın e-mail, care ajut ˘a la sortarea
e-mailurilor dac ˘a acestea sunt spam sau non-spam. Acestea folosesc unele tehnici,
cum ar fi clasificatorii Bayes.
O alt ˘a aplicat ¸ie folosit ˘a pe scar ˘a larg ˘a s ¸i reus ¸it ˘a a inteligent ¸ei artificiale este detectarea
fet ¸ei. Tot ¸i folosim un smartphone pentru a face fotografii prietenilor, familiei etc.
Ori de c ˆate ori facem asta vom observa pe ecran lucruri gen dreptunghiuri ˆın jurul
fet ¸elor care indic ˘a detectarea, exist ˆand o metoda precis ˘a s ¸i rapid ˘a care face acest
lucru. Acest ˘a metod ˘a este numit ˘a Viola Johns, numit ˘a dup ˘a inventatorii lui, Paul
Viola s ¸i Michael Johns care au scris o lucrare despre aceast ˘a metodologie ˆın cadrul
unei conferint ¸e privind viziunea pe calculator s ¸i recunoas ¸terea modelelor ˆın 2001.
Aceasta a fost una dintre cele mai de succes aplicat ¸ii ale inteligent ¸ei artificiale.

Capitolul 3
Agent¸i inteligent ¸i s¸i c˘autare neinformat ˘a
3.1 Agent ¸i Inteligent ¸i
Un agent este orice poate fi v ˘azut ca percep ˆand mediul ˆınconjur ˘ator prin intermediul sen-
zorilor s ¸i care act ¸ioneaz ˘a asupra acelui mediu prin intermediul dispozitivelor de act ¸ionare.
Un agent poate fi reprezentat cu aceast ˘a diagram ˘aˆın care noi avem mediul s ¸i agentul.
Agentul det ¸ine nis ¸te senzori care ˆıl ajut ˘a s˘a simt ˘a mediul ˆınconjur ˘ator s ¸i primes ¸te percept ¸ii
de la acesta.
Agentul poate avea de asemenea actuatori care act ¸ioneaz ˘a asupra acelui mediu, acele
act ¸iuni generatoare sunt decizia ce trebuie luat ˘a s ¸i generarea de act ¸iuni.
Deci, prima parte de aici permite agentului de fapt s ˘a simt ˘a lumea, cu alte cuvinte s ˘a
simt˘a lumea ˆın care evolueaz ˘a. Cea dea doua parte este de a act ¸iona asupra acestei lumi.
In mijloc, avet ¸i un produs ˆın care agentul dat fiind ceea ce observ ˘a sau simte din lumea
ˆınconjur ˘atoare, va g ˆandi, va delibera sau va decide un alt termen pentru a decide ceea ce s ˘a
fac˘a pe baza a ceea ce simte.
Deci, ˆın general, at ¸i putut vedea asta ca un ciclu pentru agent ˆın care percepe mediul,
gˆandes ¸te sau hotaras ¸te ce s ˘a fac ˘a, act ¸ioneaz ˘a s ¸i as ¸a mai departe. As ¸a c ˘a avem un fel de bucl ˘a
sau ciclu care se ˆıntampl ˘aˆın cazul percept ¸iei, g ˆandirii sau act ¸iunii asupra acelui mediu.
10

CAPITOLUL 3. AGENT ¸ I INTELIGENT ¸ I S ¸I C ˘AUTARE NEINFORMAT ˘A 11
Ultimul aspect care trebuie ment ¸ionat pentru agent este ca acestea sunt de fapt alc ˘atuite
din dou ˘a componente principale:
Arhitectura – arhitectura este partea fizic ˘a, caseta (omulet ¸ul) numit ˘a agent din figura
de mai sus s ¸i de care apart ¸ine setul de senzori s ¸i dispozitive de act ¸ionare. Acesta fiind
obiectul fizic care este legat de agent sau este hardware-ul agentului ˆınsus ¸i.
Sistemul sau programul- sistemul este de fapt mintea agentului. Aici se desfas ¸oar ˘a
deliberarea, g ˆandirea.
Avem astfel dou ˘a componente principale care nu sunt numai gratuite, dar trebuie s ˘a fie
s ¸i compatibile. Deci, programul este limitat de arhitectur ˘a s ¸i trebuie s ˘a lucreze ˆımpreun ˘aˆın
armonie.
S˘a lu˘am un exemplu foarte simplu agent.
Agentul de cur ˘at ¸are care evolueaz ˘aˆıntr-un mediu mic ˆın care avem dou ˘a camere, ca-
mera A s ¸i camera B s ¸i eventual unele murd ˘ariiˆın camere pentru a le cur ˘at ¸a. Deci percept ¸ia
aspiratorului ˆın acest mediu este locat ¸ia s ¸i ceea ce cont ¸ine camera.
De exemplu, dac ˘a aspiratorul are doi senzori, un senzor pentru murd ˘arie s ¸i un sen-
zor pentru locat ¸ie, ar putea crea o percept ¸ie ca o pereche. A, murdar, de exemplu, este o
percept ¸ie care spune ca, camera A este murdar ˘a. Act ¸iunea pe care aspiratorul o realizeaz ˘a
este de a merge la st ˆanga, merge la dreapta, aspir ˘a mizeria sau nu face nimic dac ˘a totul este
curat. ˆIn final, definim de fapt o funct ¸ie de agent care este de fapt o cartografiere ˆıntre setul
de percept ¸ii s ¸i setul de act ¸iuni.
Am putea scrie ˆıntr-un tabel care are de fapt o hart ˘aˆıntre percept ¸ii s ¸i act ¸iuni. De exem-
plu, dac ˘a A este curat ¸ ˘a, atunci merget ¸i drept. Daca A este murdar, aspir ˘a murdaria. Daca
B este curat, merget ¸i la st ˆanga, apoi verificat ¸i dac ˘a exist ˘a murd ˘arieˆın stanga s ¸i dac ˘a B este
murdar atunci aspir ˘a.
Aceasta este o act ¸iune simpl ˘a, perechi de tabele ˆın care avem percept ¸ii simple, nu o
succesiune de cuvinte, ci doar percept ¸ii s ¸i act ¸iuni corespunz ˘atoare. Agentul caut ˘aˆın aceste
tabele s ¸i asociaz ˘a la ceea ce percepe din mediul ˆınconjur ˘ator prin senzorii s ˘ai pentru a defini
ceea ce face.
Deci, am putea face masa asta mai larg ˘a, nu numai p ˘astrˆand o singur ˘a percept ¸ie, av ˆand
de aceasta dat ˘a combinat ¸ii de percept ¸ii sau secvent ¸e de percept ¸ii. De exemplu: dac ˘a A era
murdar s ¸i apoi A, devine curat, ce s ˘a fac? . Deci prin extinderea acestei mese nu numai ca
mentinem percept ¸ia, dar s ¸i secvent ¸ele percept ¸iilor. As ¸adar, suntem interesat ¸i de agent ¸i care
se pot comport ˘a bine, aces ¸tia sunt rat ¸ionali care sunt definit ¸i ˆın conformitate cu Russell s ¸i
Norvig dup ˘a cum urmeaz ˘a: ,, Pentru fiecare secvent ¸ ˘a perceptiv ˘a posibil ˘a, un agent rat ¸ional

CAPITOLUL 3. AGENT ¸ I INTELIGENT ¸ I S ¸I C ˘AUTARE NEINFORMAT ˘A 12
ar trebui s ˘a aleag ˘a o act ¸iune pe care o face, fiind de as ¸teptat s ˘a maximizeze m ˘asura de
performant ¸ ˘a. Av ˆandˆın vedere dovezile furnizate de succesiunea percept ¸iei, agentul are
orice cunostint ¸ ˘a de baz ˘a sau cunostint ¸ ˘a de capacitate ”.
Ca acest agent s ˘a fie rat ¸ional el trebuie ia doar decizii corecte fiind dotat cu inteligent ¸ ˘a
bazat ˘a pe logic ˘a: cunoas ¸terea prealabil ˘a a mediului, posibilele act ¸iuni pe care agentul le
poate efectua s ¸i ˆın final secvent ¸a de predict ¸ie a agentului p ˆan˘aˆın prezent.
Experient ¸a agentului este ˆımpart ¸it ˘aˆın episoade atomice. Fiecare episod const ˘aˆın perce-
perea agentului s ¸i apoi efectuarea unei singure act ¸iuni. Alegerea act ¸iunii ˆın fiecare episod
depinde doar de episodul ˆınsus ¸i.
Structura unui agent inteligent poate fi privit ˘a ca:
– Agent =arhitectur ˘a+program agent;
– Arhitectur ˘a=mas ¸inile pe care un agent execut ˘a;
– Program agent =o implementare a unei funct ¸ii agent.
Arhitectur ˘a agent ¸i
Agent bazat pe tabele – act ¸iunile specifice declans ¸ate de efectori s ¸i percept ¸iile ca-
re achizit ¸ioneaz ˘a informat ¸iile sunt organizate ˆın tabele. Tabelul reprezint ˘a cea mai
simpl ˘a cale de a realiza o corespondent ¸ ˘a dintre senzori s ¸i act ¸iuni.
Agent bazat pe percept ¸ie – starea curent ˘a a agent ¸ilor poate fi schimbat ˘a prin informat ¸iile
primite de la senzori s ¸i determin ˘a act ¸iuni directe prin intermediul efectorilor. Agent ¸ii
fiind numit ¸i agent ¸i stimul-r ˘aspuns sau reactivi.
Agent bazat pe st ˘ari – starea lumii interioare a agentului poate fi schimbat ˘a prin
achizit ¸ionarea informat ¸iilor prin intermediul percept ¸iilor. Pe baza acestora, agentul
pornes ¸te act ¸iuni prin efectori.
Agent bazat pe scop – Scopurile agentului reprezint ˘a act ¸iunile acestuia. Rezolvarea
unei probleme ˆın IA care ofer ˘a multe moduri de rezolvare reprezint ˘a atingerea unui
scop.
Agent bazat pe utilitate – Pentru maximizarea utilitat ¸ii dorite, agentul react ¸ioneaz ˘aˆın
mod specific.
Agent care ˆınvat ¸ ˘a – Agent ¸ii prin ˆınv˘at ¸are pot opera ˆın medii necunoscute.

CAPITOLUL 3. AGENT ¸ I INTELIGENT ¸ I S ¸I C ˘AUTARE NEINFORMAT ˘A 13
Natura mediului
Unele programe funct ¸ioneaz ˘aˆıntr-un mediu complet artificial, limitat la intrarea tasta-
turii, la baza de date, la sistemele de fis ¸iere pe computer s ¸i la ies ¸irea caracterelor pe ecran.
In schimb, unii agent ¸i de software (robot ¸i software sau softbot-uri) exist ˘aˆın domenii
bogate, nelimitate ˆın softbot. Simulatorul are un mediu foarte detaliat, complex. Agentul
software trebuie s ˘a aleag ˘a dintr-o gam ˘a lung ˘a de act ¸iuni ˆın timp real. Un softbot conce-
put pentru a scana preferint ¸ele online ale clientului s ¸i a arat ˘a elemente interesante pentru
lucr˘arile clientului at ˆatˆın mediul real, c ˆat s ¸i in cel artificial.
Cel mai cunoscut mediu artificial este testul Turing, ˆın care un agent real s ¸i alte substant ¸e
artificiale sunt testate pe teren egal. Acesta este un mediu foarte provocator, deoarece este
extrem de dificil ca un agent software s ˘a se comporte, precum un om.
Turing Test
Succesul unui comportament inteligent al unui sistem poate fi m ˘asurat cu testul Turing.
Dou˘a persoane s ¸i o mas ¸ina care urmeaz ˘a s˘a fie evaluate particip ˘a la test. Din cele dou ˘a
persoane, unul joac ˘a rolul testerului. Fiecare dintre ele se afl ˘aˆın camere diferite. Testerul nu
s ¸tie care este mas ¸ina s ¸i cine este omul. El interogheaz ˘aˆıntreb ˘arile prin tastarea s ¸i trimiterea
lor la ambele mas ¸ini, de la care primes ¸te raspuns ¸uri tip ˘arite.
Acest test are scopul de a p ˘ac˘ali testerul. Dac ˘a testerul nu reus ¸es ¸te s ˘a determine r ˘aspunsul
mas ¸inii de la r ˘aspunsul uman, atunci se spune c ˘a mas ¸ina este inteligent ˘a.
3.2 Agent ¸i de c ˘autare
Russell s ¸i Norvig au realizat un grup de cinci agent ¸i de c ˘autare, clasificare realizat ˘a pe baza
gradului lor de inteligent ¸ ˘a s ¸i capacitate:
Agent ¸i reflex simpli – act ¸ioneaz ˘a numai pe baza percept ¸iei curente, ignor ˆand restul
istoriei percept ¸iei. Funct ¸ia agent se bazeaz ˘a pe regula condit ¸ie-act ¸iune: dac ˘a condit ¸ia
este respectat ˘a, apoi act ¸ioneaz ˘a.

CAPITOLUL 3. AGENT ¸ I INTELIGENT ¸ I S ¸I C ˘AUTARE NEINFORMAT ˘A 14
Agent ¸i bazat ¸i pe obiective – agent ¸ii bazat ¸i pe obiective se extind si mai mult pe
capabilitat ¸ile agent ¸ilor bazat ¸i pe modele, utiliz ˆand informat ¸iile ,,t ¸int ˘a ”. Informat ¸iile
despre obiective descriu situat ¸iile care sunt de dorit. Acest lucru permite agentu-
lui sa aleag ˘aˆıntre mai multe posibilit ˘at ¸i, select ˆand cel care va atinge starea unui
gol. C ˘autarea s ¸i planificarea sunt subdomeniile inteligent ¸ei artificiale dedicate gasirii
secvent ¸elor de act ¸iune care ating obiectivele agentului.
Agent ¸i reflex pe baz ˘a de model – Un agent bazat pe modele poate gestiona medii
part ¸ial observabile. Starea sa actual ˘a este stocat ˘aˆın interiorul agentului, ment ¸in ˆand un
fel de structur ˘a care descrie partea din lume care nu poate fi vazut ˘a. Un agent reflex
bazat pe model ar trebui sa mentin ˘a un fel de model intern care depinde de istoria
percept ¸iei s ¸i prin urmare reflect ˘a cel put ¸in unele dintre aspectele nev ˘azute ale st ˘arii
actuale. Percept ¸ia istoricului s ¸i impactul act ¸iunii asupra mediului pot fi determinate
prin utilizarea modelului intern. Apoi alege o act ¸iune ˆın acelas ¸i mod ca s ¸i agentul
reflex.

CAPITOLUL 3. AGENT ¸ I INTELIGENT ¸ I S ¸I C ˘AUTARE NEINFORMAT ˘A 15
Agent ¸i bazat ¸i pe utilit ˘at ¸i- Obiectivele pe baz ˘a de agent ¸i disting doar st ˘arile de t ¸int ˘a
s ¸i st˘arile non-t ¸int ˘a. Este posibil s ˘a se defineasc ˘a o m ˘asur˘a a modului ˆın care este de
dorit ˘a o anumit ˘a stare. Aceast ˘a masur ˘a poate fi obt ¸inut ˘a prin utilizarea unei funct ¸ii de
utilitate care cartografiaz ˘a o stare la o m ˘asur˘a a utilit ˘at ¸ii statutului. Un agent rat ¸ional
de utilitate alege act ¸iunea care maximizeaz ˘a utilitatea as ¸teptat ˘a a rezultatelor act ¸iunii
– adic ˘a ceea ce agentul se as ¸teapt ˘a s˘a obt ¸in ˘a,ˆın medie, av ˆandˆın vedere probabi-
lit˘at ¸ile s ¸i utilit ˘at ¸ile fiec ˘arui rezultat. Un agent bazat pe utilit ˘at ¸i trebuie s ˘a modeleze
s ¸i s˘a urm ˘areasc ˘a mediul s ˘au, sarcinile care au implicat o mare parte din cercetarea
percept ¸iei, reprezent ˘arii, rat ¸ionamentului s ¸i a ˆınv˘at ¸arii.
Agent ¸i de ˆınv˘at ¸are -ˆınv˘at ¸are are avantajul c ˘a permite agent ¸ilor s ˘a opereze init ¸ial ˆın
medii necunoscute s ¸i s ˘a devin ˘a mai competent ¸i dec ˆat ar putea permite cunos ¸tiint ¸ele
init ¸iale.Cea mai important ˘a distinct ¸ie este ˆıntre ,,elementul de ˆınv˘at ¸are”, care este
responsabil pentru realizarea ˆımbun ˘at˘at ¸irilor, s ¸i ,,elementul de performant ¸ ˘a”, care
este responsabil pentru selectarea act ¸iunilor externe. Elementul de ˆınv˘at ¸are utilizeaz ˘a
feedback de la ,,critic” cu privire la modul ˆın care agentul face s ¸i determin ˘a modul

CAPITOLUL 3. AGENT ¸ I INTELIGENT ¸ I S ¸I C ˘AUTARE NEINFORMAT ˘A 16
ˆın care elementul de performant ¸ ˘a ar trebui s ˘a fie modificat pentru a face mai bine
ˆın viitor. Elementul de performant ¸ ˘a este cel pe care l-am considerat anterior ˆıntreg
agentului: este nevoie de percept ¸ii s ¸i el decide act ¸iunile.
Ultima component ˘a a agentului de ˆınv˘atare este ,,generatorul de probleme”. Este res-
ponsabil pentru sugerarea unor act ¸iuni care vor duce la experient ¸e noi s ¸i informative.
3.3 C ˘autare neinformat ˘a
C˘autarea neinformat ˘a utilizeaz ˘a un domeniu necunoscut.
Exist ˘a strategii diferite adoptate ˆıntr-o c ˘autare neinformat ˘a:
1. Breadth-first search (BFS) – extinde cel mai ad ˆanc nod, c ˘autarea ˆın l˘at ¸ime;
2. Depth-first search (DFS) – extinde cel mai ad ˆanc nod, c ˘autarea ˆın ad ˆancime (am putea
face o combinat ¸ie ˆın care avem o c ˘autare ˆın profunzime cu o anumit ˘a list ˘a. C˘autarea
iterativ ˘a permite aprofundarea);
3. Depth-limited search (DLS) – impunerea unei limite de ad ˆancime pe care DFS o
poate atinge, c ˘autarea limitat ˘aˆın ad ˆancime;
4. Iterative-deepening search (IDS) – DSL cu limit ˘a cresc ˘atoare;
5. Uniform-cost search (UCS) – extinde nodul cu cel mai mic cost;

CAPITOLUL 3. AGENT ¸ I INTELIGENT ¸ I S ¸I C ˘AUTARE NEINFORMAT ˘A 17
3.3.1 Breadth-first search (BFS)
C˘autare ˆın l˘at ¸ime (BFS) este un algoritm pentru traversarea sau c ˘autarea structurilor de
date ale arborilor sau grafurilor. ˆIncepe de la r ˘ad˘acina arborelui (sau un nod arbitrar al unui
grafic, uneori denumit ,,cheia de c ˘autare”) s ¸i exploreaz ˘a mai ˆıntˆai nodurile vecine, ˆınainte
de a trece la vecinii de la nivel urm ˘ator.
Descriere:
– O strategie simpl ˘aˆın care r ˘ad˘acina este extins ˘a mai ˆıntˆai, apoi tot ¸i succesorii r ˘ad˘acinilor
sunt extins ¸i ˆın continuare, apoi succesorii lor;
– Vizit ˘am nivelul arborelui de c ˘autare dup ˘a nivel, astfel ˆıncˆat toate nodurile s ˘a fie extinse
la o anumit ˘a adˆancime ˆınainte ca orice alte noduri de la nivelul urmator s ˘a fie extinse;
– Ordinea ˆın care nodurile sunt extinse.
Algorithm 1 Algoritm: BFS search
1:function BREADTH-FIRST-SEARCH(initialState, goalTest)
2:returns Succes orFailure :
3:frontiere =Queue.new(initialState)
4:explored =Set.new()
5:While not frontier.isEmpty():
6:state =frontier.dequeue()
7:explored.add(state)
8:ifgoalTest(state):
9:return Succes(state)
10:forneighbor instate.neighbors():
11:ifneighbor not in frontier[explored:
12:frontier.enqueue(state)
13:return Failure :
Aceasta reprezint ˘a coada de la frontier ˘a. Coada este de obicei o list ˘a ordonat ˘a cu ele-
mente similare care sunt ˆın ordinea numit ˘a FIFO(first-in first-out). Am as ¸ezat elementele

CAPITOLUL 3. AGENT ¸ I INTELIGENT ¸ I S ¸I C ˘AUTARE NEINFORMAT ˘A 18
ˆın asteptare pentru a fi testate, ˆıncep ˆand cu partea frontal ˘a a cozii. Act ¸iuniile care sunt luate
din fat ¸ ˘a se numesc dequeue , iar act ¸iunile de punere ˆın spatele cozii se numesc enqueue .
3.3.2 Depth-first search (DFS)
C˘autarea ˆın ad ˆancime (DFS) este un algoritm pentru traversarea sau c ˘autarea structurilor
de date ale arborilor sau grafurilor. Unul pornes ¸te de la r ˘ad˘acin˘a (select ˆand un nod arbitrar
ca r˘ad˘acin˘aˆın cazul unui grafic) s ¸i exploreaz ˘a, pe c ˆat posibil, de-a lungul fiecarei ramuri,
ˆınainte de backtracking.
Descriere:
– DFS progreseaz ˘a prin extinderea primului nod copil al arborelui de c ˘autare care apare
s ¸i, astfel, merge mai ad ˆanc s ¸i mai profund p ˆan˘a la g ˘asirea unui nod t ¸int ˘a sau p ˆan˘a cˆand
acesta atinge un nod care nu are copii. Apoi, backtrack-urile de c ˘autare, revenind la cel mai
recent nod, f ˘ar˘a a termina c ˘autarea;
-Ordinea ˆın care nodurile sunt extinse.
Algoritmul DFS este similar cu BFS, chiar dac ˘a ele sunt totus ¸i diferite. Aici nu mai
utiliz ˘am o coad ˘a, deoarce o coad ˘a merge pe principiul FIFO(first-in first-out).
DFS utilizeaz ˘a o structur ˘a de date de tip stiv ˘a. O stiv ˘a este un tip de date abstract care
serves ¸te ca o colect ¸ie de elemente, cu dou ˘a operat ¸ii principale: push , care adaug ˘a un ele-
ment la colect ¸iei s ¸i pop, care elimin ˘a elementul cel mai recent ad ˘augat care nu a fost ˆınc˘a
eliminat. Ordinea ˆın care elementele se descarc ˘a dintr-o stiv ˘a d˘a nas ¸tere la denumirea sa
alternativ ˘a, LIFO ( last-in first-out). ˆIn plus, o operat ¸iune de vizualizare poate oferi acces
ˆın partea de sus f ˘ar˘a a modifica stiva.

CAPITOLUL 3. AGENT ¸ I INTELIGENT ¸ I S ¸I C ˘AUTARE NEINFORMAT ˘A 19
Algorithm 2 Algoritm: DFS search
1:function DEPTH-FIRST-SEARCH(initialState, goalTest)
2:returns Succes orFailure :
3:frontiere =Stack.new(initialState)
4:explored =Set.new()
5:While not frontier.isEmpty():
6:state =frontier.pop()
7:explored.add(state)
8:ifgoalTest(state):
9:return Succes (state)
10:forneighbor instate.neighbors():
11:ifneighbor not in frontier[explored:
12:frontier.push(state)
13:return Failure :
3.3.3 Uniform-cost search (UCS)
C˘autarea cu cost uniform (UCS) este cel mai bun algoritm pentru o problem ˘a de c ˘autare,
care nu implic ˘a utilizarea euristicii. Se poate rezolva orice grafic general pentru costuri
optime.
Descriere:
– Costul uniform este ghidat de costul c ˘aii, mai degrab ˘a dec ˆat de lungimea traseului, ca
ˆın BFS, algoritmii ˆıncep prin extinderea r ˘ad˘acinii, apoi extinderea nodului cu cel mai mic
cost din r ˘ad˘acin˘a, c˘autarea continu ˘aˆın acest mod pentru toate nodurile;
– O sugestie pentru implementarea c ˘autarii cu cost uniform este algoritmul lui Dijkstra.
Algoritmul lui Dijkstra este un algoritm folosit pentru g ˘asirea celor mai scurte c ˘aiˆıntre
noduri unui grafic, care poate reprezenta, de exemplu, ret ¸elele rutiere;
Algoritmul lui Dijkstra are dou ˘a variante cunoscute: – varianta original ˘a a lui Dijkstra
este de a g ˘asit calea cea mai scurt ˘a dintre dou ˘a noduri; – varianta cea mai comun ˘a fixeaz ˘a
un singur nod ca nod ,,surs ˘a” s ¸i gases ¸te cele mai scurte c ˘ai de la surs ˘a c˘atre toate celelalte
noduri din grafic, produc ˆand un arbore cu cea mai scurt ˆa cale .
– Algoritmul lui Dijkstra poate fi privit ca fiind o variant ˆa a c ˆautarii cu cost uniform,
unde nu exist ˆa nici o stare a t ¸elului s ¸i prelucrarea continu ˘a pˆan˘a cˆand calea cea mai scurt ˘a
c˘atre toate nodurile a fost determinat ˘a.

CAPITOLUL 3. AGENT ¸ I INTELIGENT ¸ I S ¸I C ˘AUTARE NEINFORMAT ˘A 20
Algorithm 3 Algoritm:UCS search
1:function UNIFORM-COST SEARCH(initialState, goalTest)
2:returns Succes orFailure :
3:frontiere =Heap.new(initialState)
4:explored =Set.new()
5:While not frontier.isEmpty():
6:state =frontier.deleteMin()
7:explored.add(state)
8:ifgoalTest(state):
9:return Succes (state)
10:forneighbor instate.neighbors():
11:ifneighbor not in frontier[explored:
12:frontier.insert(state)
13:else if neighbor infrontier:
14:frontier.decreaseKey(neighbor)
15:return Failure :
C˘autare cu cost uniform necesit ˘a din nou utilizarea unei cozi de priorit ˘at ¸i. Amintit ¸i-v ˘a
c˘a funct ¸ia First Search Depth a folosit o coad ˘a prioritar ˘a cu ad ˆancimea p ˆan˘a la un nod
special fiind prioritatea, iar calea de la r ˘ad˘acin˘a la nodul fiind elementul stocat. Coada de
priorit ˘at ¸i folosit ˘a aici este similar ˘a cu prioritatea fiind costul cumulat p ˆan˘a la nod. Spre deo-
sebire de prima c ˘autare ˆın profunzime, unde ad ˆancimea maxim ˘a a avut prioritatea maxim ˘a,
uniformizarea costului de c ˘autare d ˘a costul cumulat minim pentru prioritatea maxim ˘a.

Capitolul 4
C˘autare euristic ˘a(informat ˘a)
ˆIn domeniul informaticii, al inteligent ¸ei artificiale s ¸i al optimiz ˘arii matematice, o euris-
tic˘a este o tehnic ˘a conceput ˘a pentru rezolvarea mai rapid ˘a a unei probleme atunci cand
metodele clasice sunt prea lente sau pentru g ˘asirea unei solut ¸ii aproximative atunci c ˆand
metodele clasice nu g ˘asesc nici o solut ¸ie exact ˘a. Acest lucru se realizeaz ˘a prin optimizarea
tranzact ¸ionarii, completitudinea, acuratet ¸ea sau precizia vitezei. Intr-un fel, poate fi consi-
derat ˘a o scurt ˘atur˘a.
O funct ¸ie euristic ˘a, denumit ˘a pur s ¸i simplu o euristic ˘a, este o funct ¸ie care clasific ˘a alter-
native ˆın algoritmii de c ˘autare la fiecare pas de ramificare pe baza informat ¸iilor disponibile
pentru a decide ce ramur ˘a s˘a urmeze.
4.1 Euristici s ¸i algoritmul de c ˘autare Greedy
C˘autarea neinformat ˘a utilizeaz ˘a un domeniu cunoscut.
Exist ˘a strategii diferite adoptate ˆıntr-o c ˘autare informat ˘a:
1. Best-first search
2. Greedy best-first search
3. A*(A-star) search
4. Iterative Deepening A*(IDA*) – o variant ˘a a lui A*.
4.1.1 Best-first search
Strategia Best-First este un model teoretic s ¸i reprezentat de strategie de c ˘autare euristic ˘a
ca un ideal. Ea presupune c ˘autarea nodului s ¸i alegerea acestuia ca successor a celui mai
21

CAPITOLUL 4. C ˘AUTARE EURISTIC ˘A(INFORMAT ˘A) 22
bun nod. Pentru ca acest lucru s ˘a fie posibil avem nevoie de o funct ¸ie care s ˘a caute cel mai
bun nod, iar dac ˘a acest ˘a funct ¸ie ar exista nu ar mai fi necesar un arbore de c ˘autare fiindc ˘a
strategia de c ˘autare ar merge direct la solut ¸ie av ˆand complexitate de spat ¸iu liniar s ¸i timp.
Deci conceptul de best-first search r ˘amˆane doar un model idealizat al strategiilor euristice.
Aspecte teoretice:
.Prin intermediul unei funct ¸ii putem detemina costul fiecarei st ˘ari;
.Nodurile care trebuie s ˘a fie expandate sunt ret ¸inute ˆın cozi ordonate;
.Pentru expandare se stabiles ¸te nodul care urmeaz ˘a s˘a fie expandat, astfel aleg ˆandu-se
starea cu cea mai bun ˘a evaluare;
.Exist ˘a dou ˘a categorii de SCI de tip BFS:
– SCI care ˆıncearc ˘a s˘a expandeze nodul cel mai apropiat de starea obiectiv;
– SCI care ˆıncearc ˘a s˘a expandeze nodul din solut ¸ie cu costul cel mai mic.
Algorithm 4 Algoritm: BestFS
1:bool BestFS(elem, list) f
2:found =false;
3:visited =0;
4:toVisit =fstartg;//FIFO sorted list (priority queue)
5:while ((toVisit =0) && (!found))f
6:if(toVisit ==0)
7:return false
8:node =pop(toVisit);
9:visited =visited[fnodeg;
10:if(node ==elem)
11:found =true;
12:else
13:aux=0;
14:forall unvisited children of node dof
15:aux=aux[fchildg;g
16:toVisit =toVisit U aux; //adding a node into the FIFO list based on its //evaluation
(best one in the front of list)
17:g//while
18:return found;g

CAPITOLUL 4. C ˘AUTARE EURISTIC ˘A(INFORMAT ˘A) 23
Avantajele s ¸i dezavantajele acestui algoritm sunt:
Avantaje
– Informat ¸iile oferite despre domeniul unei probleme ajut ˘a la c ˘autare (SCI);
– Dispune de o vitez ˘a mai mare de a ajunge la starea obiectiv.
Dezavantaje
– Necesit ˘a evaluarea st ˘arilor;
– Anumite path-uri pot ,,ar ˘ata” ca fiind bune datorit ˘a funct ¸iei euristice.
Aplicat ¸ii ˆın care se poate utiliza: jocuri.
4.1.2 Greedy best-first search
Strategia Greedy alege spre cercetare ˆıntotdeauna nodul cu cea mai bun ˘a euristic ˘a(informare),
adic˘a nodul care este cel mai apropiat de starea final ˘a.ˆIn acest sens se poate face o analogie
cu strategia cu cost uniform care alege ˆıntotdeauna nodul cu costul cel mai bun. Strategia
de c˘autare cu cost uniform ret ¸ine o list ˘a sortat ˘aˆın funct ¸ie de valoarea costului, dar ˆın cazul
lui Greedy se va ret ¸ine o list ˘a sortat ˘aˆın funct ¸ie de valoarea euristicii.
Aspecte teoretice:
.Funct ¸ia de evalaure f(n) =h(n)
– evalueaz ˘a costul traseului de la starea curent ˘a la starea final ˘a h(n);
– reduce costului traseului care mai trebuie parcurs.

CAPITOLUL 4. C ˘AUTARE EURISTIC ˘A(INFORMAT ˘A) 24
Algorithm 5 Algoritm:Greedy best-first search
1:function GREEDY-BEST-FIRST-SEARCH(initialState, goalTest)
2:returns Succes orFailure :
3:frontiere =Heap.new(initialState)
4:explored =Set.new()
5:While not frontier.isEmpty():
6:state =frontier.deleteMin()
7:explored.add(state)
8:ifgoalTest(state):
9:return Succes (state)
10:forneighbor instate.neighbors():
11:ifneighbor not in frontier[explored:
12:frontier.insert(state)
13:ifneighbor infrontier:
14:frontier.decreaseKey(neighbor)
15:return Failure :
Algoritmul Greedy se implementeaz ˘a la fel ca strategia de c ˘autare cu cost uniform,
doar ca nodurile vor fi ret ¸inute intr-o list ˘a ordonat ˘a dup ˘a euristic ˘a s ¸i nu dup ˘a cost. Folo-
sind o stiv ˘a s ¸i un consum redus de memorie putem implementa s ¸i pe paradigma de la DFS
(c˘autarea ˆın ad ˆancime), dar aceasta conduce mai ˆıncet spre solut ¸ie.
Strategia greedy ˆın anumite situat ¸ii prin folosirea ciclurile conduc evident la blocaje,
pentru c ˘a strategia nu este complet ˘aˆın arbori ˆınfinit ¸i. Pentru a evita aceast ˘a blocare s ¸i ast-
fel strategia algoritmului s ˘a devin ˘a un˘a complet ˘a, trebuie utilizate mecanisme de evitare a
ciclurilor.
Avantajele s ¸i dezavantajele acestui algoritm sunt:
Avantaje
– Strategia Greedy ofer ˘a rapid solutii s ¸i practicarea acestei solut ¸ii se dovedes ¸te a fi o alegere
bun˘a atunci c ˆand nu dorim g ˘asirea unei solut ¸ii optime.
Dezavantaje
– Strategia Greedy nu este nici optim ˘a s ¸i nici complet ˘a; – Atunci c ˆand este implementat ˘a
identic cu c ˘autare cu cost uniform, aceasta poate avea nevoie de o cantitate ridicat ˘a de
memorie.

CAPITOLUL 4. C ˘AUTARE EURISTIC ˘A(INFORMAT ˘A) 25
Aplicat ¸ii ˆın care se poate utiliza: puzzle-uri, drumul optim ˆıntr-un graf etc.
4.1.3 A* (A-star)search
Strategia A* poate fi privit ˘a ca o combinat ¸ie dintre strategia de c ˘autare greedy s ¸i strategia
de c˘autare cu cost uniform, astfel A* combin ˆa cele mai bune caracteristici ale acestora. Pri-
oritatea A* este o funct ¸ie de evaluare astfel: f(n) =g(n)+h(n), unde g(n) reprezint ˘a funct ¸ia de
la c˘autarea cu cost uniform, iar h(n) reprezint ˘a euristica de la c ˘autarea Greedy. Prioritatea
este maxim ˘a atunci cand valoarea f(n) este cea mai mic ˘a.
Aspecte teoretice:
.Combinarea aspectelor pozitive ale:
– c˘autarii de cost uniform: folosirea unei cozi ordonate;
– c˘autarii Greedy: ordonare bazat ˘a pe o funct ¸ie de evaluare, rapiditatea;
.Funct ¸ia de evaluare f(n):
– calcularea costului celui mai bun traseu(drum) care trece prin nodul n;
– f(n) =g(n)+h(n);1
– g(n) costul de la starea init ¸iala la starea curent ˘a n;
– h(n) costul drumului de la starea curent ˘a n la starea final ˘a;
– diminuare costului total al unui drum.
Strategia A* se implementeaz ˘a prin folosirea unei liste sortate cresc ˘ator dup ˘a funct ¸ia f.
Aceasta poate fi complet ˘a s ¸i optim ˘a doar dac ˘a condit ¸ia euristic ˘a h(n) este admisibil ˘a.
Avantajele s ¸i dezavantajele acestui algoritm sunt:
Avantaje
– A* reprezint ˘a cea mai bun ˘a strategie de c ˘autare.
– Alte strategii risc ˘a s˘a nu gaseasc ˘a cea mai optim ˘a solut ¸ie, dac ˘a exploreaz ˘a mai put ¸ine
noduri dec ˆat A-star.
Dezavantaje
– necesit ˘a resurse mari de memorie. Pentru rezolvarea acestei probleme se poate combina
A* cu Iterative Deepening(o variant ˘a a lui A*) cunoscut ˘a sub denumirea de Iterative Dee-
pening A* (IDA*);
1https:www.inf.ed.ac.ukteachingcoursesinf2dtimetable05 Heuristics wbg.pdf

CAPITOLUL 4. C ˘AUTARE EURISTIC ˘A(INFORMAT ˘A) 26
Algorithm 6 Algoritm:A* search
1:function A*-SEARCH(initialState, goalTest)
2:returns Succes orFailure :
3:frontiere =Heap.new(initialState)
4:explored =Set.new()
5:While not frontier.isEmpty():
6:state =frontier.deleteMin()
7:explored.add(state)
8:ifgoalTest(state):
9:return Succes (state)
10:forneighbor instate.neighbors():
11:ifneighbor not in frontier[explored:
12:frontier.insert(state)
13:ifneighbor infrontier:
14:frontier.decreaseKey(neighbor)
15:return Failure :
– Atunci c ˆand este implementat ˘a identic cu c ˘autare cu cost uniform, aceasta poate avea ne-
voie de o cantitate ridicat ˘a de memorie.
Aplicat ¸ii ˆın care se poate utiliza: puzzle-uri, drumul optim ˆıntr-un graf etc.
Variante ale strategia A*: real time A*, dynamic A*, iterative deepening A* (IDA*),memory-
bounded A* (MA*) etc;

Capitolul 5
Preg˘atirea mediului de dezvoltare
1.Netbeans
Programul folosit pentru dezvoltarea aplicat ¸iei este NetBeans IDE (NetBeans este
un mediu de dezvoltare open-source scris preponderant ˆın Java. Acesta este folo-
sit pentru dezvoltarea de aplicat ¸ii ˆın Java s ¸i prin intermediul altor plug-in-uri, ˆın
alte limbaje(ex: PHP). NetBeans IDE este un mediu de dezvoltare – un instrument
pentru programatori, pentru scrierea, compilarea, testarea, depanarea, proiectarea s ¸i
instalarea programelor. Este scris ˆın Java – dar poate accepta orice limbaj de progra-
mare.). Search ,,Google” , NetBeans IDE pe browser-ul Opera si am dat pe site-ul
,,.www.netbeans.org.” ˆIn partea din dreapta a primei pagini apare un buton de ,,Dow-
loands(desc ˘arcare)”.
Dˆand click pe ,,Dowloand” va aparea ,,NetBeans IDE 8.2 Download” care va oferi
posibilitatea de a alege pentru ce tip de sistem de operare dorit ¸i s ˘a desc ˘arcat ¸i pro-
gramul. Sub aceast ˘a apare programul s ¸i obt ¸iunea pentru platforma folosit ˘a. Pentru
27

CAPITOLUL 5. PREG ˘ATIREA MEDIULUI DE DEZVOLTARE 28
platforma calculatorului meu am ales Windows, ultima obt ¸iune ,,All” care include
tot s ¸i Dowloand (221 MB).
Am dat click pe obt ¸iune s ¸i am intrat pe o pagina de unde am desc ˘arcat programul
NetBeans IDE. ˆIn urma desc ˘arcarii pe partit ¸ia ,,c in dowloands” am primit un soft.
ˆInainte de instalarea acestui soft am instalat platforma JDK s ¸i apoi soft-ul.
Instalare
(a) Am dat dublu click pe soft-ul primit anterior, asta dup ˘a instalarea platformei
JDK .
S-a deschis o fereastr ˘aˆı n care urm ˘atorul pas a fost next.

CAPITOLUL 5. PREG ˘ATIREA MEDIULUI DE DEZVOLTARE 29
(b) Am acceptat termenii s ¸i condit ¸iile s ¸i am dat next.
(c) Am ales locat ¸ia unde va fi instalat NetBeans-ul next s ¸i instal.

CAPITOLUL 5. PREG ˘ATIREA MEDIULUI DE DEZVOLTARE 30
(d) Next s ¸i Finish.
2.WampServer
Wamp (Windows Apache MySQL PHP) este un mediu de dezvoltare web Windows,
care v ˘a permite s ˘a creat ¸i s ¸i s ˘a rulat ¸i aplicat ¸ii pe un server(Apache), pe un limbaj de
baze de date (MySQL) s ¸i pe un limbaj de programare (PHP). ˆIn acelas ¸i timp, Ph-

CAPITOLUL 5. PREG ˘ATIREA MEDIULUI DE DEZVOLTARE 31
pMyAdmin v ˘a permite s ˘a v˘a administrat ¸i cu us ¸urint ¸ ˘a baza de date. Acesta contribuie
s ¸i el realizarea optim ˘a a mediului de lucru.
Baza de date (MySQL)
Wamp este un mediu de dezvoltare open-source.
Search ,,Google” , WampServer pe browser-ul Opera si am dat pe site-ul ,, http: //www.
wampserver.com /en/”.
ˆIn meniul primei pagini apare un buton de ,,Dowloands(descarcare)”. Se instaleaz ˘a,
iar dup ˘a instalare pe partit ¸ia ,,C: /” vom avea un folder cu numele wamp (aici vor
trebui dezvoltate toate aplicat ¸iile pentru a putea fi rulate pe wampserver).

CAPITOLUL 5. PREG ˘ATIREA MEDIULUI DE DEZVOLTARE 32

Capitolul 6
Prezentarea aplicat ¸iei
6.1 Prezentarea aplicat ¸iei
33

Capitolul 7
Concluzii
7.1 Sectiunea 1
7.2 Subcapitol
34

Bibliografie
35