Vyhledávání II. - Nesekvenční vyhledávání
 x   TIP: Přetáhni ikonu na hlavní panel pro připnutí webu
Reklama
Reklama

Vyhledávání II. - Nesekvenční vyhledáváníVyhledávání II. - Nesekvenční vyhledávání

 
Hledat
Moderní platforma pro vytvoření vašeho nového webu – Wix.com.
Nyní už můžete mít web zdarma.
Vybavení pro Laser Game
Spuštěn Filmový magazín
Laser Game Brno

Vyhledávání II. - Nesekvenční vyhledávání

Google       Google       18. 2. 2006       15 995×

Binární vyhledávání
Uniformní binární vyhledávání
Fibonacciho vyhledávání
Jiné metody vyhledávání v seřazeném seznamu .

Reklama
Reklama

Implementujeme-li vyhledávací tabulku polem seřazeným podle velikosti klíčů položek, nabízejí se pro vyhledávání účinnější algoritmy, než je sekvenční vyhledávání. Tyto metody se poněkud podobají numerickým metodám pro hledání kořene funkce jedné proměnné, známe-li interval, v němž je právě jeden kořen. Zvlášť nápadná je podoba s metodou „půlení intervalu“. Na témže principu jsou založeny algoritmy třídy binárního vyhledávání a tzv. Fibonacciho vyhledávání, které budou blíže popsány v tomto odstavci.

1.2.1. Binární vyhledávání

Nechť pro pole implementující vyhledávací tabulku platí:

POLE[1].KLIC < POLE[2].KLIC < .... < POLE[n].KLIC

a dále nechť pro vyhledávaný klíč K platí:

K >= POLE[1].KLIC    a    K <= POLE[n].KLIC

Pak princip binárního vyhledávání lze slovně popsat takto: Vyhledávaný klíč se porovná s klíčem položky, která je umístěna v polovině prohledávaného pole. Dojde-li ke shodě, končí vyhledávání úspěšně. Je-li vyhledávany klíč menší, postupuje se porovnáváním prostředního prvku v levé polovině původního pole, je-li větší v pravé polovině původního pole. Vyhledávání končí neúspěchem v případě, že prohledávaná část pole je prázdná (tzn. že její levý index je větší než pravý).

