Serie Algoritmy
Tato serie ma za cil seznamit Vas s jednoduchymi algoritmy, ktere treba bezne pouzivate (nebo vyuzivate) a mozna o tom ani nevite. V nekolika dilech (+ bonusovka po kazdych ctyrech - na bonusovku nebudete potrebovat sbirat zadna cisla z vicek ani nic podobneho) se mimo jine dozvite, jak Vase GPS vyhledava nejkratsi trasu po silnicich, jak se elektrifikovala Morava, nebo treba jak projit tunel, kdyz dochazi baterky. Pokud Vas tohle vsechno zajima, pak je tahle serie urcena prave Vam!
V tomto dile se seznamime s tzv. Hladovymi algoritmy a zaroven si ukazeme, ze zrovna ony nemusi byt to nejlepsi.
Hladovy algoritmus
... je obecny nazev pro jakykoliv algoritmus, ktery v kazdem svem kroku vybira lokalni minimum/maximum, pricemz existuje sance, ze takto nalezne minimum/maximum globalni. Pritom existuji pripady, kdy je uspech zaruceny (na nejaky jeste v serii urcite narazime). Ve vetsine pripadu davaji hladove algoritmy alespon dostatecne dobre reseni, pokud ne rovnou nejlepsi, nehlede na to, ze byva podstatne jednodussi je naprogramovat - vysledne usetreni casu pri dobre efektivite muze pak byt vyhodnejsi, nez nejefektivnejsi algoritmus.
Priklad 1: Akce kulovy blesk
A mame tu stehovani. N rodin se rozhodlo prestehovat se podle vzorce I -> (I+1) mod N, tj. kazda rodina se prestehuje do bytu rodiny s cislem o 1 vetsim a N-ta rodina se prestehuje do jednicky. Jednoduche, ze? Tak aby to tak jednoduche nebylo, mame tady omezujici podminky:
1) kazda rodina se muze stehovat max. jednou denne, ale za celou akci se muze stehovat nekolikrat
2) stehovanim se mysli vymena dvou rodin, tj. cyklus 3 a vice rodin je v jednom dni nepripustny!
3) behem dne se muze stehovat libovolne mnozstvi rodin, pokud to neporusi jednu z predchozich podminek
Ukol: najit algoritmus, podle ktereho lze rodiny prestehovat za co nejmensi pocet dni.
Napoveda: S hladovym algoritmem je lze prestehovat priblizne za log2(N) dni, coz neni spatne, ale jde to i rychleji! Prijdete na to jak? Vztah pro nejm. pocet dnu podle Vaseho algoritmu (napr. log2(N), N, (N+1)2 apod.) napiste do LOGu!
Priklad 2: Svetlo na konci tunelu
Rodinka na vylete narazila na tunel. Tunel se neda obejit a je uzky, takze jim muzou projit soucasne max. dva lide. Potme se do tunelu boji, ale maji baterku, ktera vydrzi svitit jeste 14 minut. Dostanou se vsichni za tunel, kdyz jim cesta tunelem trva podle nasledujici tabulky? Jak dlouho jim pruchod potrva? (Pokud jdou tunelem dva, jdou rychlosti toho pomalejsiho!)
| Osoba |
Cas [min.] |
| Otec |
1 |
| Matka |
2 |
| Syn |
5 |
| Dcera |
6 |
Kde najit finalovku
K finalce je nejlepsi se vypravit od konecne autobusu 139, 253 a 157 "Na Beranku". Neni tam kde zaparkovat a autobusy jezdi dost casto, takze drive-in LOGy nejsou nutne (jinak receno: Nejezdete si pro kesku autem!). Pokud se rozhodnete kesku dobyt smerem z rokle, vezte, ze terrain rating v tom pripade je asi 4.5, mozna 5. Taky bych Vas poprosil, abyste kesku nelovili v noci. Teren tam na to neni.
Na souradnicich N 49 59.A E 014 25.B najdete stary, castecne uschly akat. Pokud slezete mezi nej a skalku, a otocite se ke skalce, najdete to, co hledate.
A = (vysledek 2. prikladu = nejlepsi cas v minutach)*48 - 3
B = (vysledek 2. prikladu = nejlepsi cas v minutach)*59 + 2
Provazej Vas Signal!
Historie cache:
- 11.09.2008 Umistena