Cautari Avansate PE Grid

CĂUTĂRI AVANSATE PE GRID

Table of Contents

Introducere

1. Gândirea Umană

2. Gândirea Rațională

3. Comportament Uman

4. Comportament Rațional

5. Scopul acestei lucrări

Capitolul I Agenți Inteligenți

1.1. Agenți Inteligenți ce rezolvă probleme prin căutare

GRAFURI

2.1. Grafuri Neorientate

2.2. Grafuri Orientate

CAPITOLUL III

CĂUTĂRI INFORMATE ȘI NEINFORMATE

3.1. Căutări Informate

3.1.1. Algoritmi Greedy

3.1.2. Algoritmul A*

3.2. Căutări Neinformate

3.2.1. Căutare în adâncime ( Depth First Search)

3.2.2. Căutare în adâncime limitată ( Depth – Limited)

3.2.3. Căutare în adâncime iterativă ( Iterative – Depending)

3.2.4. Căutare în Lățime (Breadth First Search) [1]

3.2.5. Căutare cu cost uniform ( Uniform Cost)

3.2.6. Edsger Wybe Dijkstra

3.2.7. Algoritmul lui Dijkstra

CAPITOLUL IV

APLICAȚIE

-Căutari avansate pe grid-

1.2. Framework-ul Qt [5]

1.2.1. Instalarea Qt [5]

1.2.2. Crearea unui proiect Qt

1.3. Căutări avansate pe grid folosind algoritmul lui Dijkstra

1.3.1. Structura Aplicației

1.3.2. Design-ul aplicației

1.3.3. Funcționalitatea Aplicației

CAPITOLUL V

CONCLUZII

BIBLIOGRAFIE

Introducere

Când a apărut prima dată noțiunea de Inteligență Artificială in 1956, totul părea “un vis prea frumos pentru a putea fi realizat”, fiind considerat greu de atins. Însă in ultimii aproape 50 de ani, termenul a prins contur fiind prezent in aproape toate științele care doresc să se afirme. Profesorul John McCarthy a prezentat noul concept în vara anului 1956 la întrunirea “Darthmouth Summer Research Project on Artificial Inteligence” [1].

Inteligența Artificială poate fi definită ca simularea inteligenței umane procesată de mașini, în special, de sisteme de computere. Acest domeniu a fost, în general, caracterizat de cercetări complexe în laboratoare și doar destul de recent a devenit parte a tehnologiei în aplicații comerciale.

Inteligența artificială este un termen tehnic provenit din limba engleză: Artificial Intelligence, prescurtat AI, care desemnează un domeniu de cercetare în cadrul informaticii. În vorbirea curentă este un produs rezultat în urma desfășurării acestei activități.

Definiția cea mai acceptată a inteligenței artificiale a fost dată de John McCarthy în 1955: “o mașină care se comportă într-un mod care ar putea fi considerat inteligent, dacă ar fi vorba de un om”.

O trăsătură des întâlnită a inteligenței artificiale este că sistemul respectiv este capabil să învețe, cu sau chiar fără ajutoare externe, cu scopul de a se îmbunătăți permanent.

Principalul scop al Inteligenței Artificiale este de a imita întrutotul creierul uman în modul în care acesta gândește, răspunde și interacționează. În pofida nivelului atins de cercetători, acest deziderat nu va fi atins foarte curând, creierul uman fiind încă o enigmă, aproape imposibil de analizat matematic și/sau tradus în limbaj mașină [6].

Indiferent de puterea lor de procesare, mașinile nu vor înlocui, probabil niciodată, omul, cea mai inteligentă și puternică ființă de pe Pământ. Această afirmație este sprijinită de numeroase rațiuni. Cel mai important argument împotriva dezvoltării mașinii cu adevărat inteligente este cel al evoluției. Mașinile nu au parcurs rigorile de supraviețuire timp de milioane de ani precum oamenii. Modul în care aceștia interacționează, gândesc și se adaptează sunt faze de dezvoltare ale intelectului, diferit fiecărui individ în parte. Acestui intelect i-au fost necesare milioane de ani să evolueze, reprezentând, astfel, o etapă extrem de dificil de implementat în dezvoltarea mașinii inteligente.

Unii oameni de știință afirmă că inteligența umană este imposibil de atins și întrecut pe cale artificială de o mașină. În 1989, matematicianul britanic Roger Penrose a susținut că mecanismele de funcționare specifice creierului uman nu pot fi replicate de mașină, nici măcar în principiu. În prezent, creierul uman este considerat a fi cel mai sofisticat computer cunoscut. Afirmația nu poate fi negată, dar creierul uman funcționează pe aceleași principii ca oricare alt creier din regnul animal. Spre a înțelege inteligența umană, trebuie să înțelegem modul în care se formează cele mai simple gânduri. Încercarea de a trece peste aceste etape primare și a cerceta direct acțiunile complexe ale creierului uman este aproape imposibilă.

În Figura 1 avem opt definiții ale Inteligenței Artificiale(IA), împarțite în 2 dimensiuni. Definițiile din primul rând sunt legate de procesele gândirii și ale raționării, iar cele din al 2-lea rând se adresează comportamentului. Definițiile din prima coloană măsoară succesul în raport cu deciziile umane, iar cele din dreapta în raport cu deciziile ideale sau raționale. Un sistem este rațional dacă ia decizia “corectă”, luând în considerare datele de intrare [1].

Istoric, toate cele 4 abordări ale IA au fost urmărite, fiecare de oameni diferiți prin diferite metode. O abordare umană trebuie să fie în parte știință empirică ce implică observații și ipoteze despre comportamentul uman. O abordare a unui raționalist implică o combinație de matematică și inginerie.

Gândirea Umană

Dacă vrem să zicem că un program gândește ca un om, trebuie să avem o metodă prin care să determinăm cum gândesc oamenii. Trebuie să intrăm în mecanismul gândirii umane. Sunt 3 metode pentru a face acest lucru:

Introspecție ( încercarea de a captura gândurile )

Experimente Psihologice ( observarea comportamentului unui individ )

Scanarea Creierului ( observarea creierului in acțiune )

Odată ce avem o teorie a minții suficient de precisă, devine posibilă implementarea acesteia într-un program pe calculator. Dacă comportamentul input-ului și output-ului programului corespund comportamentului uman, aceasta este dovadă a faptului că o parte din mecanismele programului operează și în oameni. De exemplu, Allen Newell și Herbert Simon , dezolvatatorii GPS ("General Problem Solver", Newell and Simon 1961) , nu au fost multumiți de faptul că programul lor doar rezolvă probleme corect. Ei erau mai mult preocupați de compararea pașilor care îi efectua programul cu pașii urmați de oameni în încercarea lor de a rezolva aceeași problem [1].

Domeniul inter-disciplinar al științei cognitivă aduce împreună modele de calculatoare din domeniul IA și tehnici experimentale din psihologie pentru a construii teorii precise și testabile ale minții umane. Știința cognitivă este bazată pe investigare prin experimentare a oamenilor sau animalelor.

În zilele de început ale IA au existat confuzii intre abordări: un autor ar aduce ca argument că, dacă un algoritm funcționeaza bine pe o sarcină, atunci acel algoritm este un model bun al performanței umane, sau vice versa. Autorii moderni separă cele două tipuri de creanțe; această deosebire a permis IA și științei cognitive să se dezvolte mai rapid.

Cele două domenii continuă să se fertilizeze reciproc, cel mai notabil in “Computer Vision”, ce incorporează dovezi neurofiziologice în modele computaționale.

