Algoritmy vyhľadávania

Z Kiwiki
Skočit na navigaci Skočit na vyhledávání
Imbox draft.png
 Toto je projekt, na ktorom sa ešte stále pracuje!!

Aj keď sú v tomto dokumente použiteľné informácie, ešte nie je dokončený. Svoje návrhy môžete vyjadriť v diskusii o tejto stránke.

Algoritmy a programovanie

Dátový typ

Štruktúry

Rekurzia

Algoritmy vyhľadávania

Algoritmy triedenia

Lineárny zoznam

Binárny strom

Numerické algoritmy

Grafové algoritmy

Practice.png
 Praktické príklady

Riešené príklady k tejto téme sú na stránke Vyhľadávanie (riešené príklady)

Vyhľadávanie

Vyhľadávanie je základnou úlohou pri práci s väčším objemom dát. Podľa povahy dát (zložitosti, usporiadania, veľkosti) volíme vhodný algoritmus vyhľadávania. Algortimy vyhľadávanie môžeme rozdeliť do niekoľko skupín:

  1. Sekvenčné vyhľadávanie
  2. Vyhľadávanie v usporiadaných zoznamoch (resp. poliach)
  3. Vyhľadávanie v rekurzívnych štruktúrach


Sekvenčné vyhľadávanie

Jednoduché sekvenčné vyhľadávanie

Princíp tohto vyhľadávania je jednoduchý. Majme pole údajov o dĺžke n, v ktorých budeme hľadať údaj x. Pod pojmom údaj si môžeme ptredstaviť ľubovoľný dátový typ (celé číslo, reálne číslo, štruktúru, smerník na nejaký dátový typ). Princíp: postupne prechádzame pole od indexu 0 až po index n-1. V prípade, ak zistíme zhodu hľadaného prvku s prvkom v poli, tak funkciu ukončíme s úspechom, v opačnom prípade skončíme s výsledkom "prvok sa nenašiel"

Dohodnuté návratové hodnoty funkcie:

Vyhľadávacia funkcia bude vracať index prvku, ktorý je zhodný s hľadaným prvkom. V prípade neúspechu (hľadaný prvok sa v poli nevyskytuje) vráti funkcia hodnotu -1.

Názov funkcie

hladajSekvencne

Návratová hodnota

index nájdeného prvku (-1 pri neúspechu)

Parametre

pole prvkov - pole
rozmer poľa - n
hľadaný prvok - x

Zložitosť algoritmu

O(n)


1 int hladajSekvencne(int *pole,int dlzka,int x)
2 {  int i=0;
3 	while( (i<dlzka) && (pole[i]!=x) )
4 		 i++;
5     if(i<dlzka)  return i;
6 	else return -1;
7 }

Analýza riešenia: Algoritmus je vhodný pre vyhľadávanie údajov v dátovej štruktúre jednorozmerné pole. Údaje v tomto poli môžu byť neusporiadané. Podmienka i<dlzka zaručí, že sa bude prehľadávať len v rozsahu poľa pole. Vždy sa začína na indexe i=0; tento index sa postupne zvyšuje (i++), pokiaľ nenarazíme na hľadaný prvok (pole[i]!=x). Podmienka na riadku 5 je tam pre kontrolu prípadu, keď sme prešli celé pole a hľadaný prvok sme nenašli.

Nevýhoda: každý cyklus sa vykonávajú 2 porovnania: i<dlzka a pole[i]!=x

Jednoduché sekvenčné vyhľadávanie s nárazníkom

V predchádzajúcom prípade sa v každom cykle robili 2 porovnania. Určitými úpravami dokážeme tieto porovnania znížiť len na 1 porovnanie. Bude to však chcieť drobnú úpravu poľa, v ktorom budeme vyhľadávať. Pole si upravíme tak, že hľadaný prvok sa tam bude vždy vyskytovať. Skutočná veľkosť poľa pole musí byť teda o jednu položku väčšia ako je počet prvkov v poli. Iba po splnení tejto podmienky môžeme urobiť priradenie, ako je ukázané v riadku 3. Toto priradenie nazveme nárazník.

