Algoritmi de Cautare Si Navigare

2)Algoritmi de căutare si navigare

2.1)Soluți existente

GPS-ul (sistem de localizare globală) este un sistem de navigare prin satelit. GPS funcționează în felul următor: mai mulți sateliți transmit semnale precise prin radio către receptoarele GPS astfel ele afla exact locația în care se afla (longitudine, latitudine și altitudine) în timp real și indiferent de condițiile meteo.Sateliții GPS înconjoară pământul de două ori pe zi pe orbite foarte precis determinate și transmit semnale/informații către stațiile terestre. Receptoarele GPS culeg aceste informații și folosesc triangulații pentru a calcula localizarea exactă a utilizatorului, triangulația este un mod de determinare a poziției unui punct prin măsurarea unghiurilor dintre această și alte două puncte de referință a căror poziție este cunoscută. Un receptor GPS trebuie să primească în același timp semnale de la minimum trei sateliți pentru a putea calcula o poziție 2D (latitudine și longitudine).Poziția 3D(latitudine, longitudine și altitudine) poate fi calculată doar dacă receptorul GPS culege informații de la patru sau mai mulți sateliți. După ce poziția exactă a utilizatorului a fost determinată GPS-ul poate calcula alte informații utile, cum ar fi viteza, cursul, direcția de mișcare, distanța parcursă, distanța până la destinație, ora răsăritului și apusului și altele.

Figură 2.1-Segmentele GPS

Preluare semnalelor pe care sateliții le transimit și calculul poziție se face în două moduri: modul absolut, modul diferențial. Modul diferențial folosește două receptoare, unul are rolul de stație de bază și este instalat într-un punct fix cu coordonate cunoscute. Se măsoară diferența dintre coordonatele punctului fix și coordonatele aceluiași punct rezultate din analiza semnalelor GPS. Modul absolut folosește doar un singur receptor GPS.

2.1.1) Google Maps

Este un serviciu online dezvoltat de către compania americană Google. Google Maps poate fi vizualizat în mai multe feluri. Butonul „Hartă" afișează o hartă tradițională, ideală pentru găsirea unei adrese sau pentru definirea unui traseu de la A la B. Pentru o explorare detaliată, se poate folosi butonul „Satelit", care afișează fotografii luate din satelit și din aer. Vederea tip „Teren" evidențiază munții și dealurile. Această opțiune oferă utilizatorului posibilitatea să își calculeze rutele între două sau mai multe puncte. Aceste rute pot fi schimbate, în funcție de preferințe. Se pot seta anumite caracteristici, cum ar fi cu sau fără autostrăzi, cu sau fără străzi cu plată de parcare, etc. Această opțiune mai oferă și un traseu amănunțit, ce poate fi listat și urmărit.

Figură 2.3- Exemplu de cătare a unui traseu (vederea „Satelit")

Figură 2.4- Exemplu de căutare a unui traseu (vederea „Hartă")

2.1.2) IGO

Igo este probabil unul din cele mai populare softuri de navigare prin satelit.Hărțile sunt actualizate des,interfața e atractivă,iar rutarea clar depășește alte softuri. Se pot alege mai multe variante de rutare ; rapid , scurt, ușor iar la ultimile variante chiar și ECOLOGIC.
Între modurile de rutare putem alege pieton/autobuz/mașină/taxi/urgent iar la Igo Primo s-a introdus și modul camion pentru șoferii profesioniști. Se pot seta de la modul de afișare 3D,unghiuri de vizualizare până la distanță de avertizare radar,sau scheme de culori folosite.

Figură 2.5-Meniu IGO

Cele mai populare versiuni de IGO apărute:

-Igo2006-utlimile hărți actualizate până în 2007-2008

-Igo8.0 (R1) -soft refăcut,hărți actualizate și în prezent

-Igo8.3.2-introduse opțiuni noi,hărți actualizate și în prezent

-Igo8.3.4-s-au introdus așa numitele DA(alerte șoferi) și optimizat engine-ul

-Igo 8.3.5 -un executabil otpimizat și îmbunătățit.

-Igo Amigo

– Igo Primo-ultimul apărut și redesenat total

Hărțile de Igo sunt de trei feluri:
-Navteq -acoperire foarte bună,info camioane ,toată Europa,alerte șofer
-Contin info camioane (folosite la Primo pentru camion ,și Becker) mai bine puse la punct.
-Acoperirea pe țara noastră este bună,lipsesc în general numere clădiri,și străduțe secundare.

Figură 2.6-Modul camion IGO PRIMO

Figură 2.7-Exemplu de cautare a unui traseu cu IGO PRIMO

2.1.3)TomTom