Gândirea Rațională

Filozoful grec Aristotle a fost unul dintre primii care au încercat să codifice “gândirea corectă”. Silogismele lui furnizau modele pentru structuri de argumente care ofereau tot timpul concluzii corecte fiindu-i oferite premise corecte, de exemplu: „Socrates este om, toți oamenii sunt muritor, deci, Socrates este muritor.”. Aceste legi ale gândirii ar fi trebuit să guverneze operațiile minții. Studiul lor a creat domeniul numit „Logica”. Logicienii secolului 19 au dezvoltat o notație precisă pentru tot felul de obiecte din lume și pentru legăturile dintre ele [1].

Până in 1965 existau programe care puteau, în principiu, să rezolve orice problemă ce avea soluție descrisă în notații logice ( dacă nu exista nici o soluție , programul putea rula la infinit ).

Așa numita „Tradiție logicistă” din IA speră să creeze programe pentru sisteme inteligente. Există două obstacole in calea acestei abordări. În primul rând , nu este ușor de luat cunoștiințe informale și rescrise în termenii formali ceruți de notațiile logice, în special când cunoștiințele sunt mai puțin de 100% sigure. Iar în al doilea rând este o diferență enormă între a rezolva o problemă „în principu” și a o rezolva practic. Chiar și problemele cu doar câteva sute de factori pot epuiza resursele computaționale ale oricărui calculator dacă nu au un ghid cu privire la ce pași de raționament să încerce prima dată. Deși ambele obstacole se aplică oricărei incercări de a crea un sistem de raționament computațional, ele apar prima dată în „tradiția logicistă”.

Comportament Uman

Testul Turing [1], propus de Alan Turing (1950), a fost creat cu scopul de a oferi o definiție operațională a inteligenței satisfăcătoare. Un computer trece testul dacă un interogator uman, după ce a pus câteva intrebari, nu poate să spună daca răspunsurile au venit de la un om sau de la un computer. Pentru a programa un computer să treacă un test aplicat riguros presupune foarte multă muncă. Computerul trebuie să posede urmatoarele capacități:

Procesarea limbajului natural pentru a putea comunica

Reprezentarea de cunoștiințe pentru a stoca ce știe sau ce aude

Raționament automat pentru a folosi informațiile stocate să răspundă la întrebări sau să tragă noi concluzii.

Abilitatea de a învăța pentru a se adapta la circumstanțe noi și abilitatea de a detecta și extrapola modele.

Testul lui Turing evită intenționat interacția fizică dintre interogator și computer, deoarece simularea fizică a unei persoane nu este necesară pentru inteligență. Totuși, așa numitul „Test Turing Total” include un semnal video astfel încât interogatorul să poată testa abilitățile de percepție ale subiectului. Pentru a trece acest test, computerul va avea nevoie de COMPUTER VISION pentru a percepe obiectele și de ROBOTICS pentru a putea manipula obiectele și pentru a se putea mișca. Acestea sunt componentele de bază în IA, iar lui Turing i se acordă credit pentru crearea unui test ce rămâne relevant 60 de ani mai târziu. Insă cercetătorii in IA au devotat puțin efort pentru trecerea testului Turing, argumentând că este mai important studiul principiilor de bază ale inteligenței [1].

Comportament Rațional

Un agent este ceva care acționează (termenul „agent” provine din limba latină „agere” . a face). Evident toate programele fac ceva, dar de la agenții unui computer se așteaptă să facă mai multe: să opereze autonom, să-și perceapă mediul, să persiste o perioadă extinsă de timp, să se adapteze schimbărilor agentului rațional și să creeze și să urmărească scopuri. Un agent rațional acționează astfel încât să obțină cel mai bun rezultat. În abordarea „Legilor Gândirii” din IA, accentul s-a pus pe deducții corecte. Făcând deducții corecte face câteodată o parte dintr-un agent rațional, deoarece un mod de a acționa rațional este să ajungi la concluzia că o acțiune iși va atinge scopul și apoi să acționeze pe baza acestei concluzii. Pe de altă parte, facerea de deducții corecte nu reprezinta toata rațiunea, în anumite situații , nu există o soluție corecta, dar totuși trebuie luată o decizie [1].

Există metode de comportare rațional care nu includ deducții. De exemplu, retragerea mâinii de pe aragazul încins este un reflex ce are mai mult succes în mod normal, spre deosebire de luarea unei decizii bazată pe dezbaterea celorlalte soluții.

Toate calificările necesare pentrutestul Turing permit deasemenea unui agent să se comporte rațional. Reprezentarea de cunoștiințe și raționarea permit agenților să ia decizii bune.

Avem nevoie să putem genera fraze inteligibile în limbaj natural pentru a ne folosi in societate. Avem nevoie de abilitatea de a învăța nu doar pentru erudiție ci și pentru că ne îmbunătățește abilitatea de a genera comportament eficient. Abordarea agent-rațional are două avantaje față de celelalte abordări.

Este mai generală decât abordarea „Legile Gândirii” deoarece inferența corectă este doar una din mai e a acționa rațional este să ajungi la concluzia că o acțiune iși va atinge scopul și apoi să acționeze pe baza acestei concluzii. Pe de altă parte, facerea de deducții corecte nu reprezinta toata rațiunea, în anumite situații , nu există o soluție corecta, dar totuși trebuie luată o decizie [1].

Există metode de comportare rațional care nu includ deducții. De exemplu, retragerea mâinii de pe aragazul încins este un reflex ce are mai mult succes în mod normal, spre deosebire de luarea unei decizii bazată pe dezbaterea celorlalte soluții.

Toate calificările necesare pentrutestul Turing permit deasemenea unui agent să se comporte rațional. Reprezentarea de cunoștiințe și raționarea permit agenților să ia decizii bune.

Avem nevoie să putem genera fraze inteligibile în limbaj natural pentru a ne folosi in societate. Avem nevoie de abilitatea de a învăța nu doar pentru erudiție ci și pentru că ne îmbunătățește abilitatea de a genera comportament eficient. Abordarea agent-rațional are două avantaje față de celelalte abordări.

Este mai generală decât abordarea „Legile Gândirii” deoarece inferența corectă este doar una din mai multe mecanisme posibile pentru a ajunge la raționament.

Este mai maleabila către dezvoltarea științifică decât abordările bazate pe comportamentul uman sau gândirii umane.

Un lucru important de ținut minte: obținerea raționamentului perfect – tot timpul luând decizia corectă – nu este posibil in medii complicate. Cerințtele computaționale sunt pur și simplu prea mari.

Scopul acestei lucrări

Scopul acestei lucrări este de a exemplifica modul de funcționare al algoritmilor de căutare în Inteligența Artificială. In acest sens am realizat o aplicație ce va fi prezentată spre finalul lucrării.

În crearea aplicației m-am ghidat pe Comportamentul Rațional. Această aplicație urmărește găsirea celui mai scurt drum dintre două puncte oarecare dintr-un graf neorientat, reprezentat printr-o matrice de adiacență. Punctele reprezintă coordonatele sălilor din cadrul Universității din Craiova, Departamentul de Informatică. În funcție de datele de intrare, căutarea se face fie pe un singur etaj , fie pe etaje diferite în cazul în care sursa se află pe un etaj diferit de punctul destinație.

Ca algoritm de căutare am folosit algoritmul lui Dijkstra.

Capitolul I

Agenți Inteligenți

