Student World

pravidelné páteční „přetištění“ staršího článku

Na Science Worldu jsme již měli celou řadu článků o obchodním cestujícím a dalších problémech spadajících do kategorie NP úplných. Na problém lze nahlížet nejen teoreticky, ale i „experimentálně“. V takovém případě se například neptáme, zda určitý algoritmus řeší v nějakém čase každou úlohu této kategorie, ale ptáme se na řešení typického příkladu, respektive na statistické rozložení doby potřebné k výpočtu.

Předpokládejme, že NP je různé od P. To ale kupodivu neznamená, že drtivá většina konkrétních zadání například problému obchodního cestujícího neumožňuje relativně snadné řešení (se všemi z toho vyplývajícími konsekvencemi pro praktické využití). Jak takovýhle abstraktní pohled konkretizovat?

V knize Umělá inteligence 5 je celý postup popsán na problému splnitelnosti (satisfiability). Vezmeme jeden z používaných algoritmů, konkrétně třeba tzv. algoritmus Davisův-Putnamův, začneme náhodně generovat různé problémy splnitelnosti a analyzovat rychlost řešení.

Ukáže se, že většina z těchto případů je řešitelná rychle, pouze v určité oblasti stavového prostoru je potřeba dlouhý čas. Možná bude ilustrativnější se vrátit opět k obchodnímu cestujícímu (ve verzi najít libovolnou cestu mezi všemi body/testovat její existenci): to, na čem především závisí, je poměr bodů a spojnic. Pokud je bodů příliš mnoho a spojnic příliš málo, je problém často tzv. přeurčený a algoritmus celkem rychle odhalí, že úloha nemá řešení. Je-li naopak hromada spojnic a několik bodů, nějaké řešení je objeveno taktéž rychle. Pouze v určité oblasti (řekněme „řádově stejně bodů jako spojnic“) se úloha stává obtížnou: není lehké ani najít řešení, ani dokázat, že žádné neexistuje.

Co z toho vyplývá? V principu lze ještě předtím, než konkrétní zadaný NP úplný problém začneme řešit, zjistit stupeň jeho obtížnosti (třeba i s využitím toho, že jednotlivé typu těchto problémů, splnitelnost, obchodní cestující atd. jsou na sebe navzájem převoditelné). To má řadu důsledků například pro kryptografii.

V empirickém zkoumání lze pokračovat ne analýzou jediného algoritmu, ale tím, že fázový přechod budeme analyzovat pro více algoritmů. Budeme na ně přitom nahlížet jako na černou skřínku a jejich efektivitu zkoumat ne na základě analýzy jejich vnitřní struktury, ale prostě testem.

Zafixujeme jeden náhodně zvolený případ problému a uplatníme na něj „náhodné“ algoritmy (ve smyslu modifikací jediného algoritmu původního). Analýza v tomto případě vede k netriviálnímu závěru – pokud není řešení nalezeno relativně rychle, bude nalezeno až za velmi dlouhou dobu. Obě oblasti délky řešení odděluje fázový přechod.

Z čehož vyplývá, že účinnou strategií je algoritmus, který po určité době nedá řešení, vypnout a spustit namísto toho modifikaci tohoto algoritmu. To je ovšem zcela antiintuitivní postřeh, protože za prvé se nezdá, že by náhodná úprava mohla statisticky vylepšit efektivitu algoritmu, za druhé (a to hlavně) je pak při vypnutí algoritmu vymazána jeho paměť a informace o zatím prohledané části stavového prostoru se nenávratně ztrácí.

V praxi tenhle přístup ale funguje. Řada kombinatorických úloh, které se do té doby nedařilo vyřešit, byla zdolána právě popsanou metodou…

Zdroj: Kolektiv autorů: Umělá inteligence 5, Academia, Praha 2007. Část F. Železný: O empirickém výzkumu algoritmického objevování

autor Pavel Houser