Subsemnatul/a………………………………………………………………………….., a bsolvent al studiilor de licență, promoția… [615076]

DECLARAȚIE DE AUTENTICITATE

Subsemnatul/a………………………………………………………………………….., a bsolvent
al studiilor de licență, promoția …………, în specializarea……………………………………..,
Facultatea de Matematică și Științe ale Naturii a Universității din Craiova, în legătură cu
elaborarea lucrării de licență cu titlul ……………………………………….. …………………….
……………………………………………………………………………………………… ………………………..c
oordonator………………………………………………………………………. …………., prin prezenta
declar pe propria răspundere că:
a. Lucrarea a fost elaborată personal și îmi aparține în întregime;
b. Nu au fost folosite alte surse decât cele menționate în Bibliografie;
c. Nu au fost preluate texte, date sau elemente de grafică din alte lucrări sau din
alte surse fără a fi citate și fără a fi precizată sursa prelucrării, inclusiv în
cazul în care sursa o reprezintă alte lucrări ale mele;
d. Lucrarea nu a mai fost folosită în alte contexte de examen sau concurs.

Data, Semnătura,

UNIVERSITATEA DIN CRAIOVA

FACULTATEA DE ȘTIINTE

SPECIALIZAREA INFORMATICĂ

LUCRARE DE LICENȚĂ

Îndrumător științific: Absolvent: [anonimizat] -Ionel RECE

Craiova
2017

UNIVERSITATAE DIN CRAIOVA
FACULTATEA D E ȘTIINTE
SPECIALIZAREA INFORMATICĂ

COMIS -VOIAJOR PENTRU ROMÂNIA

Îndrumător științific: Absolvent: [anonimizat] -Ionel RECE

Craiova
2017

4
Cuprins
Cuprins ………………………….. ………………………….. ………………………….. ………………………….. …………………… 4
1. Introducere ………………………….. ………………………….. ………………………….. ………………………….. ………. 6
1.1. Despre inteligența artificială ………………………….. ………………………….. ………………………….. ……… 6
1.2. Agenții în inteligența artificială ………………………….. ………………………….. ………………………….. ….. 7
1.2.1. Despre agenți ………………………….. ………………………….. ………………………….. …………………….. 8
1.2.2. Sisteme Agent ………………………….. ………………………….. ………………………….. ……………………. 9
1.2.3 Rațion amentul unui agent ………………………….. ………………………….. ………………………….. …. 11
2. Probleme de căutare ………………………….. ………………………….. ………………………….. ………………….. 13
2.1. Formurarea problemelor ………………………….. ………………………….. ………………………….. …………. 14
2.1.1. Tipuri de pobleme ………………………….. ………………………….. ………………………….. …………….. 15
2.2.2. Prerformațele problemelor de căutare ………………………….. ………………………….. …………. 16
2.2.3. Stări și acțiuni ………………………….. ………………………….. ………………………….. …………………… 16
2.2. Exemple de probleme de căutare ………………………….. ………………………….. ……………………….. 18
2.2.1 Probleme de jucărie ………………………….. ………………………….. ………………………….. ………….. 18
2.2.2. Probleme din viața reala ………………………….. ………………………….. ………………………….. …… 21
3. Metode de căutare ………………………….. ………………………….. ………………………….. ……………………… 22
3.1.Căutarea neinformată ………………………….. ………………………….. ………………………….. ………………. 22
2.2.1. Căutarea în lățime ( breadth –first search ) ………………………….. ………………………….. …… 22
3.2.2. Căutarea de cost minim ………………………….. ………………………….. ………………………….. ……. 23
3.2.3. Căutarea în adâncime ( deph -first search ) ………………………….. ………………………….. …… 24
3.2.4 . Căutarea în adâncime limitată ………………………….. ………………………….. ………………………. 24
3.2.5 . Căutarea în adâncime iterativă ………………………….. ………………………….. ……………………… 24
3.2.6 . Căutarea bidirecțională ………………………….. ………………………….. ………………………….. …….. 26
3.2. Căutarea informată ………………………….. ………………………….. ………………………….. …………………. 27
3.2.1. Căutarea Greedy ………………………….. ………………………….. ………………………….. ……………… 27
3.2.2. Căutarea A* ………………………….. ………………………….. ………………………….. ……………………… 29
3.2.3. Condiții pentru o fucționare optimă: admisibilitatea și consistența …………………………. 32
4. Problema comis -voiajorului ………………………….. ………………………….. ………………………….. ………… 34
4.1. Găsirea unei soluții ………………………….. ………………………….. ………………………….. …………………. 34
4.4.1. Algoritmi exacți ………………………….. ………………………….. ………………………….. …………………. 34
4.4.2. Algoritmi euristici ………………………….. ………………………….. ………………………….. ……………… 35
4.2. Algoritmul hill climbing ………………………….. ………………………….. ………………………….. ………… 36
5. Prezentarea aplicației: Comis -Voiajor pentru România ………………………….. ……………………….. 38
5.1. Deste Framework -ul Qt [8] ………………………….. ………………………….. ………………………….. ……… 38

5
5.5.1. Cum se instalează Qt ………………………….. ………………………….. ………………………….. ……….. 38
5.5.2. Creerea unui nou proiect ………………………….. ………………………….. ………………………….. ….. 42
5.2. Comis -Voiajor pentru România ………………………….. ………………………….. ………………………….. .. 44
5.2.1. Prezentarea aplicației ………………………….. ………………………….. ………………………….. ………. 44
5.2.2. Structura și funcționalitatea aplicației ………………………….. ………………………….. ……………. 47
6. Concluzii ………………………….. ………………………….. ………………………….. ………………………….. ………… 51
1. David Pole, Alan Mackworth, Artificial Inteligence: Foudation Of Computational Agents …. 51
2. Stuart Russel, Petter Norvig, Artificial Intelligence: A Modern Approach 3𝑟𝑑 Edition, 2009 51
3. https://rosettacode.org/wiki/N -queens_problem ………………………….. ………………………….. ……… 51
4. Catalin Stoean, Ruxandra Stoean, Evolutia si inteligenta aritificiala. Paradigme complete si
aplicatii, 2010 ………………………….. ………………………….. ………………………….. ………………………….. ……….. 51
5. http://www.catia.ro/articole/ai/ai.htm ………………………….. ………………………….. ……………………….. 51
8. http://doc.qt.io/qt -5/classes.html ………………………….. ………………………….. ………………………….. …. 51
9. Stuart Russel, Petter Norvig, Artificial Intelligence: A Modern Approach 3𝑟𝑑 Edition, 2009 51

6
1. Introducere

1.1. Despre i nteligenț a artificială
De-a lungul timpului, oamenii au folostit tehnologia pentru a se modela. Fiecare
nouă apariție în acest domeniu a fost exploatată petru a cosntruii agenți inteligenți sau
modele de gândire. Sistemele telfonice, hi draulice, computerele analogice și
computerele digitale au fost propuse atât ca metafore tehnologice pentru Inteligența
Artificială, căt și ca mecanisme pentru modelarea minții.
Termenul de inteligență a rtificială este întâlnit azi în numeroase publicații tehnice,
medicale, militare, științifice, de obicei, când vine vorba de aplicații ce realizeaz ă
performanțe de care numa i omul era socotit capabil: recunoașterea și analizarea vocii și
a imaginilor, traduceri dintr -o lim bă în alta, diferite jocuri de inteligență, luarea unor
decizii complexe fără intervenția unui operator uman etc . [5].
Scopul pricipal al Inteligenței Artificiale este de a i mita întrutotul creierul uman,
modul în care acesta gândește, răspunde și interacționează [5]. Acesta nu a fost atins
înca și nu va fi atins prea curâd, creierul uman facând operațiuni complexe, greu de
analizat matematic sau transp us în limbaj mașină.
Până acum sunt cun oscute două metode de abordare î n Inteligența Artificială.
Prima metoda este cunoscuta și sub numele de „symbolic approch to AI” sau „top -down
approch” [5] ,unde o mașină are la b ază un set de algoritmi care acț ionează asupra
unor date de intrare. Fiecare pas al maș inii fiind evaluat, algoritmul urmând sa
transforme dat ele de intrare intr -o formă mai ușor de utilizat. Aceasta metodă are mai
multe dezavantaje : faptul ca există o dependență puternică de mașină și faptul că
mașina poate fi utilizată doar în cazuri foarte restrânse. Bine înțeles, aboradarea se
bazeză în principală masură pe cunoștințele programatorului, nimic nu poate fi adăugat
automat .
Cea de a doua metoda constă în construir ea unor așa zise „rețele neuronale”. O
astfel de rețea poate exista atât fizic, î n electronică, câ t și virtu al, în forma uni program
pe computer.
Este prezentată sub forma unei matrici cu mai multe noduri sau neuroni, legați
intr-un mod oarecare, unul de altul. Fiecare neuron are câteva intrari și ieș iri. Intrările
sunt formate din mesaje primite de la o serie de senzori. Mesajele sunt anterior

