případně takovou, na níž spotřebujeme nejméně paliva. Algoritmus pro její nalezení proto
obvykle nepracuje přímo s mapou, ale s její abstrakcí v podobě tzv. grafu složeného z vr-
cho lů (to jsou města a křižovatky) spojených hranami (úseky silnic). Každou hranu pak
ohodnotíme cenou – podle potřeby buď délkou nebo časem či cenou za průjezd. Náš algo-
ritmus pak bude hledat, jak dané dva vrcholy propojit hranami o co nejmenší celkové
ceně.
Co děláme u nás?
Náš příklad s převodem reálného problému na otázku týkající se grafů není ojedinělý.
Pomocí grafů můžeme popsat i mnoho jiných úloh – namátkově třeba přepravu tekutiny
soustavou potrubí, konstrukci rozvrhu hodin, skládání Rubikovy kostky nebo přidělování
frekvencí vysílačům v sítích mobilních telefonů. To všechno jsou oblasti, kterým se na
Katedře aplikované matematiky věnujeme. Zabýváme se přitom nejen konkrétními prak-
tickými otázkami, ale také obecnější teorií grafů a grafových algoritmů. Ta pak slouží jako
jakési podhoubí, z něž vyrůstají řešení jednotlivých úloh.
Optimalizace
Hledání v mapě je z pohledu klasické matematiky trochu nezvyklý problém. Neptáme se
totiž, zda nějaký objekt (třeba limita posloupnosti nebo v našem případě cesta v grafu)
existuje, jelikož to je v našem případě obvykle zřejmé. Člověka pracujícího s algoritmy
především zajímá, jak daný objekt najít, případně pokud takových objektů existuje více,
jak najít nejlepší (nejlevnější, nejkratší, nejrychlejší, nejbližší, …) z nich. Tomuto hledání
nejlepších možných řešení se věnuje matematická disciplína nazvaná optimalizace.
Vzhledem k omezené rychlosti a paměťové kapacitě našich počítačů navíc potřebujeme,
aby si optimalizační algoritmus vystačil s omezeným množstvím času i paměti. To je někdy
snadné, třeba při hledání nejkratší cesty. Kdybychom ale otázku trochu pozměnili a hledali
nejkratší cestu, která navštíví všechna okresní města, rázem bychom získali problém, jehož
efektivní řešení dosud není známo.
U takových úloh studujeme i algoritmy, které přijatelně rychle naleznou řešení, jež sice
není nejlepší možné, ale v nějakém smyslu je skoro nejlepší – to může znamenat třeba ce stu
nejvýše o 10 % delší než optimální. Takovým algoritmům se říká aproximační.
Online algoritmy
Někdy se také stává, že optimalizační algoritmus nezná dopředu celý svůj vstup. Dostává
ho tedy po částech a musí průběžně reagovat na už přečtené části vstupu. Tyto on-line al go-
ritmy pěkně ilustruje následující příklad.
Uvažujme rovinnou pastvinu rozdělenou na dvě poloroviny nekonečně dlouhým plotem.
V jedné polorovině se pase kráva a ráda by se dostala na druhou stranu plotu, kde je tráva
zelenější. V plotu jsou ovšem jen jediná vrátka.
Kdyby kráva věděla, kde vrátka leží, vydala by se správným směrem a zjevně by ušla
nejmenší možnou vzdálenost. Pakliže ale správný směr nezná, musí se uchýlit k trochu
složitější strategii a střídat oba směry. Zkuste tuto strategii vymyslet. Prozradíme, že lze
najít takovou, která vždy nachodí méně než desetinásobek skutečné vzdálenosti k vrátkům.
Do světa on-line algoritmů samozřejmě patří i praktičtější otázky. Jmenujme třeba řízení
výtahů (postupně se dozvídáme požadavky cestujících) nebo obchodování s akciemi (reagu-
jeme na vývoj cen na burze).
Informatika: Algoritmy a optimalizace
79