Názov funkcie

hladajSekvencneN

Návratová hodnota

index nájdeného prvku (-1 pri neúspechu)

Parametre

pole prvkov - pole
rozmer poľa - n
hľadaný prvok - x

Zložitosť algoritmu

O(n)


 1 int hladajSekvencneN(int *pole, int n, int x)
 2 {
 3   pole[n] = x; // musi byt na to vyhradene miesto!
 4   int i = 0;
 5   while (pole[i] != x) 
 6     i++;
 7   if (i < n) 
 8     return i;
 9   else
10     return -1;
11 }

Analýza riešenia: Algoritmus je vhodný pre vyhľadávanie údajov v dátovej štruktúre jednorozmerné pole. Údaje v tomto poli môžu byť neusporiadané. Priradenie pole[n] = x dovoľuje vynechať kontrolu i<dlzka (funkcia hladajSekvencne). Vieme, že prvok v poli vždy nájdeme, preto stačí na konci urobiť porovnanie (riadok 7), či sme prvok x našli na pozícii menšej ako n (v rozsahu poľa). Ak áno, vrátime hodnotu premennej i, čo je index nájdeného prvku, ak sme hľadaný prvok našli na pozícii n, vrátime hodnotu -1, pretože na pozícii n je náš nárazník.

Poznámka: Touto úpravou sme vylepšili čas, vyhľadávania, ale nie zložitosť algoritmu.

Nasledujúci obrázok ukazuje porovanie časov vyhľadávania doteraz spomínaných algorimnov pri opakovanom vyhľadávaní vo veľkých (cca 1 000 000 položiek) poliach. <pLines ymin=0 axiscolor=888888 cubic angle=90 plots legend xtitle=pocet_cisel ytitle=cas> ,hladajSekvencne,hladajSekvencneN 10 000, 0.016, 0.015 100 000, 0.235, 0.125 200 000, 0.859, 0.813 300 000, 1.281, 1.234 500 000, 2.156, 2.063 700 000, 3.031, 2.891 1 000 000, 4.328, 4.141 2 000 000, 8.656, 8.375 5 000 000, 21.531, 20.657 10 000 000, 42.422, 41.235 </pLines>

Vyhľadávanie v usporiadaných zoznamoch

Zložitosť O(n) pre algorimy lineárneho, resp. sekvenčného vyhľadávania dokážeme znížiť, ak sú údaje v ktorých budeme vyhľadávať usporiadané. V tomto prípade nemusíme pole prvkov v ktorom hľadáme prechádzať celé (od indexu 0 až po n-1), ale stačí si skontrolovať položky len na určitých miestach.

Binárne vyhľadávanie

Predpoklad správneho vyhľadávania je, že prvku sú v poli usporiadané. Postup vyhľadávania:

Použité premenné
  • pole - jednorozmerné pole, v ktorom budeme vyhľadávať
  • x - prvok, ktorý hľadáme
  • n - veľkosť pola pole.
  • lavy, pravy - rozsah poľa, (začiatok , koniec) kde budeme hľadať.


  1. Rozdeľ pole na 2 polovice. Index stredného prvku vypočítaš ako:
    • stred=(lavy+pravy)/2
  2. Ak platí lavy>pravy, tak koniec, prvok sa nenašiel.
  3. Zober prvok v strede poľa (na indexe stred) a porovnaj ho s hľadaným prvkom x
  4. Ak sa x zhoduje so stredným prvkom - koniec. Výsledok je index tohto prvku
  5. V opačnom prípade
    • Ak je x väčšie ako stredný prvok, tak hľadaj v pravej časti poľa
      • lavy=stred+1, pravy zostava nezmenený (choď na krok 1)
    • Ak je x menšie ako stredný prvok, tak hľadaj v ľavej časti poľa
      • lavy=zostava nezmenený, pravy = stred-1 (choď na krok 1)

