V minulé lekci, Dynamické programování, jsme si představili dynamické programování,které využívá již dříve spočítané výsledky.
V dnešním tutoriálu o teorii algoritmůse budeme věnovat problémům, pro něž dosud chybí známé polynomiálníalgoritmy. Ukážeme si způsoby možných řešení.
V minulých lekcích jsme se dívali na to, jak algoritmizační problémyefektivně řešit. Nabízí se otázka, zda jdekaždý problém efektivně řešit či zda jsou problémy, kteréřešit efektivně nelze. Toto téma je velmi komplexní,takže do něj v tomto tutoriálu pouze nahlédneme několika příkladytěžkých problémů s jejich případným řešením. Podíváme se hlavně naproblém P vs NP a jeho důsledek.
7 problémů tisíciletí
V roce 2000 bylo vyhlášeno tzv. 7 problémů tisíciletí.Jedná se o matematické problémy, které jsou považovány zaopravdu těžké a které mají hluboký dopad na dění kolem nás.
Jsou to:
PvsNPproblém - Týká sepočítačů - Lze každý algoritmizační problém vyřešit "dobře"?- Hodgeova domněnka - Problém týkající setopologie.
- Poincarého domněnka - Tento problém se týkáčtyřrozměrné koule.
- Riemannova hypotéza - Týká se rozloženíprvočísel.
- Yangova-Millsova teorie - Týká se elementárníchčástic.
- Navierovy-Stokesovy rovnice - Rovnice popisujícíproudění tekutin.
- Birchova a Swinnertonova-Dyerova domněnka - Určenípočtu řešení rovnic.
Z tohoto seznamu v roce 2003 byla dokázána pouzePoincarého domněnka ruským matematikem GrigorijemPerelmanem.
Jeden z problémů ze seznamu, P vs NP problém, setýká teoretické informatiky. Za jeho vyřešení je přislíbena odměnajednoho milionu dolarů.
Co je P vs NPproblém?
Zjednodušeně řečeno, P vs NP problém jeotevřená otázka: Existuje efektivní řešení na úlohy,které zatím neumíme efektivně řešit?
P problémy
Víme, že některé problémy umíme řešit polynomiálnědobře. Tedy s časovou složitostí, která není exponenciální.Když chceme seřadit pole, nebudeme jeho prvky náhodně prohazovat, až setrefíme do kombinace, kdy jdou prvky za sebou. Použijeme např. Quick sort(více v lekci Quicksort kurzu Třídicí/řadicí algoritmy).
Tyto problémy nazýváme polynomiální problémy,zkráceně P problémy.
NP problémy
Také víme, že některé problémy jsou těžké. Např. ověřit heslo jesnadné. Převést ale ověřovací otisk hesla zpět na původní heslo, tedyprolomit jeho bezpečnost, v současné době efektivně nelzea můžeme jej jen hádat. Na tom je kupříkladu postavenápočítačová bezpečnost a šifrování (více v kurzu Kryptografie). Rozluštěníklíče a zprávy trvá exponenciálně dlouho.
Přesto je otázka, zda se i těžké problémy, na kterézatím není znám polynomiální algoritmus, dají polynomiálně vyřešit.Tyto problémy nazýváme nedeterministické polynomiálníproblémy, zkráceně NP problémy.
NP-úplné problémy
Do této třetí kategorie spadají ty NP problémy, na kteréjsou ostatní NP problémy převoditelné. To znamená, že pokudbychom uměli řešit nějaký NP-úplný problém, tak každýdalší NP problém by byl složitější nejvýše tolikrát, jakdrahý je převod mezi těmito dvěma problémy.
Příklady si ukážeme níže. Teoreticky jde tedy "jen" o to, naučit seřešit NP-úplné problémy a o tom, zda to lze. Zbytek problémůbychom na ně převedli.
P vs NP problémy
Podívejme se na tyto dva grafy:
Levý graf počítá s tím, že pro NP problémyneexistuje nějaký dobrý algoritmus. Naopak ten vpravopočítá s tím, že lepší řešení najít lze, jen hoještě neznáme.
Většina lidí se přiklání k názoru, že neexistujípolynomiální algoritmy pro třídu NP. Tedy, že problémy,které neumíme řešit dnes, nebudou pravděpodobně umět řešit ani lidé vbudoucnu.
Praktický příklad
Představme si však, že by se P skutečně rovnaloNP a bylo by možné objevit polynomiálníalgoritmus, který by rozluštil komunikaci mezi bankou a klientem.Peníze by již nebyly v bezpečí a celý systém by se mohl zhroutit.
Na druhou stranu se zatím ukazuje, že by to platit nemuselo, ale důkazještě čeká na svého objevitele.
Ukázky problémů
Pojďme se tedy vrhnout na několik populárních problémů, které neumímeřešit. Problémy jsou zadané tak, aby byly laicky dobře pochopitelné apřevoditelné na reálné problémy v bezpečnosti a dalšíchodvětvích informatiky.
Problém obchodního cestujícího
Nejznámější NP-úplný problém je následující: Mámeněkolik měst s různými vzdálenosti mezi nimi a chudáka obchodníhocestujícího, který musí navštívit všechna města. Rád by věděl, jakounejkratší vzdálenost je třeba urazit, tedy kudy se vydat,aby přes žádné město nejel 2x.
Tento problém si nebudeme plést s problémem hledánínejkratší cesty v grafu, která se hledá vždy jen mezi dvěma vrcholy ajedná se o známý P problém.
Matematicky se úloha obchodního cestujícího definuje tak, že hledámeHamiltonskou kružnici minimální délky. To je kružnice,která projde všemi vrcholy grafu bez opakování(kromě startu/cíle). Myslíme samozřejmě kružnici z hlediska teoriegrafů
Jak takový problém řešit?
Pokud máme malý počet měst, můžeme použít hrubousílu (brute-force) a vyzkoušet všechny možné variace měst. To je však prodata kolem 100 měst úplně nepoužitelné, přesnějipříliš pomalé. Je možné použít několik tzv.heuristik.
Heuristiky jsou jakési snahy o urychlení algoritmu za cenuzískání řešení, které často není ideální (pokud nemáme zrovnaštěstí), ale je dostatečně dobré. Zmíníme si zde pro ilustraci dvěheuristiky - pomoc nejbližšího souseda a hladovýalgoritmus.
Nejbližší soused
Obchodní cestující začne v libovolném městě. Potom sevydá po nejkratší možné cestě do dalšího města. Nakonec, až projdevšechna města, se vrátí zpět.
Hladový algoritmus
Na situaci můžeme jít i jinak. Obchodní cestující si nejdříveseřadí všechny dvojice měst od nejmenší podle velikosti.Nakonec se dvojice skládají do grafu. Pokud by náhodou nastal někde cyklus,hrana se přeskočí.
Problém baťohu
Představme si, že jsme horští zásobovači a v chladných ránechšplháme do odlehlých horských hotelů s naším baťohem.
Majitelé jsou tak zoufalí, že koupí všechno, co tampřineseme. Známe své meze a řekneme si, že více než určitý počet kilna záda nevezmeme, nechceme se zničit. Jinak máme volné polepůsobnosti.
Problém zní takto: Máme n věcí a každá znich má nějakou hmotnost a nějakou cenu.Chceme maximální možný součet cen jednotlivých předmětů, abyjejich hmotnost nepřekročila stanovenou nosnost.
Možná heuristika
Můžeme si předměty seřadit sestupně podle poměrucena/váha a postupně přidávat. Výsledek ovšem nebude na první pokusyideální.
Problém dvou loupežníků
Máme dva lupiče, kteří se vloupali do domu. Ukradli televizi, rádio,počítač, sošku z Indie, drahé víno a několik lentilek.
Rádi by si lup rozdělili rovným dílem, aby nikdonepřišel zkrátka, tj. aby si rozdělili předměty tak, aby se jejichcelkové sumy rovnaly (resp. aby byly co nejrovnější).
Hladové řešení
Opět si můžeme trochu pomoci heuristikou. Můžeme zkusit přidávatnejhodnotnější předmět tomu loupežníkovi, který máméně.
Problém kliky v grafu
Máme nějaký graf a hledáme největší kliku, tj. úplnýpodgraf, neboli graf, kde každý vrchol souvisí s každým.
Problém největší nezávislémnožiny
Máme nějaký graf a hledáme největší nezávisloumnožinu, tj. množinu vrcholů, mezi kterými nevede hrana.
Převoditelnost problému
Podíváme se nyní na to, zda lze efektivně nějakýproblém převést na jiný.
Problém kliky v grafu je i stylem psaní velmi podobnýnejvětší nezávislé množině. Šlo by tyto problémy nasebe přenést? Stačí prohodit hrany za nehrany a z problému hledání klikyse stane problém nalezení největší nezávislémnožiny.
Jak je však tento převod rychlý? Nemůže se stát, žesám převod bude trvat exponenciálně dlouho? Pokud ano, pak na sebe nejsouproblémy převoditelné. Zde to však bude záviset jen na reprezentaci hrangrafu. Budeme-li si je reprezentovat v matici, pak všechny 0vyměníme za 1, a 1 za 0. Tato operacebude polynomiální. Budeme-li efektivně umět řešitproblém kliky, vyřešíme i problém nezávislé množiny.
Závěr - K čemu to řešit?
Proč bychom se vlastně měli těmito problémyzabývat?
Často se totiž dostaneme do situace, kdy řešení problému trvápříliš dlouho. Není žádný návod pro vymýšleníheuristik, či nějakých optimalizací, ale znalostí problémů, kteří užpřed námi lidé řešili. Můžeme sami nalézt překvapivě hezké aelegantní řešení problémů, které ostatní řeší hrubou silou.
V následujícím kvízu, Kvíz - Teorie algoritmů, si vyzkoušíme nabyté zkušenosti z kurzu.