7
prelucrate de că tre alte rețele asociate ș i apoi trimise mai departe. Ținând cont de
„explozia” în performanță a componentelor electronice ș i a calculatoarelor în genera l,
este evident că termenul de inteligență a rtificială va căpata noi valențe în anii următori.
O scurtă enumerare a doar câteva din domeniile în care este și va fi folostă
Inteligența Artificială [5]:
1. Rețele neurnale: sunt sisteme care simuleză inteligența prin reproducerea
tipurilor de conexiuni fizice care se găsesc în creierul biologic.
2. Ințelegerea limbajului natu ral: reprezintă programarea computerelor astfel î ncât
acestea să înțeleagă și să interacționeze cu limbajul natural al acestora.
3. Agenț ii: sunt entitați computerizate care acționează în locul operatorilor umani,
mai multe despre ei î n subcapitolul ce urmează.
4. Roboți.
5. Jocurile pe calculator.
1.2. Agenții în inteligența a rtificială
Inteligența a rtificială este domeniul ce studiază sinteza și analiza agenților
computaționali care se comportă inteligent [1]. Această defi niție este destul de vagă, în
cele ce urmează vor fi explicate pe rând fiecare parte a definiției.
Putem defini un ag ent ca fiind ceva care acționează într-un anumit mediu . Acesta
poate fi orice : un căine, o pisică, o furnică, roboți, calula toare, maș ini, oameni etc .
Un agent este considerat inteligent atunci când:
1. Ceea ce face este potrivit cu circumstațele și obiectivele pe care acest a le are.
2. Este flexibil î n a-și schimba scopul și învață din experiențele anterioare .
3. Face alegeri potrivite având î n vedere limitele sale perceptuale si raționale. În
mod normal, agentul nu poate observa starea lumii î n care se află, având o
memorie finită și nu dispune de un timp limitat pentru a acționa .
Dacă d eciziile și acțiunile unui agent pot fi reprezentate printr -un calcul , acesta
se poate numi un agent computațional . Deciziile și acțiunile pot fi împă rțite î n operațiuni
primitive care ulterior sunt implementate în tr-un dispozitiv fizi c. Acest calcul poate lua
multe forme. Spre exemplu la oameni este efectuat de c ătre creier, iar la mașini de
către parte a de hardware.
Scopul ș tiințific central al iteligenței artificiale este de a înțele ge principiile care
fac posibil comportamentul inteligent în medii naturale sau artificiale. Acest e lucru este
realizat de către:
1. Analiza agenților natura li si artificiali,

8
2. Formural ea și testarea ipotezelor , pentru a vedea de ce este necesar
pentru a construi un agent .
3. Proiectarea, construirea și experimentarea cu sisteme computaționale , care
îndeplinesc sarcini așa zis inteligente .
Ca parte a științei, cercetatorii construiesc astfel sisteme pentru a tes ta ipoteze
sau pentru a explora noi posibilități . Acestea sunt destul de diferite față de aplicațiile
care sunt co ncepute pentru a fi utile într -un anumit domeniu.
Scopul central de inginerie în int eligența artificială este: proiectarea și
sintetizarea unor agnenți inteligenți utili. Se vrea a se contrui agenți care să acționeze
inteligent, fiind utili în multe aplicații ș i domenii [1].

1.2.1. Despre age nți
Un agent este un sistem de calcul situat într -un an umit mediu. Este capabil să
poarte acțiuni autonome , cu scopul atingerii obiectivelor pentru care a fost construit [1].
Agenții cu un scop sunt cei care au preferinț e. Preferă unele parți ale lumii față
de altele și acționează astfel î ncăt sa le obțină. Dacă un agent nu a re preferi nțe, nu o să
îi pese î n ce parte a lumii o sa fie ș i astfel nu o să conteze ce ea ce face. Singurul motiv
pentru a proiecta un agent este acela de a -l instala cu preferințe, făcândul asfel sa
prefere anumite parți ale lumii și să î ncerce să le obțină. Agentul nu trebuie să își
cunoască preferințele, de exeplu, termostatul este un agent car e simte lumea î n care se
află iar în funție de temperatura camerei, pornește sau nu căldura. Înglobate î n
termostat există deja un set de preferinț e, și anume de a menține temperatur a camerei
la un anumit nivel . Astefel , putem spune c ă, agentul și creatorul lui vor avea aceeleași
preferințe. Nu este cazul de fiecare dată, agentului putând fi atribuite preferințe sau
scopuri încă de la prima rulare .
Interacțiunile agentului cu mediul se fac cu ajutorul unui corp. Acțiunile pe care
aceștia le fac depind de informațiile primite de la sezori . Acești senzori pot s au nu
reflecta ceea ce se află î n lumea agentului. Pot fii z gomotoși sau chiar și defecți. Chiar
și atuci când sunt fiabili, încă există o ambiguitate a lumii, lastă de către citirile lor.
Agentul trebuie să acționeaze pe baza informațiilor ce le are la dispoziție. De cele mai
multe ori, acestă informație este foar te slabă, spre exemplu: „senzorul x pare să
producă informația y” .

9
Pentru a acționa în lume agenții se folosec de anumite dispozitive denumite ș i
efectori . Și aceș tia pot fi la randul lor zgomotoși, lenți ș i se pot strica. Ceea ce
contr olează agentul este mesajul pe car e acesta il trimite efectorilor .

1.2.2. Sisteme Agent
Interacțiunea dintre un agent ș i mediul din care face parte este cunoscută ca
un sistem agent. Agentul p rimește stimuli din mediu care îl î nconjoară și efectuează
acțiunui asu pra acestuia. Un agent este alcă tuit din tr-un corp și un controler [1].
Controlerul primește informații de la corp și trimite comenzi acestuia .
Corpul include : senzori, care transformă stimulii în informație și d ispozitivele de
acționare , care convertesc comenzi î n acț iuni. Stimulările pot fi: lumina , sunet ul,
cuvinte le introduse de la t astatură, mișcări ale mouse -ului, lovituri fizice sau pot fii de
asemena informații obținute dintr -o pagină web sau dintr -o bază de date.
Senzorii obișnuiți pot fi: senzori tactili, camera video, sonar, microfoane,
tastaturi, mouse -uri și cititoare XML folosite pentru a extra ge informații din paginile web.
Un exepmlu de sen zor prototip, o cameră detecteză lumina care intră în lentilă și o
conver teste intr-o gama bidimensională de valori de intensi tate numita pixeli. Adesea
exită mai multe astfel de matrici de pixeli pentru culori diferite sau pentru mai multe
camere. Matric ile de pixeli reprezintă percepțiile corpului nostru .
Acțiunile pot fi: direcționarea, accelerarea roților, mișcarea brațelor, vorbirea,
afișarea informaț iilor, sau trimiterea unei comezi pentru un site web. Aceste comezi pot
include unele de nivel scazut, cum ar fi: setarea voltatjului unui motor electric. De nivel
înalt, mi șcările unui robot: oprirea ș i delpasarea aceastu ia intr -o anumită direcț ie la o
anum ită viteză . Aceste motoare, ca ș i senzorii, sunt de obicei zgomoto ase. De exemplu
oprirea necesită timp. Robotul poate ajunge la o anumită viteză , iar dire ctia î n care
acesta se indreaptă deobicei fluctuează .
Așadar putem spune ca acest controler este creierul agentului.

1.2.3. Agenții i ncorporați și a genții simulați
În funcție de modul în care controler ul uni agent este folosit , există mai multe
modele de agenți. Un agent i ncorporat este cel care își desfăș oară acțiunile în lumea
reală. Acestea sunt purtate într -un domeniu de zi cu zi, stimularea venind tot de acolo
[1].

10
1. Un agent simulat este acela care lucrează intr -un mediu și cu un corp simulat.
Aici un program est e responsabil de comenizle și stimulii agentului. Acest lucuru
este desori fol osit pentru a verifica un controler înainte a fi implementat.
2. Un model de agent sistem este atunci când există modele de controlere (care pot
sa fie sau nu reprezentate printr -un cod), unde corpul și mediul pot răspunde la
întrebă ri în legatură cu deciziile agentul ui. Un astfel de model, se poate folosii
pentru a demonstra anumite proprietăți ale agentului înainte de a fi implementat,
sau pentru a răspunde la întrebă ri ipotetice d espre un agent, care pot fi dificil sau
periculos de răspus,dacă este folosit un agent real.
Fiecare dinntre acestea sunt folosite pentru scopuri diferite , de exemplu [1]:
1. Modul în care trebuie să ruleze agentul trebuie să fie i ncorporat, pentru ca acesta
sa fie util.
2. Un agent simulat este util pentru testarea și repararea controler -ului, atunci când
există multe opțiuni de proiectare, când costruirea corpului agentului este prea
costisitoare sau când mediul este periculos sau inaccesibil. Permite testarea
agentului în condiții neobișnuite, care ar putea fi dificil de recreeat în lumea reală.
Cât de bună este simularea depinde de cât de bu n este mediul, simularea
trebui nd să absoarbă întotdeauna un aspect al lumii. Abstractizarea adecvată
este importantă si mularii, pentru a putea spune dac ă agentul va putea lucra în
mediu real.
3. Un model al agentului înpreună cu un model al setului de m edii posibile și o
specificare corectă a comportamentului, permit demonstr area unor teoreme
despre modul î n care agentul va f uncționa în asfel de medii. De exemplu,
demons trarea că un robot care funcțion ează cu un anumit controler, va pastra
întotdeauna o distanță corespunzătoare față de un obiect sau nu se va rătăcii
niciodată într -un labirint.
4. Fiind dat un model al agentului ș i al mediului, unele aspecte pot fi lăsate
nespecificate și pot fi ajustate pentru a produce comportamentul dorit sau optim.
Aceasta este ideea generală din sp atele optimizătrii și planifică rii.
5. În procesul de învațare, agentul își înbunatățește performanț ele în timp ce
acționează cu lumea reală.

