Coperta: dup ă lucrarea Astrul Dimine ții de Virginia Baz-Baroiu [611566]

Coperta: dup ă lucrarea „Astrul Dimine ții” de Virginia Baz-Baroiu

Cartea „Introducere în inteligen ță artificial ă – Aplica ții cu strategii de c ăutare
neinformate și informate” scris ă de dl. dr. ing. Bogdan Groza abordeaz ă ca
subiect rezolvarea problemelor prin strategii de c ăutare, oferind totodat ă o
manieră de evaluare comparativ ă a performan țelor acestor strategii. Lucrarea
are un pronun țat caracter aplicativ, materialul fiind organizat într-o structur ă
tipică lucrărilor de laborator. De și lucrarea se adreseaz ă în principal
stundenților, maniera cursiv ă și concisă în care este scris ă oferă o lectur ă
plăcută și utilă oricărui cititor interesat de subiect. În plus, doresc s ă subliniez
rigoarea științifică a materialului prezentat în lucrare, rezultat ă în mod firesc din
experiența deosebit ă de cercet ător a autorului.

Referent științific: șef lucrări dr.ing. Dorina Petric ă

INTRODUCERE ÎN INTELIGEN ȚĂ ARTIFICIAL Ă –
APLICA ȚII CU STRATEGII DE C ĂUTARE NEINFORMATE
ȘI INFORMATE

Aplicații cu strategii de c ăutare neinformate și informate – 4 –

INTRODUCERE ÎN INTELIGEN ȚĂ ARTIFICIAL Ă –
APLICA ȚII CU STRATEGII DE C ĂUTARE NEINFORMATE
ȘI INFORMATE

Bogdan Groza
1

1 Universitatea Politehnica Timi șoara, Facultatea de Automatic ă și Calculatoare, Bd. Vasile
Pârvan nr. 2, Room A304, 300223, Timi șoara, România, e-mail: [anonimizat],
web: www.aut.upt.ro/~bgroza.

Aplicații cu strategii de c ăutare neinformate și informate – 5 –

CUPRINS

LUCRAREA 1 INTRODUCERE ÎN PROBLEMATICA INTELIGEN ȚEI
ARTIFICIALE 8
1.1 AGENTUL INTELIGENT , CAPACITATEA DE A REZOLVA PROBLEME …………………………..8
1.2 FORMULAREA UNEI PROBLEME ………………………………………………………………………..10
1.3 ETAPELE REZOLV ĂRII UNEI PROBLEME ……………………………………………………………..11
1.4 EFICIENȚA REZOLV ĂRII UNEI PROBLEME M ĂSURI CALITATIVE ȘI CANTITATIVE ÎN
EVALUAREA STRATEGIILOR DE C ĂUTARE ……………………………………………………………………….12
1.5 IMPLEMENTAREA GENERAL Ă A STRATEGIILOR INFORMATE ȘI NEINFORMATE ………..13
1.6 EXERCIȚII……………………………………………………………………………………………………..14
LUCRAREA 2 STRATEGII NEINFORMATE DE C ĂUTARE: STRATEGIILE DE
CĂUTARE PE NIVEL ȘI BIDIREC ȚIONALĂ……………………………………………………………17
2.1 STRATEGII DE C ĂUTARE ȘI CARACTERISTICI ALE ACESTORA ………………………………..17
2.2 STRATEGIA DE C ĂUTARE PE NIVEL (BREADTH -FIRST) ………………………………………..17
2.3 STRATEGIA DE C ĂUTARE BIDIREC ȚIONALĂ (BIDIRECTIONAL SEARCH ) …………………20
2.4 EXERCIȚII……………………………………………………………………………………………………..22
LUCRAREA 3 EVITAREA CICLURILOR ÎN ALGORITMII DE C ĂUTARE ……..31
3.1 EXERCIȚII……………………………………………………………………………………………………..31
LUCRAREA 4 STRATEGII NEINFORMATE DE C ĂUTARE: STRATEGIILE DE
CĂUTARE ÎN ADÂNCIME, ADÂNCIME LIMITAT Ă ȘI ADÂNCIME ITERATIV Ă…34
4.1 STRATEGIA DE C ĂUTAREA ÎN ADÂNCIME (DEPTH -FIRST) ……………………………………34
4.2 STRATEGIA DE C ĂUTARE LIMITAT Ă ÎN ADÂNCIME (DEPTH -LIMITED )……………………35
4.3 STRATEGIA DE C ĂUTARE ITERATIV Ă ÎN ADÂNCIME (ITERATIVE -DEEPENING )………..36
4.4 EXERCIȚII……………………………………………………………………………………………………..38
LUCRAREA 5 STRATEGII NEINFORMATE DE C ĂUTARE: STRATEGIA DE
CĂUTARE CU COST UNIFORM………………………………………………………………………………..42
5.1 STRATEGIA DE C ĂUTARE CU COST UNIFORM (UNIFORM COST) ……………………………42
5.2 EXERCIȚII……………………………………………………………………………………………………..44

Aplicații cu strategii de c ăutare neinformate și informate – 6 –
LUCRAREA 6 STRATEGII INFORMATE DE C ĂUTARE: STRATEGIILE DE
CĂUTARE BEST FIRST ȘI GREEDY …………………………………………………………………………54
6.1 CE ESTE O EURISTIC Ă……………………………………………………………………………………..54
6.2 STRATEGIA DE C ĂUTARE BEST FIRST ……………………………………………………………….55
6.3 STRATEGIA DE C ĂUTARE GREEDY ……………………………………………………………………55
6.4 EXERCIȚII……………………………………………………………………………………………………..56
LUCRAREA 7 ALEGEREA UNEI EURISTICI …………………………………………………….60
7.1 PROBLEME CU CONSTRÂNGERI ………………………………………………………………………..60
7.2 ROLUL UNEI EURISTICI ……………………………………………………………………………………60
7.3 EXERCIȚII……………………………………………………………………………………………………..61
LUCRAREA 8 STRATEGII INFORMATE DE C ĂUTARE: STRATEGIA DE
CĂUTARE A* 62
8.1 DEMONSTRA ȚIE ASUPRA OPTIMALIT ĂȚII LUI A* ………………………………………………..63
8.2 EXERCIȚII……………………………………………………………………………………………………..63
LUCRAREA 9 STRATEGII DE C ĂUTARE ÎN SPA ȚII CU INCERTITUDINI …….68
9.1 EXERCIȚII……………………………………………………………………………………………………..80
LUCRAREA 10 ÎNTREB ĂRI RECAPITULATIVE ȘI PROBLEME……………………….81

Aplicații cu strategii de c ăutare neinformate și informate – 7 –

Cuvânt înainte

Prezentul material este destinat pe ntru a fi utilizat în cadrul activit ății de
laborator de c ătre studen ții din anul IV ai Facult ății de Automatic ă și Calculatoare din
Universitatea “Politehnica” din Timi șoara care urmeaz ă materia Bazele Inteligen ței
Artificiale dar poate fi desigu r folosit de oricine îl consider ă util. Lucr ările conținute
reprezintă doar o parte din lucr ările de laborator efectuate în perioada 2005-2008 cu
studenții anului 4 Automatic ă la materia Inteligen ță Artificial ă, lucrări care vor fi pe de
o parte continuate cu studen ții anului 4 Ingineria Sistemelor la materia Bazele
Inteligenței Artificiale. Aceste lucr ări reprezint ă doar prima parte a laboratorului de
Inteligență Artficială ținut pentru promo țiile de 5 ani, a doua parte a adresat problemele
de logică (implementare în Prolog) și rețele neuronale. Este posibil ca prezentul
material s ă fie extins și cu lucrările aferente acestei a doua p ărți în funcție de interesul
acordat disciplinei de c ătre studen ți și posibilitatea activ ării sale, acum materia având
caracter op țional. Materialul poate fi accesat on-line la www.aut.upt.ro /~bgroza/iia.pdf .

Timișoara, Bogdan Groza
Noiembrie 2008

Aplicații cu strategii de c ăutare neinformate și informate – 8 –
Lucrarea 1 Introducere în problematica
Inteligen ței Artificiale

1.1 Agentul inteligent, capacitatea de a rezolva probleme

Russel și Norvig, în binecunoscuta lor carte „Artificial Intelligence a Modern
Approach”, devenit ă referință de nelipsit pentru orice curs în domeniu, definesc
inteligența artificial ă ca fiind studiul agen ților existen ți într-un mediu care percep și
acționează.
Agentul poate fi perceput ca o entitate care percepe mediul prin intermediul
senzorilor și acționează asupra lui prin intermediul efectorilor. De asemenea un agent
are o arhitectur ă, pe care o asociem p ărții fizice a acestuia, numit ă hardware, și un
program de func ționare, care îl numim software. Acest lucru este ilustrat în figura 1.1.
De remarcat c ă acest concept nu adreseaz ă doar agen ți de natur ă fizică tip robot ci
chiar și agenți de natur ă virtuală (sub form ă de program, algoritm etc.) care au și ei o
component ă hardware pe care func ționează. Partea software, programul, este
componenta care p ăstrează natura inteligent ă.

Figura 1.1 Agentul inteligent în interac țiunea sa cu mediul

Așadar obiectivul Inteligen ței Artificiale este construirea Agen ților Inteligen ți.
Întrebarea este îns ă ce ne face s ă numim un agent ca fiind inteligent. R ăspunsul la
această întrebare nu este simplu și de-a lungul anilor au fost dezvoltate diverse
potențiale răspunsuri. Poate cel mai cunoscut criteriu pentru a demonstra c ă o mașină

Aplicații cu strategii de c ăutare neinformate și informate – 9 –
este inteligent ă este testul Turring ilustrat în figura 1.2, descris de Alan Turing în 1950
în lucrarea "Computing Machinery and Inte lligence". În acest test, un participant A
discută pe o linie cu o ma șină de calcul B (agentul inteligent) și pe altă linie cu un alt
participant uman C. To ți participan ții la comunicare sunt în incinte izolate f ără contact
cu mediul, iar la final participantul A trebuie s ă poată face distinc ția între B și C, care
este mașină și care este om. Dac ă nu se poate face aceast ă distincție mașina a trecut
testul și este inteligent ă.

Camera ACamera CCamera B
ComunicareComunicare
Participant uman A
Participant uman C
Masina inteligenta B
Care dintre B si C este masina inteligenta sau om ?

Figura 1.2 Test Turing

Sigur, trecerea acestui test este un dezide rat greu de atins. Pentru contextul de
față vom opta pentru un r ăspuns mai simplu, care chiar dac ă mai redus ca profunzime
și complexitate, nu este lipsit de semnifica ție. Vom defini un agent inteligent ca fiind o
entitate capabil ă de a rezolva probleme. Într-adev ăr, capacitatea de a rezolva probleme
este o dovad ă de inteligen ță. Mai mult, chiar și noi, ne-am format inteligen ța încă din
cele mai timpurii stagii, rezolvând probleme.
Dar ce înseamn ă a rezolva o problem ă? Indiferent de problema adresat ă și de
mediul de care apar ține, chiar este recomandabil s ă gândim acest lucru nu în contextul
agenților inteligen ți artificiali ci al vie ții noastre de zi cu zi, rezolvarea unei probleme
poate fi întotdeauna v ăzută ca fiind echivalent ă cu capacitatea de a lua ni ște decizii,
deci orice problem ă este o problem ă decizional ă în cele din urm ă. Exemplele sunt
desigur numeroase, de exemplu a juca șah înseamn ă a putea lua în mod corect o decizie
asupra piesei care trebuie mutat ă, sau a trece strada înseamn ă a lua în mod corect o
decizie cu privire la momentul în care trebuie s ă facem un anume pas etc.
Acest lucru ne duce în cele din urm ă la a defini un agent inteligent ca fiind o
entitate capabil ă de lua decizii în scopul rezolv ării unei probleme. Pentru a accentua
caracterul inteligent al lu ării de decizii este de dorit ca entit ățile inteligente s ă poată

Aplicații cu strategii de c ăutare neinformate și informate – 10
–
evalua efectul decizilor (plan-ahead) iar aceast ă evaluare se face în baza informa ților
disponibile agentului, de cele mai multe ori acestea fiind îns ă incomplete (altfel spus,
entitățile inteligente nu sunt tot timpul omnisciente).

1.2 Formularea unei probleme

Trebuie acum s ă lămurim ce înseamn ă din punct de vedere formal rezolvarea
unei probleme. Înainte de a rezolva o problem ă aceasta trebuie formulat ă. Formularea
sau descrierea unei probleme, indiferent de natura ei, se poate face în baza a trei noțiuni:
¾ Stare inițială (SI) – starea din care începe problema.
¾ Stare final ă (SF) – starea în care se termin ă problema.
¾ Operatorii de generare a st ărilor – acțiunile care pot fi întreprinse.
Se impune observa ția că starea final ă poate fi specificat ă în mod direct, adic ă
explicit printr-o valoare, sau indirect, printr-o func ție de test. Ca exemplu putem
considera problema în care un agent trebuie s ă se deplaseze din punctul A în punctul B.
În acest caz starea final ă este explicit dat ă ca fiind punctul B. Pentru cel de-al doilea
caz putem considera alt ă problemă, de exemplu jocul de șah. În acest caz starea final ă
nu este explicit specificat ă, pentru c ă starea final ă este cea de șah mat, dar cum arat ă
șah mat? Evident acest lucru nu poate fi știut la începutul jocului și din acest motiv
trebuie să existe o func ție de test cu ajutorul c ăreia la fiecare pas se poate testa dac ă
starea atins ă este șah mat. De asemenea pot fi una sau mai multe st ări finale valide care
rezolvă problema. În general specificarea explicit ă a unei st ări finale și unicitatea
acesteia poate fi folosit ă ca avantaj în rezolvarea unei probleme deoarece se pot aplica
strategii de c ăutare ceva mai eficiente ca timp și spațiu precum c ăutarea bidirec țională
așa cum se va vedea în capitolul 2.
Spațiul stărilor este totalitatea de st ări în care se poate ajunge, aplicând
succesiv operatori pe st ările nou rezultate din starea curent ă. Putem de asemenea defini
spațiul stărilor ca fiind ansamblul de st ări și tranziții posibile între acestea, acest lucru
creând o imagine de tip graf asupra problemei (o astfel de imagine este în general un
bun punct de plecare în rezolvarea problemelor).
Prin drum sau cale în spa țiul stărilor înțelegem orice secven ță de stări legate
prin operatori în spa țiul starilor. Fiecare drum în spa țiul stărilor are un cost, care este
evaluat de o func ție care o vom nota cu g și care asociaz ă unui drum un cost. Costul
drumului prin spa țiul stărilor de la starea ini țială la starea curent ă se mai nume ște și
costul stării sau al nodului, în momentul în care discut ăm de arbori de c ăutare.
În acest context solu ția unei probleme este drumul prin spa țiul stărilor de la
starea ini țială la starea final ă. Trebuie evitat ă confuzia c ă starea final ă este solu ția
problemei, solu ția problemei este drumul pân ă la starea final ă și nu starea final ă în
sine. Acum putem defini foarte simplu și ce presupune rezolvarea unei probleme:
rezolvarea unei probleme este c ăutarea unei c ăi de la starea ini țială la starea final ă a

Aplicații cu strategii de c ăutare neinformate și informate – 11
–
problemei și deci echivaleaz ă cu găsirea unei c ăi în spațiu stărilor de la starea ini țială la
starea final ă.
Poate fi util s ă ne oprim asupra unui exemplu ilustrativ. Una dintre problemele
care vor fi studiate în acest material, datorit ă simplității dar și a puterii de
exemplificare este puzzleul 3×3, ilustrat în figura 1.3, ce poate fi generalizat sub forma
nxn. Pentru acesta putem extrage urm ătoarele caracteristici:
¾ Stare inițială: orice aranjare a pieselor din careu care este punctul de
plecare al problemei.
¾ Stare final ă: orice aranjare prestabilit ă a pieselor.
¾ Operatori: toate mut ările posibile ale spa țiului liber: stânga, dreapta, sus,
jos (desigur, e vorba de mutarea fizic ă a pieselor din jurul acestuia)
¾ Rezolvare: g ăsirea unui drum prin spa țiul stărilor de la starea ini țială către
starea final ă prin aplicarea operatorilor (deci mut ările care trebuie f ăcute
pentru a ajunge de la configura ția care se d ă la configura ția care se cere)
¾ Spațiul stărilor: num ărul de variante posibile pentru a aranja piesele pe
tablă, anume permut ări de 9 care înseamn ă 9!= 362880 st ări
Se impune îns ă o observa ție esențială, și anume, c ă de fapt sunt mult mai
puține stări decât 9! pentru c ă există și poziții în care nu se poate ajunge, de exemplu
orice pozi ție care s-ar ob ține prin interschimbarea a dou ă piese alăturate. Din acest
motiv dimensiunea spa țiului stărilor o vom trata sub indi catorul de complexitate O
astfel putem spune în mod riguros c ă dimensiunea spa țiului stărilor pentru puzzleul de
n piese este O(n!) prin aceasta indicând în fapt doar o limit ă superioar ă asupra
numărului de st ări ale problemei.