Agenții Inteligenți sunt entități ce primesc informații din exterior și acționează (ia decizii) în funcție de acestea. Deciziile sunt luate ca urmare a unui comportament rațional, văzut ca un comportament în urma căruia scopul este satisfăcut în concordanță cu convingerile entității ce îl efectuează. Chiar mai mult, un agent ar trebui să gasească, dacă se poate, cea mai bună modalitate de a satisface scopul [6].

Agenți Inteligenți ce rezolvă probleme prin căutare

Ințial vom plasa agentul într-o lume simplă, ce este la un moment dat într-o stare. O acțiune a agentului înseamnă o tranziție între două stări ale lumii (agentul evident modifică mediul în care “trăiește”). Atingerea unui scop implică găsirea unei secvențe de acțiuni ce aduc mediul într-o stare în care scopul este satisfăcut [2].

Vom analiza modul în care un agent decide ce trebuie să facă prin analizarea efectelor ce apar prin considerarea unor secvențe de acțiuni și alegerea celei mai bune secvențe. Pentru asta agentul trebuie să aibă o formulare clară a problemei, a scopului.

Fomularea problemei este procesul prin care decidem ce stări și acțiuni să considerăm. Formularea soluției este procesul prin care considerăm o mulțime de stări finale în care scopul este satisfăcut.

Găsirea scopului se face prin căutare. Un algoritm de căutare ia la intrare o problemă si returnează o soluție, în cazul nostru sub forma unei secvențe de acțiuni (poate returna și un eșec). Acestă secvență recomandată de algoritmul de căutare este executată (fiecare acțiune în parte, respectând ordinea) [2].

Designul agentului urmăreste astfel formularea problemei și a scopului, căutarea soluției, executarea ei.

Exemplu: Definirea unei probleme și cunoașterea scopului

Vom exemplifica prin considerarea problemei Misionarilor și canibalilor. Pentru început vom cita o versiune a problemei: „Trei misionari și trei canibali sunt pe un mal al unui râu, împreună cu o barcă ce poate transporta una sau maxim două persoane. Găsește o modalitate de a aduce pe toată lumea pe partea cealaltă, fără ca să rămână un grup de misionari într-un loc, depășiți ca număr de canibali.”.

Pentru a formaliza problema vom elimina toate lucrurile ce ne deturnează de la esența problemei: vom uita de ploaie, crocodili, adâncimea apei sau lățimea ei sau orice alt detaliu ce nu are importanță la găsirea unei soluții. Pentru a fi mai clar, deși în viața reală toate acestea contribuie la soluție, formalismul presupune considerarea unui subset, toate detaliile fiind greu de mapat ( exemplu: pot apărea membrii unui alt trib care să-i ia ca prizonieri pe misionarii: Maria, Costel și Ilie, să-i ucidă pe canibali și nimeni să nu mai ajungă pe partea cealaltă și să lase barca pe malul inițial ), deci urmărim un singur fir.

• Considerăm stăriile ca fiind o secvență ordonată de trei numere reprezentănd numărul de misionari, numărul de canibali, si barca de pe malul de început. De exemplu starea inițială va fi (3,3,1).

• Considerăm un operator care pornind de la o stare poate lua fie un misionar, fie un canibal, fie doi canibali, fie doi misionari și îi aduce de pe partea cealaltă a râului ( o nouă stare).

• Definim scopul ca fiind starea (0, 0, 0).

• Definim costul ca fiind numărul de treceri ale râului.

Spațiul stărilor este suficient de mic ca problema să poate fi rezolvată ușor din punct de vedere computațional.

CAPITOLUL II

GRAFURI

Grafuri Neorientate

Fie V o mulțime finită și nevidă având n elemente (V = {x1,x2,…,xn}). Fie E o mulțime finită astfel încât E ⊆ V ×V (unde V ×V este produsul cartezian al mulțimii V cu ea însăși) și E = {(x,y)|x,y ∈ V } , (E este mulțimea perechilor (x,y) cu proprietatea că x și y aparțin mulțimii V ).

Se numește graf o pereche ordonată G = (V,E). Elementele ∈ V se numesc noduri sau vârfuri. Elementele mulțimii E sunt arce sau muchii. O muchie (,) ∈ E se mai notează și cu [,].

|V | se numește ordinul grafului G și reprezintă numărul vârfurilor acestuia, iar |E| se numește dimensiunea grafului G și reprezintă numărul muchiilor/ arcelor grafului G.

Graful se numește graful vid.

Dacă într-o pereche [,] nu ținem cont de ordine atunci graful este neorientat iar perechea reprezintă o muchie ([,] = [,]). Dacă se introduce un sens fiecărei muchii atunci aceasta devine arc iar graful se numește orientat ([,] 6= [,]). Muchiile ce au aceleași vârfuri se spune că sunt paralele. O muchie de forma [u,u] se numește buclă. [9]

Un graf G se numește simplu dacă oricare două vârfuri ale sale sunt extremități pentru cel mult o muchie. Un graf este finit dacă mulțimile V și E sunt finite.

Fie un graf neorientat G = (V,E) , simplu și finit. Dacă [x,y] ∈ E vom spune că x și y sunt adiacente, iar muchia [x,y] este incidentă cu vârfurile x și y. Vârfurile x și y se mai numesc capetele muchiei. [9]

Figura 2. Exemplu de graf neorientat

Două muchii sunt adiacente dacă au un vârf comun. Un graf este trivial dacă are un singur vârf. Dacă E = ∅ atunci graful G = (V,E) se numește graf nul.

Un graf neorientat, simplu, finit poate fi utilizat drept model de reprezentare al unei relații simetrice peste o mulțime.

Se numește graf complet de ordinul n, și se notează cu , un graf cu proprietatea că oricare două vârfuri distincte ale sale sunt adiacente (∀x ∈ V,y ∈ V,x y ⇒ [x,y] ∈ E).

Figura 3. Exemplu de graf complet

Un subgraf al unui graf G = (V, E) este un graf H = () unde ⊂ V iar muchiile din sunt toate muchiile din E care au ambele extremități în mulțimea ( = = {[x,y]|[x,y] ∈ E,x,y ∈ V1}).

Se spune că graful H este indus sau generat de submulțimea de vârfuri și se notează H = sau H =.

Gradul unui vârf este egal cu numărul muchiilor incidente cu vârful x și se notează cu d(x) (d(x) = |{[x,u]|[x,u] ∈ E,u ∈ V }|). Un vârf cu gradul 0 (d(x) = 0) se numește vârf izolat.

Notăm δ(G) = min{ (u)|u ∈ G} ¸si ∆(G) = max{ (u)|u ∈ G}.

Figura 4. Graful lui Petersen

Pentru un graf G = (V,E), V = {x1,x2,…,xn}, |E| = m, avem următoarea relație:

Astfel în orice graf G există un număr par de vârfuri al căror grad este un număr impar.

Se numește secvență grafică un șir de numere naturale ,,…, cu proprietatea că ele reprezintă gradele vârfurilor unui graf neorientat.

Un lanț L = [,,…,] este o succesiune de vârfuri cu proprietatea că oricare două vârfuri vecine sunt adiacente ([,] ∈ E, ∀i = ). Vârfurile și se numesc extremitățile lanțului, iar m reprezintă lungimea lanțului.

Dacă vârfurile ,,…, sunt distincte două câte două, lanțul se numește elementar (, ∀i,j = ).

Un lanț L pentru care = se numește ciclu.

Se numește ciclu hamiltonian un ciclu elementar ce trece prin toate vârfurile grafului. Un graf ce admite un ciclu hamiltonian se numește graf Hamilton sau graf hamiltonian.