11
1.2.3 Raționamentul unui agent
Secțiunile anterioare au presupus că un agent are anumite convingeri după
care reacționează și pe care le menține de -a lungul timpului. Pentru un agent inteligent,
convingerile, pot avea o complexitate uri așă, chiar și pentru un singur start. Ce s -a
descoperit până acum din studierea și con struirea agenților inteligenți a arătat că un
astfel de agent necesită o reprezentare internă a convi ngerilor [1].
Cunoașterea reprezintă informația necesară, a unui domeniu, folosită pentru a
putea rezolva anumite probleme [1]. Acestea pote avea forma un or generalități, aplicate
în anumite situații. Un sistem bazat pe cunoaștere este un sistem care utilizează
informațiile despre un domeniu pentru a acționa sau a rezolva probleme.
Cercetătorii IA tind să utilizeze ternenii cunoștere și convingeri intersch imbabil.
Cunoașterea reprezentând informații generale, care sunt considerate a fi adevarate.
Convingerile , pe de altă parte, sunt informații care pot fi revizuite pe baza unor altor
informații noi.
Un agent bazat pe cunoaștere este construit offline și es te utilizat online pentru
a produce acțiuni [1].
În mom entul în care un agent acționează online foloseș te: baza de cunoștințe,
observațiile despre lume, activițatile și abilitațile sale de a alege ce trebuie să facă.
Baza de cunoștințe reprezintă memoria pe termen lung, în care își pastrează
informațiile necesare pentru a acționa în viitor. Starea convingerii reprezintă memoria
pe termen scurt a agentului. Nu exista întotdeauna o disticție clară între cunoștințele
generale și cunoștințele specifice. De exemplu, un robot de livreare ar putea îvața
noțiuni generale despre un anumit oraș. Există un „feedback ” de la motorul de interfață
la baza de cunoștințe, deoarece observarea și acțiunea în lume oferă m ai multe date
din care agentul î nvață.
Offline, înainte ca agentul să acționeze, se poate constri baza de cunoștințe
utilă pentru a acționa online. Rolul calculul ui offline este de a face calculul online mai
eficient. Baza de cunoștințe este construită pe baza cunoștințel or anterioare și a datelor
acumulate d in experiențele trecute. Cercetă torii au considerat, în mod tradițional, cazul
în care este implicată o mulț ime de date și puține cunoștințe anterioare în domeniul
invațarii mașinii. Cazul unei multitudini de cunoștințe anterioare și date puție sau chiar
deloc a fost studiat pe sistemele expert. Cu toate acestea, pentru mai multe domeni i,
agentul trebuie să util izeze orice informație disponibilă și, prin urmare, necesită atât o
multitudine de cunoștințe anterioare cât și o mulțime de date.

12
Obiectivele și abilit ățile pot fi date offline sau online, în funcție de agent. De
exemplu, un robot de livrare ar putea ave a, ca obiectiv general, de a păstra camera
curată și de a nu se distruge pe el însuși sau alte obiecte, dar ar putea obține alte
obiective în timpul rulării. Calculul online poate fi mai eficient dacă baza de cunoștințe
este adaptată scopurilor și abilitaț ilor specifice. Cu toate acestea, acest lucru nu este
adesea posibil at unci când obiectivele și abilită țile sunt disponibile numai la timpul
execuției.

13
2. Probleme de căutare

Agenții inteligenți ar trebui să acționeze în așa fel încât mediul să treacă print r-o
secvență de st ări care să maximizeze performanța [2]. În general, aceaste specificaț ii
sunt dificil de implementat int -un design de succes al agentului. Așa cum am menționat,
sarcina este oarecum simplificată dacă agentul poate adopta un scop pe care poate sa -l
satisfacă. Să privim mai întâi cum și de ce un agent ar putea face acest lucru.
Să zicem că agentul nostru ar fi unul uman, este în România, în orașul
Constanța , la sfârșitul concediului. Agentul are un bilet de avion, pentru zborul către
București. Biletul este nerambu rsabil, viza de călătorie este pe cale de a expira , și după
această zi nu mai exită locuri pen tru următoarele sașe saptămâni. Acum mă surarea
perfo rmanței agen tului conține mulți factori. De exemplu, vrea să -și îmbunătățească
bronzul, să cunoască mai bine limba română, să viziteze locurile de prin preajmă și așa
mai departe. Toți acești factori ar putea să rezulte într-o arie uriașă de posibilități. A vând
în vedere gravitatea situației , însă, ar trebui să adopte, ca și scop principal, faptul că
trebuie sa ajungă la București. Acțiunile care duc la o imposibilitate de a ajunge la
București pot fi respinse fară a fi luate în considerare. Formulare obiectivelor, bazată pe
situația actuală, reprezintă primul pas în reazolvarea problemelor. Pe lân ga formularea
unui obiectiv, agentul ar putea dori să decidă în funcție de alți factori, care afecteaza
dorința de a atinge obiectivul principal, în modalitați diferite.
Vom cosidera ca un scop să fie un set de stări ale lumii și anume acele stări
pentru c are scopul agentului este satifă cut. Acțiunile pot fi privite ca tranziți între stările
lumii, agentul trebuind să afle care acțiuni îl vor ajuta sa ajungă la scopul setat [2].
Înainte de a putea face acest lucru, trebuie să decidă ce fel de acțiuni și stă ri să ia în
cosiderare. Dacă ar încerca acțiuni de genul: „mută piciorul drep în față 20 cm” sau
„invârte volanul cu șase grade la stânga”, nu ar gă si nicodată ieșirea din parcare, iar
drumul spre București va fi imposbil de facut, construirea unei soluții la acest nivel de
detaliu fiind o problemă fară rezolvare.
Formularea problemelor este procesul de a decide ce acțiuni și ce stări să ia în
considerare. Să presupunem că agentul va lua în considerare acțiunea de a conduce
de la un oraș major la altul. Așadar starea lumii pe care ag entul vrea s ă o atingă, v -a
corespunde aflarii într -un anumit oraș. Agentul nostru a adoptat acum obiectivul de a
conduce la Bucrești din Constanța. Exită mai multe drumuri care duc la București . Nici

14
unul dintre acestea nu at inge obiectivul, asta doar dacă agentul nu este familiarizat cu
geografia României, nu va ști ce drum să urmeze. Cu alte cuvinte agentul nu va ști care
dintre acțiunile posibile este cea mai bună, deoarece nu știe suficient despre starea
care va rezulta at unci când va alege un drum. Dacă agentul nu are cunoștințe
suplimentare atunci acesta este blocat. Cel mai bun lucru pe care îl poate face e să
aleagă un drum la întâmplare.
Dar, să presupunem ca agentul are o hartă a României, fie undeva pe hârtie, fie
în memoria lui. Scopul hărții este de a furniza agentului informații despre starea în care
ar putea ajunge și acțiunile pe care le pute lua. Agentul poate folosii aceste informații
pentru a lua în considerare etapele ulterioare ale unei calatorii ipotetice prin fiecare
dintre aceste orașe, pentru a încerca să gasească un drum care în cele din urmă îl va
duce la București. Odată ce a gas it o cale de a ajunge de la Constanța la Bucrești, iși
poate atinge sco pul, prin efectuarea acțiunii de a conduce. În general , atunci când, un
agent cu mai multe opțiuni la îndemână, de valori necunoscute, poate decide ce să
facă, prin o examinare a diferiterlor faze de acțiuni care conduc către stări cu valori
diferite,apoi el alegând pe cea mai bună. Acest proces de găsire a u nei astfel de s tari
se numește o căutare.
Un algoritm de căutare ia problema, ca date de intrare, și returneză o soluție sub
forma unor acțiuni. Odată găsită o soluție acțiunile pe care le recomandă pot fi realizate.
Acesta se numește faza de execuție [2].
Așa avem un simplu design de formu lare, caută și exectută. După formu larea
unui scop și a problemei, agentul ape lează o procedură de rezolvare. Folosește soluțiile
pentru a își ghida acțiunile, facând ce recomandă aceasta. Odată ce această soluție se
termina agentul gasește un alt scop [2].
În urmatoarele subcapitole se va vorbii despre formularea unor astfel de
probleme și vor fi enumerate și explicate câteva probleme de căutare.
2.1. Formurarea problemelor
În acest ă secțiune, se va considera procesul de formulare a unei probleme mai
detaliat. În primul rând, se vor analiza diferitele cunoștințe pe care un agent le poate
avea cu privire la acțiunile sale sau la starea în care se află. Acest lucru depinde de
cum agentu l este conectat la lume.
Sunt patru tipuri es ențiale de probleme [2]:
1. Probleme cu un singur nivel.
2. Probleme cu mai multe nivele.

15
3. Probleme de constrângeri.
4. Probleme de explorare.
2.1.1. Tipuri de pobleme
Pentru a fi mai simplu de explicat o sa avem drept ex eplu problema lumii
aspiratorului [2]. Lumea va co nține două locații. Fiecare locație poate sau nu să conți nă
mizerie și agentul poate fi î ntr-o parte sau în alta. Sunt opt stări în care agent ul poate
ajunge, așa cum este prezentat în Figura 1. Age ntul se poate afla în trei acțiuni posibile:
stânga, dreapta sau aspiră [2]. Scopul este de a curața mizeria, așa cum se intampla in
pașii 7 și 8.