1 32
4 6
57
81 32
4 65
7 81 32
4 65
7 8
Stare Initiala Stare Finala Stare Intermediara

Figura 1.3 Exemplu de puzzle 3×3
1.3 Etapele rezolv ării unei probleme

Aplicații cu strategii de c ăutare neinformate și informate – 12
–
În baza preambulului f ăcut, putem enumera urm ătorii pași care trebuie s ă îi
urmăm în rezolvarea unei probleme:
1) Abstractizarea – înseamn ă eliminarea detaliilor inutile și păstrarea
elementelor esen țiale rezolv ării problemei
2) Determinarea st ării inițiale
3) Determinare st ării finale
4) Extragerea operatorilor (ac țiunilor posibile)
5) Pornirea unei strategii de c ăutare în spa țiul stărilor

Este de remarcat c ă pașii 1,2,3 și 4 țin de formularea problemei în timp ce
pasul 6 reprezint ă aplicarea strategiei de c ăutare și rezolvarea efectiv ă a problemei.
Generarea unor st ări noi se face prin aplicarea operatorilor asupra st ării curente în timp
ce alegerea efectiv ă a stării care urmeaz ă să fie explorat ă (expandat ă) este determinat ă
de strategia de c ăutare folosit ă.
Odată cu pornirea unei strategii de c ăutare se ajunge implicit la generarea
spațiului stărilor și mai exact se va ajunge la o structur ă ce poate fi asociat ă unui
Arbore de C ăutare. Este de remarcat c ă arborele de c ăutare nu trebuie s ă apară explicit
ca structur ă de date, ci acesta poate fi simulat de c ătre algoritmul de c ăutare. Așadar
structura de date asociat ă în mod concret sau virtual unei strategii de c ăutare este
arborele de c ăutare. În mod uzual asociem urm ătoarele informa ții unui nod al arborelui
de căutare:
¾ Starea – starea c ăreia nodul îi este asociat
¾ Părintele nodului – nodul care a generat nodul curent
¾ Operator – operatorul prin care a fost generat nodul
¾ Adâncime – num ărul de nivele pân ă la acest nod
¾ Cost – costul drumului de la nodul r ădăcină la nodul curent
¾ Euristica – valoare estimativ ă a distanței până la starea final ă
Este important de observat c ă arborele de c ăutare nu este acela și lucru cu
spațiul stărilor, de exemplu Arborele de C ăutare poate avea un num ăr infinit de st ări
chiar dac ă Spațiul Starilor este finit în cazul în care strategia de c ăutare are cicluri
(aspect discutat în capitolul 3). De asemenea un nod dintr-un Arbore de Cautare
corespunde unei st ări dar nu este echivalent cu aceasta deoarece de exemplu un nod are
un singur nod p ărinte în timp ce într-o stare se poate ajunge din mai multe st ări și în
acest caz o stare poate avea mai multe st ări părinte.

1.4 Eficien ța rezolvării unei probleme m ăsuri calitative și
cantitative în evaluarea strategiilor de c ăutare

La alegerea unei strategii de c ăutare pentru rezolvarea unei probleme,
evaluarea eficien ței rezolvării problemei poate fi pus ă din diverse puncte de vedere. De
exemplu iat ă câteva întreb ări orientative: C ăutarea ajunge la o solu ție? Soluția găsită a
fost cea mai bun ă? Soluția a fost furnizat ă în timp util? Care au fost costurile g ăsirii

Aplicații cu strategii de c ăutare neinformate și informate – 13
–
acestei solu ții? De cele mai multe ori, strategia de c ăutare aleas ă poate fi un compromis
între calitatea solu ției (costul c ăii Stare ini țială – Stare final ă) și costul c ăutarii (timp,
memorie, costuri de implementare etc.).
Pe lângă astfel de întreb ări orientative, exist ă măsuri cantitative și calitative
exacte pentru a estima eficien ța unei strategii de c ăutare. Acestea sunt urm ătoarele:
¾ Măsuri cantitative:
¾ Complexitatea de timp a strategiei T – în cât timp (m ăsurat ca num ăr de
pași ai algoritmului) este g ăsită soluția.
¾ Complexitatea de spa țiu a strategiei S – de cât spa țiu (este vorba de
memorie) este nevoie pentru g ăsirea solu ției.
¾ Măsuri calitative:
¾ Completitudine – o strategie se nume ște complet ă dacă garanteaz ă găsirea
unei soluții.
¾ Optimalitate – o strategie se nume ște optimal ă dacă garanteaz ă găsirea
celei mai bune solu ții din punctul de vedere al costului c ăii între starea
inițială și starea final ă.
Trebuie precizat c ă în timp ce complexit ățile de timp și spațiu sunt aprecieri
pur cantitative, m ăsurate cu ajutorul indicatorului de complexitate O, completitudinea
este întotdeuna o proprietate binar ă: o strategie este sau nu este complet ă. În ceea ce
privește optimalitatea, aceasta este în general tot o proprietate binar ă: o strategie este
sau nu este optimal ă, dar, exist ă și strategii, numite sub-optimale, care nu g ăsesc cea
mai bună soluție dar găsesc o solu ție foarte apropiat ă ca și cost de cea mai bun ă soluție
(de exemplu A* atunci când nu folosim euristici admisibile, un astfel de caz va fi
discutat în sec țiunea 8).
1.5 Implementarea general ă a strategiilor informate și neinformate

Toate strategiile de c ăutare neinformate și informate discutate în acest material
urmează aceeași paradigm ă generală în implementare. Pe lâng ă pașii anterior aminti ți
de abstractizare, extragere a st ărilor inițială și finală, respectiv a operatorilor, trebuie s ă
adăugăm și pasul în care se realizeaz ă căutarea efectiv ă pe care îl vom denumi func ție
de căutare (func ție search). Acest lucru este ilustrat în figura 1.4.
În ceea ce prive ște funcția search aceasta are ca și component ă de bază o buclă
în care se realizeaz ă succesiv: extragerea noului nod successor, testarea dac ă acest nod
corespunde st ării finale, ad ăugarea succesorilor nodului curent în lista utilizat ă pentru
memorarea st ărilor. Lista de noduri este cea care face diferen ța între diversele strategii
de căutare, aceasta fiind stiv ă, coadă, listă ordonată după euristică etc. Pseudocodul
funcției search este urm ătorul:
funcție search {
nod_curent.stare = stare_ini țială
adaugă nod_curent în lista_noduri
repet ă la infinit {
dac ă lista_noduri este vidă atunci return(failure)

Aplicații cu strategii de c ăutare neinformate și informate – 14
–
nod_curent = extrage_nod( listă_noduri )
dac ă nod_curent.stare=stare_final ă atunci solu ție()
adaug ă în lista_noduri succesori( nod_curent )
}
} sfârșit funcție

1.6 Exerci ții

1. Se consider ă un puzzle 3×3 (asemenea celui din figura 2) și un tablou cu leduri de
dimensiune 3×3 la care prin ap ăsarea unui led acesta î și schimbă starea proprie din
stins în aprins ( și invers) precum și a ledurilor aflate în stânga, dreapta, sus, jos fa ță de
acesta. În starea ini țială toate ledurile sunt stinse și se dorește o stare final ă cu toate
ledurile aprinse. Se cere:
a) Care este dimensiunea spa țiului starilor pentru cele 2 probleme?
b) Care sunt operatorii asocia ți?
c) Desena ți arborele de c ăutare.

2. Una dintre cele mai vechi prob leme abordate de strategiile de c ăutare este problema
canibalilor și misionarilor. Trei canibali și trei misionari se afl ă pe marginea unui râu,
știind că barca de care dispun nu poate lua decât 2 persoane și pe nici unul dintre
țărmuri nu pot fi mai mul ți canbali decât misionari s ă se găsească o soluție pentru ca
aceștia să traverseze râul (în figura 1.5 este sintetizat arborele de c ăutare pentru aceast ă
problemă).

Aplicații cu strategii de c ăutare neinformate și informate – 15
–

Figura 1.4. Abordarea general ă a unei probleme folosind o strategie de c ăutare

Aplicații cu strategii de c ăutare neinformate și informate – 16
–

Figura 1.5. Arborele de c ăutare pentru problema canibalilor și misionarilor

Aplicații cu strategii de c ăutare neinformate și informate – 17
–
Lucrarea 2 Strategii neinformate de c ăutare:
strategiile de c ăutare pe nivel și bidirec țională

2.1 Strategii de c ăutare și caracteristici ale acestora

Strategiile de c ăutare care nu folosesc euristici pentru a alege nodul successor
se mai numesc și strategii de c ăutare neinformate sau oarbe (blind-search). Șapte
strategii de c ăutare neinformate sunt abordate în acest material:
¾ Strategia de c ăutare pe nivel (Breadth-First)
¾ Strategia de c ăutare în adâncime (Depth-First)
¾ Strategia de c ăutare cu cost uniform (Uniform Cost)
¾ Strategia de c ăutare limitat ă în adâncime (Depth-Limited)
¾ Strategia de c ăutare iterativ ă în adâncime (Iterative-Deepening)
¾ Strategia de c ăutare bidirec țională (Bidirectional search)
Cu privire la toate acestea, inclusiv strategiile informate ce vor urma,
intereseaz ă aflarea răspunsului la urm ătoarele întreb ări:
a) Care este complexitatea de timp a strategiei?
b) Care este complexitatea de spa țiu a strategiei?
c) Este strategia complet ă?
d) Este strategia optimal ă?
e) Cum se implementeaz ă?
f) Ce avantaje și dezavataje are?
Răspunsul la întreb ările de la a) la f) va fi dat în cele ce urmeaz ă în cazul
particular al fiec ărei strategii în parte. În ceea ce prive ște întrebarea e) aceasta se refer ă
la tipul structurii de date în care se re țin nodurile arborelui de c ăutare. Așa cum se va
observa este vorba de structuri de tip coad ă, stivă sau liste sortate. În ceea ce prive ște
întrebarea de la f) aceasta presupune o analiz ă în baza caracteristicilor proprii de la a)
la e) dar și o analiză comparativ ă cu celelalte strategii.

2.2 Strategia de c ăutare pe nivel (Breadth-First)

Cea mai simpl ă strategie de c ăutare este c ăutarea pe nivel, numit ă și breadth-
first. Aceast ă strategie exploreaz ă nodurile în ordinea nivelelor, altfel spus nodurile de
pe nivelul d sunt explorate înaintea nodurilor de pe nivelul d+1. Acest aspect este
ilustrat în figura 2.1, doar pentru simplita tea figurii s-a optat pentru un arbore binar,
deci exist ă doar doi operatori, altfel num ărul de operatori poate fi variabil.

Aplicații cu strategii de c ăutare neinformate și informate – 18
–

Figura 2.1 Arborele de c ăutare în cazul strategiei breadth-first

¾ Complexitate de timp și spațiu

Complexitatea de timp a strategiei poate fi simplu calculat ă ca
()d dbO b bb T =++++= … 12, unde d este adâncimea primei solu ții a problemei
(depth), iar b este factorul de ramifica ție al problemei (branching factor).
Factorul de ramifica ție maxim este egal cu num ărul de operatori. Trebuie îns ă
observat c ă nu toți operatorii pot fi aplica ți pe orice stare și din acest motiv factorul de
ramificație nu este tot timpul egal cu num ărul de operatori. Astfel putem avea un factor
de ramifica ție minim, maxim și mediu. Dac ă luăm ca exemplu un puzzle 3×3 a șa cum
se poate observa și în figura 2.2 factorul de ramifica ție maxim este 4 și minim 2 dar în
medie va fi 3. Se poate defini deasemenea un factor de ramifica ție efectiv. Acesta se
calculează pe cale experimental ă și este rezultatul ecua ției
21. . .d d
ee e e nb b bb n=+ + ++ ⇒ ≈ unde n este num ărul de noduri explorate ob ținut pe
cale experimental ă.
1 32
4 6
57
81 32
4 65
7 81 32
4 65
7 8
Factor Ramificatie 4 Factor Ramificatie 2 Factor Ramificatie 3

Figura 2.2 Factori de ramifica ție variabili pe problema puzzleului 3×3

Aplicații cu strategii de c ăutare neinformate și informate – 19
–

Complexitatea de spa țiu este ()d dbO bS== deoarece strategia re ține tot
timpul doar nodurile de pe ultimul nivel al arborelui de c ăutare.

¾ Completitudine și optimalitate

Așa cum se poate observa strategia de c ăutare pe nivel este complet ă atunci
când num ărul de operatori este finit deoarece pa rcurge în mod exhaustiv toate nodurile
arborelui de c ăutare.
Strategia este îns ă optimală doar dacă costul cre ște proporțional cu adâncimea,
deci dacă orice nod este mai scump decât orice alt nod aflat pe un nivel deasupra lui.
Altfel spus, dac ă pentru oricare dou ă noduri: ()()( ) )( ,, ygxg yDxDyx <⇒< ∀
unde D este func ția care returneaz ă adâncimea nodului și g reprezint ă costul. Deci nici
un nod de pe nivelul d+1 nu poate fi mai ieftin decat un nod de pe nivelul d , această
condiție este în particular satisfacut ă când costul operatorilor este egal, lucru valabil
pentru multe probleme întâlnite în practic ă, inclusiv problema puzzleului 3×3 anterior
aminitită.

¾ Implementare

Strategia breadth-first poate fi u șor implementat ă folosind o structur ă de tip
coadă (queue) în care la fiecare pas se extrage din coad ă nodul curent și se adaug ă la
sfârșit nodurile rezultate din explorarea nodului curent.

1 2 3 4 3 5 4 5 6 7
Pasul 1 Pasul 2Pasul 3 Pasul 4Extrage nod 1 Adauga succesori nod 1 Extrage nod 2 Adauga succesori nod 2 Extrage nod 3 Adauga succesori nod 3
Coada:

Figura 2.3. Evoluția cozii la strategia de c ăutare Breadth First

¾ Avantaje și dezavantaje

Avantajul major este faptul c ă strategia este complet ă, mai mult este chiar și
optimală în condițiile anterior men ționate.

Aplicații cu strategii de c ăutare neinformate și informate – 20
–
Dezavantajul major este faptul c ă are necesit ăți de memorie mult prea mari,
creșterea spațiului fiind tot exponen țială. În general spa țiul este o problem ă mult mai
mare decât timpul, astfel, dac ă pentru un algoritm care solicit ă mult timp de calcul
putem în cele din urm ă aștepta pân ă când furnizeaz ă rezultatul, în cazul în care
memoria nu este suficient ă, algoritmul evident nu poate rula și nu va furniza nicioadat ă
un rezultat. Tabelul 2.1 ilustreaz ă acest lucru pe o cre ștere exponen țială de timp și
memorie.

Adâncime Timp Memorie
16 0.06 secunde 64 KB
32 1.19 ore 4 GB
40 12 zile 1 TB
56 2284 ani 664 10× TB

Tabel 2.1. Creșterea necesit ăților de timp și spațiu pentru un algoritm de complexitate timp și
spațiu ()nO2 pentru cazul în care dimensiunea unei st ări este 1 octet iar durata unui pas al algoritmului
610− secunde.

2.3 Strategia de c ăutare bidirec țională (Bidirectional search)

O potențială îmbunătățire la adresa strategiei de c ăutare pe nivel poate fi adus ă
prin pornirea a dou ă căutări simultane: una de la starea ini țială către starea final ă și una
în sens invers. Acest lucru duce în mod evident la înjum ătățirea resurselor de timp și
memorie necesare având singura cerin ță suplimentar ă de a păstra o list ă a frontierelor
pentru cele dou ă căutări în care s ă se verifice periodic dac ă nu exist ă noduri care
coincid, figura 2.4 ilustreaz ă acest lucru. Aceast ă strategie poart ă numele de strategia
de căutare bidirec țională și menționăm încă de acum c ă pentru economie de memorie
pe una dintre direc ții poate fi aplicat ă și altă strategie precum strategia de c ăutare în
adâncime ce va fi discutat ă în secțiunea urm ătoare.

Aplicații cu strategii de c ăutare neinformate și informate – 21
–
Stare
InitialaStare
Finala
d
d/2 d/2Arbore de cautare BF Arbore de cautare BF
Noduri Frontiera
Noduri Frontiera

Figura 2.4. Strategia de c ăutare bidirec țională

¾ Complexitate de timp și spațiu

Deoarece adâncimea arborelui de c ăutare se înjum ătățește, complexit ățile de
timp și spațiu vor deveni ( )()2/ 2/ 2… 12d dbO b bb T =++++⋅= respectiv
()2/ 2/2d dbO b S =⋅= . Acest lucru este sugerat și în figura 2.4. La complexitatea de
timp trebuie ad ăugat și timpul de calcul necesar pentru verificarea coliziunilor între
cele două frontiere. Deoarece acest lucru implic ă o căutare binar ă, sub indicatorul O
complexitatea nu se schimb ă, mai exact îns ă timpul de calcul va fi
()2/ 2/
22/ 2
22
22log … log log 1 … 1d d d dbO b b b bb b b bb T = ++ ++++++= în
cazul în care presupunem c ă la fiecare nod nou explorat se verific ă dacă acesta nu
cumva exist ă în lista de frontiere a c ăutării pornite din cealalt ă parte.

¾ Completitudine și optimalitate

Căutarea bidirec țională este complet ă și optimal ă după cum sunt cele dou ă
strategii care le implic ă. Astfel pentru cazul în care se folose ște breadth-first, este
completă tot timpul (atunci când factorul de ramifica ție este finit) și este optimal ă pe
toate cazurile unde este și breadth-first optimal ă.

¾ Implementare

Se implementeaz ă cele două strategii de c ăutare, astfel se porne ște cu breadth-
first simultan de la starea ini țială și de la starea final ă. Pe lângă aceasta se p ăstrează și
două liste ale frontierelor între care se verific ă periodic dac ă nu există coliziuni. Se

Aplicații cu strategii de c ăutare neinformate și informate – 22
–
poate alege breadth-first dintr-o parte și o căutare diferit ă din cealalt ă parte, aten ție însă
la riscurile ca nodurile din cele dou ă frontiere s ă nu coincid ă.

¾ Avantaje și dezavantaje

Avantajul major este c ă reduce semnificativ costurile c ăutării Breath First, dar
mai mult faptul c ă este mult mai rapid ă decât orice alt ă strategie neinformat ă. Ca
dezavantaj r ămâne consumul de memorie care este tot exponen țial. Alt dezavantaj este
faptul că nu poate fi implementat ă dacă nu este cunoscut ă starea final ă sau dacă
operatorii de generare a st ărilor nu sunt inversabili sau sunt greu de calculat
predecesorii.

2.4 Exerci ții

1. Doi fra ți au un vas de 8 litri cu “ap ă” și doresc sa îl împart ă în mod egal. Ei mai
dispun de dou ă vase de 3 respectiv 5 litri goale. Se cere:

a) abstractiza ți starea ini țiala și finală