TomTom este un soft de navigare prin sateliți foarte cunoscut,compania a fost fondată în 1991. Aparatul are în interior un modul gps ,acesta calculează locația curentă de la semnalele de satelit recepționate. Sateliții trimit în mod constant semnale și modulul le preia pe cele care sunt mai apropiate. În interiorul modulului este un mic cip GPS, extrem de sensibil, care poate primi și înregistra semnale chiar și atunci când este în locații inaccesibile. Aparatul folosește o tehnologie inteligenta numită RDS-TMC ("Radio Data System-Traffic Message Channel"),este un serviciu care oferă informații din trafic în timp real pe telefonul mobil. TMC sisteme de informare a traficului conform unui standard global care a fost adoptată de către culegători de date, furnizorii de informații, de radiodifuziune. Datele referitoare la fluxurile de trafic, incidente, vremea etc pot fi adunate dintr-o varietate de surse (sisteme de monitorizare a traficului, serviciile de urgență, etc), colectate într-un centru de informare central.

Figură 2.8-GPS TomTom

Figură 2.9- Transmiterea infromațiilor din trafic

2.2)Algoritimi de căutare

2.2.1)A* (A star)

A* este cel mai cunoscut algoritm de căutare. A* gasește drumul cu costul cel mai mic de la un nod inițial pană la un nod-scop, unde nodul inițial reprezintă locația curentă si nodul-scop locația in care trebuie sa se ajungă. Algoritmul urmărește mereu soluția care pare cea mai aproape de sursă. Costul reprezintă timpul de trecere dintr-un nod în altul, a* gasește dumul cu costul cel mai mic. La cele mai multe probleme, costul de a ajunge de la un nod la altul nu poate fi determinat exact, doar estimat. Funcția care estimează astfel de costuri se numește funcție euristică și este notata de obicei cu h .Pentru fiecare nod definim o funcție de evaluare f care indică cât de promițator este un nod în gasirea unui drum catre nodul-scop(cu cât f este mai mic cu atât nodul este mai promițător).

f(nod)=g(nod)+h(nod)

g(nod)-este drumul parcurs de la nodul ințial până la nodul curent

h(nod)- este o estimare euristică de la nod până la cea mai apropiată soluție

Algoritmul folosește doua mulțimi:

1) close- indică nodurile deja explorate (s-a trecut deja prin nodurile respective, ele nu vor fi niciodată reexplorate)

2) open- indică nodurile descoperite(nodurile prin care urmează să treacă)

A star functionează în felul următor: se introduce în mulțimea open nodul corespunzător stării inițiale . Nodurile care urmează să fie explorate vor fi introduse in mulțimea open. La fiecare trecere se extrage din open nodul cu f(n) minim,care reprezintă si drumul cel mai scurt până la nodul-scop. După ce un nod a fost explorat va fi introdus in close.

Exemplu: Figura 1 poate fi considerată o hartă în care S reprezintă punctul de plecare, G este punctul final și X reprezintă anumite obstacole . A star trebuie să gasescă drum cel mai scurt de la S la G ținând cont de obstacole. Direcțiile pe care le parcurge sunt:sus,jos,dreapta și stânga.

0 1 2 3 4

0

1

2

3

4

Figură 1-Hartă

Euristicul (h)

Figură 2-Euristicul

f=g+h(x,y)

Open-poziția nodul prin care trece

Valoarea g=5(drumul parcrus,până in momentul

de fată s-au parcurs 5 noduri)

Euristicul h=3(estimare euristică,ea este aleasă din

Figura 2)

open[4,1] 5,8 (f=5+3)

Acuma programul va avea două direcți,va trebui să caute drumul cu valorea f cea mai mică.

open[4,2]

Valoarea g=6

Euristicul h=2

open[4,2] 6,8 (f=6+2)

open[3,2] 7,10

Valoarea g=7

Euristicul h=3

open[3,2] 7,10 (f=7+3)

Dacă va merge in sus începe să se departeze de punctul final iar valorea f crește.

Open[4,3]

Valoarea g=7

Eurisitul h=1

Open[4,3] 7,8(f=7+1)

Din moment ce se urmrăește o valorea f mai mică a star va merge in dreapta deoarece nodul din dreapta are valore f mai mică, scăzând valorea lui f a star incepe să se apropie de punctul final.

Traseul cel mai scurt găsit de a star.

A* este completă și este optimală cu condiția că 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ă. A* este cea mai bună strategie de căutare, orice altă strategie care explorează mai puține noduri decât A* riscă să nu găsească cea mai bună soluție.

2.2.2)Depth-first (parcurgerea în adâncime a grafurilor)

Un graf este o mulțime de obiecte (numite noduri) legate între ele printr-o mulțime de muchii cărora le pot fi atribuite direcții. Această operație constă într-o căutare asupra tuturor nodurilor. Toate nodurile se consideră nevizitate, parcurgerea fiecaruia, marcându-l ca vizitat. În acest caz nodurile sunt explorate în ordinea adâncimii și se revine la nivelul superior doar când căutarea se ajunge într-un punct mort. Dezavantajul căutări in adâncime este faptul că nu este completă, această deficiență poate fi înlăturată parțial prin introducerea unei limite de adâncime. Utilizarea căutării în adâncime este recomandată atunci când se cunoaște adâncimea unei soluții.