Figura 1: Cele opt posibilități ale agentului [2].
Presupunem că senzorii agentului îi oferă acestuia destule informații despre
mediul în care se află, și să presupunem că va ști rezultatul fiecărei acțiuni pe care o va
face. Atunci acesta poate calcula cu exactitate în ce stare a lumii se alfă după fiecar e
acțiune. De ex emplu daca el se află în starea 5, atunci poate calcula, s ecvența de
acțiuni, dreapta și aspiră, secvență care să îl duce la curățarea camerei. Acesta est e un
caz simplu, numit și problema cu o singură stare [2].
Acum să luă m un exemplu mai complex. Să presupunem că agent ul cunoaște
toate rezultatele acțiunilor lui. De exemplu, într -un caz mai extrem, agentul nu poate
avea senzori. În acest caz el știe doar starea lui inițială, care poate fi oricare din cele din
Figura 1. Agentul știe ficare acțiune pe care o va face, dacă face dreapta, acțiunea îl va
duce într-unul din stagiile 2, 4, 6, 8. De fapt, agentul poate descoperi că secvența de

16
acțiuni: dreapta, aspiră, stânga, asp iră, va granta faptul ca își va atinge scopul. Acesta
este problema c u stări multiple [2].
Problemele cu stari simple și multiple pot fi rezolvate cu tehnici de căutare
similare. Tot odată duc la formarea unor agenți care sunt oarecum diferiți, care pot
acționa înainte de a avea un plan bine stabilit. Acest lucru este util deoarece mai bine
de a sta să se gandescă la fiecare rezultat al acțiunil or pe care le face, agentul poate
efectiv să facă acele acțiuni vazând ce se întâm plă după aceea .
2.2.2. Prerformațele problemelor de căutare
Eficiența unei căutări poate fi masurată în cel puțin trei moduri. În primul rând,
soluția obținută este înt radevăr o soluție? În al doiela rând, este bună ? În al treilea
rând, care este costul căutării, în raport cu timpul și memoria care a u fost folosite?
Costul to tal al unei că utări este o sumă a cost ului traseului și costului căută rii [2].
Pentru problema comis -voiajor ului, costul traseului este egal cu suma distanț elor
între orașe le care fac parte din turul complet . Costul căutării va depide de anumite
circumstanțe. Într -un mediu static , acesta va fi zero, deoarece mă sura performanței este
idenpendetă de timp. Dacă există o anume urgență, care să î l va face pe agent să
ajungă la București, atunci mediul este semi -dinamic , deoarece amânând pornirea va
costa mai mult. În acest caz, costul că utării poate varia aproximativ linia r cu timpul de
exectuție. Așă că, pentru a calcula costul total va trebui să adaugăm kilometri și
milisecunde. Acest lucru nu este deloc ușor deoarece nu există o varia ntă oficială de
schimb între acestea. Agentul trebuie cumva să decidă ce resurese să aloce atât pentru
căutare cât și pentru exectuare. Pentru probleme care au spații de stări mici este ușor
de găsit o soluție. Dar pentru problemele complicate și de dimesiuni mari, ar trebui să
existe un orec are compr omis: agentul să caute foarte mult timp pentru a găsi o soluție
optimă sau agentul va căuta pentru un timp mai scurt și va gasi o soluție a cărei drum
are un cost mai mare.
2.2.3. Stă ri și acțiuni
Să luam drept exeplu problema de rutare ( Figura 2 ). Aceas ta presupune
pleacarea dintr -un oraș, se parcurg toate o singură dată, ajungând în orașul din care am
plecat.
Există douăzeci de stă ri, ficare definită de către un oraș. Așadar starea inițială a
agentului este în Arad iar scopul este de a ajunge la București , trecând prin toate
orașele o sigură dată . Acțiunile c orespund, coducerii între orașe.

17
Sunt o mulțime de drumu ri. Pentru a decide care din aceste soluții este mai
eficientă, agentul trebuie să ș tie care este costul călătoriei: poate fi exprimat î n kilo metri
sau în timp. Deoarece în F igura 2 nu sunt specificate distanțele între orașe și nici
timpul, costul c ălătoriei va fi numarul de pași pe care agentul îl va face ca să ajungă la
București . Asta înseamnă că drumul care trece prin Sibiu și Făgărași va avea costul
total 3, fiind cea mai bună soluție.

Figura 2: O variantă simplificată a harții României [2].

Probema principală devine atunci când trebuie descrise acțiunile și stările și care
din acestea trebuie date la o parte . Pentru a ajunge la București , starea lumii poate
include foarte multe lucruri: dacă în mașină se află alți pasageri , ce se ascultă la radio,
ce se vede pe geam, ce vehicol se utilizeză pentru călatorie, cât de repede se merge,
dacă exista filtre de poliție pe drum, cât e ste ceasul, coducătorul autovehiculului poate fi
obosit sau înfometat, condițiile drumului, vremea și așa mai departe. Toți acesti factori
sunt lăsați de o parte deaoarece nu sunt relevanți problemei găsirii rutei către București.
Procesul acesta de a lasă de o parte detaliile care nu sunt utile rezolvării problemei, se
numește abstractizare [2].
Și acțiunile trebuie abstractizate. O acțiune, de exemplu drumul cu mașina de la
Arad la Zerind, poate avea multe efecte. Înafara schimbării locației și a ocupanților
vehicolului, necesită timp, consumă conbustibil, generează poluare etc.. În problemă, se
iau în calcul doar schimbările de locație. De asemenea, m ai sunt acțiuni care sunt
omise: pornirea radioului, uitatul pe geam, încetinirea vitezei petru ca este radar și așa
mai departe.

18
Aria de s arcini care po ate fi caracterizată de o problemă bine definită este vastă.
Se poa te face o distincție c lară dintre aș a zisele problemele de jucărie, care sunt
construite pentru a ilustra sau a exemplifica diferite metode ale prob lemelor de căutare
și probleme din viața reală, care t ind să fie mai dificile și a căr or soluții sunt folos itoare
omului. În următorul subcapit ol vor fii ilustrate ambele .

2.2. Exemple de probleme de căutar e
2.2.1 Probleme de jucărie

Puzzel cu 8 cifre [2]:
Puzze -lul este de fapt o tablă de 3×3 cu opt blocuri cu numere. Un ul din
acestea este este un spațiu gol, în care un bloc cu numar poate fi tras. Obiectivul e ste
de a ajunge la configura rea din dreapta a F igurii 3. Acț iunile vor consta în a muta spațiul
în care nu se alfă nimic cu blocul respectiv. Așadar o sa avem următoarele informații:
1. Stări: unde se vor specific a ce număr va conține fiecare bloc și unde se afă
spațiul liber.
2. Operațiuni: spațiul gol se mișcă stânga, dreapta, sus sau jos.
3. Scopul: de ajunge în starea din dreapta , cum este în F igura 3.
4. Costul: fiecare mutare va fi 1, costul final fiind totalul de mutări.

Figura 3: Puzzel -lul. Ce este în stânga este s tarea inițială, ce se afă în dreapta
starea finală .
Puzze l-ul cu 8 cifre face parte din familia puzzel -urilor cu blocuri. De la a cestă
clasă de puzzel -uri nu se așteaptă să se gasească metode signifiant mai bune decât
ceea ce algoritmul de căutare descrie. Puzzel -urile cu 15 cifre, reprezintă un test
standard pet ru noi aglor timi de căutare în inteligența a rtificial ă.

19
Problema damelor [2]:
Scopul acestei probleme este de a plasa cele 8 dame pe tablă astfel încât
acestea sa nu se atace una pe alta. Dam a atacă ce se află pe același râ nd, coloană
sau diagonală. Figura 4 este un rezultat reușit al unei astefel de problme.

Figura 4:Rezultatul reușit al problemei damelor [3].

Deși există algoritmi cu scop special eficienți pentru problema cu n -dame,
ramâne un test destul de bun pentru algoritmii noi de căutare. Exită două tipuri
principale de formulare. Formularea incrementată, implică plasarea damelor una câte
una, în timp ce formularea completă implică plasarea celor opt dame aleator pe tablă,
urmând a le muta după. În ambele cazuri, costul pașilor nu este de interes deoarece
doar starea finală contează, agorit mi sunt așadar comparați doar după costul căută rii.
Vor fi definite următoarele:
1. Scopul: să avem opt dame pe tablă, niciuna să nu atace.
2. Costul : să fie zero .
3. Stări: oricare aranjamet de opt dame pe tablă.
4. Operațiun i: adaugă oricare dama pe tablă .
Această formulare po ate duce la o mulține de stări de investigat. O variană mai
fiabilă este de a pune dama în sapțiul în care nici o altă dama nu o poate ataca. Atu nci,
vor fi definite :
1. Stări: aranjarea damelor astfel încât să nu fie atacate

20
2. Operațiuni: plasarea damei în coloana liberă cea mai din stânga, astfel încât sa
nu fie atacat ă.

Criptaritmetica :
Acestă problemă este de fapt un puzzel matematic, unde literele din alfabet
sunt înlocuite de către cifre . De obicei fiecare cifră ia locul unui litere diferit e.
Vom avea următoarea formulare:
1. Stări: un puzzel unde literele sunt îlocuite de către cifre
2. Oprețiuni: se î nlocuiește fiecare literă cu o cifră
3. Scopul: puzzel -ul să conțină doar cifre, iar rezultatul să fie suma corectă
4. Costul: este zero, toate soluțiile fiind valide
Sunt momente în care nu se va știi ce lit eră trenuie î nlocuită pr ima. Această
problemă se poate re zolva adoptând un set de regului, de exeplu î nlocuirea literelor în
ordine alfabetică.