SI={R 1=0,R 2=0,R 3=8} SF={R 1=0,R 2=4,R 3=4}

b) extrageți operatorii

1. R3 → R2
2. R3 → R1
3. R2 → R1
4. R2 → R3
5. R1 → R2
6. R1 → R3

→ semnifică toarnă conținutul lui R i în R j până când R i este gol sau R j este la
capacitate maxim ă

c) Propuneți o strategie de c ăutare optimal ă și complet ă și precizați complexitatea
acesteia la o adâncime d=8

Breadth-first: S=T=O(bd)=68

d) Căutați soluția folosind strategia de la c) (se va evita explorarea st ărilor care
deja au mai fost întâlnite)

1 2 3 4 5 6

Aplicații cu strategii de c ăutare neinformate și informate – 23
–
{0,0,8} {0,5,3} {3,0,5} Ø Ø Ø Ø
{0,5,3} Ø {3,5,0} {3,2,3} {0,0,8}r Ø Ø
{3,0,5} {3,5,0}r Ø Ø Ø {0,3,5} {0,0,8}r
{3,5,0} Ø Ø Ø {3,0,5} r Ø {0,5,3} r
{3,2,3} {3,5,0} r Ø Ø {3,0,5} r {0,5,3} r {0,2,6}
{0,3,5} {0,5,3} r {3,3,2} {3,0,5} r {0,0,8} r Ø Ø
{0,2,6} {0,5,3} r {3,2,3} r {2,0,6} {0,0,8} r Ø Ø
{3,3,2} {3,5,0} r Ø Ø {3,0,5} r {1,5,2} {0,3,5} r
{2,0,6} {2,5,1} {3,0,5} r Ø Ø {0,2,6} r {0,0,8} r
{1,5,2} Ø {3,5,0} r {3,3,2} r {1,0,7} Ø {0,5,3} r
{2,5,1} Ø {3,5,0} r {3,4,1} {2,0,6} r Ø {0,5,3} r
{1,0,7} {1,5,2} r {3,0,5} r Ø Ø {0,1,7} {0,0,8} r
{3,4,1} {3,5,0} r Ø Ø {3,0,5} r {2,5,1} r {0,4,4}
{0,1,7} {0,5,3} r {3,1,4} {1,0,7} r {0,0,8} r Ø Ø
{0,4,4}

r – înseamn ă stare repetat ă și nu se va dezvolta în continuare
Ø – înseamn ă că operatorul nu poate fi aplicat

e) Determina ți câte noduri au fost explorate, ce adâncime are solu ția și care este
factorul efectiv de ramifica ție

– adâncimea este 8 și au fost explorate doar 14 noduri la un factor efectiv de
ramificație b≈1,39

2. Să se scrie programul C# care rezolv ă problema unui puzzle 3×3 folosind strategia
breadth-first urm ărind interfa ța din figura 2.5 de mai jos. Se cere: a) utilizarea unor
casete text TextBox pentru introducerea st ării inițiale și finale b) pentru consum minim
de memorie se impune codificarea fiec ărei stări a puzzle-ului ca întreg pe 32 de bi ți c)
utilizarea unei cozi Queue pentru pentru implementarea strategiei e) afi șarea pe ecran a
soluției într-un obiect ListBox f) afi șarea pe ecran a cantit ății de memorie utilizate, a
numărului de st ări explorate și a adâncimii solu ției.

Aplicații cu strategii de c ăutare neinformate și informate – 24
–

Figura 2.5. Exemplu de interfa ță pentru un puzzle 3×3

Indicații pentru rezolvare:

¾ Definim o clas ă pentru reprezentarea nodurilor din arborele de c ăutare. Clasa
va conține un constructor care prime ște nodul p ărinte, starea care corespunde
nodului și adâncimea acestuia. Toate aceste valori sunt private și pot fi
returnate cu metode Get.

class SearchTreeNode
{
//nodul parinte
private SearchTreeNode parrentNode = null;
//starea asociata nodului curent
private int state;
//adancimea nodului
private int depth;

public SearchTreeNode (SearchTreeNode pn, int s,
int d)
{
parrentNode = pn;
state = s;
d = depth;
}

public SearchTreeNode GetParrentNode ()

Aplicații cu strategii de c ăutare neinformate și informate – 25
–
{
return parrentNode ;
}

public int GetState ()
{
return state;
}

public int GetDepth ()
{
return depth;
}
}

¾ Coada se declar ă ca obiect de tip Queue. Vom mai defini ca valori globale
starea inițială respectiv starea final ă.

private Queue nodesToExplore = new Queue();
// coada care retine nodurile ce vor fi explorate
private int initialState ; // starea initiala
private int finalState ; // starea finala

¾ Codificarea și decodificarea st ărilor din șir în întreg și invers, util ă pentru
consum sc ăzut de memorie și pentru compararea simpl ă a stărilor, este
realizată de următoarele metode. Vom memora puzzleul ca șir și nu ca matrice
(deci ca matrice liniarizat ă).

// functile DecodeState si EncodeState se utilizeaza
pentru a decodifica starea din intreg in
// vector (pentru a putea face deplsarea spatiului sus,
jos, stanga, dreapta) respectiv codificarea // din vector in intreg pentru a face memorarea starii in
nodul arborelui de cautare
private byte[] DecodeState (int state)
{
byte[] dstate = new byte[9];
int i = 0;
for (i = 0; i<9; i++)
{
dstate[8 – i] = (byte) (state % 10);
state = state / 10;
}
return dstate;

Aplicații cu strategii de c ăutare neinformate și informate – 26
–
}

private int EncodeState (byte[] state)
{
int estate = 0, i = 0;
for (i = 0; i < 9; i++)
{
estate = estate * 10 + state[i];
}
return estate;
}

¾ Succesorii se genereaz ă în baza metodelor de mai jos

//generare stare succesor in functie de operatorul aplicat
up, down, left, right (daca e 0 nu se aplica, daca e 1 se
aplica)
private byte[] GenerateState (byte[] state, int pos, int
up, int down, int left, int right)
{
int i = 0;
byte[] newstate =new byte[9];
for (i = 0; i < 9; i++)
{
newstate [i] = state[i];
}
newstate [(pos / 3)*3 + pos % 3] =
newstate [((pos / 3) + up * (-1) + down * 1) * 3 + (pos %
3) + left * (-1) + right * 1];
newstate [((pos / 3) + up *(-1) + down * 1) * 3
+ (pos % 3) + left * (-1) + right * 1] = 0;
return newstate ;
}

//adaugare succesori ai starii curente in coada (maxim 4 succesori)
private void AddSuccessors (SearchTreeNode currentNode ){
SearchTreeNode left, right, up, down;
int
i = 0;
while ((i < 9) &&
(DecodeState (currentNode .GetState ())[i] != 0)) i++;
//determina pozitia spatiului liber, se observa ca i div 3
e linia pe care se afla spatiul liber si i mod 3 e coloana
if ( (i / 3) != 0)

Aplicații cu strategii de c ăutare neinformate și informate – 27
–
//nu este pe prim linie deci se poate muta sus
{
up = new SearchTreeNode ( currentNode ,
EncodeState (GenerateState (DecodeState (currentNode .GetState
()), i, 1, 0, 0, 0)), currentNode .GetDepth () + 1);
nodesToExplore .Enqueue(up);
}
if ((i/3) != 2)
//nu este pe linia de jos deci se poate muta jos
{
down = new SearchTreeNode ( currentNode ,
EncodeState (GenerateState (DecodeState (currentNode .GetState
()), i, 0, 1, 0, 0)), currentNode .GetDepth () + 1);
nodesToExplore .Enqueue(down);
}
if ((i%3) != 0)
//nu este pe coloana din stanga deci se poate muta stanga
{
left = new SearchTreeNode (currentNode ,
EncodeState (GenerateState (DecodeState (currentNode .GetState
()), i, 0, 0, 1, 0)), currentNode .GetDepth () + 1);
nodesToExplore .Enqueue(left);
}
if ((i%3) != 2)
//nu este pe coloana din dreapta deci se poate muta
dreapta
{
right = new SearchTreeNode (currentNode ,
EncodeState (GenerateState (DecodeState (currentNode .GetState
()), i, 0, 0, 0, 1)), currentNode .GetDepth () + 1);
nodesToExplore .Enqueue(right);
}
}

¾ Funcția search care implementeaz ă algoritmul de c ăutare este urm ătoarea

//functie search (algoritm de cautare)
private void Search()
{
SearchTreeNode currentNode = new
SearchTreeNode (null, initialState , 0);
nodesToExplore .Enqueue(currentNode );
do
{

Aplicații cu strategii de c ăutare neinformate și informate – 28
–
if ( nodesToExplore .Count == 0 )
//verifica daca mai sunt stari de explorat
{

System.Windows.Forms.MessageBox .Show("Nu exista solutie" );
break;
}
currentNode = (SearchTreeNode )
nodesToExplore .Dequeue();
if ( currentNode .GetState () == finalState )
//verifica daca s-a ajuns la solutie
{

System.Windows.Forms.MessageBox .Show("S-a gasit solutia" );
ShowSolution (currentNode );
break;
}
AddSuccessors (currentNode );
// adauga succesorii starii curente
}while(true);
}

¾ Soluția este afi șată prin parcurgerea arborelui de c ăutare de la nodul cu starea
finală până la rădăcină care conține starea ini țială

//afiseaza solutia in ListBox
private void ShowSolution (SearchTreeNode fs)
{
SearchTreeNode currentnode = fs;
byte[] dstate;
while (currentnode != null)
{
dstate = DecodeState (currentnode .GetState ());
listaSolutie .Items.Add(dstate[0].ToString () + " " +
dstate[1].ToString () + " " + dstate[2].ToString () + " " +
dstate[3].ToString () + " " + dstate[4].ToString () + " " +
dstate[5].ToString () + " " + dstate[6].ToString () + " " +
dstate[7].ToString () + " " + dstate[8].ToString ());
currentnode = currentnode .GetParrentNode ();
}
listaSolutie .SelectedIndex = listaSolutie .Items.Count – 1;
labelAdancime .Text = "Adancime Solutie: " +
listaSolutie .Items.Count.ToString ();

Aplicații cu strategii de c ăutare neinformate și informate – 29
–
labelDim .Text = "Dimensiune Coada: " +
nodesToExplore .Count.ToString ();
}

¾ Alte câteva func ții legate de interfa ță sunt urm ătoarele

//pentru evenimentul Click pe buton
private void startButton_Click (object sender, EventArgs e)
{
nodesToExplore .Clear();
listaSolutie .Items.Clear();
InitStates ();
Search();
}

//initializeaza starea initiala si starea finala din
casetele text
private void InitStates ()
{
byte[] iState = { Convert.ToByte(SI0.Text),
Convert.ToByte(SI1.Text), Convert.ToByte(SI2.Text),
Convert.ToByte(SI3.Text), Convert.ToByte(SI4.Text),
Convert.ToByte(SI5.Text), Convert.ToByte(SI6.Text),
Convert.ToByte(SI7.Text), Convert.ToByte(SI8.Text) };
byte[] gState = { Convert.ToByte(SF0.Text),
Convert.ToByte(SF1.Text), Convert.ToByte(SF2.Text),
Convert.ToByte(SF3.Text), Convert.ToByte(SF4.Text),
Convert.ToByte(SF5.Text), Convert.ToByte(SF6.Text),
Convert.ToByte(SF7.Text), Convert.ToByte(SF8.Text) };
initialState = EncodeState (iState);
finalState = EncodeState (gState);
}

//afiseaza starea selectata din ListBox in casetele text
private void listaSolutie_SelectedIndexChanged (object
sender, EventArgs e)
{
char[] state =
listaSolutie .Items[listaSolutie .SelectedIndex ].ToString ().
ToCharArray ();
SS0.Text = state[0].ToString ();
SS1.Text = state[2].ToString ();
SS2.Text = state[4].ToString ();
SS3.Text = state[6].ToString ();

Aplicații cu strategii de c ăutare neinformate și informate – 30
–
SS4.Text = state[8].ToString ();
SS5.Text = state[10].ToString ();
SS6.Text = state[12].ToString ();
SS7.Text = state[14].ToString ();
SS8.Text = state[16].ToString ();
}

3. Să se rezolve în C# problema anterioar ă folosind c ăutarea bidirec țională.

4. Să se scrie programul C# care rezolv ă problema tabloului cu leduri. Se consider ă un
tablou cu leduri de dimensiune 3×3 la care prin apasarea unui led acesta î și schimbă
starea proprie din stins în aprins ( și invers) precum și a ledurilor aflate în stânga,
dreapta, sus, jos fa ță de acesta. În starea ini țială toate ledurile sunt stinse iar tabloul
trebuie adus în starea final ă în care toate ledurile vor fi aprinse. Se va folosi o interfa ță
apropiată de cea de la problema 2.

Aplicații cu strategii de c ăutare neinformate și informate – 31
–
Lucrarea 3 Evitarea ciclur ilor în algoritmii de
căutare

Stările repetate, st ări în care agentul deja a mai fost și care conduc la ad ăugarea
în listele de succesori a unor noduri ce con țin stări deja explorate, conduc la cre șterea
inutilă a necesit ăților de timp și spațiu precum și la arbori de c ăutare de dimensiune
infinită. De exemplu, datorit ă stărilor repetate, strategia breadth-first anterior
implementat ă pentru puzzleul 3×3 nu g ăsește în timp util solu ția chiar la adâncimi
relativ mici. Mai mult, arborii infini ți fac în unele cazuri ca strategia de c ăutare să nu
mai găsească niciodată soluția problemei, intrându-se într-o bucl ă infinită. Chiar dac ă
strategiile orientate pe c ăutarea pe nivel evit ă buclele infinite, și sunt astfel complete
indiferent de situa ție, același lucru nu se întâmpl ă în cazul c ăutărilor în adâncime ce
vor fi discutate în capitolul urm ător și care în cazul intr ării într-un ciclu nu vor mai
furniza nicicând o solu ție.
Pentru evitarea acestui neajuns exist ă câteva restric ții care pot fi aplicate. În
ordinea cresc ătoare a eficien ței dar și a dificult ății implementare și a resurselor
solicitate acestea sunt:
¾ dintr-un nod fiu nu se accept ă succesori cu aceea și stare cu a nodului p ărinte,
¾ dintr-un nod nu se accept ă succesori cu aceea și stare cu a unui nod care i-a fost
strămoș,
¾ dintr-un nod nu se accept ă succesori cu st ări care au mai fost generate
vreodată.
Desigur, implementarea ultimei metode necesit ă stocarea tuturor st ărilor deja
explorate, pentru aceasta, complexitatea de spa țiu este cea care induce problemele cele
mai mari, altfel complexitatea de timp este logaritmic ă datorită posibilității de a plasa
stările parcurse în liste ordonate și a efectua c ăutări binare.