Un lanț L ce conține fiecare muchie exact o singură dată se numește lanț eulerian. Dacă = și lanțul este eulerian atunci ciclul se numește ciclu eulerian. Un graf ce conține un ciclu eulerian se numește graf eulerian.

Un graf se numește conex dacă pentru orice pereche de vârfuri x și y există un lanț de la x la y.

Se numește componentă conexă un subgraf conex maximal, adică un subgraf conex în care nici un vârf din subgraf nu este adiacent cu unul din afara lui prin intermediul unei muchii aparținând grafului inițial. [9]

Figura 5. Componente Conexe

O muchie e ∈ E se numește muchie critică dacă prin eliminarea acesteia o componentă conexă se împarte în două sau mai multe componente conexe.

Un graf planar este un graf ce poate fi reprezentat în plan astfel încât muchiile sale să nu se intersecteze două câte două.

Un graf G = (V,E) se numește graf bipartit dacă există o partiție a mulțimii nodurilor {,} (V = ∪,∩ = ∅,, ∅) astfel încât orice muchie din E va avea o extremitate în mulțimea și cealaltă extremitate în mulțimea (∀[x,y] ∈ E avem x ∈ și y ∈ ). [9]

Un graf bipartit este complet dacă ∀x ∈ , ∀y ∈ , ∃[x,y] ∈ E (G = (V,E),V = ∪ , ∩ = ∅). Dacă || = p, || = q atunci graful bipartit complet se notează .

Figura 6. Exemplu de graf bipartite si graf bipartite complet

Se numește izomorfism de la graful G la graful o funcție bijectivă ϕ : V (G) → V () astfel încât [u,v] ∈ E(G) ⇔ ϕ([u,v]) ∈ E(). Dacă există un izomorfism de la graful G la graful atunci se spune că G este izomorf cu și notăm acest lucru astfel:.

Un graf etichetat este un graf în care fiecare muchie și vîrf poate avea asociată o etichetă.

Grafuri Orientate

Fie o mulțime finită V = { }. Fie E ⊆ V × V (unde V × V este produsul cartezian al mulțimii V cu ea însăși).

În cazul unui graf orientat, noțiunea de muchie este înlocuită cu noțiunea de arc (o pereche de noduri (x,y) devine ordonată, adică (x,y) (y,x)). Pentru un arc (x,y) ∈ E, vârful x reprezintă extremitatea inițială a arcului, iar vârful y reprezintă extremitatea finală. Vom spune că vârfurile x și y sunt adiacente.

Un graf orientat este o pereche ordonată G = (V, E), unde V este o mulțime de vârfuri sau noduri, iar E este o mulțime de arce.

Un graf parțial al unui graf orientat G = (V, E) este un graf orientat = (V,) unde ⊂ E.

Un subgraf al unui graf orientat G = (V, E) este un graf orientat H = (,)) unde ⊂ V iar arcele din sunt toate arcele din E ce au ambele extremități în mulțimea ( = E|×).

Gradul exterior al unui vârf este egal cu numărul arcelor ce au ca extremitate inițială pe x.

Gradul interior al unui vârf este egal cu numărul arcelor ce au ca extremitate finală pe x (= |{(x,u)|(x,u) ∈ E,u ∈ V }|, = |{(u,x)|(u,x) ∈ E,u ∈ V }|).

Figura 7. Exemplu de graf orientat.

Se numește lanț o secvență de arce L = {,…,} cu proprietatea că oricare două arce consecutive ale secvenței au o extremitate comună. (L = [,,…,] unde (,) ∈ E sau (,) ∈ E, ∀i = ).

Un drum L = = [,,…,] este o succesiune de vârfuri cu proprietatea că oricare două vârfuri vecine sunt adiacente. ((,) ∈ E, ∀i = ).

Dacă vârfurile ,,…, sunt distincte două câte două, drumul se numește elementar.

Un drum L pentru care = se numește circuit.

Se numește circuit Hamiltonian un circuit elementar ce trece prin toate vârfurile grafului. Un graf ce admite un circuit Hamiltonian se numește graf Hamiltonian orientat.

Un drum L ce conține fiecare arc exact o singură dată se numește drum Eu-lerian. Dacă = și drumul este eulerian atunci circuitul se numește circuit Eulerian. Un graf ce conține un circuit Eulerian se numește graf Eulerian orientat.

Un graf se numește conex dacă pentru orice pereche de vârfuri x și y există un lanț de la x la y.

Un graf orientat este complet dacă oricare două vârfuri sunt adiacente. Metodele utilizate pentru reprezentarea unui graf neorientat se pot adapta în mod natural pentru reprezentarea unui graf orientat, înlocuind noțiunea de muchie cu cea de arc.

Un graf orientat care nu posedă circuite se numește graf orientat aciclic (directed acyclic graph – DAG).

Figura 8. Graf Orientat Aciclic

O componentă tare conexă a unui graful orientat G este o mulțime maximală de vârfuri U ⊆ V , astfel încât, pentru fiecare pereche de vârfuri {u,v} (u,v ∈ U) există atât un drum de la u la v cât și un drum de la v la u. Astfel se spune că vârfurile u și v sunt accesibile unul din celălalt.

Un graf orientat ce are o singură componentă tare conexă astfel încât U = V este un graf tare conex. În cazul în care un graf orientat nu este tare conex atunci el se poate descompune în mai multe componente tare conexe. O astfel de componentă este determinată de un subgraf al grafului inițial.

Un graf orientat G se numește tare conex dacă pentru orice pereche de vârfuri u v, există un drum de la nodul u la nodul v și un drum de la nodul v la nodul u.

CAPITOLUL III

CĂUTĂRI INFORMATE ȘI NEINFORMATE

Căutări Informate

Strategii precum metode “oarbe” de căutare (neinformate) pot fi incredibil de ineficiente. Generând sistematic noi stări și testarea lor pentru a determina dacă scopul a fost atins nu este o strategie bună în majoritatea cazurilor.

Inițial definim noțiuni elementare, apoi un algoritm neinformat GeneralSearch pe care îl vom folosi ca bază la algoritmii de căutare informați (mai exact vom oferi informații algoritmului).

Pornim cu o stare inițială. Verificăm dacă starea nu este o stare finală ( stare în care scopul este satisfăcut ) folosind o funcție de testare a scopului. Dacă nu generăm un nou set de stări aplicând operatorul asupra unei stări. Acest proces se numește expandarea stării. De exemplu la probleme cum ar fi găsirea rutelor putem avea mai multe stări posibile pe care le putem expanda. Putem merge de la Bistrița la Iași prin Suceava, Botoșani sau alte rute. Decizia “ce stare să expandăm” îi revine strategiei de căutare. Procesul de căutare poate fi vizualizat sub forma unui arbore de căutare cu noduri-stări având ca rădăcină starea inițială, și frunzele ca stări care nu au fost încă expandate sau care au fost, dar au generat o mulțime vidă de stări.

Algoritmi Greedy

Puși în fața unei probleme pentru care trebuie să elaborăm un algoritm, de multe ori “nu știm cum să începem”. Ca și în orice altă activitate, există câteva principii generale care ne pot ajuta în această situație. Câteva din aceste principii sunt atât de generale, încât le folosim frecvent, chiar dacă numai intuitiv, ca reguli elementare în gândire [2].

Algoritmii greedy (greedy = lacom) sunt în general simpli și sunt folosiți la probleme de optimizare, cum ar fi: să se găsească cea mai bună ordine de executare a unor lucrări pe calculator, să se găsească cel mai scurt drum într-un graf etc [9].