Problema misionarilor și a canibalilor :
Enunțul problemei este următorul :
Sunt trei misionari și trei canibali pe margina unui râu. În fața acestora se af lă o
barcă care poate duce unul sau doi oameni. Trebuie găsită o soluție, pentru aducerea
persoanelor pe celălat mal, fără să se lase în urmă mai mulți canibali decât misionari.
Așadar vor fi definite următoarele:
1. Stări: o stare reprezintă un vector de forma (0,0,0), unde primul element al
acestuia este reprezentat de numărul de misionari aflați pe mal, cel de -al doilea
element reprezentat de numărul de canibali , de asemenea aflați pe mal și cel
de-al treilea element este numărul de bărci. Așadar v -om avea starea inițială
(3,3,1).
2. Operațiuni: constau în a duce, cu barca : un misionar, un canibal, doi misionari
sau doi canibali pe malul celăla lt.
3. Scopul: de a ajun ge în starea (0,0,0)
4. Costul: numărul de drumuri.
Este unul din cele mai clasice exemple de problemă de inteligență artificială.

21
2.2.2. Probleme din viața real a
Problema căutătii unei rute [2]:
Problema căutarii unei rute este folosită în diverse aplicații, cum ar fi : rețele le
de calculatoare, sisteme le automate de călatorie și sisteme le de planificare a zborulilor.
Ultima aplicație enumerată este oarec um mai complicată, deoarece călă toriile cu
avionul au un cost al drumului complex, din pu nct de vedere al banilor, calitatea locului
pasagerului, timpul zilei, tipul avionului și așa mai departe. Mai mult, acțiunile din
problemă nu au rezultate bine definite: zborurile pot avea disconforturi sau pot fi
suprarezervate și ceața sau reparațiile urgete pot cauza întârzieri.

Robot de navigare [2]:
Robotul de navigare este o generalizare a problemei căutarii unei rute descrise
mai sus. Mai degrabă decât un sistem discret de găsire a unei rute, un robot se poate
mișca contunuu în spațiu cu un set infinit de acțiuni și stări. Pentru un exemplu mai
simplu, un robot circular care se mișcă pe o suprafața plană, spațiul de căutare este bi –
dimensional. Când un robot are picioare și mâini, care p ot fi controlate, spațiul de
căutare va devenii multi -dimensional. În plus față de complixitatea unei astfel de
probleme, roboții r eali au de asemea erori în citi rea senzorilor.

Asambalrea automată [2]:
Asamblarea automată este facută în mare parte de r oboți. Acesția s unt folosiți
în fabrici unde sunt puse cap la cap, obiecte percum motoarele electrice. Principala
problemă î n domeniul de ansamblare automată este, găsirea unei ordin în care se pot
ansambla pă rțile. Dacă ordinea este greșită nu se poate adău ga o piesă nouă fără să
se deza sambleze alta. Pentru astfel de roboți se folosesc probleme complexe de
căutare geometrică, asemănătoare robotului de navigare.

22
3. Metode de căutare

Așa cum s -a precizat în paragrafele anterioare, după formula rea problemei
urmeaz ă găsirea unei soluți , obținut ă prin diferite metode de căuatre. Acestea pot fi:
1. Căut ari neinformate .
2. Căutari informate .

3.1. Căutarea neinformată
În cazul căutarii neinformate nu se folosește, în timpul căutarii, nici o informație
din domeniul problemei. Aceste căută ri mai sunt cunoscute și sub numele de căutari
oarbe [2].
2.2.1. Căutarea în lățime ( breadth –first search )
Reprezintă una dintre cele mai ușo re strategii de căutare. Nodul rădăcină este
expandat primul, apoi nodurile generate de către nodul rădacia sunt și ele la rândul lor
expandate și așa mai departe. În general nodurile de adâncime n sunt expandate
înainte nodurilor de adâncime n+1 [2].
Parcurgerea în adâncime reprezitntă o strategie sistemizată, deor ece
consideră toate drumurile de lungime 1, apoi de lungime 2 și așa mai dep arte. Figura 5
ne arătă progresul unei astfel de căutari pe un arbore binar.

Figura 5: Căutarea în lățime , expansiunea nodurilor: 1, 2 și 3 [2].
Dacă exi stă o soluție , căutarea în lățime o va gasi, dacă există mai multe soluții
metoda o va lua pe cea care are o adâncime mai mică.
Cut toate acestea nu este folosită foarte des. Ca să aflăm de ce , trebuie vă zut
cât timp și câte resurese o astef el de căutare neces ită. Dacă fiecare nod determi nă prin
expandare b noduri și so luția se obține în urma expandării cu d nivele, numărul maxim

23
de noduri poate fi: 1+𝑏+𝑏2+𝑏3+⋯+𝑏𝑑 [2]. Acesta este numarul total de noduri,
soluția însă se poa te gă sii pâ na să se ajungă la niveulu 𝑏𝑑.
Vom avea o complexitate 𝑂(𝑏𝑑), atât pentru timpul de execuție cât și petru
memorie. În tabelul următor se ilustrează complexitatea pentru 𝑏=10 și pentru diferite
valori ale lui 𝑑.
S-au cosniderat 1000 de noduri de testare, expandarea este gata într-o
secundă, iar memoria pentru un singur nod este de 100 B [2].

Tabel 1: C omplexitatea căutarii în lățime [2].
Adăncime Numă r noduri Timp Memorie
0 1 1 ms 100 B
2 1 0,1 s 11 kB
4 11111 11 s 1 MB
6 106 18 min 111 MB
8 108 31 ore 11 GB
10 1010 128 zile 1 TB
12 1012 35 ani 111 TB
14 1014 3500 ani 11 111 TB

3.2.2. Căutarea de cost minim
Reprezintă o variantă o arecum modificată a căută rii în adâncime , având
avantajul că poate gă sii o soluție optimă. La fel ca și mai sus se expandează nodur ile
pe nivel, dar cu condiția că nodul expandat are costul minim. Condiția de oprire este
aceea ca să nu existe o altă cale cu un cost mai mic și nodul în care se termină să fie
un nod la unei stări finale.

Figura 6: Arbore de căutare pentru metoda costului minim [4].

24
În figura 6 este exiplificată o aplicare a căută rii cu cost minim. În acest caz,
după ce nodul A se expandează, se poate alege pentru a continua nodul B, deoarece
are cel mai mic cost și anume 1 . Urmărind regula se va alge în continuare nodul C, care
duce apoi la nodul G. Dacă acesta nu este expandat, atunci căutarea se oprește,
deoarece nu se mai găsește un alt nod a cărui cale sa fie mai mică de 9. Dacă aceste
condiții nu sunt respec tate, atunci numai o căutare ca re dureză foarte mult poate
asigura soluția optimă.

3.2.3 . Căutarea în adâncime ( deph -first search )
În această metodă se expandeaz ă nodurile ale căror adâncime este cea mai
mare. Unul dintre avantjele acestei metode este acela că nece sită mai puțină memorie,
față de căutarea în lățime. Algoritmul păstrează în memori e doar o singură cale și
anume de la nodul inițial la cel terminal. Pentru arbolele binar cu factorul de expandare
𝑏 și o adâncime maximă 𝑑, metoda va păstra în memorie 𝑏∗𝑑 noduri [4]. Din punct de
vedere al timpului, este la fel ca și căutarea în lățime . Petru problemele cu un număr
mare de soluții, se folosește căutarea în adâncime, deoarece are o șansă mai mar e ca
algoritmul să gasească o so luție.
Principalul dezava ntaj al acestei căutări est e acela că poate sta mult timp tot
mergâ nd în jos pe arbore, pentru a gă sii o soluție. În unele probleme metoda poate
duce la blocarea programului.

3.2.4 . Căutarea în adâncime limitată
Reprezintă o variație a met odei de căutare în adâncime, cu specificația că se
impune o limită maximă pentru adâncimea unui nod. Astfel se vor evita toate parțile
negative ale căutarii în adâncime. Condiția de oprire este acea c a nodul în care se
termină caută rea să se afle în limita impusă. Cu toa te acestea, nu se asigură
optimiz area, din aceleași motive preci zate mai sus.

3.2.5 . Căutarea în adâncime iterativă
Și aceasta este o variantă a căutării în adâncime, eliminând însă necesitatea
de găsi re a unei variante optime impuse . Penru o problemă se cunosc valorile: 𝐷=
max (min 𝑑(𝑠𝑖,𝑠𝑗)), [4], unde 𝑠𝑖, 𝑠𝑗 sunt stări, iar 𝑑(𝑠𝑖,𝑠𝑗) este numărul de stări al căii în
spațiu stărilor 𝑠𝑖 și 𝑠𝑗 [4]. Valoarea lui D se numește diametru al spațiu lui [4].

25
Dacă cunoaștem valaorea diametrului, se va folosii ca limită, găsinduse
întotdeauna o soluție. De obicei, această valoarea este obținută d oar după ce se
rezolvă problema. P entru a implementa căutarea se procedează la o creștere iterativă a
limitei impuse.
În alte cuvint e, metoda de căutare în adâncime iterativ, presupune repetarea
metodei de căutarea cu limită pâna când se găsețe soluția . În F igura 7 este
exemplificată această metodă, unde factorul de expandare 𝑏=2 iar adâncimea are
limita 𝑑=3.