Ukážme si konkrétny príklad (šedé políčka predstavujú indexy poľa, biele sú prvky poľa): 

 x=18
 n=10
pole=
0 1 2 3 4 5 6 7 8 9 10
1 2 6 18 20 23 29 32 34 39 43

Pre implementáciu algoritmu binárneho vyhľadávania si musíme vypočítať hodnoty ľavého a pravého indexu poľa, v ktorom hľadáme. Na začiatok je to jednoduché: 

 lavy=0
 pravy=n-1
  • Porovnajme hľadaný prvok x=18 so stredným prvkom:
 stred=(lavy+pravy)/2
 stred=5
pole=
0 1 2 3 4 5 6 7 8 9 10
1 2 6 18 20 23 29 32 34 39 43
  • pole[5] != x (23 != 18 )
    • platí že x<23 (resp. x<pole[stred])
    • budeme vyhľadávať vľavo (žltá časť)
      • lavy zostane nezmeneny (0)
      • pravy=stred - 1 (4)
  • Porovnajme hľadaný prvok x=18 so stredným prvkom:
 stred=(lavy+pravy)/2 = (0+4)/2=2
 stred=2
pole=
0 1 2 3 4 5 6 7 8 9 10
1 2 6 18 20 23 29 32 34 39 43
  • pole[2] != x (6 != 18 )
    • platí že x>6 (resp. x>pole[stred])
    • budeme vyhľadávať vpravo (žltá časť)
      • lavy = stred + 1 (3)
      • pravy zostane nezmeneny (4)
  • Porovnajme hľadaný prvok x=18 so stredným prvkom:
 stred=(lavy+pravy)/2 = (3+4)/2=3
 stred=3
  • pole[3] == x (18 = 18 )
  • Stredný prvok je zhodný s hľadaným
  • Algoritmus končí
    • Výsledok je index nájdeného prvku, teda stred. V našom príklade je to 3.

Binárne vyhľadávanie - zdrojový kód v jazyku C

Názov funkcie

hladajBinarne
hladajBinarneR

Návratová hodnota

index nájdeného prvku (-1 pri neúspechu)

Parametre

pole prvkov - pole
rozmer poľa - n
hľadaný prvok - x

Zložitosť algoritmu

O(Log(n))


Keďže samotné definícia binárneho vyhľadávania je rekurzívna, uvádzame aj rekurzívnu verziu funkcie.


Iteračná verzia 

int hladajBinarne(int *pole,int dlzka, int x)
{	int najdene=0;
int lavy = 0, pravy = dlzka - 1, stred;
while ( (lavy <= pravy) && (najdene==0) )
{
   stred = (lavy + pravy) / 2;
   if (pole[stred] == x) 
	 najdene=1;
   else 
  	  if (pole[stred] < x) 
	     lavy = stred + 1;
	   else 
 	     pravy=stred - 1;
}
if(najdene==1)
	return stred;
else
	return -1;
}

Rekurzívna verzia 

int hladajBinarneR(int *pole,int lavy, int pravy, int x)
{   if(lavy>pravy)
		return -1;
	else
	{	
		int stred=(lavy+pravy)/2;
		if(pole[stred]==x)
		  return stred;
		else
		{   if( x<pole[stred] )
			return hladajB(pole,lavy,stred-1,x);
		   else
			return hladajB(pole,stred+1,pravy,x);
		}
	}
}

Ternárne vyhľadávanie

Predpoklad správneho vyhľadávania je, že prvku sú v poli usporiadané. Postup vyhľadávania je podobný ako pri binárnom vyhľadávaním abšak pole nerozdelíme na polovicu ale na tretiny.

