Cuprins:
1. Ce este algoritmul de cautare?.
2. Cautarea in tablouri.
3. Cautarea neinformata.
4. Cautarea in liste.
5. Cautarea in arbore.
6. Cautarea in graf.
7. Cautarea in baza de date structurate (SQL).
8. Cautarea informata.
1. Prezentarea algoritmului de cautare. >>>
In domeniul calculatoarelor un algoritm de cautare este o metoda care
trebuie sa returneze un returneze numai un rezultat aflat intr-un spatiu
de solutii, pentru o anumita cerinta (problema).Majoritatea algoritmilor
studiati in domeniul calculatoarelor care pot oferii solutii cerintelor propuse
fac parte din familia algoritmilor de cautare.Spatiul tuturor solutiilor
posibile ale unei cerinte care trebuie rezolvata este denumit spatiu de
solutii posibile.Cautarea neinformata este o metoda abordata de algoritmii
de cautare simpli.Cele mai intuitive metode de cautare prin spatiul de solutii
posibile, cum sunt algoritmii de cautare informata, isi folosesc cele mai
eficiente astfel de metode pentru a primii informatii despre structura spatiului
de raspunsuri pentru a incerca sa reduca cat mai mult perioada de cautare.
2. Cautarea in tablouri. >>>
Fie v un tablou unidimensional de dimensiune n si k un element de acelasi tip cu elementele tabloului.(k=cheie de cautare).Cautarea lui k revine la a gasii daca exista sau nu, un element din v de valoare k.În functie de aranjarea elementelor în tabloul v, exista trei tipuri de cautari: 2.1. Secventiala – nu se specifica nimic despre elementele tabloului v
2.2. Secventiala în tabloul ordonat
2.3. Cautare binara (caz în care tabloul este ordonat)
2.1. Cautarea secventiala intr-un tablou. >>>
In cautarea secventiala – nu se specifica nimic despre elementele tabloului v.Functia care rezolva aceasta cautare este: int cautare(int v[], int n, int k)
{ i=1;
while (i<=n && v[i]!=k) i++;
if (i<=n) return 1;
else return 0; } Un exemplu mai concret:
#include
#include int main(void)
{int v[20],n,i,k;
printf("n="); scanf("%d",&n);
printf("introduceti elementele vectorului\n");
for (i=1;i<=n;i++)
{printf("v[%d]=",i);
scanf("%d",&v[i]); } printf("nr cautat in sir =");
scanf("%d",&k);
i=1;
while (i<=n && v[i]!=k) i++; if(i<=n) printf("Numarul cautat se afla in sir");
else printf("Numarul cautat nu se afla in sir"); }
2.2 Cautarea secventiala într-un tablou ordonat. >>>
Fie v un tablou sortat crescator:
v1<=v2<=... <=vn. La compararea unui element vi cu k avem urmatoarele trei situatii: * vi = k: Algoritmul se încheie,rezultand o cautare cu succes;
* vi > k: Algoritmul se încheie, rezultand o cautare fara succes;
* vi< k: Se continua cautarea daca i < n;
Functia cautare() implementeaza cele trei cazul prezentate mai suscazurile care rezolva aceasta cautare: void cautare()
{
gata=0;
gasit=0;
i=1;
while (i<=n && !gata)
{if (v[i]==k)
{}
else if (v[i]>k) gata=1;
else i++; }
if (i>n || !gasit) printf("Numarul cautat nu se afla in sir");
else printf("Numarul cautat se afla in sir"); } Un exemplu de program care dezvolta functia prezentata mai sus: #include
#include
int v[20];
int n,i,k,gata,gasit,ind,aux;
void sortv()
{do
{ind=0; for(i=1;i<=n-1;i++)
{ if (v[i]>v[i+1])
{ ux=v[i];
v[i]=v[i+1]; v[i+1]=aux;
ind=1; } } }
while (ind!=0); }
void fisare()
{for(i=1;i<=n;i++) printf("v[%d]=%d ",i,v[i]);
printf("\n"); }
void main(void)
{clrscr();
printf("n="); scanf("%d",&n);
printf("introduceti elementele vectorului\n");
for (i=1;i<=n;i++)
{printf("v[%d]=",i);
scanf("%d",&v[i]); }
sortv();
printf("vectorul sortat \n");
afisare();
printf("Numarul cautat in sir =");
scanf("%d",&k);
gata=0; gasit=0;
i=1;
while (i<=n && !gata)
{if (v[i]==k)
{}
else if (v[i]>k) gata=1;
else i++; }
if (i>n || !gasit) printf("Numarul cautat nu se afla in sir");
else printf("Numarul cautat se afla in sir");
getch(); }
2.3. Cautarea binara intr-un tablou. >>>
Cautarea binara (caz în care tabloul este ordonat) se poate realiza recursiv sau iterativ.
Fie v sortat crescator: v1<= v2 <= ... <= vn.
Astfel varianta recursiva presupune compararea cheii cu elementul din mijlocul tabloului, obtinându-se urmatoarele trei situatii: * vmijloc= k: Se opreste cautarea, deoareace s-a gasit cheia cautata.
* vmijloc< k : Se continu? cautarea în secventa vmijloc+1,v'mijloc=2, ... ,vn
* vmijloc> k: se continua cautarea in segventa: v1,v'2, ... ,vmijloc-1
Exemplu de functie recursiva: int cautare(int k,int inf, int sup)
{ int mij;
if (inf<=sup)
{mij=(inf+sup)/2;
if (v[mij]==k) return mij;
else if (v[mij]>k) cautare(k,inf,mij-1);
else cautare(k,mij+1,sup); }
else return 0; } Exemplu de program care foloseste functia prezentata mai sus: #include
#include
int v[20];
int n,k,c;
void citire()
{int i;
printf("Elementele sirului in ordine crescatoare\n");
printf("v[1]=");scanf("%d",&v[1]);
for(i=2;i<=n;i++) do
{printf("v[%d]=",i);scanf("%d",&v[i]); }
while (v[i]<=v[i-1]); }
void afisare()
{int i;
for(i=1;i<=n;i++) printf("v[%d]=%d ",i,v[i]);
printf("\n"); }
int cautare(int k,int inf, int sup)
{int mij;
if (inf<=sup)
{mij=(inf+sup)/2;
if (v[mij]==k) return mij;
else if (v[mij]>k) cautare(k,inf,mij-1);
else cautare(k,mij+1,sup); }
else return 0; }
void main(void)
{do
{
printf("n="); scanf("%d",&n); }
while(n<1||n>20);
citire();
printf("Vectorul introdus \n");
afisare();
printf("Numarul cautat in sir este=");
scanf("%d",&k);
c=cautare(k,1,n);
if (c==0) printf("Elementul nu este in sir\n");
else printf("Elementul cautat este pe pozitia %d\n",c);
getch(); }
Fie v sortat crescator: v1<= v2 <= ... <= vn.
Implementarea cautarii binare iterative: int cautare(int v[], int n, int k)
{ int mij,inf,sup,ind;
inf=1;sup=n;
ind=0;
do
{mij=(inf+sup)/2;
if (v[mij]==k) ind=1;
else if (v[mij]else sup=mij-1; }
while(inf<=sup && ind==0);
if (ind==1) return mij;
else return 0; }
Programul care foloseste metoda prezentata mai sus este urmatorul: #include
#include
int v[20];
int n,k;
void citire()
{int i;
printf("Elementele sirului in ordine crescatoare\n");
printf("v[1]=");scanf("%d",&v[1]);
for(i=2;i<=n;i++)
do
{printf("v[%d]=",i);scanf("%d",&v[i]); }
while (v[i]<=v[i-1]); }void afisare()
{int i;
for(i=1;i<=n;i++)
printf("v[%d]=%d ",i,v[i]);
printf("\n"); }
void cautare()
{int mij,inf,sup,ind;
inf=1;sup=n;
ind=0;
do
{ mij=(inf+sup)/2;
if (v[mij]==k) ind=1;
else if (v[mij]else sup=mij-1; }
while(inf<=sup && ind==0);
if (ind==1) printf("Elementul este pe pozitia %d\n",mij);
else printf("Elementul nu este in sir"); }
void main(void)
{clrscr();
do
{printf("n="); scanf("%d",&n); }
while(n<1||n>20);
citire();
printf("Vectorul introdus \n");
afisare();
printf("Numarul cautat in sir este=");
scanf("%d",&k);
cautare();
getch(); }
3. Cautarea neinformata. >>>
Un algoritm de cautare neinformata este unul dintre algoritmii care nu
abordeaza in amanunt natura specifica a cerintei ce trebuie solutionata.Astfel
dar, ei pot fi implementati in general astfel incat aceeasi metode de cautare
poate functiona prin abstractizare si pentru a rezolva alte cerinte de cautare.Dezavantajul
acestei metode este atunci cand spatiul raspunsurilor posibile este prea
mare, isa o cautare informata, mai ales intr-un arbore, poate furniza un raspuns
corect intr-un interval de timp foarte scurt.Ca urmare, pentru usurarea procesului
de cautare se foloseste pe langa algoritmul de cautare neinformata si un
algoritm de cautare informata.
4. Cautarea in liste. >>>
Algorimii de cautare in liste sunt probabil cei mai performanti algorimi
din familia algorimilor de cautare.Scopul este sa se gaseasca un element
dintr-un grup de elemente care au acelasi tip (probail continand si alte informatii
referitor la elemente).Aceasta este o problema ivita in domeniul de studiu
al calculatoarelor, functionarea complexa a algoritmulor de acest tip a fost
bina studiata.Algorimii simpli, cum este de exemplu algorimul de cautare
liniara,sunt usor de implenetat si procedura de cautare consta in examinarea
in ordine a fiecarui element al unui spatiu de solutii posibile.Acesti tip
de algoritmi realizeaza O(n) treceri de cautare (unde n reprezinta
numarul de elemente din spatiul de solutii posibile), ei fi folositi si-n
cadrul listelor neprocesate (nesortate).Cel mai sofisticat algoritm de cautare
in lista este cautarea binara, care realizeaza O(log n) treceri de
cautare.Acest algoritm este mult mai eficient decat metoda cautarii liniare
cand se opereaza cu liste de mari dimensiuni, numai ca el lucreaza numai
pentru liste sortate in prealabil.Cautarea prin interpolare este mai eficienta
decat cautarea binara cand se lucreaza cu liste mari de date egal distribuite.Algoritmul
lui Grover este si el un algoritm de cautare numit algoritm de quantum care
ofera o viteza de patru ori mai mare decat clasicul algoritm de cautare liniara
pentru liste nesortate.
Tablourile asociate sunt si ele folosite in cautarea listelor de date,si
care necesita numai perioade constante de timp pentru o solutionare de complexitate
medie, numai ca ele necesita spatiu de memorie mare si se comporta foarte
inaficient din punct de vedere al performantei.Alte metode de cautare bazate
pe structuri de date speciale sunt folosite de arborii binari de cautare,
care neceista o perioada o perioada de timp O(log n) pentru a efectua
o cautare, putand fi vazuti ca provenind din familia algoritmilor de cautare
binara, si care permit inserii rapide si usor de mutat.Multi algoritmi de
cautare, cum sunt algaritmul de cautare binara, algoritmul de cautare liniara
sau arborii binari de cautare, pot fi extinsi prin mici modificari adaugate
pentru a gasii taoate valorile mai mici sau mai mari decat cheia data, operatie
denumita cautare prin intindere.In acest criteriu nu intra tablourile
asociate, caci nu se pot comporta eficient intr-o cautare.
5. Cautarea in arbore.
>>>
Algoritmii de cautare abordati in structura de date abstracta numita
arborii reprezinta pulsul tehnicilor de cautare.Algoritmul arborelui binar
de cautare cauta nodurile valorile din nodurile unui arbore de tip explicit
sau implicit (adica generat la intrare).Principiul de baza functioneaza
pe faptul ca un nod este luat dintr-o structura de date, iar succesorii
sai sunt verificati si adaugati la structura de date.Prin intermediul structurilor
de date, arborele este parcurs in ordini diferite de la un nivel la altul
pentru a verifica arborele nivel cu niver (traversand arborele prin cuprindere)
sau extinderea primului nod radacina si reluarea traseului de parcurgere
din locul de unde acesta s-a oprit (procedura abordand o parcurgere a arborelui
in adancime).Alte exemple de arbori de cautare sunt "Iterative-deepending
search","Deph-limited search (DLS)",cautarea bidirectionala si cautarea prin
cost unuform.
6. Cautarea in graf. >>>
Cele mai multe probleme din cadrul domeniului de studiere a grafurilor
pot fi solutionate folosind algoritmi de cautare, cum ar fi algoritmul lui
Dijkstra, algoritmul lui Kruskal,algoritmul lui Prim si algoritmul de cautare
numit "algoritmul celui mai apropiat vecin".Acesti algoritmi pot fi vazut
ca metode de cautare ce provin din algoritmul de cautare in arbore.
6. Cautarea in baza de date structurate (SQL). >>>
Majoritatea problemelor de cautare sin arbori pot fi rezolvati folosind
cautarile de tip SQL (Structured Query Language).De obicei SQL se comporta
eficient in baze de date structurate.El ofera unul dintre avantajele de eficienta
a comportarii mai bun decat tipul de cautare ierarhica, deoarece permite
accese la date inmai multe moduri.In cautarile ierarhice traseul este fortat
prin conexiuni (legaturi -exemplu aranjarea in ordine alfabetica), insa in
cautarea SQL este posibilitatea accesarii datelor prin mai multe directii
( de exemplu prin nume, adresa, salariu etc..)
7. Cautarea informata.
>>>
Intr-o cautare informata se foloseste o euristica ca si ghid in abordarea
problemei.Folosind strategiile cautarii neinformate pentru solutionarea cerintelor
(problemelor), numarul de sortari investigate inainte de a gasii o solutie
poate ajunge prohibitiv de mare, chiar si pentru cerinte relativ simplu
de rezolvat.Spatiul solutiilor posibile poate fi redus prin aplicarea informatiilor
euristice despre problema.In cele din urma se va decide pe baza unei functii
de evaluare euristica atasarea starilor pentru a determina care este starea
ce urmeaza sa fie exlorata.O astfel de comportare corespunde unei strategii
de cautare informata, numita si cautare euristica.In aceasta categorie
sunt inclusi si cativa algoritmi de informare proeminenta in cautarea in
liste.Un posibil membru al acestei categorii este un tablou asociat cu o
functie asociata care reprezinta o euristica de baza in rezolvarea cerintei
de cautare.Cei mai multi algorimi de cautare informata sunt pentru traversarea
arborilor, cum sunt de exemplu cautarea informata "Best-first" si A*.Acestea
au principul de functionare asemanator cu cel al algoritmilor de cautare
neinformata, si pot fi expusi si in cautarile in grafuri. |