Figura 7: Patru iterații ale căutarii iterative în adâncime pentru un arbore binar [4].
Se poate observa faptul că metoda combină lucrurile bune pe care cautările în
lățime și adâncime le au. Principalul dezavantaj fiind acela că expandarea unor noduri
se re petă. În mod ciudat, creșterea timpilui de calcul nu este importantă. Considerând
un arbore caracterizat prin valoarea 𝑑 și 𝑏, numărul de noduri exp andate petru căutarea
în lățime va fi: 1+𝑏+𝑏2+𝑏3+⋯+𝑏𝑑, în cazul nostru determinând valoarea 111 111.
Aplicând căutarea în adâncime interativ, nodurile de pe ultimul nivel sunt expandate
odata, cele de pe nivelul 2 de doua ori, etc., nodul inițial fiind expandat de 𝑑+1 ori [4].
Înesmnând că numarul de expandări este (𝑑 + 1) 1 + 𝑑 𝑏 +𝑏2 (𝑑 – 1) + …+ 1 𝑑𝑏 [4].
Pentru exemplu nostru valoarea va fi de 123 456, acest lucru reprezentând o creștere
nesmnificativă. Așadar, metoda căutarii în adâncime iterative, are o complexitate la fel
ca și cea în l ățime și necesită la fel de multă m emorie precum căutarea în adâncime.

26
3.2.6 . Căutarea bidirecțională
Este varianta în care căuratrea se pornește deodată cu starea inițială și cea
finală. Se realizeă o cautare înainte din starea inițială și o cautare înapoi plecând de la
scopul îndeplinit [4]. Punctul de oprire este acela când cele două procese se întâlnesc.
O astfel de căutare este exeplificată vizual în figura 8.

Figura 8 : Principiul căutarii bi direcționale [4].
Căutarea biderecțională, are foarte multe avantaje în ceea ce privește
complexitatea. Ambii arbori de căutare au factorul de expandare 𝑏, iar soluția se
gasește la o adâncime 𝑑, ceea însemnă că se parcurge, 𝑑
2 pași din nodul stării inițiale și
tot 𝑑
2 pași din nodul stării finale. Din aceste lucruri r ezultă o coplexitate, data de numărul
de noduri expandate de tip: 𝑂(2𝑏𝑑
2)=𝑂(2𝑏𝑑
2) . Comparând cu cazul căutării în
lărgime, unde pentru 𝑏=10 și 𝑑=6 aveam generarea a 1 111 111 noduri, la aceeași
problemă, căutarea bidirecțională, mergănd în ambele sensuri până la 𝑑=3, va rezulta
generarea a 2 x 1 111 = 2 222 noduri [4].
În ciuda faptului că reduce coplexitatea foarte m ult, căutarea bidimensională
pune următoare probleme:
1. Implementarea unui arbore de căutare, care să meargă înapoi, poate fii greu de
făcut, deoarece este greu de pus în evidență legăturile dintre noduri pornind de
la starea finală.
2. Dacă avem mai multe stări finale problema se complică, trebuind a concepe mai
mulți arbori, făcând mai dificil procesul de căutare.
3. Trebuie găsită o codiție de oprire. În genral, aceasta apare atunci când apare
același nod în cei doi arbori.

27
3.2. Căutarea i nformată
Căutarea inform ată, este este modul de căutare care folosește date specifice,
față de problema avută [2]. În plus poate gă sii soluțiile necesare mai eficient decât
modul de căutare neinformată.
Așadar ceea ce este reprezentativ pentu acest mod de căutare , este cel mai
bun prim rezultat. Acesta este obținut în urma utilizării algortimilor de căutarea prin
arbori sau prin grafuri, în care un nod este ramificat pe baza funcției de căutare
evolutive 𝑓(𝑛). Acestă funcție este utilizată astfel încât noudul cel mai relevant este
expandat primul.
Utiliazarea funcției f, determină strategia de căutare. Cei mai efici enți algorimi
de căutare i nclud, pe lângă fucția evolutivă, o altă funcție ℎ(𝑛) [2], aceasta
reprezentând costul estimat al celui mai rapid drum de la nodul n la nodul țintă.

3.2.1 . Căutarea Greedy
Modul de căutare denumit Greedy, are drept scop obținerea celui mai bun p rim
rezultat al căutarii. U tilizeză expandarea nodului care este cel mai apropriat de scopul
căutarii, utilizând astfel premiza că acesta este cel mai probabil să conducă la obținerea
unei soluții mai rapide .
În concluzie Greedy utilizează evaluarea nodurilor prin utilizarea funcției
informate 𝑓(𝑛)=ℎ(𝑛), unde ℎ(𝑛) este costul estimat pentru cel mai scurt drum de la
nodul n până la starea țintă [2].
Să luam următorul exemplu: trebu ie să aplicăm Greedy pentru a ob ține un
drum de la Arad la București:

Figura 9: Harta româniei cu drumurile între orașe si distanțele acestora [2].

28
În Figura 9 este prezentată o hartă a României cu distanțele ș i drumurile între
orașe.
Sunt încercuite orașele Arad ( nod sursă ) și București ( destin ația ).

Figura 10: Primii doi pași din cadrul găsirii unei soluții de la Arad la București folosind
Greedy.
Așadar avem în Figura 10 primii doi pași ai algoritmului Greedy. Așa cum zice
problema se plecă din Arad ( stare inițială ). Acesta se expandează în nodurile: Sibiu,
Zerind, Timișoara. Urmând să se aleagă a fii expandat nodul cu h -ul cel mai mic.

Figura 10: Pasul al treilea.
În Figura 10 se poat e observa cum din orașele expandate este ale s Sibiul
deoarece are un cost mai mic. Acum Sibiul v -a reprezenta nodul care trebuie expandat.
V-om obține următoarele 4 noduri ( orașe ): Arad, Făgărași, Oradea, Râmnicu -Vâlcea.
Arad
h=366
Arad
h=366Sibiu
h=253
Zerind
h=374
Timișoara
h=329
Arad
h=366Sibiu
h=253Aarad
h=366
Făgăraș
h=178
Oradea
h=380
Râmnicu -Vâlcea
h=193Zerind
h=374
Timișoara
h=329

29

Figura 11: Pasul al patrul ea și ajungerea în București .
În Figura 11 este arătat ur mătorul pas și finalul căutării. Aici după expandarea
Sibiului, s -a ales ca următor nod Făgăraș ( h= 178 este cel mai mic ). Din Făgăraș s -au
expandat nodurile Sibiu și București, cel din urmă fiind ș i destinația unde trebuia să
ajungem.
Căutarea Greedy poate fi de asemenea incompletă chiar și într -un spațiu finit.
Spre exemplu, dacă luam ca punct de plecare Iași și ca nod terminal Făgăraș , funcția
euristică ar sugera ca nodul Neamț să fie ales și expandat, fiind cel mai aprop riat de
Făgăraș . Dar acest lucru v -a duce la o blocare a programului. Soluția astfel fiind de a
alge Vaslui, ceea ce însemnă departarea de scop, apoi Urziceni, București și în cele din
urmă Făgăraș. Algoritmul nu v -a găsii nici odată această soluție deoarece, expandând
nodul Neamț, se va alfa în situația atingerii limitei frontierei, urmând să expandeze din
nou nodul Iași, coducând astfel la o buclă infinită .
Ca și în cazul căutarii în adâncime, algoritmul de căutare Greedy nu e ste optim
și incomplet, deoarece poate urma un drum la infinit, neîntorcânduse să aleagă o altă
posibilitate.

3.2.2. Căutarea A*
A* este considerată cea mai cunsuctă dintre funcțiile de căutare și una dintre
cele m ai bune. Eficiența acestei căută ri este datorată faptului că evaluează nodurile prin
cobinarea funcției 𝑔(𝑛) ( aceasta reprezintă costul pentru a ajunge la nod ) și ℎ(𝑛)
( costul de la nodul de pornire la cel de terminare ), folosind următoarea formulă 𝑓(𝑛)=
𝑔(𝑛)+ℎ(𝑛) [2]. Arad
h=366Sibiu
h=253Arad
h=366
Făgăraș
h=178Sibiu
h=253
București
Oradea
h=380
Râmnicu -Vâlcea
h=193Zerind
h=374
Timișoara
h=329

30
În timp ce 𝑔(𝑛) oferă costul de la nodul de pornire către nodul n și ℎ(𝑛)
estimează calea cu cel mai mic cost către scop, se deprinde concluzia că 𝑓(𝑛)
reprezinză soluția ce are cel mai mic cost care atinge scopul.
Indiferent dacă trebuie sau nu găsită calea cea mai scurtă, este important să
încercăm primul nod cu valoarea cea mai mică dintre 𝑔(𝑛) și ℎ(𝑛). Făcând acest lucru ,
rezultatul va fii unul complet și optim. O re marcă interensantă este aceea că acestă
căutare este asemănătoare cu cea de cost uniform, difern ța fiind în utilizarea 𝑔+ℎ în
loc de 𝑔.
Vom considera același exemplu ca cel de sus. Pornim din Arad și vrem să
ajungem la București ( Figura 9 ).

Figura 12 : Primi doi pași în găsirea unei soluții de la Arad la București folosind A*
Așa c um se poate observa în Figura 12 , s-a ales ca nod de plecare Arad, apoi
s-a expandat în: Sibiu, Zerind, Timișoara. Cum s -a precizat mai sus , nodul care
urmează a fii expandat este acela cu cel mai mic f. Arad
f=0+366=3
66
Arad
h=366Sibiu
f=140+ 253=393
Zerind
h=75+374=499
Timișoara
h=118+329=447

31

Figura 13 : Al treilea pas.
Se poate observa ( Figura 13 ) cum nodul ales pentru a fii expandat este Sibiul
deoarece are f = 393, acesta fiind cel mai mic dintre cele trei.