Použité premenné
  • pole - jednorozmerné pole, v ktorom budeme vyhľadávať
  • x - prvok, ktorý hľadáme
  • n - veľkosť pola pole.
  • i, j - rozsah poľa, (začiatok , koniec) kde budeme hľadať.
  • m1 - index prvku v prvej tretine
  • m2 - index prvku v druhej tretine


  1. Rozdeľ pole na tretiny
    1. m1=( i*2 + j ) / 3;
    2. m2=( i + j*2 ) / 3;
  2. Porovnaj, či sa hľadaný prvok zhoduje z prvkom na indexe m1, ak áno, tak koniec. Výsledok je index m1
  3. Porovnaj, či sa hľadaný prvok zhoduje z prvkom na indexe m2, ak áno, tak koniec. Výsledok je index m2
  4. Ak platí i>j, skonči, prvok x sa v poli nenachádza.
  5. Ak je hľadaný prvok menší ako prvok pole[m1], tak hľadaj v prvej tretine poľa
    • i zostáva nezmenené , j=m1-1. Choď na krok 1.
  6. Ak je hľadaný prvok väčší ako prvok pole[m2], tak hľadaj v tretej tretine poľa
    • i = m2+1 , j zostáva nezmenené. Choď na krok 1.
  7. inak hľadaj v druhej tretine poľa
    • i = m1+1 , j=m2-+. Choď na krok 1.

Uveďme príklad: V prechádzajúcom príklade hľadajme číslo x=39

Na začiatku máme: 

 i=0
 j=10

Vypočítame m1, m2 

 m1=( i*2 + j ) / 3 = (0+10)/3 = 3
 m2=( i + j*2 ) / 3 = (0+20)/3 = 6
pole=
0 1 2 m1=3 4 5 m2=6 7 8 9 10
1 2 6 18 20 23 29 32 34 39 43

Teraz hľadáme v tretej tretine poľa: 

 i=m2+1=7
 j=10

Vypočítame m1, m2 

 m1=( i*2 + j ) / 3 = (14+10)/3 =8
 m2=( i + j*2 ) / 3 = (7+20)/3 = 9
pole=
0 1 2 3 4 5 6 7 m1=8 m2=9 10
1 2 6 18 20 23 29 32 34 39 43

Platí, že x=pole[m2]. Výsledkom bude teda hodnota m2 (index nájdeného prvku v poli)

Ternárne vyhľadávanie - zdrojový kód v C

Názov funkcie

hladajTernarne

Návratová hodnota

index nájdeného prvku (-1 pri neúspechu)

Parametre

pole prvkov - pole
rozmer poľa - n
hľadaný prvok - x

Zložitosť algoritmu

O(Log n)


int hladajTernarne(int pole[],int i,int j,int x) {
  int m1,m2;
  m1=( i*2 + j ) / 3;
  m2=( i + j*2 ) / 3;
  if(x==pole[m1])
    return m1;
  if(x==pole[m2])   
    return m2;
  if(i>j) return -1; // prvok sa nenašiel  
  if(x<pole[m1]) // hľadaj v prvej tretine
    return(hladajTernarne(pole, i,m1-1,x));
  if(x>pole[m2])  // hľadaj v druhej tretine
    return(hladajTernarne(pole, m2+1,j,x));
  else   // hľadaj v tretej tretine
    return(hladajTernarne(pole, m1+1,m2-1,x));
}

Porovnanie binárneho a ternárneho vyhľadávania

Provnávané varianty
rekurzívne verzie funkcií
Spôsov porovnávania
Veľkosť poľa v ktorom hľadáme - n (os x grafu)
Počet hľadaných čísel - 1000
Počet opakovaní každého hľadania - 1000

<pLines ymin=0 axiscolor=888888 cubic angle=90 plots legend xtitle=pocet_cisel ytitle=cas_[s]> ,binarne,ternarne 1 000, 2.115, 2.094 5 000, 2.537, 2.513 10 000, 2.674, 2.622 50 000, 3.028, 3.005 100 000, 3.252, 3.032 500 000, 3.642, 3.358 1 000 000, 3.719, 3.471 5 000 000, 4.129, 3.771 10 000 000, 4.410, 3.963 50 000 000, 5.679, 4.304 100 000 000, 5.806, 5.248 </pLines>