3.1 Exerci ții

1. Pentru implemetarea strategiei breadth-first pentru puzzleul 3×3 din capitolul
anterior aplica ți restricțiile pentru evitarea st ărilor repetate și extrageți caracterisiticile
de performan ță pentru fiecare dintre restric ții. Se va folosi o interfa ță apropiată de cea
din figura 3.1, care afi șează în plus fa ță de problema anterioar ă și numărul de stări
explorate.

Aplicații cu strategii de c ăutare neinformate și informate – 32
–

Figura 3.1. Exemplu de interfa ță

Indicații pentru rezolvare:

¾ Se folose ște o tabel ă HashTable pentru memorarea st ărilor care sunt deja
explorate

private Hashtable exploredStates = new Hashtable (); //
tabela care retine starile ce au fost deja explorate

¾ În funcția search, înainte de a explora o stare (a îi ad ăuga succesorii) se
verifică în tabela HashTable dac ă stărea nu a fost deja explorat ă

private void Search()
{
SearchTreeNode currentNode = new
SearchTreeNode (null, initialState , 0);
nodesToExplore .Enqueue(currentNode );
do
{
if ( nodesToExplore .Count == 0 )
//verifica daca mai sunt stari de explorat
{

System.Windows.Forms.MessageBox .Show("Nu exista solutie" );
break;

Aplicații cu strategii de c ăutare neinformate și informate – 33
–
}
currentNode = (SearchTreeNode )
nodesToExplore .Dequeue();
if ( currentNode .GetState () == finalState )
//verifica daca s-a ajuns la solutie
{

System.Windows.Forms.MessageBox .Show("S-a gasit solutia" );
ShowSolution (currentNode );
break;
}
if
(!exploredStates .ContainsKey (currentNode .GetState ()))
//verifica daca starea curenta a mai fost explorata
{
AddSuccessors (currentNode ); // adauga
succesorii starii curente

exploredStates .Add(currentNode .GetState (), currentNode );
//adauga starea curenta intre starile explorate
}
}while(true);
}

¾ La repornirea c ăutării se gole ște lista de noduri explorate și a celor care
urmează a fi explorate

private void startButton_Click (object sender, EventArgs e)
{
nodesToExplore .Clear();
listaSolutie .Items.Clear();
exploredStates .Clear();
InitStates ();
Search();
}

3. Să se rezolve în C# problema anterioar ă cu restric ții pentru st ări repetate și folosind
căutarea bidirec țională.

4. Să se scrie programul C# care rezolv ă problema tabloului cu leduri folosind
restricțiile pentru evitarea st ărilor repetate. Se va folosi o interfa ță apropiată de cea de
la problema 1.

Aplicații cu strategii de c ăutare neinformate și informate – 34
–
Lucrarea 4 Strategii neinformate de c ăutare:
strategiile de c ăutare în adâncime, adâncime
limitată și adâncime iterativ ă

4.1 Strategia de c ăutarea în adâncime (Depth-First)

Strategia de c ăutarea în adâncime, a șa cum se va vedea în cele ce urmeaz ă, este
alternativa pentru a reduce consum ul ridicat de memorie de la c ăutarea pe nivel. În
acest caz nodurile sunt explorate în ordinea adâncimii și se revine la nivelul superior
doar când c ăutarea ajunge într-un punct mort (dea d-end). Acest lucru este sugerat în
figura 4.1 pe un arbore de c ăutare de adâncime 4 și factor de ramifica ție 2.

Figura 4.1. Arborele de c ăutare în cazul strategiei depth-first

¾ Complexitate de timp și spațiu

Este ușor de observat c ă în cazul cel mai dezavantajos din punct de vedere
computațional complexitatea de timp este tot ()dbOT= . În ceea ce prive ște spațiul
însă, din cauz ă că explorarea se face întotdeauna în adâncime acesta ajunge la
()dbOS⋅= ceea ce înseamn ă complexitate liniar ă și este desigur un avantaj major
comparativ cu complexitatea exponen țială de la căutarea pe nivel .

¾ Completitudine și optimalitate

Aplicații cu strategii de c ăutare neinformate și informate – 35
–
Căutarea în adâncime nu este complet ă în arbori infini ți, adică atunci când apar
cicluri. Altfel, dac ă se folose ște o constrângere pentru evitarea st ărilor repetate
strategia este complet ă. Deoarece risc ă să găsească soluția aflată la adâncimea cea mai
mare, și nu ține cont nici de costuri, strategia nu este optimal ă.

¾ Implementare

Căutarea în adâncime se implementeaz ă ușor folosind o stiv ă în care sunt
adăugate, evident la începu t, nodurile care rezult ă din explorarea nodului curent și tot
așa. Acest lucru este ilustrat în figura 4.2.

1
Pasul 1 Pasul 2 Pasul 3 Pasul 4Extrage nod 1 Adauga succesori nod 1 Extrage nod 2 Adauga succesori nod 2 Extrage nod 3 Adauga succesori nod 3
Stiva:
2
96
93
6
94
5

Figura 4.2. Evoluția stivei la c ăutarea depth-first

¾ Avantaje și dezavantaje

Avantajul major al strategiei de c ăutare în adâncime este faptul c ă necesitățile
de memorie sunt minimale, complexitatea de spa țiu fiind liniar ă. Dezavantajul major
este că strategia nu este nici optimal ă și nici complet ă.

4.2 Strategia de c ăutare limitat ă în adâncime (Depth-Limited)

Principalul dezavantaj al strategiei de c ăutare în adâncime este faptul c ă nu
este complet ă. Din fericire aceast ă deficien ță poate fi înl ăturată parțial prin
introducerea unei lim ite de adâncime l. Astfel, vor fi explorate doar nodurile pâna la o
limită l și dacă adâncimea solu ției este mai mic ă decât l atunci ea va fi g ăsită.
Utilizarea strategiei de c ăutare în adâncime este recomandat ă atunci când se cunoa ște
adâncimea unei solu ții. De altfel, algoritmul numit BackTracking a șa cum fost
prezentat în cadrul unor materii este de fapt o c ăutare limitat ă în adancime și motivul
pentru care a func ționat era faptul c ă se cunoștea limita de adâncime iar atunci când nu
se cunoștea adâncimea solu ției BackTracking nu se mai putea aplica.

Aplicații cu strategii de c ăutare neinformate și informate – 36
–

¾ Complexitate de timp și spațiu

Complexitatea de timp r ămâne cea de la c ăutarea în adâncime și anume
()dbOT= , la fel și cea de spa țiu ()bdOS= . Deoarece explorarea se face efectiv
până la limita de adâncime l, este mai corect s ă spunem c ă ()lbOT= și ()blOS= .

¾ Completitudine și optimalitate

Strategia de c ăutare limitat ă în adâncime este complet ă doar dac ă adâncimea
unei soluții este mai mic ă decât l, i.e. d<l . Rămâne necesar ă și remarca de la breadth
first, anume c ă arborele trebuie s ă fie finit, ceea ce presupune și un număr de operatori
finit.
Strategia nu este optimal ă deoarece este predispus ă la a găsi întâi solu ția cea
mai adânc ă, mai mult nu ține cont nici de poten țiale costuri ale operatorilor. Totu și este
interesant de observat c ă există un caz în care strategia este optimal ă: atunci când toate
soluțiile problemei se afl ă pe limita de adâncime. Acesta este cazul multor probleme
rezolvate cu backtracking în liceu sau primul an de facultate: aranjarea a n regine pe
tabla de șah, umplerea unei table de șah de dimensiune nxn prin săritura calului etc.

¾ Implementare

Strategia se implementeaz ă identic cu strategia de c ăutare în adâncime, doar c ă
în acest caz se impune și o limită de adâncime peste care func ția search nu mai desface
succesori.

¾ Avantaje și dezavantaje

Principalul avantaj este acela c ă are necesit ăți de memorie sc ăzute, la fel ca la
căutarea în adâncime, în timp ce r ămâne complet ă atunci când d<l. Dezavantajul este
faptul că nu este optimal ă.

4.3 Strategia de c ăutare iterativ ă în adâncime (Iterative-
Deepening)

Ar fi desigur de dorit s ă avem o strategie de c ăutare care este complet ă și
optimală precum c ăutarea pe nivel, dar în acela și timp are necesit ățile de memorie
scăzute de la c ăutarea în adâncime. Din fericire acest lucru este posibil folosind
căutarea limitat ă în adâncime cu limite iterate (0,1,2,3,…). Aceast ă strategie îmbin ă
cele mai bune caracteristici de la c ăutarea în adâncime și căutarea pe nivel apelând

Aplicații cu strategii de c ăutare neinformate și informate – 37
–
succesiv c ăutarea limitat ă în adâncime cu limite iterate. Astfel, unele noduri vor fi
explorate de mai multe ori a șa cum se poate observa și în figura 4.3. În figur ă, pentru a
nu încărca desenul s-a omis faptul c ă primul nod este explorate de 4 ori, pentru cei 4
arbori de c ăutare genera ți la adâncime 1, 2, 3 respectiv 4.

¾ Complexitate de timp și spațiu

Complexitate de timp r ămâne ()dbOT= dar deoarece unele noduri sunt
explorate de mai multe ori, la fiecare itera ție în adâncime, complexitatea este de fapt
() () ()d dbO b b dbd d T =++⋅−+⋅++= … 1 12. Din aceast ă cauză, chiar dac ă din
punct de vedere asimptotic, al indicatorului O, strategia are aceea și complexitate de
timp cu celelalte strategii, în realitate timpul de calcul este mai mare și trebuie s ă ne
așteptăm ca strategia de c ăutare iterativ ă în adâncime s ă dea un r ăspuns într-un timp
ceva mai lung decât celelalte.
Complexitatea de spa țiu rămâne cea de la strategia de c ăutare în adâncime
()dbOS⋅= .

Figura 4.3. Arborele de c ăutare în cazul strategiei iterative-deepening

¾ Completitudine și optimalitate

Strategia este complet ă în arbori fini ți la fel ca strategia de c ăutare pe nivel. De
asemenea este și optimală în acelea și condiții cu strategia de c ăutare pe nivel: costul
crescător odată cu adâncimea (lucru adev ărat în cazul particular al operatorilor cu
costuri egale).

Aplicații cu strategii de c ăutare neinformate și informate – 38
–
¾ Implementare

Se implemenetaz ă prin apelarea iterativ ă a strategiei de c ăutare limitat ă în
adâncime prin iterarea limitei de adâncime l. Structura folosit ă este deci stiva.

¾ Avantaje și dezavantaje

Avantajul major este faptul c ă este optimal ă și complet ă la fel ca strategia de
căutare pe nivel având îns ă necesități scăzute de memorie la fel ca strategia de c ăutare
în adâncime. În general, în spa ții de dimensiune mare este strategia preferat ă datorită
consumului redus de memorie. Dezavantajul este faptul c ă fiecare nod este parcurs de
mai multe ori, dar asimptotic vorbind acest lucru devine irelevant.

4.4 Exerci ții

1. Există probleme pentru care c ăutarea depth-limited este optimal ă și complet ă? Dați
3 exemple și o regulă generală pentru ca depth-limited este optimal ă și complet ă.

2. Se considera un puzzle 3×3 si un tablou cu leduri de dimensiune 3×3 la care prin
apăsarea unui led acesta î și schimba starea proprie din stins în aprins ( și invers) precum
și a ledurilor aflate în stan ga, dreapta, sus, jos fa ță de acesta. Se cere: pentru fiecare
dintre strategiile de cautare neinformate cunoscute explora ți arborele de cautare pân ă la
adâncimea d=3 precizand ordinea în care nodurile au fost explorate și indicând
structura utilizat ă pentru implementare (coad ă, stivă etc.)

3. Să se scrie programul C# care rezolv ă problema unui puzzle 3×3 folosind strategia
depth-first evitând st ările repetate și folosind o interfa ță apropiată de cea din figura de
mai jos. Se recomand ă folosirea codului surs ă din capitolele anterioare.

Aplicații cu strategii de c ăutare neinformate și informate – 39
–

Figura 4.4. Exemplu de interfa ță

Indicații pentru rezolvare:

¾ Coada de la breadth-first în care se re țin nodurile ce urmeaz ă a fi explorate se
transform ă în cazul lui depth-first în stiv ă

private Stack nodesToExplore = new Stack(); // stiva care
retine nodurile ce vor fi explorate

¾ În funcțiile de adăugare succesori și de căutare opera țiile se vor face cu Push și
Pop în loc de Enqueue și Dequeue

//adaugare succesori ai starii curente in coada (maxim 4
succesori)
private void AddSuccessors (SearchTreeNode
currentNode ){
SearchTreeNode left, right, up, down;
int i = 0;
while ((i < 9) &&
(DecodeState (currentNode .GetState ())[i] != 0)) i++;
//determina pozitia spatiului liber, se observa ca i div 3
e linia pe care se afla spatiul liber si i mod 3 e coloana
if ( (i / 3) != 0) //nu este pe prim linie
deci se poate muta sus
{
up = new SearchTreeNode ( currentNode ,

Aplicații cu strategii de c ăutare neinformate și informate – 40
–
EncodeState (GenerateState (DecodeState (currentNode .GetState
()), i, 1, 0, 0, 0)), currentNode .GetDepth () + 1);
nodesToExplore .Push(up);
}
if ((i/3) != 2) //nu este pe linia de jos deci
se poate muta jos
{
down = new SearchTreeNode ( currentNode ,
EncodeState (GenerateState (DecodeState (currentNode .GetState
()), i, 0, 1, 0, 0)), currentNode .GetDepth () + 1);
nodesToExplore .Push(down);
}
if ((i%3) != 0) //nu este pe coloana din
stanga deci se poate muta stanga
{
left = new SearchTreeNode (currentNode ,
EncodeState (GenerateState (DecodeState (currentNode .GetState
()), i, 0, 0, 1, 0)), currentNode .GetDepth () + 1);
nodesToExplore .Push(left);
}
if ((i%3) != 2) //nu este pe coloana din
dreapta deci se poate muta dreapta
{
right = new SearchTreeNode (currentNode ,
EncodeState (GenerateState (DecodeState (currentNode .GetState
()), i, 0, 0, 0, 1)), currentNode .GetDepth () + 1);
nodesToExplore .Push(right);
}
}

//functie search (algoritm de cautare)
private void Search()
{
SearchTreeNode currentNode = new
SearchTreeNode (null, initialState , 0);
nodesToExplore .Push(currentNode );
do
{
if ( nodesToExplore .Count == 0 )
//verifica daca mai sunt stari de explorat
{

System.Windows.Forms.MessageBox .Show("Nu exista solutie" );
break;

Aplicații cu strategii de c ăutare neinformate și informate – 41
–
}
currentNode = (SearchTreeNode )
nodesToExplore .Pop();
if ( currentNode .GetState () == finalState )
//verifica daca s-a ajuns la solutie
{

System.Windows.Forms.MessageBox .Show("S-a gasit solutia" );
ShowSolution (currentNode );
break;
}
if
(!exploredStates .ContainsKey (currentNode .GetState ()))
//verifica daca starea curenta a mai fost explorata
{
AddSuccessors (currentNode ); // adauga
succesorii starii curente

exploredStates .Add(currentNode .GetState (), currentNode );
//adauga starea curenta intre starile explorate
}
}while(true);
}

¾ La repornirea c ăutării trebuie golit ă acum stiva de nodurile ce urmeaz ă a fi
explorate

4. Să se rezolve problema anterioar ă folosind c ăutarea limitat ă în adâncime și căutarea
iterativă în adâncime.

5. Să se rezolve problema anterioar ă folosind c ăutarea bidirec țională cu breath-first
dintr-o parte și depth-first din cealalt ă parte.

6. Să se scrie programul C# care rezolv ă problema tabloului cu leduri folosind
iterative-deepening. Se poate rezolva aceast ă problemă folosind depth-first?

Aplicații cu strategii de c ăutare neinformate și informate – 42
–
Lucrarea 5 Strategii neinformate de c ăutare:
strategia de c ăutare cu cost uniform

5.1 Strategia de c ăutare cu cost uniform (Uniform Cost)