Figura 14 : Pasul 4
De data aceasta s-a ales ruta prin Râmnicu -Vâlcea, deoarece are f cu valuarea
minimă. Nodul s -a expandat în: Sibiu, Craiova, Pitești. Arad
h=366Sibiu
f=393Aarad
f=239+178=417
Făgăraș
f=280+366=646
Oradea
f=146+380=576
Râmnicu -Vâlcea
f=220+193=413Zerind
f=499
Timișoara
f=447
Arad
h=366Sibiu
f=393Aarad
f=417
Făgăraș
f=646
Oradea
f=576
Râmnicu –
Vâlcea
f=413Sibiu
f=300+253=553
Craiova
f=366+160=526
Pitești
f=317+98=415Zerind
f=499
Timișoara
f=447

32

.Figura 13: Descoperirea solutiei.
Nodul Pitești este expandat. Acest lucru duce la descoperirea nodului terminal
și anume București, terminânduse căutarea. Așadar v -om avea drumul: Arad, Sibiu,
Râmnicu Vâlcea, Pitești, București. S-a preferat în acest caz drumul prin Râmnicu –
Vâlcea decât cel prin Făgăraș. Chiar dacă Făgăraș este mai apoape de București în
linie dreaptă, calea către Fă găraș nu este la fel de eficientă în apropriere de București,
mai efi cient fiind calea către Râmnicu -Vâlcea.

3.2.3. Condiții pentru o fucționare optimă: admisibilitatea și consistența
O primă condi ție pentru o funcționare cât mai optimă este ca ℎ(𝑛) să fie o
funcție euristic admisibilă [2]. Acest lucru este posibil atunci când funcția nu
supraestimeză costul pentru atingerea scopului. În cazul lui A*, unde 𝑔(𝑛) este defapt
costul de a ajunge la scop folosind calea actuală și 𝑓(𝑛)=𝑔(𝑛)+ℎ(𝑛), va rez ulta că
𝑓(𝑛) nu va supraestima costul solulției pentru calea aleasă prin n.
Funcțiile euristic admisibile, sunt considerate prin natura lor, optimiste
deoarece cosideră că soluția problemei va avea un cost mult mai mic decât în realitate.
Un exemplu m ai elocvent a unei funcții euristic admisibile îl reprezintă distanța dată de
linia dreaptă utilizată petru a ajunge la nodul București. Acesta este admisibilă deoarece
reprezintă calea cea mai scurtă dintre cele două puncte, astfel linia neputând genera o
supraestimare. Arad
h=366Sibiu
f=393Aarad
f=417
Făgăraș
f=646
Oradea
f=576
Râmnicu –
Vâlcea
f=413Sibiu
f=553
Craiova
f=526
Pitești
f=415Bucureșt iZerind
f=499
Timișoara
f=447

33
O a doua condiție, considerată mai puternică, este consistența sau monotonia
și este necesară doar pentru aplicarea A* asupra unui grafic de căutare. Consisteța
este astfel o cerință mai strictă decât admisibilitatea, dar una care lucrează din greu
pentru a crea funcții euristic admisibile însă nu și consistente.

34
4. Problema comis -voiajorului

Considerată a fi una din cele mai iconice probleme de intelingeță artificială,
problema Comisului -Voiajor are urm ătorul enunț: fiind date o listă de orașe și distanțele
dintre acestea, să se găsesască cel mai scurt drum prin care să se viziteze toare
orașele o singură dată.
La o primă analiză a enunțului se poate spune că problema nu este așa de
grea, însă lucruril e nu stau chiar așa. Comisului -voiajor fiind una din cele mai studiate
probleme în matematica computațională, negăsinduse însă o soluție eficientă. Cu toate
acestea, datorită studiului asupra probleme de mai mult de 50 de ani s -au găsit
numeroase soluții î mbunătățite în multe domenii de optimizare matematică.
Problemele matematice precum comis -voiajorul, au fost definite în anul 1800
de către matematicianul de origine Irlandeză Sir William Rowan Hamilton și de către
matematicianul Britanic Thomas Penyngton Kirkman . Forma generală a probleme i a
fost studiată prima dată undeva in anul 1930 de către Karl Menger în universitatea din
Viena și Harvard, urmând a fi ulterior promovtă de către Hassler Whitnez și Merril Flod
la Priston [6].

4.1 Găsirea unei soluți i
Având o complexitate forate mare, problema poate fi abordată prin :
1. Conceperea unor algoritmi exacți, capabili să gasească soluții pentru un număr
mic de orșe
2. Implementarea unor algoritmi suboptimali sau euristici, capabili de aducerea unor
solții bune însă care nu poate a fi optimă.
3. Împărțirea problemei într -un set de subprobleme pe care se pot apl ica algorimi
euristic i într-un mod mai bun și mai eficient.

4.1.1. Algoritmi exacți
Una dintre soluțiile cele mai directe este de a încerca toate posibilitățile,
comparândule și alegând ca soluție cea mai puțin costisitoare. Timpul de execuție va fi
de forma polinomului 𝑂(𝑛!), 𝑛 reprezentând numărul de orașe [7] . Această soluție nu
este destul de practică, algoritmul având foarte mult de muncă chiar și pentru 20 de
orașe.

35
Mai sunt și alte abordări prin care problema se poate rezolva, cum ar fi [7]:
1. Diferiți algoritmi de ramificare, care pot găsii soluția unei probleme cu 40 -60 de
orașe.
2. Algoritmi care folosesc tehnici asemănătoare progamării liniare, aceștia pot găsi
soluția la probleme cu până la 200 de orașe.
3. Implementări ale unor algoritmi care ramifică și împart problema. Sumt folos iți
pentru probleme cu multe orșe.

4.1.2. Algoritmi euristici
Sunt folosiți algoritmi euristici și de aproximare, care generează soluții bune și
eficiente. Aceștia sunt:
1. Algorimi Greedy :
Lasă ca agentul să aleagă cel mai apropriat or aș ca ș i următoare mișcare.
Algoritmul genereză repede o rută de distanță mică și eficientă.

Figura 14: Comisul va pleca din puncul negru .
Așa cum este precizat în Figura 14 agentul nostru pleacă din punctul negru. Se
va duce în toat e punctele, al egând ca soluție puncul cu cel mai mic drum

Figura 15: Gasirea unei soluții . Ce este cu albastru repezintă drumul cel mai scurt, ce este cu
roșu drum mai lung.

36
2. Optimizarea folosind coloniile de furnici
Așa cum spune si numele, această metodă este bazată pe comportamentul
furnicilor. Mai exact găsirea drumului cel mai mic de la sursele de hrană la mușuroi.
După ce o furnica face un traseu acesata lasă în ur mă feromoni, după care celelate
furnici se iau pe ntru a nu face acelasi drum de mai multe ori.
Acest lucru este implementat și într -un algoritm, prin trimitea mai multor furnici
virtuale. Fiecare furnică alge orașul pe care vrea să il viziteze, în funcție de distanța
între orașe și cantitatea de feromon i virtuali lăsați în urmă. Cantitatea de feromoni
depoziți este invers proporțională cu distanța turului: cu cât este turul cel mai scurt, cu
atât cantitarea de f eromoni virtuali este mai mare.

Figura 16: Drumul furnicilor [7].
În Figura 16 sunt descrise 4 stări. Starea cu numărul 1 reprezintă drumul și
ferominii lasați de către o furnică, acesta nu este drumul optim deoarece cantitatea de
feromoni lăsăta este slabă. În starea 2, sunt reprezentate mai multe tururi ale mai
multor furnici. Așa cum se vede în 3,este reprezentat turul unde feromonul lăsat este cel
mai puternic , ca în cele din urmă în 4 să fie ales ca fiind turul cel mai eficient.

4.2. Algoritmul hill climbing
În analiza matematică hill climbing reprezintă o tehnică de optimizare care
aparține familiei de căutari locale [9]. Este un algoritm iterativ, care pornește cu o soluție
arbitrală a problemei, apoi încearcă să găsească o soluție mai bună, prin schimbarea
treptată a câte unui singru elemet a soluției. Dacă această schimbare confe ră o soluție
mai bună, o incrementarea a noii solții are loc, acest lucru se repetă până când nu mai
există o cale mai eficicentă.
Un exeplu foarte bun, este aplicarea algoritmului în problema comisului -voiajor.
Este mai ușor de a găsii o soluție inițial ă, în care toate orașele să fie vizitate o singrură

37
dată, dar va fi foarte slabă în comparație cu soluția optimă. Algoritmul pornește cu o
astfel de soluție și aduce mici îmbunătațiri acesteia, cum ar fi schimbarea ordinei în care
se vizitează două orașe. În cele din urmă, un drum mult mai scurt este obținut.
Hill climbing, at inge soluții optime pentru problem ele covexe, altfel va găsii doar
optimele locale , care nu sunt neapărat soluțiile cele mai bune. Exemple de algoritmi ce
rezolvă probleme covexe prin hill climbing sunt: algoritmul simplex pentru programarea
lineară și căutarea binară [9]. Pen tru a evita blocarea, se pot folosi restartări, sau
scheme mai complexe bazate pe folosirea iterației sau memorie.
Faptul că acest algoritm este destul de simplu în structură, îl face alegerea cea
mai folosită pentru problemele de optimizare. Este folosit și în inteleogența artificială,
pentru cerecetarea scopului unui nod. Deși există algoritmi mult mai eficienți care pot
avea rezultate mai bune, în unele situați i hill climbing funcționează la fel de bine.
Algoritmul poate produce rezultate mai bune decât alți algoritmi, atâta timp cât durata
de căutare este mică, așa cum este în sistemele din viața reală.
Așadar hill climbing este un algoritm pe care poți să îl folosești oricând,
returnând o soluție validă chiar dacă este întrerupt înainte să se termine.