Zápis algoritmu má tvar:

	l := 1;	{ var l:1..MAX;	ukazatel levé hranice prohledávaného pole }
	r := n;	{ var r:1..MAX;	ukazatel pravé hranice prohledávaného pole }
	repeat
		i := (l+r) div 2;
		if K < POLE[i].KLIC
			then r := i–1;	{ hledaný klíč může být v levé polovině }
			else l := i+1;	{ hledaný klíč může být v pravé polovině }
	until (K = POLE[i].KLIC) or (r

Dijkstrova varianta binárního vyhldávání vychází z předpokladu, že pole může obsahovat více položek, jejichž klíče se navzájem rovnají. V případě úspěšného vyhledání se nalezne nejlevější položka ze skupiny položek se shodnými klíči, ATD tabulka sice takový předpoklad vylučuje, algoritmus však může být užitečný pro řadu aplikací.

Nechť platí:

POLE[1].KLIC <= POLE[2].KLIC <= .... <= POLE[n-1].KLIC < POLE[n].KLIC

a dále nechť pro vyhledávaný klíč K platí:

POLE[1].KLIC <= K

a

K < POLE[n].KLIC

Pak algoritmus Dijkstrovy varianty buinárního vyhledávání má tvar:

<*kod> l := 1; r := n; while r <> (l+1) do begin i := (l+r) div 2; if POLE[i].KLIC < K then l := i else r := i end; SEARCH := K = POLE[i].KLIC; { if SEARCH then prvek POLE[i] je nejlevějším prvkem skupiny položek s klíčem rovným K }

Zatímco u prvního algoritmu může úspěšné vyhledávání trvat kratší dobu než neúspěšné, Dijkstrova varianta má úspěšné i neúspěšné vyhledání stejně dlouhé.

1.2.2. Uniformní binární vyhledávání

Místo tří proměnných i, l a r lze použít pouze dvou: aktuální index i a odchylka m od aktuálního indexu i. Po každém neúspěšném porovnání ustavíme:

i := i+m		a	m := m div 2;

Při návrhu tohoto algoritmu je nutné promyslet všechny detaily, aby nedošlo k nepředvídané chybě.

Nechť je dáno pole, pro jehož položky platí:

POLE[1].KLIC < POLE[2].KLIC < .... < POLE[n].KLIC

Je-li MAX sudé, pak algoritmus potřebuje prázdnou (slepou) položku s indexem 0, jejíž klíč se nastaví na hodnotu menší, než jsou všechny vyhledávané klíče. Algoritmus uniformního binárního vyhledávání má tvar:

	POLE[0].KLIC := MINKLIC;	{ jen pro sudé MAX }
	i := (n+1] div 2;
	m := n div 2;
	while (m <> 0) and (K <> POLE[i].KLIC) do
		begin
			if K < POLE[i].KLIC
				then i := i – (m+1) div 2
				else i := i + (m+1) div 2;
			m := m div 2;
	end;
	SEARCH := K = POLE[i].KLIC;
	{ if SEARCH then prvek POLE[i] je hledaný prvek }

Hlavní přednost této metody se může využít, je-li tabulka statická. V tom případě lze pro daný počet položek vytvořit před vyhledáváním pomocné pole odchylek DELTA a jejím použitím v cyklu vyhledávání odstranit operaci dělení, čímž se algoritmus značně zrychlí. Pro DELTA platí:

DELTA[j] = round (n/2j)

Algoritmus uniformního vyhledávání využívající této výhody má tvar:


	MOCNINA := 2;		{ var MOCNINA:POSINT }
	for j := 1 to m+2 do	{ kde platí 2m-1 < n <= 2m }
		begin
			DELTA[j] := round(n/MOCNINA);
			{ var DELTA:array[1..(m+2)] of POSINT }
			MOCNINA := MOCNINA * 2;
		end;

	i := DELTA[1];
	j := 2;	
	while (K <> POLE[i[.KLIC) and (DELTA[j] <> 0) do
		begin
			if K < POLE[i[.KLIC 	then i := i + DELTA[j]
						else i := i - DELTA[j];
			j := succ(j);
		end;
	SEARCH := K = POLE[i].KLIC;
	{ if SEARCH then prvek POLE[i] je hledaným prvkem }

1.2.3. Fibonacciho vyhledávání

Existuje vzájemný vztah mezi binárním vyhledáváním v seřazeném poli a binárním stromem. Algoritmus Fibonacciho vyhledávání pracuje podobně jako binární vyhledávání. Daný interval v poli však nedělí na dvě poloviny, ale dělící bod odvozuje z Fibonacciho posloupnosti a k jeho získání stačí aditivní operace, což zvýší rychlost vyhledávání tam, kde aditivní operace jsou výrazně rychlejší než celočíselné dělení číslem 2.

V řadě metod hraje Fibonacciho posloupnost podobnou roli, jako mocninná řada dvou v obdobných metodách. K pochopení Fibonacciho vyhledávání se jen ztěží obejdeme bez Fibonacciho rozhodovacího stromu.

Fibonacciho strom řádu l má Fl+1-1 uzlů neterminálních a Fl+1 listů.
	Je-li l = 0 nebo l = 1 je strom tvořen jen listem 0.
	Je-li l>=2, pak kořenem stromu je uzel Fl
		přitom 	levý podstrom je Fibonacciho strom řádu l-1
		a 	pravý podstrom je Fibonacciho strom řádu l-2
			jehož uzly mají hodnotu zvýšenou o Fl

Pro jednoduchost budeme předpokládat, že n+1 je Fibonacciho číslo Fl+1. Pro jiné n je nutno provést potřebné počáteční úpravy. V následujícím algoritmu budeme používa funkce F(l) pro určení Fibonacciho čísla řádu.

Proměnné p a q budou mít vždy hodnoty dvou po sobě jdoucích Fibonacciho čísel.

Algoritmus Fibonacciho vyhledávání má tvar:


	i := F(l);
	p := F(l-1);
	q := F(l-2);
	TERM := false;
	while (K <> POLE[i].KLIC) and (not TERM) do
		if K < POLE[i].KLIC
		then { hledá se v levém podstromu }
			if q = 0
				then TERM := true	{ vyhledávání končí v levém listu }
				else { ustaví se nové hodnoty i,p a q pro levý podstrom }
				begin	i ;= i – q;
					p1 := q;		{ pomocná proměnná p1}
					q1 := p – q;	{ pomocná proměnná q1}
					p := p1;
					q := q1;
				end
			else { hledá se v pravém podstromu }
				if p = 1 	then TERM := true	{ vyhledávání končí v pravém listu }
					else 	{ ustaví se nové hodnoty i,p a q pro pravý podstrom }
						begin	i := i + q;
							p := p – q;
							q := q – p
						end;	{ konec if K < POLE[i].KLIC a konec while }
	SEARCH := not TERM;
	{ if SEARCH then prvek POLE[i] je hledaným prvkem }

1.2.4. Jiné metody vyhledávání v seřazeném seznamu

Má-li se vyhledávat prvek v seznamu seřazeném podle velikosti klíčů jednotlivých položek, nabízejí se principiálně i jiné metody, které známe dobře z praxe při vyhledávání žádaného hesla ve slovníku, či osoby v telefonním seznamu. V tom případě lze vyhledávání usnadnit s využitím těchto principů:

a) Některé slovníky mají na straně opačné než je hřbet výřezy označené jednotlivými písmeny abecedy (tzv. „prstové indexy“), které umožňují jedním hmatem otevřít slovník na stránce, od které jsou uvedena hesla začínající na dané písmeno. Tento princip je podobný indexsekvenčnímu přístupu k seznamu (k vhodnému místu seznamu se dostaneme pomocí „indexu“ a dále postupujeme sekvenčně) a proto mu říkáme indexsekvenční vyhledávání. Tento přístup je vhodný především pro externí vyhledávání.

b) Hledáme-li ve slovníku, který není vybaven prstovými indexy, jistě nevyhledáváme tak, že bychom „půlili“ plný rozsah slovníku abychom zjistili, zda je hledané heslo v levé nebo v pravé polovině, ale dělící bod získáváme intuitivní interpolací. Víme-li, že hledaný klíč K leží mezi klíči K1 a K2 (K1 < K2), pak dělící bod hledáme v místě blízkém hodnotě (K – K1)/ (K2 - K) a mlčky předpokládáme, že rozdělení klíčů v intervalu od K1 do K2 je rovnoměrné. Tato úvaha je základem interpolačního vyhledávání.

Řada experimentů i praktické zkušenosti však ukazují, že interpolační metoda aplikovaná na seřazené pole nesníží počet porovnání tak dostatečně, aby se kompenzoval čas, potřebný navíc pro složitější určení dělícího bodu. Metoda může být poněkud úspěšnější při aplikaci na vyhledávání na vnějších paměťových zařízeních.

Zdroj: Petr Pindur - vyhledávání

×Odeslání článku na tvůj Kindle

Zadej svůj Kindle e-mail a my ti pošleme článek na tvůj Kindle.
Musíš mít povolený příjem obsahu do svého Kindle z naší e-mailové adresy kindle@programujte.com.

E-mailová adresa (např. novak@kindle.com):

TIP: Pokud chceš dostávat naše články každé ráno do svého Kindle, koukni do sekce Články do Kindle.

1 názor  —  1 nový  
Hlasování bylo ukončeno    
0 hlasů
Google
(fotka) Lukáš ChurýLukáš je šéfredaktorem Programujte, vyvíjí webové aplikace, fascinuje ho umělá inteligence a je lektorem na FI MUNI, kde učí navrhovat studenty GUI. Poslední dobou se snaží posunout Laser Game o stupeň výše a vyvíjí pro něj nové herní aplikace a elektroniku.
Web     Twitter     Facebook     LinkedIn    

Nové články

Obrázek ke článku Datafesťak 2018 bude o datech, byznyse a ženách v IT

Datafesťak 2018 bude o datech, byznyse a ženách v IT

Na Univerzitě v Hradci Králové se 23. a 24. listopadu potkají všichni, které zajímá práce s daty. 

Reálné zkušenosti se zpracováním dat budou v prostorách univerzity prezentovat zástupci obchodních i výrobních firem. Potkat tak bude možné představitelé například z Kiwi.com, Crocodille, Dáme Jídlo nebo společnosti Adler. 

Reklama
Reklama
Obrázek ke článku 4 tipy, jak financovat rozvoj start-upu

4 tipy, jak financovat rozvoj start-upu

Možná jste právě jedním ze zakladatelů či manažerů nadějného start-upu 
a aktuálně řešíte, kde sehnat finanční prostředky pro další rozvoj. Zde pro vás máme čtyři tipy.

Obrázek ke článku Virtuální zrcadla změní způsob nakupování v e-shopech

Virtuální zrcadla změní způsob nakupování v e-shopech

Díky pluginu Virtooal.com získávají zákazníci e-shopů možnost si vyzkoušet produkty ve virtuálním světě. E-shopy, které si plugin nainstalují, výrazně snižují množství vráceného zboží, dělají nákupy zábavnějšími, a tím budují lepší vztahy se svými zákazníky. V současnosti lze Virtooal.com využít zejména pro kosmetiku, brýle a šperky, do budoucna půjde také o módu.

Obrázek ke článku Kariérní postup & vyšší plat: Titul MBA ve sféře IT

Kariérní postup & vyšší plat: Titul MBA ve sféře IT

Působíte jako specialista v oblasti IT a aspirujete na povýšení, příp. řídící pozici? Pak se jistě potýkáte nejen s vysokými nároky (potenciálních) zaměstnavatelů, ale i se silnou konkurencí ze strany ostatních uchazečů. Pokud chcete zvýšit své šance na kariérní posun a lepší plat, měli byste vedle technických dovedností ovládat i ty manažerské. Pomoci vám v tomto ohledu může studium MBA se specializací na management IT.

Reklama autora

Hostujeme u Českého hostingu       ISSN 1801-1586       ⇡ Nahoru Webtea.cz logo © 20032018 Programujte.com
Zasadilo a pěstuje Webtea.cz, šéfredaktor Lukáš Churý