Ceea ce nici una din strategiile de c ăutare anterior introduse nu putea s ă
rezolve era optimalitatea pentru cazul în care operatorii nu au costuri egale și deci
costul unor noduri de pe un nivel mai mare (aflat mai jos în arbore) nu este neap ărat
mai mare decât costul unor noduri de pe un nivel mai mic. Strategia de c ăutare cu cost
uniform rezolv ă eficient aceast ă problemă. Strategia mai este cunoscut ă și ca Dijkstra's
Single-Source Shortest Path sau simplu algoritmul lui Dijkstra.
Strategia func ționeză similar cu strategia de c ăutare pe nivel doar c ă de aceast ă
dată nodurile sunt explorate nu în ordinea nivelelor ci în ordinea costurilor explorându-
se întotdeauna nodul cel mai ieftin. În cazul în care costul operatorilor este egal,
strategia de c ăutare cu cost uniform se comport ă identic cu strategia de c ăutare pe
nivel.
Un scurt exemplu poate fi util în l ămurirea modului de func ționare al
strategiei. Fie graful orientat aciclic din figura 5.1, se dore ște găsirea celui mai scurt
drum de la A la E. Pentru aceasta nodurile sunt explorate în ordinea costurilor, lucru
indicat în figura 5.2 în care se observ ă că drumul g ăsit de strategie este A-C-E care este
cel mai ieftin.

Figura 5.1. Graf orientat aciclic

Aplicații cu strategii de c ăutare neinformate și informate – 43
–

Figura 5.2. Arborele de c ăutare în cazul strategiei cu cost uniform

A
1B
3C
4
Pasul 1 Pasul 2Pasul 3 Pasul 4Extrage nod 1 Adauga succesori nod 1 Extrage nod 2 Adauga succesori nod 2 Extrage nod 3 Adauga succesori nod 3
Lista
ordonata
dupa
cost:D
2B
3C
4E
15E
16C
4E
15

Figura 5.3. Evoluția listei ordonate dup ă costuri

¾ Complexitate de timp și spațiu

Complexitatea de timp este ()dTO b= . O altă valoare frecvent folosit ă pentru
complexitatea de timp este o
mc
cTO b⎛⎞
=⎜ ⎟⎜⎟⎝⎠ unde oc este costul c ăii optime în arbore iar
mceste costul minim al operatorilor. Complexitatea de spa țiu este ()dTO b= .

¾ Completitudine și optimalitate

Aplicații cu strategii de c ăutare neinformate și informate – 44
–
Strategia de c ăutare cu cost uniform este complet ă, costul strict cresc ător odată
cu adâncimea în arbore f ăcând ca ciclurile s ă fie evitate. Strategia este optimal ă în
funcție de cost cu excep ția situației când apar costuri negative în arbore.

¾ Implementare

Se implementeaz ă folosind o list ă sortată crescător după costuri.

¾ Avantaje și dezavantaje

Avantajul strategiei este c ă este complet ă și optimal ă chiar și atunci când
costul nu este strict cresc ător cu nivelul. Dezavantajul îns ă este că are necesit ăți de
memorie ridicate, la fel ca în cazul lui breath-first.

5.2 Exerci ții

1. Poate fi v ăzută căutarea breadth-first ca un caz particular de uniform-cost?

2. Complexitatea strategiei uniform-cost este T=O(bd) . Explicați de ce este corect ă și
relația T=O(bco/cm) unde co este costul c ăii optime în arbore iar cm este costul minim
al operatorilor.

3. Se consider ă un puzzle 3×3 și un tablou cu leduri de dimensiune 3×3 la care prin
apasarea unui led acesta î și schimbă starea proprie din stins în aprins ( și invers) precum
și a ledurilor aflate în st ânga, dreapta, sus, jos fa ță de acesta. Pentru ficare dintre
următoarele strategii stabili ți dacă sunt optimale și complete precum și complexitatea
efectivă de timp și spațiu la o adâncime a solu ției d=10: a) breadth-first b) depth-first c)
depth-limited d) iterative-deepening e) uniform-cost f) bidirectional search.

4. Se consider ă un spațiu cu obstacole de dimensiune 100×100 careuri și un agent
inteligent care doreste s ă ajungă din SI(x,y) în SF(x’,y’) . Fiecare careu are asociat ă o
cotă care are asociat ă o valoare aleatoare și se define ște un prag care reprezint ă
valoarea numeric ă a cotei maxime peste care agentul poate s ă treacă (orice careu a
cărui cotă depășește acest prag se consider ă obstacol). Se consider ă că deplasarea în
linie dreapt ă are costul 100 iar cea în diagonal ă are costul 141. S ă se implementeze
programul C# care rezolv ă această problemă. Se va folosi o interfa ță apropiată de cea
din figura 5.4.

Aplicații cu strategii de c ăutare neinformate și informate – 45
–

Figura 5.4 Exemplu de interfa ță pentru problema spa țiului cu obstacole

Indicații pentru rezolvare:

¾ Se define ște o clasă pentru nodul arborelui de c ăutare

class SearchTreeNode
{
public SearchTreeNode parrent = null;
public int cost;
public int level;
public long id = 0;
public int coordX = 0;
public int coordY = 0;
public int nodeOperator = 0; //degreess from 90 to
360
}

Aplicații cu strategii de c ăutare neinformate și informate – 46
–
¾ Se definesc costurile pentru deplasarea în linie dreapt ă și în diagonal ă

// costul miscarii in linie dreapta
private const int straigthMovement = 100;
// costul miscarii in diagonala sqrt(2) =
1.4142135623730950488016887242097
private const int diagonalMovement = 141;

¾ Se define ște matricea pentru memorarea h ărții și înălțimea treptei pentru
obstacole (ulterior aceasta se va citi dintr-un text-box)

// matrice utilizata pentru memorarea hartii 100×100
private int[,] m = new int[100,100];
private int obstacleHeight = 50;

¾ Se definesc listele cu noduri deja explorate respectiv cu noduri ce urmeaz ă a fi
explorate. Deoarece lista cu noduri ce urmeaz ă a fi explorate trebuie sortat ă se
definește și un obiect de tip IComparer

Hashtable ExploredStates ;
ArrayList StatesToExplore ;
private IComparer myComparer = null;

¾ Clasa care implementeaza IComparer pentru costuri este urm ătoarea

class CostComparer : IComparer
{

int IComparer .Compare(Object x, Object y)
{
SearchTreeNode n1 = (SearchTreeNode )x;
SearchTreeNode n2 = (SearchTreeNode )y;
if (n1.cost > n2.cost)
{
return 1;
}
else
{
if (n1.cost < n2.cost)
{
return -1;

Aplicații cu strategii de c ăutare neinformate și informate – 47
–
}
else
{
return 0;
}
}
}
}

¾ Se genereaz ă aleator harta și se afișează în PictureBox. Pentru a face problema
mai interesant ă harta a fost generat ă aleator cu cote care evolueaz ă de la
centrul spre marginea h ărții astfel încât în centru s ă fie densitate de obstacole
mai mare (pentru simplitate se poate renun ța la acest lucru).

// harta este generata aleator cu obstacole a caror
densitate creste spre centrul hartii
private void GenerateMap ()
{
int i,j;
Random r = new Random();
for (i = 0; i < 100; i++)
{
for (j = 0; j < 100; j++)
{

if ((Math.Pow(i – 50, 2) + Math.Pow(j
– 50, 2)) < Math.Pow(10, 2))
{
m[i, j] = r.Next(128);
}
else
{
if ((Math.Pow(i – 50, 2) +
Math.Pow(j – 50, 2)) < Math.Pow(20, 2))
{
m[i, j] = r.Next(100);
}
else
{
if ((Math.Pow(i – 50, 2) +
Math.Pow(j – 50, 2)) < Math.Pow(30, 2))
{
m[i, j] = r.Next(80);
}

Aplicații cu strategii de c ăutare neinformate și informate – 48
–
else
{
m[i, j] = r.Next(40);
}
}
}
}
}
}

// harta din matrice este desenata in PictureBox
private void DisplayMapOnPictureBox ()
{
Bitmap bmp = new Bitmap(100, 100);
int i, j;
Color col = Color.Green;
for (i = 0; i < 100; i++)
{
for (j = 0; j < 100; j++)
{
bmp.SetPixel (i, j,
Color.FromArgb (col.R , col.G – m[i, j], col.B));
}
}
pictureBoxMap .Image = bmp;
pictureBoxMap .SizeMode =
PictureBoxSizeMode .StretchImage ;
}

¾ Funcția search cu evitarea st ărilor repetate

//algoritmul de cautare (functia Search)
private void Search(SearchTreeNode startNode ,
SearchTreeNode targetNode )
{

bool solutionFound = false;
SearchTreeNode currentNode ;
StatesToExplore .Add(startNode );
// cautarea continua pana cand se gaseste o
solutie
while (solutionFound == false)
{
if (StatesToExplore .Count == 0)

Aplicații cu strategii de c ăutare neinformate și informate – 49
–
{
// daca lista e goala nu mai sunt
succesori si deci nu exista solutie

System.Windows.Forms.MessageBox .Show("Nu exista solutie" );
break;
}
currentNode =
GetNextSuccessor (StatesToExplore );
if (Solution (currentNode , targetNode ))
{

System.Windows.Forms.MessageBox .Show("Solutie Gasita" );
ShowSolution (currentNode );
solutionFound = true;
}
else
{
// verifica daca nodul current nu a
fost deja explorat
if
(!(ExploredStates .ContainsKey (currentNode .id)))
{
AddSuccessors (currentNode ,
StatesToExplore , targetNode );
ExploredStates .Add(currentNode .id,
currentNode );
}
}
}
}

¾ Crearea, ad ăugarea și extragerea succesorilor. Pentru o mai bun ă vizualizare a
mișcărilor au fost codificate dup ă unghiul la care se face mi șcarea 0, 45, 90
etc.

// se adauga succesorii nodului curent in lista dupa cele
8 directii de miscare
private void AddSuccessors (SearchTreeNode node,
ArrayList StatesToExplore , SearchTreeNode target)
{
int i, newX, newY;
SearchTreeNode n;
int cost = 0;

Aplicații cu strategii de c ăutare neinformate și informate – 50
–
for (i = 0; i < 8; i++)
{
newX = -1; newY = -1;
switch ( i*45 )
{
case 0: newX = node.coordX; newY =
node.coordY + 1; cost = straigthMovement ; break;
case 45: newX = node.coordX + 1; newY
= node.coordY + 1; cost = diagonalMovement ; break;
case 90: newX = node.coordX + 1; newY
= node.coordY; cost = straigthMovement ; break;
case 135: newX = node.coordX + 1; newY
= node.coordY – 1; cost = diagonalMovement ; break;
case 180: newX = node.coordX; newY =
node.coordY – 1; cost = straigthMovement ; break;
case 225: newX = node.coordX – 1; newY
= node.coordY – 1; cost = diagonalMovement ; break;
case 270: newX = node.coordX – 1; newY
= node.coordY; cost = straigthMovement ; break;
case 315: newX = node.coordX – 1; newY
= node.coordY + 1; cost = diagonalMovement ; break;
}
// creeaza succesorul doar daca nodul nu
este in afara hartii si nivelul este mai mic decat nivelul obstacolului
if (CoordinatesInsideBounds (newX, newY))
{
if (m[newX,
newY] < obstacleHeight )
{
n = new SearchTreeNode ();
n.parrent = node;
n.Accessible = true;
n.nodeOperator = i * 45;
n.coordX = newX;
n.coordY = newY;
n.id = n.coordX + n.coordY * 10000;
n.level = node.level + 1;
n.heuristic = DiagonalDistance (n,
target);
n.cost = node.cost + cost;
node.succesors [i] = n;
StatesToExplore .Add(n);
}
}

Aplicații cu strategii de c ăutare neinformate și informate – 51
–
}
StatesToExplore .Sort(myComparer );
}

// verifica daca coordonatele sunt in interiorul
hartii
private bool CoordinatesInsideBounds (int x, int y)
{
if ((x >= 0) && (x < 100) && (y >= 0) && (y <
100))
{
return true;
}
else
{
return false;
}
}

// returneaza urmatorul succesor, adica starea cea
mai apropiata de starea finala
private SearchTreeNode GetNextSuccessor (ArrayList
StatesToExplore )
{
SearchTreeNode state =
(SearchTreeNode )StatesToExplore [0];
StatesToExplore .RemoveAt (0);
return state;
}

¾ Afișarea soluției și testarea dac ă un anume nod con ține sau nu starea final ă.

private void ShowSolution (SearchTreeNode position )
{
Bitmap bmp = new Bitmap(pictureBoxMap .Image);
SearchTreeNode n = position ;
while (n != null)
{
bmp.SetPixel (n.coordX, n.coordY,
Color.Red);
n = n.parrent;
}
pictureBoxMap .Image = bmp;
pictureBoxMap .SizeMode =

Aplicații cu strategii de c ăutare neinformate și informate – 52
–
PictureBoxSizeMode .StretchImage ;
labelNoduri .Text = "Noduri explorate: " +
ExploredStates .Count.ToString ();
labelDimensiune .Text = "Dimensiune lista: " +
StatesToExplore .Count.ToString ();
labelCost .Text = "Costul soltiei: " +
position .cost.ToString ();
}

// verifica daca nodul curent este chiar nodul
tinta
private bool Solution (SearchTreeNode node,
SearchTreeNode targetnode )
{
if ((node.coordX == targetnode .coordX) &&
(node.coordY == targetnode .coordY))
{
return true;
}
else
{
return false;
}
}

¾ Funcția care calculeaz ă distanța diagonal ă.

// calculeaza distanta diagonala intre doua puncte
private int DiagonalDistance (SearchTreeNode
current, SearchTreeNode target)
{
int xd = Math.Abs(current.coordX –
target.coordX);
int yd = Math.Abs(current.coordY –
target.coordY);
return straigthMovement * (Math.Max(xd, yd) –
Math.Min(xd, yd)) + diagonalMovement * Math.Min(xd, yd);
}

¾ Funcțiile asociate diverselor evenimente.

private void Form1_Load (object sender, EventArgs e)
{

Aplicații cu strategii de c ăutare neinformate și informate – 53
–
GenerateMap ();
DisplayMapOnPictureBox ();
}

private void buttonGenerateMap_Click (object
sender, EventArgs e)
{
GenerateMap ();
DisplayMapOnPictureBox ();
}

private void buttonCostUniform_Click (object
sender, EventArgs e)
{
SearchTreeNode x = new SearchTreeNode ();
SearchTreeNode y = new SearchTreeNode ();
y.coordX =
Convert.ToInt32(textBoxFinalStateX .Text);
y.coordY =
Convert.ToInt32(textBoxFinalStateY .Text);
y.heuristic = 0;
y.id = y.coordX + 10000 * y.coordY;
x.coordX =
Convert.ToInt32(textBoxInitialStateX .Text);
x.coordY =
Convert.ToInt32(textBoxInitialStateY .Text);
x.heuristic = DiagonalDistance (x, y);
x.id = x.coordX + 10000 * x.coordY;
x.level = 0;
x.parrent = null;
x.cost = 0;
m[x.coordX, x.coordY] = 0;
m[y.coordX, y.coordY] = 0;
ExploredStates = new Hashtable ();
StatesToExplore = new ArrayList ();
myComparer = new CostComparer ();
Search(x, y);
}

5. Se va scrie programul pentru rezolvarea aceleia și probleme de la punctul anterior
dar de aceast ă dată fiecare cot ă reprezint ă costul de acces al careului în cauz ă (se
renunță deci la costul deplas ării în linie dreapt ă și în diagonal ă).

Aplicații cu strategii de c ăutare neinformate și informate – 54
–
Lucrarea 6 Strategii informate de c ăutare:
strategiile de c ăutare best first și greedy

6.1 Ce este o euristic ă

Conform dic ționarului explicativ al limbii române euristic,- ă,euristici cu
referire la procedee și metodologie înseamn ă ceva care serve ște la descoperirea unor
cunoștinte noi. În ceea ce prive ște strategiile de c ăutare, euristica este o informa ție care
ajută la luarea unei decizii cu privre la noul nod ce urmeaz ă a fi explorat, informa ție
care ar trebui s ă conducă mai repede la atingerea st ării finale. Russell și Norvig spun în
lucrarea lor de referin ță “… information about the state space can prevent algorithms
from blundering about in the dark”. Acesta es te rolul eurisiticilor, de a preveni ca o
strategie s ă caute “în întuneric” încercând s ă deschidă o cale mai bun ă, mai scurt ă,
către starea final ă. Strategiile euristice de c ăutare se mai numesc și strategii informate
de căutare.
Euristica este valoarea estimat ă a distanței de la starea curent ă la starea final ă,
iar funcția care evalueaz ă acest lucru o not ăm în general cu h, i.e.

h(n) = costul estimat al celei mai ieftine c ăi de la nodul dat la nodul solu ție