Exemplu:

Căutarea în adâncime : A, B, D, H, I, E, J, K, C, F, L, M, G, N, O.

Căutarea în adâncime funcționează in felul urmator: dacă ajunge în nodul N din figura 3 vor fi explorate muchiile care sunt conectate la nodul N dar care nu au fost incă descoperite. Atunci când toate muchiile nodului N au fost explorate căutarea se retrage pentru a explora muchiile ce pleacă din nodurile adiacente lui N. Acest proces continuă până când se descoperă toate nodurile ce pot fi vizitate plecând de la sursa K. Dacă rămân noduri nedescoperite, atunci unul din ele poate fi stabilit ca sursă, și atunci, căutarea este repetată din acea sursă.

Figură 3

De exemplul pentru garful din figura 3.1, se va proceda in felul urmator:

Se pornește din nodul 1

Figură 3.1

Se explorează primul vecin al nodului : nodul 2

Dupa care din 2 se explorează nodul adiacent cu acesta și care nu a fost vizitat : 3

In  continuare ar trebui să se parcurgă vecinul nodului 3 nevizitat : 4 

Din nodul 4 ar trebui să se parcurgă primul sau vecin neexplorat(nodul 1,dar acesta a fost deja explorat). Deorece nu mai are ce sa exploreze se trece la nodul anterior 3.Se parcurge vecinul său nevizitat nodul 5.

Nodul 3 nu mai are vecini  nevizitați si se trece pe nivelul anterior nodul 2. Nici acesta nu mai are vecini nevizitați si se trece pe nivelul anterior la nodul 1. Cum nici acesta nu mai are vecini nevizitați se incheie algoritmul.Nodul 6 rămâne nevizitat.

2.2.3)Breadth first (căutare pe lățime)

Căutarea pe lățime este unul din cel mai simpli algoritmi,a fost folosită pe scară largă începând cu sfârșitul anului 1950, în special în programele din domeniul inteligenței artificiale.Parcurgerea pe lățime sau Breadth-First este numită astfel pentru că lărgește, uniform, frontiera dintre nodurile descoperite și cele nedescoperite, pe lățimea frontierei. Traversarea în lățime a grafurilor presupune faptul că după vizitarea unui anumit nod , sunt parcurși toți vecinii nevizitați ai acestuia, apoi toți vecinii nevizitați ai acestora din urmă până la vizitarea tuturor nodurilor. Strategia de căutare pe nivel garantează găsirea soluției, in cazul in care aceasta există și, in plus, gasește cel mai scurt drum spre soluție.

Căutarea în lățime :A,B,C,D,E,F,G,H,I,J,K,L,M,N,O

De exemplul pentru garful din figura 4, se va proceda in felul următor:

Se pornește din nodul 1

Figură 4

Se explorează vecinii: nodul 1 și nodul 4

După care din nodul 2 se vizitează nodul vecin acestuia 3.Nodul 1 nu se mai vizitează.

În  continuare ar trebui parcurși vecinii lui 4  dar acesta nu mai are vecini nevizitați si se trece la vecinii nodului 3 respectiv nodul 5.

Nodul 6 ramâne neparcurs.

2.2.4) Căutarea Greedy

Se bazează pe faptul că trebuie minimizat costul drumului pană la nodul scop. Cel mai important element al algoritmilor de tip “greedy” îl reprezintă selecția elementului care se adaugă la fiecare pas. Selecția se realizează pe baza unui criteriu care este stabilit în funcție de specificul problemei de rezolvat. Criteriul de selecție se bazează de regulă pe euristici

( euristica = tehnică bazată mai mult pe experiență și intuiție= arta de a descoperi cunoștințe noi (DEX)).

Exemplu de funcționare a algoritmului Greedy. Algoriuml trebuie sa găsescă distanța cea mai scurtă de la Arad la București.

h(n) = distanța in linie dreapta de la Arad pana la București.

Ruta găsită de Greedy: Arad-Sibiu-Făgăraș-București

Soluția găsită nu este optimală deoarece Sibiu-Făgăraș-București este cu 32 km mai mult decat Sibiu-Râmnicu Vâlcea-Pitești-București.

Algorimul Greedy nu a ales calea cea mai convenabilă deoarece Făgăraș este mai aproape de București in linie dreaptă decât Râmnicu Vâlcea. Căutarea Greedy în general gasește soluția rapid însă nu găsește intotdeauna soluția optimală. Ca și în cazul căutării in adâncime, algoritmul de căutare Greedy nu este optimal si este incomplet pentru că o poate apuca pe un drum infinit si astfel să nu se mai intoarcă pentru a alege alte posibilități.

3)Program de căutare