38
5. Prezentarea aplicației: Comis -Voiajor pentru România

5.1. Deste Framewor k-ul Qt [ 8]
Qt este un framework open -sorce cross platform folosit pentru dezvoltarea
produselor software în mai multe platforme. Acesta este format din din:
1. Un pachet de librării Qt pentru C++.
2. Mediu de dezvoltare alcătuit din Qt Creator IDE și tool -uri pentru dezvoltarea de
interfețe.

5.5.1. Cum se instalează Qt
Frameworul -ul Qt se poate instala foarete ușor . Acesta se poate desca de pe
siteul oficial ( https://www.qt.io/download -open -source/#section -2 ).

Figura 17: Ob țiuni de instalare Qt pentru sistemul de operare preferat [8].
După ce se alge varianta, în cazul nostru varianta de installer pentru Windows ,
se descară automat un installer.

Figura 18: Instal ler pentru Windows [8].

După descărca re, se poate trece la instalarea Qt, o istalare de altfel normală.
Se începe prin deschiderea installer -ului ( Figura 18 ) , și apoi se urmează pașii din
figurile următoare.

39

Figura 19: Prima fereastră, în care avem detlii despre Qt. Se va da click pe next.

Figura 20: Cea de -a doua fereastră, unde se poate înregistra cu adresa de e -mail
pentru a primii mai multe detalii și noutăți. Aceasta nu este obligatorie, putem da skip .

40

Figura 21 : Următoarea fereastră avem butonul de Settings, unde putem configura
anumite setări ale Qt-ului, butonul de Next va fi apăsat.

Figura 22: Aici Qt își descarcă tot de ce are nevoie pentru a putrea începe instalarea.

41

Figra 23: În această fereastră se poate selecta versiunea de Qt de care avem nevoie,
petru acest exemplu selectăm ultima ver siune valabilă și anume Qt 5.9.

Figura 24: După ce suntem de acoord cu termenele și condițiile apăsăm Next.
După ce se termină instalarea, o altă fereastră apare cu un buton de Finish.
După ce apăsăm acel buton instalarea se termină.

42
5.5.2. Creerea unui nou proiect
Pentru a creea un nou proiect în Qt, deschidem bine înțeles Qt și vom da pe
File->New Project apoi ne vor apărea urămătoarele:

Figura 25: Primul pas.
După ce am dat New Project , o nouă fereastră ne va apărea. Aici putem să
selectăm ce fel de aplicație vrem să facem, pentru acest exemplu vom selecta Qt Gui
Application ( dublu click ).

Figura 26: Cel de -al doilea pas.
După ce am dat dublu click, o nouă fereastră va apărea. Aici putem să
schimbăm numle și locația unde se va afla și salva proiectul. După ce terminăm
apasăm Next.
În următorul pas ( Figura 27 ) se vor selecta Kit -urile. Pe scurt cel, de Debug și
cel de Release .

43

Figura 27: Cel de -al treilea și al patrulea pas.
În pasul 4 se poate schiba numelei ferestrei principale, clasei, he ader-ului, etc.
După ce dam Next putem începe a programa.

44
5.2. Comis -Voiajor pentru România

5.2.1 . Prezentarea aplicației
Aplicația poate fi pornită fie din fișierul executabil: „ ComisVoiajor_licenta ”, fie
prin apă sarea butonului „ Run” din Qt. După ce rulăm aplicația fereastra pricipală va
aparea pe ecran.

Figura 28: Fereastra principală a aplicației.
Mai trebuie menționat faptul că pentru rularea aplicației este necesar să se
descarce un fisier de tip text în care se vor afla coordonatele orașelor din România.
Acesta se poate descărca de pe http://cadredidactice.ub.ro . Unele orșe din acest fișier
sunt situate în af ara româniei, pentru o proiectare mai exactă se pot șterge acele
coordonate. Acest fișier va avea în total 2950 de orașe.
Înainte de a genera fișierul, pu tem să selectăm, prin butonul „drop down” ,
numărul de oașe pentru care se poate aplica algo ritmul de căutare. Se pot selecta: 100,
150, 200 și așa mai departe până la 2950 de orașe .
După ce se selctează numarul de orașe se apasă butonul de „ Generate File ”.
Acesta va deschide o noua fereastră în care se p oate încă rca fișierul ro2950_geo .txt,.
După se va genera automat pe desktop un filșier de tip text numit drum.txt. Fișierul
drum.txt va conține exact numărul de orșe însa așezate după algoritmul Hillclimbing,
mai mult despre aceastea în capitolul ce urmează .

45

Figura 29: Generate File, selectarea și creearea fișierelor de tip text.
Fișierul drum.txt se încarcă apoi în siteul: „http://www.gpsvisualizer.com/draw/ ”,
unde se vor proiecta coordonatele pe harta Român iei. Cest lucuru se face prin
apăsarea butonului de „ Import a Gps file ”, apoi „ Chose File ”, alegem fișierul și în cele
din urmă o sa apasam „ IMPORT ”.

46

Figura 30 : Imporatarea fișierului drum.txt .
După ce am importat fișierul o sa avem pe hară orașele și ordinea în care au
fost vizitate.

Figura 31 : Orașele pe hartă .
Pentru a face o altă căutare se va șterge fișierul drum.txt și se va da „ Reset ”.

47
5.2.2 . Structura și funcționalitatea aplicației

Figura 32: Structura aplicației.
1. „mainwidow.ui” conține toate obiectele grafice ale apl icației, împreună cu
atributele acestora .

Figura 33: „mainwindow.ui”
Aceasta conține două butoane: „Generate file ” folosit pentru a genera un fișier
de timp tex t și un buton de „ Reset” care va reseta aplicația pentru a încerca încă
odată. Butonul de tip dropdown: impune limita orașelor. Încă un widget în care este
încărcat siteul : „http://www.gpsvisualizer.com/draw/ ” în care se va încărca fișierul de
tip text generat.
2. „mainwindow. cpp”: conține decl arările și inițierile obiectelor grafice :

48

Figura 34 : Implementarea ferestrei principale a aplicației. Poza de fundal și
proiecrarea siteului „http://www.gpsvisualizer.com/draw/ ”.

Figura 35 : Creearea butonului drop down .

49
3. „hillcliming .cpp”: conține implemtarea algoritmului „hillcli minig”, prin care este
calculat traseul pe care comisul îl va facem. Acest lucru este realizat prin creerea
unui drum aleator a orașelor, acel drum fiind comparat cu un altul. Dacă cel din
urmă drum are o dist anță mai mică va fi cel care se va alege . Calcularea
distanței drumului se face prin funcția „evaluare”.

Figura 32: Fucnția de evaluare.

Figura 3 6: Compararea drumului aletaor cu un altul.
Tot aic i se va face citirea și scrierea fișierului text: „ro2950_geo.txt ”. După ce se

50
face distanța aleatoare și se va compara cu o altă di stanță, se v a scrie într -un alt
fișier de tip text numit „drum.txt ”.

Figura 37 : Citirea și parcuregerea primelor „n” elemete ale fisiereului
„ro2950_geo.txt”.

Figura 38 : Scrierea fișierului „drum.txt”.
4. „distanta.cpp ” : calculează distanța folosind coordonatele din fișierulul text pentru
a o afișa .

Figura 39 : Calcularea distanței.
5. Tot ceea ce se află în fișierul Headrs se folosește pentru a defini și pentru a
vedea funcțiile din alte f ișiere.

51
6. Concluzii

Scopul acestei lucrări a fost de a prezenta anumite aspecte legate de
inteligența artificială, aspecte legate de căutări folosind algoritmi specififci. A m vorbit
despre agenții inteli genți, ce sunt, cum se folosesc și despre importanța acestora î n
inteligența artificială. Am mai discutat despre problema comisului -voiajor, una dintre
cele mai clasice probleme de inteligență artificială și despre agloritmul Hillclimbing,
algoritm folosit în dezvoltarea aplicației.
Aplicațiile de path -finding sunt destul de răspândite. Acești algoritmi sunt
folosiți î n sistemele de GPS ( Global Positioning System ) pentru calcularea celei mai
scurte rute către destinație. Principalul sistem de poziționare prin satelit de tip GPS este
sistemul militar american numit "Navigationa l Satellite Timing and Ranging"
(NAVSTAR). Acesta poate calcula poziția exactă a unui obiect pe suprafața Pământului ,
cu condiția ca acesta să fie e chipat cu dispozitivul necesar, un receptor GPS .
BIBLIOGRAFIE
1. David Pole, Alan Mackworth, Artificial Inteligence: Foudation Of Computational
Agents
2. Stuart Russel, Petter Norvig, Artificial Intelligence: A Modern Approach 3𝑟𝑑
Edition, 2009
3. https://rosettacode.org/wiki/N -queens_probl em
4. Catalin Stoean, Ruxandra Stoean, Evolutia si inteligenta aritificiala. Paradigme
complete si aplicatii, 2010
5. http://www.catia.ro/articole/ai/ai.htm
6. https://web.archive.org/web/20161026182815/http://www.math.uwaterloo.ca:80/t
sp/problem/index.html
7. https://en.wikipedia.org/wiki/Travelling_salesman_problem
8. http://doc.qt.io/qt -5/classes.html
9. Stuart Russel, Petter Norvig, Artificial Intelligence: A Modern Approach 3𝑟𝑑
Edition, 2009