În cele mai multe situații de acest fel avem:

mulțime de candidați (lucrări de executat, vârfuri ale grafului etc)

o funcție care verifică dacă o anumită mulțime de candidați constituie o soluție posibilă, nu neapărat optimă, a problemei

o funcție care verifică dacă o mulțime de candidați este fezabilă, adică dacă este posibil să completăm această mulțime astfel încat să obținem o soluție posibilă, nu neapărat optimă, a problemei

o funcție de selecție care indică la orice moment care este cel mai promițător dintre candidații încă nefolosiți

o funcție obiectiv care dă valoarea unei soluții (timpul necesar executării tuturor lucrărilor într-o anumită ordine, lungimea drumului pe care l-am găsit etc); aceasta este funcția pe care urmărim să o optimizăm (minimizăm/maximizăm)

Pentru a clarifica luăm exemplul găsirii celei mai bune rute de la Arad la București. Definim o funcție euristică h(n) ce reprezintă estimarea costului celei mai ieftine căi de la starea (nodul) n până la starea scop. Ca o notă, euristic vine din greacă de cuvântul heuriskein cu întelesul de a găsi, a descoperi. În cazul nostru este un adjectiv asociat unei metode ce îmbunătățeste performanța în cazurile obișnuite, dar nu îmbunătățeste neapărat performanța în cazurile cele mai rele (en: worst case scenario ), toate realizate prin estimarea costului unei soluții [2].

Funcție GreedySearch( problemă ) returnează o soluție sau un eșec

returnează BestFirstSearch( problemă, h )

Primul nod (nodul sursă) este Arad. Următorul nod considerat este Sibiu deoarece este mai aproape de București decât de exemplu Timișoara.

Figura 10. Primii doi pași din cadrul căutării unei soluții de la Arad la București folosind căutarea Greedy

Urmatorul nod va fi Făgăraș deoarece este mai aproape de București (în linie dreaptă) decât este Râmnicu-Vâlcea ( de aproape de București în linie dreaptă ). Totuși ar fi fost mai eficient să alegem Râmnicu-Vâlcea deoarece calea prin Sibiu-Făgăraș către București este mai lungă cu 50 de km decât calea prin Râmnicu-Vâlcea-Pitești și apoi pe autostradă către București. Totuși această cale din urmă nu a fost găsită.

Figura 11. Pasul 3 din cadrul căutării unei soluții de la Arad la București folosind căutarea Greedy

O altă problemă ar fi ca funcția să expandeze noduri ce nu sunt necesare. De exemplu mergem la Iași la Făgăraș. Funcția sugerează ca Neamț să fie expandat prima dată deși reprezintă un “dead-end”. Chiar mai mult dacă nu detectăm stările care se repetă soluția nu va fi niciodată gasită (căutarea va oscila intre Neamț si Iași).

Figura 12. Pașii 4 și 5 din cadrul căutării unei soluții de la Arad la București folosind căutarea Greedy

Algoritmul A*

Cum am văzut mai sus Greedy minimizează costul estimat de la n către țintă. Din păcate acest lucru nu este optim și nici complet. O opțiune ar fi căutarea uniformă-cost, dar aceasta poate fi foarte ineficientă ( sunt foarte multe căi de testat în majoritatea situațiilor ) [2].

Numim funcția care calculează valoarea căii până la starea (nodul) curent ca fiind g(n). Considerăm f(n) a cărei evaluare va fi g(n) + h(n), unde h(n) estimează valoarea căii de la nodul n la scop. Astfel, g(n) oferă informații asupra costului de la nodul de start (starea inițială) până la nodul n, iar h(n) costul estimat de la n până la scop. Însumând acestea, obținem estimarea costului prin nodul n. Pentru ca strategia aleasă să fie completă și optimă trebuie să punem o restricție asupra funcției h și anume h nu ar trebui sa supraestimeze costul până la ținta. Spunem acum despre h că este admisibil euristică.

Putem zice că o astfel de funcție este optimistă deoarece crede că, costul rezolvării problemei este mai mic decât în realitate. Mai mult optimismul se transferă funcției f.

Funcție A*Search( problemă ) returnează o soluție sau un eșec

returnează BestFirstSearch( problemă, g+h )

Vom aplica algoritmul A* asupra exemplului anterior ( ruta Arad – București).

Figura 13. Căutărea unei soluții de la Arad la București folosind căutarea A*

Observăm că de acesta dată este preferat drumul din Râmnicu-Vâlcea decât cel din Făgăraș. Chiar dacă Făgăraș este mai aproape de București în linie dreaptă, calea către Făgăraș nu este la fel de eficientă în apropierea de București, mai eficientă fiind calea către Râmnicu-Vâlcea.

Să clarificăm printr-un exemplu ce înseamnă funcție admisibil heuristică. Funcția h, din exemplul cu rutele, este admisibil euristică deoarece cel mai scurt drum dintre două puncte este o linie dreaptă (costul ( aici distanța ) este evident mai mic decât în realitate unde rutele sunt curbe).

Vom începe cu o observație asupra funcție f. Se observă că de-alungul orcărei căi funcția nu descrește. În termeni matematici spunem că funcția manifestă proprietatea de monotonie. Pentru a păstra o euristică monotonă ( lucru necesar cum vom vedea ), de exemplu, în cazul nostru pentru două noduri n și n’, unde n este părintele lui n’, vom verifica dacă costul în n’ este mai mic, în acest caz vom considera ca valoare a funcției g(n’) valoarea funcției g(n). Matematic avem f(n’) = max( f(n), g(n’) ) + h(n’). Această ecuație poartă numele de pathmax.

Obiectivul acestei observații este de a legitimiza o anumită imagine asupra comportamentului algoritmului A*. Dacă f nu descrește de-alungul orcărui path, putem desena contururi în spațiul soluțiilor. De exemplu în spatiul conturat și marcat cu 200, toate nodurile vor avea pe f(n) mai mic sau egal cu 200. Reamintim că nodul frunză expandat este nodul frunză cu valoarea funcție f minimă [9].

Dacă folosim o căutare uniformă, contururile vor fi circulare în jurul starii inițiale. Cu o euristică mai precisă ( și nu h = 0 ca în cazul unei căutări uniforme ), vom vedea cum aceste contururi vor fi din ce în ce mai înguste ( și focalizate pe calea optimă ) înspre scop.

Algoritmul A* nu răspunde la toate nevoile de căutare. Pentru destul de multe probleme, numărul de noduri din conturul scopului este exponențial în lungimea soluției. De fapt o creștere exponențială nu va avea loc doar dacă | h(n) – h*(n) | ≤ O(log h*(n)) unde h* este costul real de la n până la țintă. Ca o ultima observație asupra algoritmului: nici un alt algoritm optimal nu garantează să extindă mai puține noduri decât A* în condițiile aceleiași eurisitci, conform Dechter și Pearl (1985).

Căutări Neinformate

Căutare în adâncime ( Depth First Search)

Parcurgerea unui graf în adâncime se face prin utilizarea stivei (alocate implicit prin subprograme recursive).Pentru fiecare vârf se parcurge primul dintre vecinii lui neparcurși încă.

Dupa vizitarea vârfului inițial x1, se explorează primul vârf adiacent lui, fie acesta x2 , se trece apoi la primul vârf adiacent cu x2 și care nu a fost parcurs încă , ș.a.m.d. Fiecare vârf se parcurge cel mult odată [1].

Algoritm Depth First Search (varianta nerecursivă)