Vyhľadávanie v rekurzívnych štruktúrach

Ďalším špeciálnym typom vyhľadávania je vyhľadávanie v rekurzívne definovaných štruktúrach. Medzi tieto štruktúry patria stromy, konkrétne Binárny strom alebo B-strom. V týchto štruktúrach sa nedá implementovať lineárne vyhľadávanie ani binárne (resp. ternárane) vyhľadávanie, pretože samotná štruktúra takéhoto dátového typu to nedovoľuje.

Vyhľadávanie v binárnych stromoch

Najjednoduchšia forma stromu je binárny strom. Binárny strom je stromová dátová štruktúra, v ktorej každý uzol má najviac dvoch potomkov. Binárny strom sa skladá z

  1. koreňového uzla
  2. ľavý a pravý podstrom.
    • Oba podstromy sú taktiež binárne stromy.
Binárny strom

Uzly na najnižšej úrovni stromu (2, 5, 11, 4) sa nazývajú listy. Vlastnosťou binárneho stromu je to, že údaje v ňom sú vždy usporiadané nasledovným spôsobom:

  • naľavo od uzla sú tie prvky, ktoré majú hodnotu menšiu ako tohoto uzla
  • napravo od uzla sú tie prvky, ktoré majú hodnotu väčšiu ako tohoto uzla

Pri tomto predpoklade môžeme sformulovať vyhľadávací algoritmus pre binárne stromy:

Budeme hľadať v binárnom strome, ktorý si označme bstrom. Tento každý uzol stromu môže mať žiadneho, jedného alebo dvoch potomkov. Potomkov budeme značiť ľavý a pravý. V strome bstrom budeme hľadať prvok x.

  1. Označ si koreň stromu v ktorom budeme hľadať ako uzol.
  2. Porovnaj hodnotu uzla uzol s hľadaným prvkom x.
  3. Ak sa tieto hodnoty zhodujú - koniec. Našli sme prvok x.
  4. Ak aktuálny uzol nemá potomkov, tak koniec - Nenašli sme prvok x.
  5. Ak je hodnota x menšia ako hodnota uzla uzol, tak označ si ako uzol potomka ľavý. Choď na krok 1.
  6. Ak je hodnota x menšia ako hodnota uzla uzol, tak označ si ako uzol potomka pravý. Choď na krok 1.

Pseudokód algoritmu vyhľadávania: 

hľadaj(strom, x)
uzol <- vrhol stromu strom
ak je uzol list
  koniec - x sme nenašli
ak je hodnota uzla == x tak 
  koniec - vráť hodnotu x
ak je hodnota uzla < x tak
  hľadaj(uzol->lavy,x)
ak je hodnota uzla > x tak
  hľadaj(uzol->pravy,x)

značenie uzol->lavy, resp. uzol->pravy má význam, že ďalej budeme pracovať len s ľavou, resp. pravou časťou binárneho stromu.

Implementácia v jazyku C

Definícia binárneho stromu je v kapitole Binárny strom. Pre správne pochopenie nasledujúcej časti je potrebné vedieť pracovať s binárnym stromom.


Definujme dátovú štruktúru binárny strom: 

struct TUzol
{   int data;
	 TUzol *lavy,*pravy;
};


Názov funkcie

hladajRekurzivneStrom

Návratová hodnota

smerník na nájdený prvok (v prípade neúspechu NULL)

Parametre

binárny strom - strom
hľadaný prvok - x

Zložitosť algoritmu

O(n)


TUzol* hladajRekurzivneStrom(TUzol *s, int x)
{ 
  if(s==NULL) return NULL;   
  if(s->data == x ) return s;
  if(x < s->data) return hladajRekurzivneStrom(s->lavy);
  if(x > s->data) return hladajRekurzivneStrom(s->pravy);

}


Odkazy

Zdroj: „http://www.kiwiki.info/index.php?title=Algoritmy_vyhľadávania&oldid=6647“