Deci euristica este o func ție care se aplic ă unui nod dintr-un arbore de c ăutare,
mai exact st ării asociate lui, și se folose ște la ordonarea nodurilor în lista de noduri ce
urmează a fi explorate. Astfel, lista este ordonat ă după euristică în cazul c ăutării
Greedy respectiv dup ă cost plus euristic ă în căutarea cazul A*, a șa cum se va vedea în
cele ce urmeaz ă.
Pentru ilustrarea mai clar ă a conceptului de euristic ă iată câteva exemple de
euristici:
¾ Pentru explorarea unei h ărti funcția h(n) poate fi distan ța în linie dreapt ă de la
punctul current la punctul final (numit ă și Straight Line Distance Heuristic
hSLD).
¾ Pentru umplerea unui rucsac cu obiecte: h(n) poate fi spa țiul liber care r ămîne
în rucsac (sau invers volumul/greutatea obiectului ales).
¾ Pentru un puzzle h(n) poate fi num ărul de piese aflate în pozitii gre șite sau
suma distan țelor pieselor pân ă la poziția lor final ă, sumă evaluată ca suma
distanțelor Manhattan a fiec ărei piese pân ă la poziția ei final ă (distanța
Manhattan se mai nume ște și “city block distance” și este distan ța în linie
dreaptă fără a merge în diagonal ă).

Aplicații cu strategii de c ăutare neinformate și informate – 55
–
1 32
4 65
7 81 32
4 65
7 8
Stare Finala Stare Curenta
Numarul de piese care nu sunt la locul lor: 1+0+1+0+0+0+1+0+1=4
Suma distantelor Manhattan: 2+0+2+0+0+0+2+0+2=8

Figura 6.1 Stare a unui puzzle 3×3 cu valorile celor dou ă euristici

Se face relevant ă următoarea observa ție. Căutarea cu cost uniform utilizeaz ă o
informație pe baza c ăreia se decide care este nodul cel mai bun dar aten ție aceasta nu
este o căutare euristic ă deoarece aceast ă măsură este un simplu cost care faciliteaz ă
găsirea solu ției optimale ca și cost dar nu împinge strategia spre starea final ă. Este
extrem de relevant s ă putem distinge între ce înseamn ă un cost și ce înseamn ă o
euristică, dacă un cost ajut ă strategia la a g ăsi soluția de cost optim euristica aduce
avantaje în necesit ățile de timp și necesitățile de spa țiu.

6.2 Strategia de c ăutare Best First

Strategia Best-First este un simplu model teoretic și idealizat de strategie de
căutare euristic ă. Aceasta presupune explorarea nodului și alegerea ca successor a celui
mai bun nod. Sigur acest lucru este imposibil de realizat în general pentru c ă este
necesară o funcție care evalueaz ă care este nodul cel mai bun, iar dac ă o astfel de
funcție ar exista nici nu mai am avea nevoie de un arbore de c ăutare pentru c ă strategia
de căutare ar merge direct c ătre soluție având complexitate de timp și spațiu liniară.
Deci noțiunea de c ăutare best-first r ămâne doar ca model idealizat al strategiilor
euristice.

6.3 Strategia de c ăutare Greedy

Aplicații cu strategii de c ăutare neinformate și informate – 56
–
Strategia greedy alege spre explorare întotdeauna nodul care este cel mai
apropiat de starea final ă, deci cel cu cea mai bun ă euristică. În acest sens se poate face
o analogie cu strategia cu cost uniform care alegea întotdeauna nodul cu costul cel mai
bun. Dac ă strategia de c ăutare cu cost uniform p ăstra o list ă sortată după valoarea
costului, Greedy va p ăstra o listă sortată după valoarea euristicii.

¾ Complexitate de timp și spațiu

Complexitatea de timp a strategiei Greedy este tot ()dTO b= în cel mai
defavorabil caz. La fel și complexitatea de spa țiu ()dSO b= . În practic ă însă, de cele
mai multe ori nu ne confrunt ăm cu cazuri defavorabile pentru Greedy și timpul de
calcul respectiv spa țiul sunt mult mai mici.

¾ Completitudine și optimalitate

Strategia greedy nu este complet ă în arbori infini ți, ciclurile conducând evident
la blocaje. Dac ă se folosesc mecanisme de evitare a ciclurilor, strategia este complet ă.
Totodată, strategia nu este nici optimal ă deoarece nu ține cont de costuri.

¾ Implementare

Greedy se implementeaza identic cu strategia cu cost uniform, doar c ă nodurile
sunt păstrate în list ă ordonate dup ă euristică și nu după cost. Se poate îns ă implementa
și pe paradigma de la c ăutarea în adâncime, folosindu-se o stiv ă și păstrându-se un
consum mai mic memorie dar conducând mai încet spre solu ție.

¾ Avantaje și dezavantaje

Avantajul major este c ă strategia greedy ofer ă rapid solu ții și în practic ă greedy
se dovede ște a fi o alegere foarte bun ă atunci când nu se dore ște găsirea unei solu ții
optimale. Dezavantajul este c ă strategia nu este complet ă și nici optimal ă, deasemenea
când se implementeaz ă identic cu uniform-cost poate conduce la necesit ăți de memorie
ridicate.

6.4 Exerci ții

1. Să se scrie programul pentru problema puz zleului 3×3 din capitolele anterioare
folosind strategia informat ă Greedy. Se va rezolva pentru ambele euristici anterior
introduse și se vor compara rezultatele ob ținute: adâncime solu ție, număr de noduri
explorate etc.

Aplicații cu strategii de c ăutare neinformate și informate – 57
–

2. Se consider ă spațiul cu obstacole din capitolul anterior. S ă se scrie programul care
rezolvă această problemă folosind strategia Greedy. Se va folosi interfa ța din figura
6.2.

Figura 6.2 Exemplu de interfa ță pentru problema spa țiului cu obstacole

Inidicații pentru rezolvare

¾ În clasa pentru nodul arborelui de c ăutare se adaug ă euristica

class SearchTreeNode
{
public SearchTreeNode parrent = null;
public int cost;
public int heuristic ;
public int level;
public long id = 0;
public int coordX = 0;
public int coordY = 0;

Aplicații cu strategii de c ăutare neinformate și informate – 58
–
public int nodeOperator = 0; //degreess from 90 to
360
}

¾ Se folosește un IComparer pe baz ă de euristic ă

¾ Restul programului este identic cu cel din lucrarea anterioar ă, doar sortarea se
va face dup ă euristică așa cum rezult ă din următorul cod surs ă

private void buttonGreedy_Click (object sender, EventArgs
e)
{
SearchTreeNode x = new SearchTreeNode ();
SearchTreeNode y = new SearchTreeNode ();
y.coordX =
Convert.ToInt32(textBoxFinalStateX .Text);
y.coordY =
Convert.ToInt32(textBoxFinalStateY .Text); class HeuristicComparer : IComparer
{

int IComparer .Compare(Object x, Object y)
{
SearchTreeNode n1 = (SearchTreeNode ) x ;
SearchTreeNode n2 = (SearchTreeNode ) y ;
if (n1.heuristic > n2.heuristic )
{
return 1;
}
else
{
if (n1.heuristic < n2.heuristic )
{
return -1;
}
else
{
return 0;
}
}
}

Aplicații cu strategii de c ăutare neinformate și informate – 59
–
y.heuristic = 0;
y.id = y.coordX + 10000 * y.coordY;
x.coordX =
Convert.ToInt32(textBoxInitialStateX .Text);
x.coordY =
Convert.ToInt32(textBoxInitialStateY .Text);
x.heuristic = DiagonalDistance (x, y);
x.id = x.coordX + 10000 * x.coordY;
x.level = 0;
x.parrent = null;
x.cost = 0;
m[x.coordX, x.coordY] = 0;
m[y.coordX, y.coordY] = 0;
ExploredStates = new Hashtable ();
StatesToExplore = new ArrayList ();
myComparer = new HeuristicComparer ();
Search(x, y);
}

3. Se va scrie programul pentru rezolvarea aceleia și probleme de la punctul anterior dar
de această dată fiecare cot ă reprezint ă costul de acces al careului în cauz ă (se renun ță
deci la costul deplas ării în linie dreapt ă și în diagonal ă).

Aplicații cu strategii de c ăutare neinformate și informate – 60
–
Lucrarea 7 Alegerea unei euristici

Pentru problemele discutate în acest material, dar și pentru multe alte probleme
din practic ă, este ușor să inventăm euristici. Nu în utimul rând exist ă și programe
dedicate pentru aceasta. Problema care se pune acum este de a decide din mai multe
euristici care este mai bun ă. Astfel, dac ă pentru dou ă euristici h1, h2 avem h1(n)>h 2(n)
atunci spunem c ă h1 domină pe h2 și utilizarea euristicii dominatoare duce întotdeauna
la un rezultat mai bun, adic ă vor fi explorate mai pu ține noduri pentru a g ăsi soluția. La
modul general, dac ă se cunosc mai multe euristici monotone h1,h2,…,h m și nu se știe
care euristic ă domină se poate utiliza h(n)=max(h 1,h2,…,h m ).

7.1 Probleme cu constrângeri

O gamă aparte de probleme decizionale sunt problemele cu constrângeri, în
care un set de variabile care pot lua diverse valori trebuie s ă satisfacă anumite
constrângeri pentru ca starea final ă să fie atinsă. Între cele mai cunoscute probleme cu
constrângeri, studiate în liceu sau în primii ani de facultate, sunt: a șezarea a 8 regine pe
o tablă de șah, colorarea unei h ărți etc. În acest caz sunt în general preferate
urmatoarele trei euristici:
¾ Euristica celei mai constrânse variabile – variabila care poate lua cele mai
puține valori este aleas ă.
¾ Euristica variabilei cu cea mai mare putere de constrângere – variabila care
constrânge cele mai multe variabile este aleas ă.
¾ Euristica valorii cu cea mai mic ă putere de constrângere – valoarea care ofer ă
cea mai mare libertate în alegerile ulterioare este aleas ă.
Pentru evitarea st ărilor fără rezolvare se folose ște mecanismul numit forward-
checking. De exemplu: la problema a șezării celor 8 regine, se încearc ă așezarea unei
noi regine doar pe pozi țiile pe care nu este deja atacat ă.

7.2 Rolul unei euristici

Rolul unei euristici este de a aduce factorul efectiv de ramifica ție către 1
deoarece în acest caz indiferent de adâncimea solu ției necesit ățile de timp și spațiu nu
vor înregistra o cre ștere exponen țială. Sigur, pentru marea parte a problemelor o
euristică care să realizeze acest lucru nu se poate g ăsi, dar se poate constata c ă
euristicile reu șesc în general s ă reducă semnificativ factorul de ramifica ție. Pentru
evaluarea eficien ței unei euristici se poate calcula factorul efectiv de ramifica ție așa
cum a fost el definit în capitolul 2.

Aplicații cu strategii de c ăutare neinformate și informate – 61
–
7.3 Exerci ții

1. Scrieți programul pentru rezolvarea problemei aranj ării a 8 regine pe tabla de șah
folosind diverse constrângeri și compara ți rezultatele ob ținute.

2. Scrieți programul pentru rezo lvarea problemei color ării unei h ărți folosind diverse
constrângeri și compara ți rezultatele ob ținute.
3. Scrieți programul pentru rezolvarea problemei unui puzzle 3×3 cu cele dou ă euristici
din secțiunea anterioar ă și compara ți rezultatele ob ținute. Care dintre cele dou ă
euristici este cea dominatoare.

Aplicații cu strategii de c ăutare neinformate și informate – 62
–
Lucrarea 8 Strategii informate de c ăutare:
strategia de c ăutare A*

Strategia A* poate fi v ăzută ca o combina ție între strategia de c ăutare greedy și
strategia de c ăutare cu cost uniform, A* combin ând cele mai bune caracteristici ale
acestora. Pentru aceasta A* utilizeaz ă funcția de evaluare a nodului: f(n)=g(n)+h(n)
unde g(n) este costul de la starea ini țială la starea curent ă (funcția de la căutarea cu cost
uniform) iar h(n) este costul celui ieftin drum de la starea curent ă la starea final ă
(euristica de la c ăutarea Greedy).

¾ Complexitate de timp și spațiu

Complexitatea de spa țiu în cel mai r ău caz este exponen țială și la A* dac ă nu
este respectat ă condiția: |h(n)-h*(n)|<O(lg(h*(n))) (h*(n) este costul real pân ă la
starea final ă). Totuși pentru marea parte a situa ților practice A* solicit ă resurse mai
mici decât ceilal ți algoritmi de complexitate exponen țială.

¾ Completitudine și optimalitate

A* este complet ă și este optimal ă cu condi ția ca euristica h(n) să fie
admisibilă. O euristic ă se nume ște admisibil ă dacă nu supraestimeaz ă costul atingerii
stării finale plecând din starea curent ă. Eurisiticile admisibile se mai numesc și euristici
optimiste deoarece întodeauna estimeaz ă că este mai u șor de a ajunge la final decât este
în realitate. În baza discu ției din capitolul anterior se poate utiliza h(n)=max(h 1,h2,…,h m
) iar dacă fiecare din euristicile hi este admisibil ă atunci și h(n) este adimisibil ă.

¾ Implementare

A* se implementeaz ă folosind o list ă sortată crescător după funcția f.

¾ Avantaje și dezavantaje

A* este cea mai bun ă strategie de c ăutare, se poate demostra chiar c ă este
optimal-eficient ă, adică orice altă strategie care exploreaz ă mai puține noduri decât A*
riscă să nu găsească cea mai bun ă soluție. Dezavantajul este c ă necesită resurse de
memorie relative ridicate. Pentru a înl ătura acest dezavantaj o poten țială soluție este
combinarea lui A* cu Iterative Deepening combina ție cunoscut ă sub numele de
Iterative Deepening A* sau IDA*.

Aplicații cu strategii de c ăutare neinformate și informate – 63
–
8.1 Demonstra ție asupra optimalit ății lui A*

Este evident c ă A* este complet ă, costul uniform conducând inevitabil la
explorarea nodurilor pân ă la găsirea unei solu ții. Pentru a demonstra c ă A* este
optimală recurgem la reducere la absurd și presupunem c ă A* nu este optimal ă. Fie în
acest caz co costul optim al c ăii către soluție și fie x o stare final ă sub-optimal ă
returnată de A*, avem deci:

g(x) > c o (1)

Fie un nod n care apar ține căii optimale, deoarece h este o euristica admisibil ă:

co >=f(n) (2)

Deoarece A* nu a deschis starea n avem:

f(n)>=f(x) (3)

Din (2) si (3) rezult ă
c
o >=f(x) (4)

Dar din moment ce x este starea final ă avem:

h(x) = 0 (5)

Acum din (4) și (5) rezult ă:

co >=g(x) (6)
Și deci x nu poate fi suboptimal deoarece costul s ău este mai mic sau egal cu
costul optimal, ceea ce este o contradic ție cu ipoteza (1) și deci A* este optimal.

8.2 Exerci ții

1. Se consider ă harta din figur ă și distanțele în linie dreapt ă (hSLD) din tabel. Se cere:

Aplicații cu strategii de c ăutare neinformate și informate – 64
–

Figura 8.1 Hartă oarecare.

Oras h SLD (Resita)
Timisora 100
Recas 90
Lugoj 30
Buzias 65
Farliug 30
Bocsa 10
Sag 95
Voiteg 40
Deta 70

Figura 8.2 Euristica distan ței în linie dreapt ă pentru punctele de pe hart ă.

a) explicați căutarea greedy și ilustrați ordinea în care nodurile sunt explorate
pentru găsirea unui drum Timi șoara-Reșita

Aplicații cu strategii de c ăutare neinformate și informate – 65
–

Figura 8.3 Arborele de c ăutare pentru strategia Greedy

b) Explicați căutarea A* și ilustrați ordinea în care nodurile sunt explorate pentru
găsirea unui drum Timi șoara-Reșița

Figura 8.4 Arborele de c ăutare pentru strategia A*

Aplicații cu strategii de c ăutare neinformate și informate – 66
–

c) Care dintre cele dou ă căutări a ajuns mai rapid la solutie și care a g ăsit soluția
optimală? Observa ți că arborele de c ăutare are aceea și adâncime pentru ambele
strategii, îns ă doar A* a g ăsit soluția optimal ă (Greedy a parcurs 115km iar A*
94km)

2. Se consider ă spațiul cu obstacole din capitolul anterior. S ă se scrie programul care
rezolvă această problemă folosind strategia A*. Se va folosi interfa ța din figura 8.5.

Figura 8.5 Exemplu de interfa ță pentru problema spa țiului cu obstacole