Procedure DFS(k,n,vecin)

INPUT:

For ido

end for

call Vizitare(k)

while do

if then

end if

while do

if then

call Vizitare(i)

else

end if

end while

end while

end procedure

De exemplul pentru garful din figura de mai jos, se va proceda în felul următor:

Se pornește din vârful 1, (se poate începe de la oricare alt vârf).

Figura 14. Pasul 1din cadrul căutării unei soluții folosind căutarea DFS

Se explorează în continuare primul vecin al acestuia : vârful  2

Se obține 1,2.

Figura 15. Pasul 2 din cadrul căutării unei soluții folosind căutarea DFS

Se  explorează vârful adiacent cu acesta și care nu a fost vizitat : 3.

Se obține 1,2,3.

Figura 16. Pasul 3 din cadrul căutării unei soluții folosind căutarea DFS

În  continuare ar trebui să se parcurgă vecinul lui 3 nevizitat : 4  

Se obține 1,2,3,4.

Figura 17. Pasul 4 din cadrul căutării unei soluții folosind căutarea DFS

Pentru vârful 4 ar trebui să se parcurgă primul său vecin neparcurs (vârful 1 dar acesta a fost deja parcurs. Nu mai avem ce vizita și se trece la nivelul anterior din stivă, la varful 3.

Se obține 1,2,3,4 . Se parcurge vecinul său nevizitat, vârful 5.

Figura 18. Pasul 5 din cadrul căutării unei soluții folosind căutarea DFS

Vârful 3 nu mai are vecini nevizitați și se trece pe nivelul anterior din stivă, vârful 2: 1, 2, 3, 4, 5. Nici acesta nu mai are vecini nevizitați și se trece pe nivelul anterior la vârful 1 : 1, 2, 3, 4 , 5. Cum nici acesta nu mai are vecini nevizitați se incheie algoritmul. Vârful 6 rămâne nevizitat.

Complexitatea de timp este , iar cea de spațiu

Căutare în adâncime limitată ( 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 limite de adâncime l. Astfel, vor fi explorate doar nodurile până la o limită l și dacă adâncimea soluției este mai mică decât l atunci ea va fi găsită [3].

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 adâncime ș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.

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

Strategia de căutare limitată în adâncime este completă doar dacă adâncimea unei soluții este mai mică decât l, adică 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 optimă 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 optimă: atunci când toate soluțiile problemei se află pe limita de adâncime.

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 optimă.

Căutare în adâncime iterativă ( Iterative – Depending)

Ar fi desigur de dorit să avem o strategie de căutare care este completă și optimă precum căutarea pe nivel, dar în același timp are necesitățile de memorie scăzute de la căutarea în adâncime [3].

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 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 următoare. În figura 19 , pentru a nu încărca desenul s-a omis faptul că primul nod este explorat de 4 ori, pentru cei 4 arbori de căutare generați la adâncime 1, 2, 3 respectiv 4.

Figura 19. Căutarea in adâncime iterativă

Complexitate de timp rămâne dar deoarece unele noduri sunt explorate de mai multe ori, la fiecare iterație în adâncime, complexitatea este de fapt .

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

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.

Căutare în Lățime (Breadth First Search)

La explorarea în latime, dupa vizitarea vârfului initial, se explorează toate vârfurile adiacente lui, se trece apoi la primul vârf adiacent și se explorează toate vârfurile adiacente acestuia și neparcurse încă, ș.a.m.d. Fiecare vârf se parcurge cel mult odată [1].

Algoritm Breadth First Search

procedure BFS(k,n,Vecin)

INPUT:

for i<-1,n do

<- 0

<- 0

k

Vizitare(k)

do

k

for i<-1,n do

if

<- 1

i

Vizitare(i)

end if

end for

end while

end procedure

De exemplul pentru graful din figura de mai jos, se va proceda in felul următor:

Se pornește din nodul 1, (se poate începe de la oricare alt nod).

Figura 20. Pasul 1 din cadrul căutării unei soluții folosind căutarea BFS

Se explorează în continuare vecinii acestuia : nodul 2 și apoi 4.

Se obține 1,2,4.

Figura 21. Pasul 2 din cadrul căutării unei soluții folosind căutarea BFS

Din 2 se explorează nodul adiacent acestuia 3. Nodul 1 nu se mai vizitează odată.

Se obține 1,2,4,3

Figura 22. Pasul 3 din cadrul căutării unei soluții folosind căutarea BFS

În  continuare ar trebui parcurși vecinii lui 4  (1,2,4,3 )  dar acesta nu mai are vecini nevizitați și se trece la vecinii lui 3 : 1,2,4,3 respectiv nodul 5.

Se obține 1, 2, 3, 4, 5 , vârful 6 rămâne neparcurs.

Figura 23. Pasul 4 din cadrul căutării unei soluții folosind căutarea BFS

Observații!

Parcurgerea în lățime are următoarea proprietate : fiecare vârf este vizitat pe cel mai scurt lanț/drum, începând din vârful de start.

Complexitatea timp a algoritmilor de parcurgere în adâncime și în lățime a unui graf depinde de modalitatea de reprezentare a acestuia. În cazul reprezentării prin liste de adiacență, complexitatea este . În cazul reprezentării prin matrice de adiacență este .

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ă [3].

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ânduse î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.

Complexitatea de timp este altă valoare frecvent folosită pentru complexitatea de timp este unde este costul căii optime în arbore iar este costul minim al operatorilor. Complexitatea de spațiu este .

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.

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

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.
Un scurt exemplu poate fi util în lămurirea modului de funcționare al strategiei. Fie graful orientat aciclic din figura următoare, 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 următoare în care se observă că drumul găsit de strategie este A-C-E care este cel mai ieftin.

Figura 24. Graf orientat

Edsger Wybe Dijkstra

Edsger Wybe Dijkstra s-a născut pe data de 11 Mai 1930 in Rotterdam .

Tatăl său a fost președintele Societății Olandeze de Chimie. Acesta a predate chimia la gimnaziu urmând să devină mai târziu directorul acesteia.

Mama sa a fost mathematician, dar nu a lucrat in domeniu.

Edsger Wybe Dijkstra  a studiat Fizică Teoretică la Univeristatea din Leiden, dar a realizat destul de repede că era mai interest in Computer Science. După o perioadă de lucru ca cercetător la Burroughs Corporation, a lucrat la Universitatea Tehnică din Eindhoven și mai apoi la Universitatea din Austin, Texas, de unde s-a retras în 2000.

Dijkstra a rămas celebru pentru algoritmul drumului minim într-un graf, algoritm care-i poartă numele. De asemenea, într-un articol celebru din 1968, a luat atitudine împotriva folosirii instrucțiunii GOTO, considerînd-o "dăunătoare" (în engleză harmful) [4].

Instrucțiunea GOTO este instrucțiunea de salt necondiționat care oferă posibilitatea de a întrerupe această secvență și de a relua execuția dintr-un alt loc al programului.

Instrucțiunea GOTO are forma: (instructiunea GOTO):= goto (etichetă),unde etichetă este un număr întreg fără semn care prefixează o instrucțiune a programului.

În ultimul an din viață a fost premiat cu “ACM PODC Influential Paper Award” pentru munca sa legată de auto-stabilizarea programelor de calcul. În onoarea sa,acest premiu a fost redenumit în “Dijkstra Prize” anul următor.

Edsger Wybe Dijkstra a decedat pe data de 6 August 2002 in Nuenen, Olanda.

Algoritmul lui Dijkstra 

Este o metodă de a stabili drumul de cost minim de la un nod de start la oricare altul dintr-un graf. Numele este dat de Edsger Wybe Dijkstra savantul care l-a descoperit [4].

Fie G = (V,E) un graf orientat unde V = {1,2,…,n} este mulțimea nodurilor și E este mulțimea arcelor (E ⊆ V ×V ). Pentru reprezentarea grafului se utilizează matricea costurilor:

Fie u un vârf al grafului numit sursă. Dorim să determinăm pentru fiecare vârf j ∈ V, j u, dacă există, un drum de lungime minimă de la u la j. Lungimea unui drum se definește ca fiind suma costurilor asociate arcelor ce-l compun.

Algoritmul lui Dijkstra utilizează metoda generală de elaborare a algoritmilor Greedy, drumurile de lungime minimă fiind generate în ordinea crescătoare a lungimii lor [4].

Vom nota cu S mulțimea nodurilor grafului G pentru care se cunoaște drumul de lungime minimă de la sursă. La început mulțimea S este formată doar din nodul sursă.

La fiecare pas se adaugă la mulțimea S un nod k ∈ V \ S cu proprietatea că drumul de la sursă la acel nod este cel mai mic dintre toate drumurile posibile de la sursă la noduri din mulțimea V \ S, cu proprietatea că un astfel de drum are drept noduri intermediare numai elemente din mulțimea S, cu excepția extremității finale.

Vom utiliza un tablou D ce va păstra pentru fiecare nod k, lungimea drumului cel mai scurt de la sursă ce trece numai prin noduri din mulțimea S.

După ce am identificat un astfel de nod k, mulțimea S se modifică astfel: S = S ∪ {k}. Este posibil ca lungimea unui drum de la sursă la un nod j ∈ V \ S, ce are drept noduri intermediare noduri din mulțimea S, să se modifice datorită faptului că, mai înainte, nodul k nu fusese luat în considerare, deoarece nu aparținea mulțimii S.

Astfel, se poate ca un drum de la sursă la nodul j, ce trece prin nodul k, să fie mai mic decât drumul anterior de la sursă la nodul .

function DISTANTAMINIMA(n,vizitat,d)

min

for do

if( () then

min

end if

end for

if (min = ) then

return -1

else

return

end if

end function

procedure DIJKSTRA(n,C,u)

← 0, ← 0

for i ← 1,n do

if(

← 0

← , ← u

end if

end for

while (true) do

k ← DistantaMinima(n,vizitat,d)

if (k < 0) then

break

else

← 1

for i ← 1,n do

if( 1)∧(+<) then

← k

← +

end if

end for

end if

end while

end procedure

Algoritmul lui Dijkstra prezintă asemănări cu algoritmul de căutare în lățime, la final, vectorul tată păstrând un arbore al drumurilor minime ce are drept rădăcină nodul sursă.

În momentul în care alegem nodul k ∈ V \S având proprietatea că drumul de la sursă la acel nod este cel mai mic dintre toate drumurile posibile de la sursă la noduri din mulțimea V \S, ce trec numai prin noduri din mulțimea S, cu excepția extremității finale, acel drum este cel mai mic drum de la sursă la k dintre toate drumurile posibile.

Denumim drum special un drum de la sursă la un nod k ce are drept noduri intermediare numai elemente din mulțimea S, cu excepția extremității finale.

Să presupunem că există un drum de lungime mai mică de la nodul sursă la nodul k, ce nu are toate nodurile intermediare din mulțimea S. Fie j ∈ V \S, primul nod pe drumul de la nodul sursă la nodul k, ce nu aparține mulțimii S. Atunci drumul de la nodul sursă u la nodul k se compune dintr-un drum de la u la j, și un drum de la j la k.

Datorită modului de alegere al lui j, drumul de la u la j are drept noduri intermediare numai elemente din mulțimea S (j este primul nod pe drumul de la nodul sursă la nodul k, care nu aparține mulțimii S), deci este un drum special și are o lungime mai mică decât drumul special de la sursă la nodul k. Prin urmare am găsit un alt drum special de lungime mai mică, ceea ce contrazice modul de alegere al nodului k.

Trebuie să demonstrăm că în orice moment, păstrează lungimea celui mai scurt drum special de la nodul sursă u la nodul k ∈ V \ S. În momentul în care nodul k este adăugat mulțimii S, avem grijă să verificăm dacă nu există un drum special de la nodul u la un nod j ∈ V \ S care să aibă o lungime mai mică.

Deoarece nodul x a fost adăugat mulțimii S înaintea nodului k avem ≤ . Prin urmare drumul special de la sursă la nodul j ce trece prin nodul x are lungimea mai mică decât drumul special compus din drumul de la nodul sursă la nodul k, drumul de la nodul k la nodul x și arcul (x,j).

CAPITOLUL IV

APLICAȚIE

-Căutari avansate pe grid-

Framework-ul Qt

Qt este un framework open-source cross-platform folosit pentru dezvoltarea produselor software în mai multe platforme [5].

Framework-ul Qt este format din :

un pachet de librării Qt pentru platforma C++

mediu de dezolvare alcătuit din Qt Creator IDE și tool-uri pentru dezvoltarea de interfețe.

Instalarea Qt

Frameworuk-ul Qt [5] vine cu un IDE propriu ce poate fi descărcat de site-ul oficial Qt ( https://www.qt.io/download-open-source/#section-2 ).

De asemenea , acesta poate fi integrat in Visual Studio, insă este necesară descărcarea unui add-in.

După ce s-a instalat Add-in-ul , un nou tab va aparea în bara de meniu.

În pasul următor trebuie să introducem path-ul către folderele bin și lib. Fără acest pas vom primi eroarea “ Unable to find a Qt build! To solve this problem specify a Qt build” când încercăm să creăm un proiect Qt. Cele două foldere se găsesc in locația de instalare a Qt.

Path-ul se introduce în Visual Studio la QT5 ->Qt Options , apoi click pe “Add” iar calea se introduce în zona “Path”.

Version Name reprezintă versiunea de Qt instalată.

Crearea unui proiect Qt

Pentru a crea un proiect Qt in Visual Studio mergem la File->New->Project. Observăm o nouă adiție la secțiunea “Templates”. Aceasta ne permite să alegem dintr-o varietate de aplicații Qt, dar pentru început selectăm “Qt Application”.

Lăsăm setările default.

Setăm numele clasei principale și apăsăm “Finish”.

În acest moment au fost generate toate fișierele necesare rularii unei aplicații de bază Qt.

Căutări avansate pe grid folosind algoritmul lui Dijkstra

Structura Aplicației

“cautaripegrid.ui” conține toate obiectele grafice ale aplicației, împreună cu atributele acestora.

“ui_cautaripegrid.h” conține declarările si inițierile obiectelor grafice.

“cautaripegrid.h” este clasa principală

“CustomView.h” este clasa unui obiect grafic important din Qt numit “Graphics View”. În acest “canvas” vom încărca hărtile facultății, vom desena ruta rezultată în urma executării algoritmului lui Dijkstra pe baza unor date de intrare.

“dijkstra.h” conține implementarea algoritmului lui Dijkstra. Primește ca parametrii nodul sursă, nodul destinație și etajul corespunzător acestor noduri. Returnează un array ce conține cel mai scurt drum dintre cele două puncte. În căutarea celui mai scurt drum , algoritmul se folosește matricea de adiacență specific etajului primit ca parametru.

“căutăripegrid.cpp” conține implementarea funcțiilor pentru event-urile butoanelor.

“CustomView.cpp” conține implementarea funcției pentru Zoom-In și Zoom-Out

“matrici_adiacena.h” conține matricile de adiacență ale celor 3 etaj, numele camerelor aparținând fiecărui etaj, si coordonatele fiecărei camere.

Design-ul aplicației

Design-ul aplicației a fost realizat in Qt Designer. Interfața este asemănătoare designer-ului pentru C# oferit de Visual Studio, iar facilitățile oferite de Qt Designer sunt aproape identice.

Interfața Aplicației

Obiectul QGraphicsView conține harta etajului curent. Pe această hartă va fi desenat traseul obținut în urma rulării algoritmului lui Dijkstra.

Punctul de start al traseului alcătuit dintr-un QComboBox ce conține lista de etaje, un QComboBox ce conține lista de camere din etajul selectat.

Punctul de sfârșit al traseului alcătuit dintr-un QComboBox ce conține lista de etaje, un QComboBox ce conține lista de camere din etajul selectat.

Un QLabel ce afișeaza harta cărui etaj este afișată in QGraphicsView

Două QPushButton , unul pentru a rula algoritmul lui Dijkstra în urma selectării punctelor de început și sfârșit, și al doilea pentru a schimba etajul current.. La executarea aplicației punctele de inceput și sfârșit sunt setate automat la etajul Parter și punctul Intrare Parter.

Funcționalitatea Aplicației

Fnncționalitatea QComboBox pentru etaj si camera.

În momentul selectării unui etaj este lansat signal-ul QComboBox::currentIndexChanged(int). În acest moment este modificat conținutul QcomboBox-ului ce conține lista de camere din etajul respectiv cu lista noului etaj.

Această funcționalitate se aplică atât QcomboBox-ului punctului de start cât și celui de sfârșit.

Funcționalitatea QpushButton-ului pentru schimbarea etajului curent

În momentul apăsării butonului Change Level , este desenată harta următorului etaj . În total sunt 3 etaje ( subsol, parter, etajul 1). Etajul următor este calculat după următoarea formulă:

Funcționalitatea QpushButton-ului pentru calcularea drumului cel mai scurt

În momentul apăsării butonului Show Path ,este lansat event-ul QPushButton::clicked(bool).

Se sterge conținutul QGraphicsView, sunt redefinite cele 3 QPixmap pe baza hărților etajelor, se declară câte un QPainter pentru fiecare QPixmap și este apelată metoda set_start_end_points() .

Verificăm dacă suntem pe același etaj cu punctul de start. Dacă nu suntem, setăm etajul curent ca fiind etajul punctului de start.

Pe baza unor condiții apelăm odată algoritmul lui Dijkstra astfel:

O singură dată dacă punctul de start și punctul de sfărșit sunt pe același etaj

De două ori dacă modulul diferenței dintre etajul sursă si etajul destinație este egal cu 1. Primul apel va avea apela algoritmul cu punctul de start și cea mai apropiată scară de acest punct, iar al doil-lea va apela algoritmul etajul următor, scara legată de destinația primului apel și punctul de sfărsit.

De 3 ori dacă modulul diferenței dintre cele două etaj este egal cu 2.

După executarea algoritmului, se desenează soluția pe hartă

CAPITOLUL V

CONCLUZII

Scopul acestei lucrări a fost de a prezenta aspecte legate de Inteligența Artificială, aspect legate de căutare folosind algoritmu specifici. Am vorbit despre grafuri, importanța acestora in Inteligența Artificială, mai exact despre importanța acestora in utilizarea algoritmilor de căutare.

Aplicațiile de path-finding sunt destul de răspândite. Acești algoritmi sunt folosiți in sistemele de GPS (Global Positioning System) pentru calcularea celei mai scurte rute către destinație. Principalul sistem de poziționare prin satelit de tip GPS este sistemul militar american numit "Navigational Satellite Timing and Ranging" (NAVSTAR). Acesta poate calcula poziția exactă (coordinate geografice ) exacte ale unui obiect pe suprafața Pământului, cu condiția ca acesta să fie echipat cu dispozitivul necesar – un receptor GPS. 

Inteligența Artificială are multe aplicații practice:

Deep Blue, un computer de la firma IBM care joacă șah, l-a învins pe campionul mondial la șah Gari Kasparov în celebrul meci din 1997.

Logica Fuzzy și sistemele expert sunt folosite pentru a controla sisteme industriale

Sistemele de traducere automată precum SYSTRAN sunt folosite pe anumite domenii restrânse, deoarece rezultatele sunt mult mai slabe decât traducerea umană.

Optical Character Recognition (OCR) – recunoașterea automată a scrisului de tipar sau de mână

Voice recognition – recunoașterea acustică a vorbirii naturale (recunoașterea verbală)

Rețelele neuronale, folosite mai mult în jocuri pe calculator și multe altele.

Pe viitor voi aduce îmbunătățiri aplicației prezentate anterior, eventual și portarea acesteia pe o platformă WEB.

BIBLIOGRAFIE

Stuart RUSSEL, Peter Norvig, Artificial Intelligence: A Modern Approach 3rd Edition, 2009

Stuart RUSSEL, Peter Norvig, Artificial Intelligence: A Modern Approach 1st Edition, 1995

Bogdan GROZA, Introducere în Inteligența Artificiala, Aplicații cu Strategii de Căutare Neinformate și Informate, 2008

E. W. Dijkstra, A note on two problems in connections with graphs, Numerische Math-ematik, 1, pp. 269-271, 1959.

http://doc.qt.io/qt-5/classes.html

Stoean R., Stoean C., Evolutie si inteligenta artificiala. Paradigme moderne si aplicatii, Editura Albastra – Grupul MicroInformatica, 2010.

Dumitrescu D., 2002, Principiile Inteligentei Artificiale, Editura Albastra, Cluj-Napoca.

Eiben, A. E. Smith, J. E., 2003, Introduction to Evolutionary Computing. Springer-Verlag, Berlin, Heildelberg, NY.

S. Pettie, A faster all-pairs shortest path algorithm for real-weighted sparse graphs, in Proceedings of 29th International Colloquium on Automata, Languages, and Program-ming (ICALP02), LNCS Vol. 2380, pp. 85-97, 2002.

BIBLIOGRAFIE

Stuart RUSSEL, Peter Norvig, Artificial Intelligence: A Modern Approach 3rd Edition, 2009

Stuart RUSSEL, Peter Norvig, Artificial Intelligence: A Modern Approach 1st Edition, 1995

Bogdan GROZA, Introducere în Inteligența Artificiala, Aplicații cu Strategii de Căutare Neinformate și Informate, 2008

E. W. Dijkstra, A note on two problems in connections with graphs, Numerische Math-ematik, 1, pp. 269-271, 1959.

http://doc.qt.io/qt-5/classes.html

Stoean R., Stoean C., Evolutie si inteligenta artificiala. Paradigme moderne si aplicatii, Editura Albastra – Grupul MicroInformatica, 2010.

Dumitrescu D., 2002, Principiile Inteligentei Artificiale, Editura Albastra, Cluj-Napoca.

Eiben, A. E. Smith, J. E., 2003, Introduction to Evolutionary Computing. Springer-Verlag, Berlin, Heildelberg, NY.

S. Pettie, A faster all-pairs shortest path algorithm for real-weighted sparse graphs, in Proceedings of 29th International Colloquium on Automata, Languages, and Program-ming (ICALP02), LNCS Vol. 2380, pp. 85-97, 2002.