Dijkstra, bubble sort, DFS: poznáte najznámejšie algoritmy sveta?

Hlavnou úlohou informatiky je hľadať najrýchlejšie a najlepšie riešenia. Rýchlosť závisí nielen od hardvéru, na akom procesy bežia, ale aj od samotných algoritmov. Pozrime sa na tri z nich, ktoré by mal poznať každý informatik.

Bubble sort

Bubble sort patrí medzi takzvané triediace algoritmy, ktoré majú veľmi jednoduchú úlohu: zoradiť prvky poľa od najmenšieho po najväčší (prípadne od najväčšieho po najmenší).

Čo sa týka efektivity, existuje mnoho lepších algoritmov ako Bubble sort. Beží v čase O(n2), čo znamená, že pri rádovo väčšom počte triedených prvkov je časovo náročný. Okrem toho sa príliš nekamaráti so súčasnými procesormi. Svoje využitie však našiel v počítačovej grafike, konkrétne pri triedení čiastočne utriedených polí.

S Bubble sortom sa často stretávajú aj študenti informatiky pri úvode do problematiky triediacich algoritmov, keďže je jednoduchý a ľahko pochopiteľný. Poďme sa o tom presvedčiť!

Algoritmus postupne prechádza poľom. Keď zistí, že prvok na i-tej pozícii je väčší než prvok na (i+1)-vej pozícii, tak ich jednoducho prehodí a poznačí si, že sa udiala výmena. Zjednodušene povedané, poľom opakovane prechádza dovtedy, kým je čo vymeniť.

Ak prejde celým poľom bez toho, aby vymenil nejaké dve čísla (teda pole je usporiadané), končí. Každé číslo tak postupne „vybublinkuje“ na správne miesto. Pekné, však?

DFS

Ako to už naznačuje jeho názov, DFS alebo Depth-first search (prehľadávanie do hĺbky) je algoritmus slúžiaci na prehľadávanie grafov. Znamená to, že keď mu dáme na vstup graf a počiatočný vrchol, tak nám vráti zoznam vrcholov grafu, do ktorých sa dá dostať z počiatočného vrchola.

Algoritmus začína v počiatočnom vrchole v0. Vyberie si ľubovoľného suseda v1, ktorého zatiaľ nenavštívil a vojde doň. Vrchol v1 označí ako navštívený a vloží ho do množiny vrcholov grafu. Znovu si vyberie ľubovoľného nenavštíveného suseda vrchola v1, označme ho v2, vojde doň, označí ho ako navštívený a vloží ho do množiny vrcholov grafu.

Ak vrchol v2 už nemá nenavštívených susedov, algoritmus sa vráti do vrchola v1 a vyberá si nového nenavštíveného suseda.

Takýmto spôsobom precestuje celým grafom, pričom na výstup nám dá množinu vrcholov grafu, respektíve jeho súvislého komponentu.

V matematike má tento algoritmus mnohé využitia. Okrem súvislých komponentov dokáže nájsť mosty a artikulácie grafov, využíva sa na testovanie planarity grafov a na riešenie bludísk. Dá sa aplikovať aj v umelej inteligencii či v prehľadávaní webu.

V reálnom živote sa však často stretávame s obrovskými (alebo nekonečnými) grafmi. To môže mať za následok, že sa DFS zacyklí alebo bude pracovať neefektívne. V takýchto prípadoch sa preto využíva jeho modifikácia, kde sa graf prehľadáva len do určitej hĺbky.

Dijkstrov algoritmus

Jeden z najznámejších algoritmov na svete slúži vyhľadávanie najkratšej cesty v ohodnotenom grafe.

Využíva sa v umelej inteligencii a v navigácii – vrcholy grafu reprezentujú obce a hrany reprezentujú cesty medzi nimi. Každej hrane priradíme číselnú hodnotu, ktorá vyjadruje dĺžku alebo časovú náročnosť príslušnej trasy.

Algoritmus sa viaže k holandskému vedcovi Edsgerovi Dijkstrovi, ktorý naň prišiel – ako to už býva – za úsmevných okolností. V roku 1956, jedného krásneho dňa nakupoval so svojou snúbenicou v Amsterdame. Keď si unavený sadol na kávu, kopla ho múza a o 20 minút bol slávny algoritmus na svete – bez použitia ceruzky a papiera.

Dijkstrov algoritmus je trochu náročnejší na pochopenie ako Bubblesort a DFS, takže namiesto vrcholov a hrán grafu si ho ukážeme na príklade miest a trás. Poďme na to!

Začnime v meste A. Budeme hľadať dĺžku najkratšej cesty z mesta A do mesta Z. Aby bola zábava, predpokladajme, že medzi A a Z neexistuje priama cesta. Ostatné mestá na mape si rozdelíme do dvoch skupín: tie, ktoré sme už navštívili a tie, ktoré sme zatiaľ nenavštívili.

Pri navštívených mestách budeme poznať presnú dĺžku najkratšej cesty z mesta A. Na začiatku budú všetky mestá okrem A nenavštívené.

Pre každé mesto M si budeme pamätať hodnotu d(M), a teda vzdialenosť od mesta A do mesta M. Túto hodnotu si pre nenavštívené mestá nastavíme ako nekonečno. V priebehu algoritmu sa bude postupne meniť, kým z nej nevypadne dĺžka najkratšej cesty z A do M.

Začíname teda v meste A. Pozrime sa na všetky mestá, do ktorých vedie priama cesta z A (teda taká, ktorá neprechádza žiadnym iným mestom). Pre všetky tieto mestá nastavme d rovné dĺžke cesty z A. Logicky, do týchto miest sa nevieme dostať kratšou cestou z mesta A.

Vyberme si nenavštívené mesto B s najnižšou hodnotou d(B) a prejdime doň. Pozrime si teraz mestá, do ktorých vedie priama cesta z B. Vyberme si jedno, povedzme, že mesto C. Vieme sa doň dostať kratšou cestou, než je hodnota d(C)?

Ak áno, tak túto hodnotu aktualizujeme – priradíme jej dĺžku cesty z A do B + dĺžku cesty z B do C.

Postupne si takto prejdeme všetky mestá, ktoré sú susedné s mestom B. Nezabudneme označiť mesto B ako navštívené a presunieme sa do ďalšieho nenavštíveného mesta X s najmenšou hodnotou d(X), pri ktorom postupujeme rovnako.

Budeme pokračovať dovtedy, kým nenavštívime aj mesto Z, teda mesto, kam sme sa chceli na začiatku dostať. Ako výstup vrátime hodnotu d(Z), čo bude presne dĺžka najkratšej cesty z mesta A do mesta Z.

Ak sa ti z týchto algoritmov nezatočila hlava alebo ich už máš teraz v malíčku, neváhaj a pridaj sa k nám. Hľadáme ľudí, ktorí dokážu myslieť inovatívne a chcú tento svet posunúť ďalej.