private void buttonAstar_Click (object sender,
EventArgs e)
{
SearchTreeNode x = new SearchTreeNode ();
SearchTreeNode y = new SearchTreeNode ();
y.coordX =
Convert.ToInt32(textBoxFinalStateX .Text);

Aplicații cu strategii de c ăutare neinformate și informate – 67
–
y.coordY =
Convert.ToInt32(textBoxFinalStateY .Text);
y.heuristic = 0;
y.id = y.coordX + 10000 * y.coordY;
x.coordX =
Convert.ToInt32(textBoxInitialStateX .Text);
x.coordY =
Convert.ToInt32(textBoxInitialStateY .Text);
x.heuristic = DiagonalDistance (x, y);
x.id = x.coordX + 10000 * x.coordY;
x.level = 0;
x.parrent = null;
x.cost = 0;
m[x.coordX, x.coordY] = 0;
m[y.coordX, y.coordY] = 0;
ExploredStates = new Hashtable ();
StatesToExplore = new ArrayList ();
myComparer = new CostPlusHeuristicComparer ();
Search(x, y);
}

3. Se va scrie programul pentru rezolvarea aceleia și probleme de la punctul anterior dar
de această dată fiecare cot ă reprezint ă costul de acces al careului în cauz ă (se renun ță
deci la costul deplas ării în linie dreapt ă și în diagonal ă). Se mai poate folosi euristica
distanței diagonale în acest caz? Explica ți implicațiile, propune ți o altă euristică.

4. Același program de la punctele 3 și 4 dar care deseneaz ă cu culori diferite traseele
urmate de Uniform-cost, Greedy, A* și afișează casete comparative cu parametrii
fiecărei strategii (costul drumului, timp, memorie etc.).

Aplicații cu strategii de c ăutare neinformate și informate – 68
–
Lucrarea 9 Strategii de c ăutare în spa ții cu
incertitudini

Un caz aparte sunt scenariile cu incertit udini, în acest caz agentul inteligent nu
este omniscient cu privire la spa țiul stărilor. De exemplu în cadrul problemei g ăsirii
drumului optim pe o hart ă, harta era generat ă anterior și cunoscut ă de către agent. Dar,
putem la fel de bine trata și cazul în care agentul nu cunoa ște harta și trebuie s ă o
descopere singur. Un astfel de scenariu nu este simplu de tratat din punct de vedere al
optimalității și completitudinii, din fericire putem construi o solu ție relativ eficient ă
bazată pe noțiunile introduse pân ă acum. În cele ce urmeaz ă vom trece direct la
rezolvarea problemei g ăsirii drumului pe harta 100×100 din capitolele anterioare la
care adăugăm faptul c ă harta nu este cunoscut ă în prealabil și agentul trebuie s ă o
descopere. Recurgem la simplificarea în baza c ăreia punctele de pe hart ă au valori
binare 1 sau 0 dup ă cum sunt accesibile sau nu. Se va folosi o interfa ță apropiată de cea
din figura 9.1. Sintetiz ăm indicațiile pentru rezolvare dup ă cum urmeaz ă:

Figura 9.1 Drumul g ăsit de agentul inteligent folosind strategia de c ăutare adaptiv ă

Aplicații cu strategii de c ăutare neinformate și informate – 69
–

¾ Se definesc costurile deplas ării și se genereaz ă harta într-o manier ă similară cu
cea din capitolele aterioare
private const int straigthMovement = 100; // costul
miscarii in linie dreapta
private const int diagonalMovement = 141; //
costul miscarii in diagonala sqrt(2) =
1.4142135623730950488016887242097

private int[,] m = new int[100,100]; // matrice
utilizata pentru memorarea hartii 100×100
// harta este generata aleator cu obstacole a
caror densitate creste spre centrul hartii
private void GenerateMap ()
{
int i,j;
int treshold ;
Random r
= new Random();
for (i = 0; i < 100; i++)
{
for (j = 0; j < 100; j++)
{

if ((Math.Pow(i – 50, 2) + Math.Pow(j
– 50, 2)) < Math.Pow(10, 2))
{
treshold = 4;
}
else
{
if ((Math.Pow(i – 50, 2) +
Math.Pow(j – 50, 2)) < Math.Pow(20, 2))
{
treshold = 6;
}
else
{
if ((Math.Pow(i – 50, 2) +
Math.Pow(j – 50, 2)) < Math.Pow(30, 2))
{
treshold = 8;
}
else

Aplicații cu strategii de c ăutare neinformate și informate – 70
–
{
treshold = 9;
}
}
}
if (r.Next(10) < treshold )
{
m[i, j] = 0;
}
else
{
m[i, j] = 1;
}
}
}
}

// harta din matrice este desenata in PictureBox
private void DisplayMapOnPictureBox ()
{
Bitmap bmp = new Bitmap(100, 100);
int i, j;
for (i = 0; i < 100; i++)
{
for (j = 0; j < 100; j++)
{
if (m[i , j ] == 0)
{
bmp.SetPixel (i, j, Color.White);
}
if (m[i , j ] == 1)
{
bmp.SetPixel (i, j, Color.Black);
}
}
}
pictureBoxMap .Image = bmp;
pictureBoxMap .SizeMode =
PictureBoxSizeMode .StretchImage ;
}

¾ În funcția search are loc urm ătoarea modificare, deoarece nu este sigur c ă
agentul va putea fi mutat în succesorul generat de func ție (ar putea fi un

Aplicații cu strategii de c ăutare neinformate și informate – 71
–
obstacol) se apeleaz ă roboPosition =
MoveBetweenTreeNodes (roboPosition , currentNode ). După
acest apel, c ătre funcția care încearc ă să pună agentul în succesor, dac ă poziția
este egală cu nodul succesor atunci înseamn ă că succesorul a fost accesibil și
deci nu era un obstacol.

//algoritmul de cautare (functia Search)
private void PathFind (SearchTreeNode startNode ,
SearchTreeNode targetNode )
{
int movements = 0;
Hashtable ExploredStates = new Hashtable ();
ArrayList StatesToExplore = new ArrayList ();
bool solutionFound = false;
SearchTreeNode currentNode ;
SearchTreeNode roboPosition ;
SearchTreeNode rootNode ;
roboPosition = startNode ;
rootNode = startNode ;

StatesToExplore .Add(rootNode );
// search continues until a solution is found
or no states to explore axists
while ((StatesToExplore .Count != 0) &&
(solutionFound != true))
{
currentNode =
GetNextSuccessor (StatesToExplore );

if
(!(ExploredStates .ContainsKey (currentNode .id))) // current
node was not explored
{
// inca nu se stie daca pozitia
din nodul curent este sau nu accesibila
// se incearca mutarea robotului
din pozitia curenta in pozitia din nodul curent
roboPosition =
MoveBetweenTreeNodes (roboPosition , currentNode );
// se marcheaza pe harta noua
pozitie a robotului
Bitmap bmp = new
Bitmap(pictureBoxMap .Image);

Aplicații cu strategii de c ăutare neinformate și informate – 72
–
bmp.SetPixel (roboPosition .coordX, roboPosition .coordY,
Color.Blue); pictureBoxMap .Image = bmp;
// se verifica daca pozitia
robotului este identica cu pozitia din nodul curent
if (roboPosition .id ==
currentNode .id)
{
// daca da se adauga
succesorii nodului curent in lista
AddSuccessors (currentNode ,
StatesToExplore , targetNode );

ExploredStates .Add(currentNode .id, currentNode );
}
// daca nu, pozitia din nodul
curent nu este accesibila
else
{
currentNode .Accessible =
false;
}
}
// se verifica daca pozitia curenta este
chiar solutia
if (Solution (roboPosition , targetNode ))
{

System.Windows.Forms.MessageBox .Show("Target Reached" +
movements .ToString ());
solutionFound = true;
}
}
if (solutionFound == false) {
System.Windows.Forms.MessageBox .Show("There is no
solution" ); }
}

¾ Funcțiile de ad ăugare a succesorilor, extragere a noului nod de explorat și de
verificare a coordonatelor sunt similare cu cele din capitolele anterioare.

// se adauga succesorii nodului curent in lista
// atentie, nu toti succesori sunt accesibili,
putand fi si obstacole, lucru care se va afla cand robotul

Aplicații cu strategii de c ăutare neinformate și informate – 73
–
incearca sa miste in acel nod
// dupa ce au fost adaugati, lista de succesori
este sortata
private void AddSuccessors (SearchTreeNode node,
ArrayList StatesToExplore , SearchTreeNode target)
{
int i, newX, newY;
SearchTreeNode n;
for (i = 0; i < 8; i++)
{
newX = -1; newY = -1;
switch ( i*45 )
{
case 0: newX = node.coordX; newY =
node.coordY + 1; break;
case 45: newX = node.coordX + 1; newY
= node.coordY + 1; break;
case 90: newX = node.coordX + 1; newY
= node.coordY; break;
case 135: newX = node.coordX + 1; newY
= node.coordY – 1; break;
case 180: newX = node.coordX; newY =
node.coordY – 1; break;
case 225: newX = node.coordX – 1; newY
= node.coordY – 1; break;
case 270: newX = node.coordX – 1; newY
= node.coordY; break;
case 315: newX = node.coordX – 1; newY
= node.coordY + 1; break;
}
if (CoordinatesInsideBounds (newX, newY))
{
n = new SearchTreeNode ();
n.parrent = node;
n.Accessible = true;
n.nodeOperator = i * 45;
n.coordX = newX;
n.coordY = newY;
n.id = n.coordX + n.coordY * 10000;
n.level = node.level + 1;
n.heuristic = DiagonalDistance (n,
target);
node.succesors [i] = n;
StatesToExplore .Add(n);

Aplicații cu strategii de c ăutare neinformate și informate – 74
–
}
}
IComparer myComparer = new
HeuristicComparer ();
StatesToExplore .Sort(myComparer );
}

// verifica daca coordonatele sunt in interiorul
hartii
private bool CoordinatesInsideBounds (int x, int y)
{
if ((x >= 0) && (x < 100) && (y >= 0) && (y <
100))
{
return true;
}
else
{
return false;
}
}

// returneaza urmatorul succesor, adica starea cea
mai apropiata de starea finala
private SearchTreeNode GetNextSuccessor (ArrayList
StatesToExplore )
{
SearchTreeNode state =
(SearchTreeNode )StatesToExplore [0];
StatesToExplore .RemoveAt (0);
return state;
}

¾ Avem nevoie acum de câteva func ții care nu au mai fost întâlnite în cazul
implement ărilor anterioare, este vorba de func țiile care încearc ă mutarea
robotului între nodurile arborelui de c ăutare. Se disting aici dou ă cazuri
distincte: cazul în care se încearc ă mutarea dintr-un nod fiu într-un nod p ărinte
sau într-un nod care nu este terminal respectiv cazul în care se încearc ă
mutarea într-un nod terminal. În primul caz drumul este accesibil iar în cel de-
al doilea caz trebuie verificat dac ă mutarea poate fi f ăcută. Funcțiile
MoveRobotFromChildToParrentNode,
MoveRobotFromParrentToChildNode adresează primul caz iar func ția
MoveRobotFromParrentToChildNodeIfPossible adresează cel de-

Aplicații cu strategii de c ăutare neinformate și informate – 75
–
al doilea caz. Func ția MoveBetweenTreeNodes folosește cele trei func ții
pentru a deplasa robotul între nodurile arborelui de c ăutare.

// se incearca mutarea robotul intre doua noduri ale
arborelui de cautare
// atentie, pozitia noua este posibil sa nu poata
fi accesata daca este obstacol
private SearchTreeNode
MoveBetweenTreeNodes (SearchTreeNode position ,
SearchTreeNode newposition )
{
SearchTreeNode n;
Hashtable pList = new Hashtable ();
n = newposition ;
// se construieste o lista a parintilor
nodului tinta
while (n != null) { pList.Add(n.id, n); n =
n.parrent; }
n = position ;
// robotul este mutat din parinte in parinte
pana cand se gaseste parintele comun
while (!(pList.ContainsKey (n.id))) { position
= MoveRobotFromChildToParrentNode (n); n = n.parrent; }
// acum robotul este in parintele comun
if (position .id == newposition .id)
{
// daca este chiar pozitia noua ne putem
opri
return position ;
}
else
{
// altfel continuam deplasarea din parinte
in nodul tinta
Stack sList = new Stack();
SearchTreeNode s;
s = newposition .parrent;
// adaugam intr-o stiva toti parintii
nodului tinta
while (s != n) { sList.Push(s); s =
s.parrent; }
// robotul se muta din parinte in fiu pana
cand ajunge la parintele nodului tinta
while (sList.Count != 0) { s =

Aplicații cu strategii de c ăutare neinformate și informate – 76
–
(SearchTreeNode )sList.Pop(); position =
MoveRobotFromParrentToChildNode (s); }
// acum robotul este in parintele nodului
tinta // se efectueaza mutarea daca este
posibila
position =
MoveRobotFromParrentToChildNodeIfPossible (newposition );
return position ;
}
}

// robotul este mutat din nodul fiu in nodul
parinte // atentie, aceasta mutare este tot timpul
posibila, deoarece intr-un nod fiu intotdeauna s-a ajuns dintr-un nod parinte
private SearchTreeNode
MoveRobotFromChildToParrentNode (SearchTreeNode roboNode )
{
return roboNode .parrent;
}

// robotul este mutat din nodul parinte in nodul
fiu
// atentie, aceasta functie este doar pentru cazul
cand nodul fiu este deja explorat si deci accesibil
private SearchTreeNode
MoveRobotFromParrentToChildNode (SearchTreeNode roboNode )
{
return roboNode ;
}

// robotul este mutat din nodul fiu in nodul
parinte
// atentie, aceasta mutare nu este tot timpul
posibila, functia testeaza asadar daca nodul fiu este
accesibil
private SearchTreeNode
MoveRobotFromParrentToChildNodeIfPossible (SearchTreeNode
roboNode )
{
SearchTreeNode n = null;
if (m[roboNode .coordX, roboNode .coordY] == 0)

Aplicații cu strategii de c ăutare neinformate și informate – 77
–
// daca pe harta in acest punct nu este un obstacol
{
if ((roboNode .nodeOperator == 0) ||
(roboNode .nodeOperator == 90) || (roboNode .nodeOperator ==
180) || (roboNode .nodeOperator == 270))
{
n = roboNode ;
}
else // se interzice pe ramura else ca
mutarea sa se faca in diagonala pe langa un obstacol
{
switch (roboNode .nodeOperator )
{
case 45:
if
((m[roboNode .parrent.coordX, roboNode .parrent.coordY + 1]
== 0) && (m[roboNode .parrent.coordX + 1,
roboNode .parrent.coordY ] == 0))
{
n = roboNode ;
}
else
{
n = roboNode .parrent;
}
break;
case 135:
if
((m[roboNode .parrent.coordX, roboNode .parrent.coordY – 1]
== 0) && (m[roboNode .parrent.coordX + 1,
roboNode .parrent.coordY] == 0))
{
n = roboNode ;
}
else
{
n = roboNode .parrent;
}
break;
case 225:
if
((m[roboNode .parrent.coordX, roboNode .parrent.coordY – 1]
== 0) && (m[roboNode .parrent.coordX – 1,
roboNode .parrent.coordY] == 0))

Aplicații cu strategii de c ăutare neinformate și informate – 78
–
{
n = roboNode ;
}
else
{
n = roboNode .parrent;
}
break;
case 315:
if ((m[roboNode .parrent.coordX
– 1, roboNode .parrent.coordY] == 0) &&
(m[roboNode .parrent.coordX, roboNode .parrent.coordY + 1]
== 0))
{
n = roboNode ;
}
else
{
n = roboNode .parrent;
}
break;
}
}
}
else // daca pe harta in acest punct este un
obstacol atunci robotul se va afla tot in nodul parinte
{
n = roboNode .parrent;
}
return n;
}

¾ Următoarele func țiile sunt din nou similare cu cele din capitolele anterioare.

// verifica daca nodul curent nu este chiar nodul
tinta
private bool Solution (SearchTreeNode node,
SearchTreeNode targetnode )
{
if ((node.coordX == targetnode .coordX) &&
(node.coordY == targetnode .coordY))
{

Aplicații cu strategii de c ăutare neinformate și informate – 79
–
return true;
}
else
{
return false;
}
}

// calculeaza distanta diagonala intre doua puncte
private int DiagonalDistance (SearchTreeNode
current, SearchTreeNode target)
{
int xd = Math.Abs(current.coordX –
target.coordX);
int yd = Math.Abs(current.coordY –
target.coordY);
return straigthMovement * (Math.Max(xd, yd) –
Math.Min(xd, yd)) + diagonalMovement * Math.Min(xd, yd);
}

private void Form1_Load (object sender, EventArgs
e)
{
GenerateMap ();
DisplayMapOnPictureBox ();
}

private void buttonGenerateMap_Click (object
sender, EventArgs e)
{
GenerateMap ();
DisplayMapOnPictureBox ();
}

private void buttonSearch_Click (object sender,
EventArgs e)
{
SearchTreeNode x = new SearchTreeNode ();
SearchTreeNode y = new SearchTreeNode ();
y.coordX =
Convert.ToInt32(textBoxFinalStateX .Text);
y.coordY =
Convert.ToInt32(textBoxFinalStateY .Text);
y.heuristic = 0;

Aplicații cu strategii de c ăutare neinformate și informate – 80
–
y.id = y.coordX + 10000 * y.coordY;
x.coordX =
Convert.ToInt32(textBoxInitialStateX .Text);
x.coordY =
Convert.ToInt32(textBoxInitialStateY .Text);
x.heuristic = DiagonalDistance (x, y);
x.id = x.coordX + 10000 * x.coordY;
x.level = 0;
x.parrent = null;
m[x.coordX, x.coordY] = 0;
m[y.coordX, y.coordY] = 0;
PathFind (x, y);
}

9.1 Exerci ții

1. Este algoritmul de c ăutare descris anterior complet? Dar optimal? Modifica ți
programul astfel încât agentul s ă găsească drumul de cost minim.

Aplicații cu strategii de c ăutare neinformate și informate – 81
–
Lucrarea 10 Întreb ări recapitulative și probleme

1. Se consider ă o tablă de șah de dimensiune nxn și se dorește parcurgerea celor nxn
careuri o singur ă dată folosind s ăritura calului. Se cere: a) Care este complexitatea
spațiului stărilor pentru aceast ă problemă b) Propune ți două strategii neinformate de
căutare care s ă fie optimale c) Pentru strategiile propuse în func ție de factorul de
ramificație aferent problemei și de adâncimea c ăutarii preciza ți complexitatea de timp
și spațiu d) Este posibil ă folosirea c ăutării limitate în adâncime pe aceast ă problema și
dacă da atunci este aceast ă strategie complet ă și optimală?

Indicații pentru rezolvare

a) Complexitatea spa țiului stărilor este ()22nO .
b) Strategiile breadth-first și iterative deepening sunt optimale deoacrece costul
operatorilor este egal.
c) Factorul de ramifica ție este 8 iar adancimea este 2nn n×= deoarece calul trebuie s ă
treacă prin fiecare careu o singura data. Pentru breadth-first avem
()()28dn
BF BFTSO bO== = iar pentru iterative-deepening avem ()()28dn
IDTO b O== ,
()()28IDSO b d O n=⋅ =⋅ .
d) Da, căutarea limitat ă în adâncime este complet ă deoarece se cunoa ște adâncimea
soluției 2n și optimală deoarece toate solu țiile se află pe limita de adâncime.

2. Se consider ă spațiul cu obstacole din figura 10.1 și se dorește găsirea unui drum de
la B la A. Numerele supraunitare din careuri reprezint ă costurile trecerii în pozi ția
respectivă. Se cere: a) Demonstra ți dacă euristica “distan ța diagonal ă” este o euristic ă
admisibilă sau nu. b) Propune ți două strategii (una neinformat ă și una informat ă)
complete și două strategii optimale de c ăutare c) Propune ți o euristic ă care să fie
admisibilă d) Explora ți câte 3 noduri folosind cele 4 strategii propuse e) Este c ăutarea
iterativă în adâncime optimal ă pe aceast ă problemă și în caz contrar cum poate fi f ăcută
optimală?

Figura 10.1 Spațiu cu obstacole

Aplicații cu strategii de c ăutare neinformate și informate – 82
–

Indicații pentru rezolvare
a) Distanța diagonal ă nu este o euristic ă admisibil ă deoarece fiecare careu are asociat
un cost aleator (distan ța diagonal ă era o euristic ă definită pentru spa țiul cu obstacole în
cazul când diferen ța de cost ap ărea doar la deplasarea în linie dreapt ă față de
diagonală)
b) Strategii complete: breadth first, bidire ctional search, strategii optimale: uniform
cost, A*
c) Pentru a fi admisibil ă o euristic ă trebuie s ă nu supraestimeze costul drumului între
două puncte, astfel ținând cont c ă avem costuri supraunitare, distan ța între dou ă puncte
este mai mare sau egal ă cu diferen ța maximă dintre coordonatele lor. Aceast ă euristică
se define ște astfel:
(),P P Pxy , (),B B Bx y , (){} ,m a x ,x y hP B=ΔΔ , x PBx x Δ= − ,
yP ByyΔ= − .
e) Căutarea iterativ ă în adâncime nu este optimal ă deoarece costul operatorilor este
diferit. Ea poate fi f ăcută optimală dacă în loc de limita de adancime se utilizeaz ă o
limită de cost iterativ ă.

3. a) Explica ți cum se calculeaz ă complexitatea de timp și spațiu a strategiei Iterative
Deepening b) Da ți un exemplu de spa țiu al stărilor pentru care strategia Depth-First
este mai eficient ă decât Iterative Deepening c) În ce ordine sunt parcurse nodurile dac ă
la strategia Greedy se folose ște euristica h(n)=-g(n) , care ar fi caracteristica esen țială la
nivelul timpului de calcul ( g(n) reprezint ă costul uniform) d) În ce situa ții este A*
optimală, demonstra ți si exemplifica ți.
4. a) Dați un exemplu de problem ă cu constrângeri (CSP) și justifica ți alegerea a
minim dou ă euristici pe aceast ă problemă b) Ce intelege ți prin euristic ă admisibil ă, ce
se întâmpl ă dacă folosim o euristic ă ne-admisibil
ă la A* (explica ți aspectele pozitive și
negative care exist ă). Dați un exemplu de spa țiu al stărilor pentru care strategia Depth-
Limited este mai eficient ă decât Iterative Deepening c) Construi ți o euristic ă pentru
strategia Greedy astfel încât s ă fie explorate întâi nodurile cele mai scumpe d) Este o
euristică admisibil ă monoton ă (exemplifica ți)? e) Explica ți de ce A* nu intr ă în cicluri
infinite f) Da ți un exemplu de spa țiu al stărilor pentru care strategia Iterative
Deepening este mai eficient ă decât A* g) Este o euristic ă monoton ă admisibil ă
(exemplifica ți)? h) Explica ți de ce Iterative Deepening nu intr ă in cicluri infinite.

6. Se consider ă un spațiu bidimensional re ținut într-o matrice de dimensiune mn× și
un agent (entitate) aflat în punctul (),AAAxy ce dorește să ajungă în puctul (),B B Bx y ;
, { 1,2,…, }ABxxm∈ , , { 1, 2,…, }AByy n∈ . Fiecare punct din spa țiu (),P P Pxy are asociat un
cost supraunitar ()() {} , 1,2,…,PP CPx y μ∈ care reprezint ă costul de acces al loca ției

Aplicații cu strategii de c ăutare neinformate și informate – 83
–
respective și orice cost cλ>, λμ≤ se consider ă obstacol și nu poate fi trecut de c ătre
agent. Euristica folosit ă va fi (){} ,m a x ,x y hP B=ΔΔ , x PBx x Δ= − , yP ByyΔ= − iar
pentru costul uniform se utilizeaz ă costul de acces al fiec ărei locații, deci
()() ()() ( ) ,, ( )PP PP gPx y CPx y gP a r i n t e P =+ unde ( )() gParinte P este costul nodului
părinte al lui (),P P Px y (deci la costul fiului se adaug ă costul uniform al tat ălui).
Valorile , ,,,,, ,AA BB m n xyxy λμ sunt variabile și se introduc de la tastatur ă iar costurile
se distribuie aleator pe harta. Se cere:

a) Să se implementeze pe aceast ă problemă strategiile de c ăutare: a) breadth-first b)
depth-first c) depth limited d) iterative deepening e) uniform-cost f) bidirectional
search (breadth first din ambele p ărți) g) bidirectional search (breadth first dintr-o parte
și depth-first din alta) h) bidirectional search (breadth first dintr-o parte și iterative
deepening din alta) i) bidirectional search (uniform cost din ambele p ărți) j) greedy k)
A-star l).
b) Se consider ă că agentul are de parcurs circuitul { }01, ,…,k PPPΩ= și trebuie s ă
depună obiecte în fiecare punct iP⊂Ω respectând un set de priorit ăți {} :0 , 1ΠΩ × Ω →
unde (),1ijPPΠ= dacă depunerea de obiecte în iP este condi ționată de depunerea
prealabilă în jP respectiv (),0ijPPΠ= dacă nu există nici o condi ționare între iP și jP.
Mulțimea Ω și funcția Π (definită sub forma unei matrici) se citesc de la tastatur ă.
Folosind algoritmul (algoritmii) de la a) da ți un traseu pe care agentul poate s ă îl
parcurgă astfel încât circuitul s ă fie parcurs în mod optimal. Observa ție: este evident c ă
mulțimea Ω și relația Π formează un graf orientat aciclic – în cazul în care graful ar
contine cicluri problema nu ar mai avea solu ție.

Programul va afi șa si rezultate refer itoare la timpul de calcul, memoria utilizat ă,
numărul de stări atise, etc.

Aplicații cu strategii de c ăutare neinformate și informate – 84
–

Bibliografie

[1] Konar, A., Artificial Intelligence and Soft Computing Behavioral and
Cognitive Modeling of the Human Brain , CRC Press, 1999.
[2] Korf, R.E., Artificial Intelligence Search Algorithms , Computer Science
Department University of California, Los Angeles, 1998.
http://citeseer.ist.psu.edu/493289.html .
[3] Russell, S.J., Norvig, P., Artificial Intelligence A Modern Approach , Prentice
Hall, Englewood Cliffs, New Jersey, 1996.
[4] Exemple de Jocuri, Learn4Good , (recomandate in scop didactic) –
http://www.learn4good.com/games/.
[5] Exemplu A-star http://www.policyalm anac.org/games/aStarTutorial.htm.

Aplicații cu strategii de c ăutare neinformate și informate – 85
–

Anexe

Anexa 1. Elemente de teoria complexit ății algoritmilor

O problem ă este o mul țime nevid ă de întreb ări între care exist ă o relație, pot fi
una sau mai multe întreb ări și este obligatoriu ca ele s ă aibă o dimensiune finit ă. De
exemplu factorizarea unui întreg este o problem ă cu următorul enun ț: având un întreg n
să se găsească numerele prime al c ăror produs este. Un algoritm este un set bine definit
de pași pentru rezolvarea unei probleme. Altfel spus, un algoritm este ansamblul de
pași prin care un set de date de intrare es te transformat într-un set de date de ie șire în
scopul rezolv ării unei probleme. De exemplu pentru rezolvarea problemei factoriz ării
întregului de mai sus se poate folosi urm ătorul algoritm: pentru to ți întregii i de la 2 la
radical din n verifică dacă n este divizibil cu i.
Este evident c ă eficiența unui algoritm este o func ție care depinde de
dimensiunea datelor de intrare și totodată eficiența unui algoritm trebuie s ă fie o
caracteristic ă intrinsec ă a algoritmului care s ă nu depind ă de un anume model al
mașinii de calcul. În acest context este impropriu s ă numim un algoritm ca fiind
eficient în baza faptului c ă pe un anumit procesor a avut un timp de rulare oarecare, și
mai mult, faptul c ă pe un procesor a avut un anume timp de rulare nu va spune nimic
cu privire la timpul de rulare în momentul în care dimensiunea datelor de intrare se
dublează. Să presupunem ca exemplu naiv doi algoritmi care caut ă un element într-un
șir ordonat cresc ător, algoritmul A1 implementeaz ă o căutare naiv ă în care șirul este
parcurs de la un cap ăt la altul element cu element în scopul identific ării elementului
căutat iar A2 implementeaz ă o căutare binar ă, prin înjum ătățirea succesiv ă a șirului în
care se face c ăutarea. Să presupunem c ă timpul de calcul pentru un tablou cu 1.000.000
de elemente este pentru primul algoritm 5 milisecunde și pentru al doilea 5
microsecunde. La dublarea dimensiunii date lor de intrare timpul de calcul pentru
primul algoritm se va dubla în timp ce pentru al doilea va cre ște nesemnificativ.
Aceasta deoarece, pentru g ăsirea unui element într-un șir de n elemente, primul
algoritm efectueaz ă cel mult n pași iar cel de-al doilea cel mult log 2n pași. În
consecință performan ța unui algoritm nu trebuie descris ă în funcție de timpul de rulare
al acestuia ci în func ție de num ărul de pași pe care algoritmul îi necesit ă. Aici intr ă în
joc teoria complexit ății care este domeniul care ne ofer ă un răspuns cu privire la
numărul de pași necesari ca un algoritm s ă ofere în rezultat.
În general cu privire la un al goritm, sub raportul complexit ății, ne intereseaz ă
atât timpul (despre care s-a spus c ă se măsoară în număr de pași) cât și spațiul (care
înseamnă cantitate de memorie necesar ă) – de aici și noțiunile de complexitate de timp
și complexitate de spa țiu. Pentru m ăsurarea complexit ății folosim urm ătorii indicatori
de performan ță:

Aplicații cu strategii de c ăutare neinformate și informate – 86
–
i) limita asimptotic ă superioar ă:
() ( ) ()()0 0. . , )( nnngcnf ianc ngOnfo ≥∀⋅≤≤ ∃⇔ =
ii) limita asimptotic ă inferioar ă:
() ( ) ()()0 , 0. . , )( nnnf ngc ianc ng nfo ≥∀≤⋅≤ ∃⇔Ω=
iii) limita asimptotic ă restrâns ă:
() ( ) ()()()0 2 1 2 1 . . ,, )( nnngcnf ngciancc ng nfo ≥∀⋅≤≤⋅ ∃⇔Θ=
iv) limitele asimptotice relaxate :
() ( ) ()()0 0 . . )( nnngcnf cian ngonfo ≥∀⋅<≤∀∃⇔=
() ( ) ()()0 0 . . )( nnnf ngc cian ng nfo ≥∀<⋅≤∀∃⇔ =ω
Este important de spus c ă ()() fFgn= , unde F este oricare din indicatorii
Ω, Θ, Ο, ο, nu se cite ște: “f egal F de g(n)”, ci corect este “f este de ordinul F al lui
g(n)” sau mai simplu “f este F(g(n))”. Intuitiv semnul “=“ nu are semnifica ția semnului
egal, în acest caz este echivalent cu ∈.
Astfel în func ție de timpul de calcul algoritmii se împart în clase dup ă cum
urmează: constant ()1O , logaritmic ()()n Olg (se observ ă că
0 ),(lg log >∀Θ= c n nc ), poli-logaritmic ()() lgcOn , fracțional (),0 1cOn c<< ,
liniar ()nO , liniar logaritmic ()2logOn n , pătratic (sau cvadratic) ()2nO , cubic
()3nO , polinomial ()mnO (cu observa ția că: liniar, p ătratic, cubic sunt timpi
polinomiali), super-polinomial ()()nfcO (unde c este o constant ă iar ()nf nu este
constant dar este mai mic decât ()nO ), exponen țial ()()nfcO (unde c este o constant ă
iar ()nf este un polinom de gradul 1) , factorial (sau Combinatorial) ()!On , dublu
exponențial ()2ncO .
Următoarele propriet ăți intuitive decurg direct din defini ția acestor indicatori:
i) () ()()()()()nf ng ngOnf Ω=⇔=
ii) () ()()()()()()()()ng nf ngOnf ng nf Ω=∧=⇔Θ=
iii) () ()()()()()()()()()nhOngf nhOng nhOnf =+⇒=∧=
iv) () ()()()()()()()()()()ninhOngf niOng nhOnf ⋅=⋅⇒=∧=

Aplicații cu strategii de c ăutare neinformate și informate – 87
–
v) () ()() ate reflexivitnfOnf −=
vi) () ()()()()()()()() tate tranzitivinhOnf nhOng ngOnf −=⇒=∧=
Reținem de asemenea urm ătoarele aproxim ări utile:
i) () ()()k k
kk
k n nf ana n a nanf Θ=⇒+⋅++⋅+⋅=−
− 0 11
1 …
ii) ()()n nn non 2 ! ! Ω=∧=
iii) (ln )(ln ln ) ln1l n l n l nnnn cn n n cnn e n n nc n cε<< < < < < < < <
Pentru a ilustra importan ța cunoașterii complexit ății prezent ăm următorul tabel
al unor magnitudini uzuale și de asemenea vom considera 4 algoritmi 1A, 2A, 3A, 4A
având complexit ățile ()nO , ()2nO , ()3nO , ()nO2 precum și un sistem capabil s ă
execute 1010 operații/secundă, în scopul unei compara ții vom evalua timpul necesar
rezolvării algoritmilor pentru 610=n . Tabelul 1 sintetizeaz ă aceste rezultate.

Secunde într-un an 7103×
Vârsta sistemului solar în secunde 17102×
Electroni în univers 771037.8×
Timpul pentru a rezolva 1A 3101−×
Timpul pentru a rezolva 2A 2101×
Timpul pentru a rezolva 3A 8101×
Timpul pentru a rezolva 4A 303020101×
Tabel 1. Câteva magnitudini uzuale.