Kombinatorické problémy hledání se podobají hře, ve které se části určité struktury mají složit určeným způsobem. Takové problémy vedou k prohledávání velké strukturované množiny možných řešení, modelů nebo systémů, aby se nalezl jeden, který vyhovuje zadaným podmínkám.

V každém z kombinatorických problémů se skrývá možnost kombinatorické exploze. Počet možností, které je třeba prohledat, neohraničeně roste a musí se provádět velké množství výpočtů, pokud se nepoužije nějaká matematická lest.

V roce 1959 Richard Karp pracoval ve výzkumném centru IBM Yorktown Heights pod vedením J. P. Rotha, odborníka v algebraické topologii. Posláním Rothovy skupiny bylo vytvořit algoritmus pro automatickou syntézu logických schémat. Vstupem programu byla množina booleovských vztahů, které udávaly, jak výstupy schématu závisí na jeho vstupech. Cílem bylo, aby program vygeneroval schéma s použitím co nejmenšího počtu logických hradel.

Program, který skupina vytvořila, obsahoval řadu velmi elegantních zjemnění a zjednodušení, ale základní mechanismus jednoduše vyčíslil možná schémata v pořadí jejich rostoucí ceny. Počet schémat se zvětšováním množství vstupních proměnných velmi rychle rostl. Z toho bohužel plynulo, že program nebyl použitelný na složitější logická schémata.

Velké vědecké práce 60. a 70. let 20.století prokázaly, že numerické přístupy k řešení těchto problémů byly značně naivní. Přibližně ve stejné době, v níž Rothova skupina řešila problém logických schémat, se Richard Karp podílel s Michaelem Heldem z IBM na řešení problému obchodního cestujícího. Tento problém dostal svůj název podle situace, v níž obchodní cestující má navštívit všechna místa ve své oblasti s tím, že svoji cestu chce začít a skončit ve svém bydlišti a přitom chce mít minimální dopravní náklady. Ve speciálním případě jsou těmito místy body v euklidovské rovině a cestovní náklady odpovídají euklidovské vzdálenosti těchto bodů. Problém obchodního cestujícího pak znamená nalézt polygon (mnohoúhelník) s minimálním obvodem, který prochází všemi body.

Na první pohled zcela nevinný problém obchodního cestujícího obsahuje potenciálně kombinatorickou explozi. Počet možných cest přes n míst v rovině je (n - 1)!/2, což je velmi rychle rostoucí funkce proměnné n. Již pro 20 míst při rychlosti výpočtu jednoho miliónu cest za sekundu je doba průchodu všemi cestami rovna několika tisícům let.

Michael Held a Richard Karp zkoušeli různé přístupy k tomuto problému. Začali znovuobjevením algoritmu založeném na dynamickém programování, na který původně upozornil Richard Bellman. Metoda dynamického programování sice redukovala čas prohledávání na (n^2).2^n, ale tato funkce také explozivně roste a je prakticky ohraničena na problémy s nejvíce 20 místy. Proto se Held a Karp vzdali myšlenky řešit problém exaktními metodami a začali experimentovat s metodami lokálního prohledávání, které vedly k dobrým, ikdyž ne k optimálním výsledkům. V těchto metodách se vybere některá cesta a opakovaně se provádí lokální změny, které tuto cestu mají vylepšit. Proces se ukončí, jakmile se nalezne taková cesta, kterou nelze lokálními změnami vylepšit. Heldova a Karpova metoda lokálního zlepšování byla těžkopádná. Později Shen Lin a Brian Kernighan z Bell Labs nalezli metody mnohem lepší. Takové metody se v praxi často používají, pokud se striktně nepožaduje nalezení optimálního řešení. Nelze však zaručit, že v praxi tyto metody budou vždy vést k cíli.

Později Held a Karp začali zkoumat metody ohraničeného větvení. Tyto metody jsou v zásadě enumerické povahy, ale svoji efektivnost získávají useknutím velkých částí prostoru možných řešení. Počítá se dolní odhad ceny každé cesty, která obsahuje určitá spojení a nemůže obsahovat žádné jiné. Pokud je dolní odhad dostatečně velký, znamená to, že žádná taková cesta nemůže být optimální. Po dlouhé sérii neúspěšných experimentů Held a Karp objevili silnou metodu získávání dolních odhadů. Jejich metoda byla schopna podstatně omezit prohledávání, takže bylo možno řešit problém obchodního cestujícího až z 65 místy. Později autoři ukázali, že jejich metoda je variací Lagrangeovy relaxace, která se používá na získávání dolních odhadů při technikách ohraničeného větvení.

Určitou dobu Heldův a Karpův program sloužil při řešení problému obchodního cestujícího. Později byla objevena metoda polyedrální kombinatoriky, která problém obchodního cestujícího převádí na problém lineárního programování. Tyto metody jsou schopny řešit problémy až se 300 místy, ale ani tento přístup neeliminuje možnost kombinatorické exploze.

Problém obchodního cestujícího byl fascinující záhadou. Byla publikována 400 stránková kniha, která pokrývala většinu znalostí o tomto problému. Teorie NP-úplnosti, o které se zmíníme později, poskytuje důkaz, že podstatou problému obchodního cestujícího, je praktická neřešitelnost. Neexistuje algoritmus, který by byl schopen obejít kombinatorickou explozi.

Počátkem 60. let 20. století mělo IBM Research Laboratory v Yorktown Heights skupinu kombinatorických matematiků, která sestavila důležité techniky pro řešení kombinatorických problémů s vyloučením kombinatorické exploze. Matematik George Dantzig z Rand Corporation sestavil simplexový algoritmus pro řešení problému lineárního programování, který se používá dodnes. Problémem lineárního programování je nalézt bod na mnohostěnu v mnohorozměrném prostoru, který je nejblíže dané nadrovině. V praxi se lze spolehnout, že simplexový algoritmus nalezne řešení velmi rychle.

Richard Karp se seznámil také s teorií o toku v sítích, jejímiž autory byli Lester Ford a Fulkerson. Tato teorie řeší problém přepravy nějaké látky daného množství určitou sítí, v níž každé spojení má určitou kapacitu (množství látky za jednotku času). Tento problém lze použít nejen na přepravu plynu, vody, elektřiny, ale také na tok informace v síti. Mnohé kombinatorické problémy lze převést na problém toků v síti. Příslušná teorie umožňuje tyto problémy řešit elegantně a efektivně pomocí operací sčítání a odčítání.

Metodu toku v sítích lze ilustrovat například na algoritmu pro řešení tzv. svatebního problému. Problém obsahuje skupinu n mužů a n žen, kdy cílem je vytvořit páry mužů a žen s určitou minimální cenou, pokud každé možné dvojici je přiřazena určitá cena. Ceny jsou zadány maticí n x n, ve které každý řádek odpovídá jednomu muži a každý sloupec jedné ženě. Vytvoření párů n mužů a n žen obecně odpovídá výběru n prvků matice, přičemž žádné dva vybrané prvky neleží ve stejném řádku a sloupci. Počet možných výběrů roste jako funkce n!. Matice na obr. 1.a ukazuje, že cena páru 2. ženy a 3. muže je 9.

3  4  2         1  2  0          0  0  0           0  0  1

8  9  1         7  8  0          6  6  0           5  5  0

7 9 5           2  4  0          1  2  0           0  1  0

 (a)                 (b)                (c)                (d)                       Obr. 1.

Základem maďarského algoritmu pro řešení svatebního problému je skutečnost, že problém se nezmění, pokud se od všech prvků určitého řádku odečte stejná konstanta. Algoritmus tímto způsobem vytvoří matici, ve které jsou všechny prvky nezáporné (obr. 1.b). Na vytvoření nuly v každém sloupci algoritmus odečte ve všech sloupcích, které ještě neobsahují nulu, nejmenší prvek v daném sloupci (obr 1.c). V tomto případě leží všechny nuly výsledné matice v prvním řádku a ve třetím sloupci. Protože úplné párování obsahuje pouze jeden prvek z každého řádku nebo sloupce, není ještě možno nalézt úplné párování obsahující pouze nulové prvky. Na vytvoření takového párování je nutné vytvořit nulu v levé dolní části matice. V tomto případě algoritmus vytvoří nulu odečtením jednotky od prvního a druhého sloupce a přidáním jednotky k prvnímu řádku (obr. 1.d), aby se eliminovaly záporné prvky. Ve výsledné matici tvoří prvky [1,2], [2,3] a [3,1] úplné párování s nulovou cenou. Toto párování je optimální jak v této tak v původní matici.

Uvedený algoritmus pro řešení svatebního problému je mnohem efektivnější, než výpočet hrubou přímou metodou. Čas potřebný na řešení svatebního problému roste s n^3. Proto je možné řešit příklady s tisíci řádky a sloupci.

Generace vědců, kteří rozpracovali teorii lineárního progra- mování a toků v sítích, měla pragmatický vztah k základům výpočetní složitosti. Algoritmus se považoval za efektivní, pokud běžel dostatečně rychle ve všech možných případech. V roce 1967 si Richard Karp povšiml, že standardní algoritmus na řešení určitých problémů toků v sítích má teoretickou díru, která způsobovala, že algoritmus běžel velmi pomalu při určitých vhodně zvolených příkladech. Velmi podobné výsledky jako Richard Karp prezentoval Jack Edmonds z National Bureau of Standards.

Karp a Edmonds začali společně pracovat na teoretické efektivitě algoritmů toků v sítích a publikovali společný článek. Hlavním výsledkem jejich spolupráce bylo posílení některých úvah o výpočetní složitosti. Jack Edmonds využil některých myšlenek spojených s lineárním programováním a vytvořil různé algoritmy pro rozsáhlé třídy kombinatorických problémů. Ve svých článcích vyslovil názor, že algoritmus lze považovat za "dobrý", pokud je čas jeho běhu omezen polynomiální funkcí velikosti vstupu. Proto např. maďarský algoritmus pro řešení svatebního problému lze považovat za dobrý. Naopak všechny algoritmy pro řešení problému obchodního cestujícího vykazují exponenciální růst času a proto je nelze považovat v tomto smyslu za dobré. Edmondsova definice tak určila hranici mezi jednoduchými a složitými kombinatorickými problémy.

Vedle pokroku v oblasti kombinatorických algoritmů se v 60. letech 20. století rozvíjel teoretický směr v oblasti výpočetní složitosti. Základem této teorie byly práce logiků v 30. letech včetně Alana Turinga, které se zabývaly existencí a neexistencí automatických procedur pro rozhodování a dokazatelností tvrzení.

Turing a další teoretici dokázali, že určité dobře definované matematické problémy jsou nerozhodnutelné, tedy že principiálně nemůže existovat algoritmus schopný řešit všechny případy těchto problémů. Příkladem takového problému byl problém zastavení. Vstupem problému zastavení je počítačový program se svými daty, problémem je rozhodnout, zda se program nakonec zastaví. Těžkosti plynou z možnosti neomezeného hledání. Obvyklým řešením je program spustit a čekat na jeho zastavení. Ale kdy je logické se rozhodnout program zastavit uměle? Zdá se, že neexistuje možnost stanovit hranici potřebného množství hledání. S použitím techniky zvané diagonalizace Turing vytvořil důkaz, že neexistuje algoritmus, který může úspěšně řešit všechny případy v problému zastavení.

Postupem doby se nalezly nerozhodnutelné problémy téměř v každé oblasti matematiky. Příkladem z teorie čísel je problém řešení diofantických rovnic. Je-li např. dána rovnice

                     4xy^2 + 2x.y^2.z^3 - 11x^3.y^2.z^2 = - 1164,

existuje nějaké její celočíselné řešení? Problém nalézt obecnou rozhodovací proceduru na řešení diofantických rovnic poprvé předložil David Hilbert v roce 1900 a tento problém je znám jako desátý Hilbertův problém. Problém byl vyřešen až v roce 1971, kdy se dokázalo, že žádná taková rozhodovací procedura nemůže existovat.

Jedním ze základních prostředků při vymezení hranice mezi řešitelnými a neřešitelnými problémy je pojem redukovatelnosti. Problém A je redukovatelný na problém B, pokud za předpokladu, že je znám program na řešení problému B, lze zkonstruovat program na řešení problému A. Například problém zastavení lze redukovat na desátý Hilbertův problém, z čehož plyne, že desátý Hilbertův problém je nerozhodnutelný.

Teorie složitosti zdědila z teorie výpočtů otázku, jaký je rozdíl mezi schopností řešit daný problém a schopností vyzkoušet nějaká řešení. Ikdyž neexistuje žádný obecný postup, jak nalézt řešení diofantické rovnice, lze snadno vyzkoušet navrhované řešení. Například se snadno ověří, že x = 3, y = 2, z = -1 je řešením výše uvedené diofantické rovnice.

Některá odvětví teoretické informatiky mají svůj původ ve formalismech teorie výpočtů. Významným odvětvím je teorie výpočetní složitosti. Místo jednoduché otázky, zda problém je rozhodnutelný, si teorie výpočetní složitosti klade otázku, jak těžké je problém řešit. Teorie složitosti se zabývá schopnostmi univerzálních výpočetních zařízení, pokud jsou dána omezení na dobu výpočtu nebo velikost paměti atd. První náznaky teorie složitosti se objevily v roce 1959 a 1960 v článcích Michaela Rabina, Roberta McNaugtonoa Hidea Yamadi. Teprve článek Jurije Hartmanise a Richarda Stearnse znamenal začátek moderní teorie složitosti. S použitím Turingova stroje jako modelu abstraktního počítače poskytli Hartmanis a Stearns definici "třídy složitosti" složené z problémů řešitelných v počtu kroků omezeném danou funkcí velikosti vstupu n. Adaptací techniky diagonalizace dokázali autoři řadu výsledků o struktuře tříd složitosti.

V této době Richard Karp studoval teorii výpočtů podle knihy Hartleyho Rogerse. Přibližně ve stejné době byl Michael Rabin, který v roce 1976 dostal Turingovu cenu, na návštěvě v IBM Research Laboratory v Yorktown Heights, kde pak vedl diskuse s Richardem Karpem.

V roce 1968 Richard Karp odešel od IBM na University of California v Berkeley. V IBM Richard Karp pracoval s vynikajícími vědci, jako byli Alan Hoffman, Raymond Miller, Arnold Rosenberg a Shmuel Winograd. V Berkeley jeho kolegy byli Michael Harrison, odborník na teorii jazyků, Eugen Lawler, odborník na kombinatorickou optimalizaci, Manuel Blum, zakladatel teorie složitosti a Stephen Cook, jehož práce Karpa ovlivnila později. Na katedře matematiky byl Robert Solovay, známý logik, který objevil významný náhodný algoritmus na testování, zda číslo je prvočíslem, Julius Robinson, který pracoval na desátém Hilbertově problému, Steve Smale, který byl průkopníkem v pravděpodobnostní analýze lineárního programování. Ve Stanfordu pracoval George Dantzig, otec lineárního programování, Donald Knuth, zakladatel oblasti datových struktur a analýzy algoritmů, Robert Tarjan a John Hopcroft.

V roce 1971 Stephen Cook publikoval článek "O složitosti procedur na dokazování teorémů" [On the complexity of theorem-proving procedures]. Cook v této práci analyzoval třídy problémů, které se dnes označují jako P a NP a zavedl pojem, který se dnes označuje jako NP-úplnost. Třída P obsahuje všechny problémy, které lze řešit v polynomiálním čase. Třída NP obsahuje všechny problémy, pro které lze navrhované řešení prověřit v polynomiálním čase. Pokud např. uvažujeme problém obchodního cestujícího, který nepatří do třídy P, pak lze tento problém modifikovat tak, že se zavede číslo T a má se rozhodnout, za existuje cesta kratší nebo rovna T. Taková modifikace problému obchodního cestujícího je problémem třídy NP. Lze ukázat, že zavedením cílového čísla T se všechny kombinatorické problémy dají převést na verze, které leží v třídě NP.

NP je tedy třída, v níž leží kombinatorické problémy. Uvnitř této třídy leží pak třída P těch problémů, které mají efektivní řešení. Základní otázkou je vztah třídy P a třídy NP. Pokud by obě třídy byly sobě rovny, mělo by to úžasné důsledky. Každý problém, pro který lze prověřit nějaké řešení, by byl řešitelný. Kdykoliv by se nalezl krátký důkaz nějaké věty, brzy by se našla uniformní procedura. To by znamenalo, že všechny kombinatorické optimalizační problémy by byly řešitelné v polynomiálním čase. Dosud se však rovnost tříd P a NP neprokázala. Značná část odborníků dnes věří, že žádný takový důkaz neexistuje.

Nejvýznamnějším výsledkem Cookova článku bylo, že třídy P a NP se rovnají právě tehdy, když problém splnitelnosti leží v P. Problém splnitelnosti pochází z matematické logiky a má aplikace v teorii obvodů. Lze ho formulovat jako kombinatorickou hru. Jsou dány posloupnosti malých a velkých písmen. Problémem je, zda lze vybrat z každé posloupnosti písmeno, aniž bychom vybrali také velkou a malou verzi jakéhokoliv písmena. Pokud je posloupnost Abc, Bc, aB, ac, pak lze např. vybrat A z první posloupnosti, B ze druhé a třetí posloupnosti a c ze čtvrté. Stejné písmeno lze vybrat vícekrát, pokud nevybereme současně jeho malou a velkou verzi:

Příkladem, kdy neexistuje možnost výběru jsou posloupnosti AB, Ab, aB a ab. Problém splnitelnosti patří do třídy NP, protože lze snadno ověřit, zda navrhovaný výběr písmen splňuje podmínky výběru. Cook dokázal, že pokud je problém z třídy NP řešitelný v polynomiálním čase, pak třídy P a NP se rovnají.

Cook svůj důkaz založil na pojmu redukovatelnosti. Ukázal, že každý konkrétní případ problému NP lze převést na odpovídající případ problému splnitelnosti. Původní problém má řešení jen tehdy, má-li řešení problém splnitelnosti. Problém splnitelnosti je tedy natolik obecný, že jím lze popsat strukturu jakéhokoliv problému v NP. Pokud bychom uměli řešit problém splnitelnosti v polynomiálním čase, mohli bychom vytvořit algoritmus pro řešení jakéhokoliv problému v NP. Takový algoritmus by obsahoval dvě části: jednou částí by byla polynomiální transformační procedura pro převod problému v NP na problém splnitelnosti a druhou částí by byla procedura pro řešení vlastního problému splnitelnosti.

Richard Karp si uvědomil, že pojem typického kombinatorického problému v Cookově práci byl formalizací myšlenky, která byla dlouho součástí kombinatorické optimalizace. Odborníci v této oblastí vědí, že problém celočíselného programování (tj. problém rozhodnout, zda soustava lineárních nerovnic má celočíselné řešení) je dostatečně obecný k tomu, aby vyjádřil omezení běžně uvažovaných problémů kombinatorické optimalizace.

Richard Karp se proto rozhodl přezkoumat, zda určitá třída kombinatorických problémů, které se považovaly za neřešitelné, je také typická v Cookově smyslu. Tyto problémy Cook označil jako "polynomiálně úplné" (později "NP-úplné"). Problém je NP-úplný, pokud patří do třídy NP a každý problém v NP je na něj polynomiálně redukovatelný. Pokud chceme dokázat, že daný problém v NP je NP-úplný, stačí nalézt jiný NP-úplný problém, který je polynomiálně redukovatelný na daný problém. Pomocí polynomiálních redukcí Karp ukázal, že většina klasických problémů ukládání, pokrývání, porovnávání, rozkládání, propojování a plánování, které vznikají v kombinatorické optimalizaci, jsou NP-úplné Tyto výsledky publikoval v roce 1972 v článku "Redukovatelnost mezi kombinatorickými problémy" [Reducibility among combinatorial problems].

Výsledky týkající se NP-úplnosti dokázané počátkem 70. let 20. století ukázali, že pokud není rovno P a NP, pak většina praktických problémů kombinatorické optimalizace, které se objevují v obchodě, vědě a v technických oblastech, je prakticky neřešitelná. Žádná metoda nemůže obejít kombinatorickou explozi. V praxi lze využít několik přístupů. Často postačuje nalezení dostatečně dobrého, téměř optimálního řešení. Například obchodní cestující se spokojí s cestou, která je jen o několik procent delší, než je cesta optimální. Odborníci proto začali hledat polynomiální algoritmy, které by zaručovaly nalezení téměř optimálních řešení pro NP-úplné problémy kombinatorické optimalizace. Ve většině případů bylo dosaženo horního odhadu poměru ceny řešení daným algoritmem a ceny optimálního řešení.

Velmi zajímavými pracemi o aproximačních algoritmech se zárukou úspěšnosti byly práce o jednorozměrném problému ukládání do poliček. Problém spočívá v ukládání položek různých velikostí do poliček se stejnou kapacitou. Cílem je minimalizovat počet poliček potřebných na uložení za předpokladu, že součet velikostí položek uložených do poličky nesmí překročit její kapacitu. V polovině 70. let 20. století byla publikována řada prací o aproximačních algoritmech, které se týkaly tohoto problému. David Johnson ve své práci analyzoval sestupný algoritmus prvního uložení. Algoritmus uvažuje položky seřazené sestupně podle své velikosti. Položka, která je na řadě, se umístí do první poličky, která je schopna ji přijmout.

Uvažujme např. čtyři poličky s kapacitou 10 a osm předmětů velikostí 8, 7, 6, 5, 3, 3, 2. Pak uložení vypadá následovně:

David Johnson ve své práci ukázal, že tato metoda zaručuje relativní chybu 2/9, tj. počet potřebných poliček bude o 22 % větší, než je počet poliček v optimálním stavu. Několik let se tyto výsledky zlepšovaly a nakonec se ukázalo, že chybu lze zmenšit libovolně, ačkoliv potřebné algoritmy již nejsou tak jednoduché, jako původní Johnsonův algoritmus.

Výzkum v oblasti polynomiálních algoritmů ukázal rozdíly mezi NP-úplnými problémy kombinatorické optimalizace. Pro některé problémy lze relativní chybu zmenšit libovolně. Jiné problémy mají velikost relativní chyby omezenou zdola. Další problémy nemají algoritmy s velikostí relativní chyby omezené shora. Konečně existují problémy, pro které existence polynomiálních aproximačních algoritmů znamená rovnost P a NP.

Teorie kombinatorické optimalizace ukázala, že téměř všechny problémy, které bylo třeba řešit, byly NP-úplné a ve většině případů polynomiální aproximační algoritmy nemohly poskytnout záruku úspěšnosti, aby je bylo možno použít v praxi. Na druhé straně vzniklo mnoho algoritmů, které fungovaly v praxi, ale chybělo pro ně teoretické zdůvodnění. Například Lin a Kernighan, jeden z pozdějších autorů programovacího jazyka C, vymysleli úspěšný algoritmus lokálního zlepšování pro problém obchodního cestujícího. Algoritmus zvolil náhodnou cestu a pak ji zlepšoval přidáváním nebo ubíráním některých spojení, dokud nevytvořil cestu, kterou již nebylo možno lokálně zlepšit. Ve speciálně vytvořených případech algoritmus zcela selhával, ale prakticky poskytoval téměř optimální řešení. Podobná situace nastávala u simplexového algoritmu, který řešil velké problémy lineárního programování.

Vysvětlení fenoménu těchto neexaktních algoritmů vyžadovalo nutně rozchod s tradičními metodami teorie složitosti, které algoritmus hodnotily podle chování na nejhorším možném vstupu. Tradiční analýza nejhoršího vstupu, která byla dominantním směrem této teorie, odpovídala případům vytvořeným nějakým nekonečně inteligentním protivníkem. Takový protivník by měl znát strukturu algoritmu a vybíral by vstupy, které by algoritmus donutily k maximálnímu výkonu. Takový scénář nutně vede k závěru, že algoritmus Lina a Kernighana a simplexový algoritmus jsou zcela chybné. Richard Karp tehdy začal uplatňovat jiný přístup, v němž se předpokládá, že vstupy přicházejí od uživatele a proto mají určité rozumné rozdělení pravděpodobnosti. Takové vstupy se nesnaží algoritmu ani pomáhat, ani škodit.

V roce 1975 Richard Karp začal provádět pravděpodobnostní analýzu kombinatorických algoritmů. Tento směr výzkumu měl své odpůrce, kteří zastávali stanovisko, že neexistuje způsob, jak lze zjistit, jaké vstupy se budou algoritmu předkládat, a proto se musí vycházet z nejhoršího případu. Richard Karp však cítil, že v případě NP-úplných algoritmů záruka nejhoršího případu není možná a že pravděpodobnostní přístup je jediný, na jehož základě lze pochopit, proč heuristické kombinatorické algoritmy v praxi tak dobře fungují.

Pravděpodobnostní analýza začíná předpokladem, že jednotlivé případy problému vznikají podle určitého rozdělení pravděpodobnosti. Například v případě obchodního cestujícího lze očekávat, že rozmístění n míst je určeno rovnoměrným rozdělením nad jednotkovým čtvercem. Pak lze studovat rozdělení pravděpodobnosti délky optimální cesty nebo délky cesty vytvářené určitým algoritmem. V ideálním případě je cílem dokázat, že nějaký jednoduchý algoritmus vytváří optimální nebo téměř optimální řešení s dostatečně vysokou pravděpodobností. Takový výsledek má pochopitelně význam pouze tehdy, když rozdělení pravděpodobnosti jednotlivých případů problému odpovídá reálné situaci v praxi. Případně musí být pravděpodobnostní analýza dostatečně robustní na to, aby byla pravdivá pro širokou třídu rozdělení pravděpodob- nosti.

Jedním z nejvýznamnějších objevů teorie pravděpodobnosti jsou zákony velkých čísel. Zhruba řečeno, tyto zákony ukazují, že kumulativní efekt velkého počtu náhodných jevů lze předvídat s vysokou pravděpodobností i v případě, že jednotlivé jevy lze předpovědět jen s malou pravděpodobností. Proto například lze předvídat, že v sérii mnoha hodů mincí bude přibližně polovina výsledků "rub" a polovina výsledků "líc". Pravděpodobnostní analýza ukázala, že podobným způsobem se chová mnoho algoritmů kombinatorické optimalizace, pokud jejich vstupy mají jednoduché rozdělení pravděpodobnosti. Běh algoritmu se s velkou pravděpodobností bude vyvíjet předvídatelným způsobem a vzniklé řešení bude téměř optimální. Článek Beardwooda, Haltona a Hammersleyho z roku 1960 např. ukázal, že pokud n míst v problému obchodního cestujícího je vybráno z rovnoměrného rozdělení pravděpodobnosti, pak při velkém n je délka optimální cesty skoro jistě rovna absolutní konstantě násobené odmocninou počtu míst.

Lze uvést řadu případů, v nichž jednoduché aproximační algoritmy skoro jistě dávají téměř optimální řešení pro velký počet vstupů s určitým rozdělením pravděpodobnosti.

Jedním z pozoruhodných použití pravděpodobnostní analýzy byla její aplikace na problém lineárního programování. Geometricky se tento problém podobá nalezení vrcholů mnohostěnu, které jsou nejblíže k určité vnější nadrovině, která mnohostěn neprotíná. Algebraicky jde o minimalizaci lineární funkce vzhledem k omezení ve tvaru lineárních nerovnic. Lineární funkce měří vzdálenost k nadrovině a omezení ve tvaru lineárních nerovností odpovídají nadrovinám, které tvoří hranice mnohostěnu.

Simplexový algoritmus pro problém lineárního programování je metodou postupu směrem k vrcholu. Opakovaně se posouvá od vrcholu k sousednímu vrcholu, přičemž se tak stále přibližuje vnější nadrovině. V nejhorším případě počet iterací roste exponenciálně s počtem lineárních nerovností potřebných na popis mnohostěnu. V praxi však je počet iterací jen zřídka vyšší než je trojnásobek nebo čtyřnásobek počtu lineárních nerovností.

Karl-Heinz Borgwart ze Spolkové republiky Německo a Steve Smale z Californské univerzity v Berkeley použili jako první pravděpodobnostní analýzu na vysvětlení úspěšnosti simplexového algoritmu a jeho dalších variant. Jejich analýza vycházela z ohodnocení jistých vícerozměrných integrálů. Jejich kolega z Berkeley Ilan Adler navrhl postup, který sliboval provedení pravděpodobnostní analýzy v podstatě bez výpočtů. Metoda byla založena na použití určitých principů symetrie a na provedení požadovaného průměrování.

V roce 1983 Richard Karp, Ilan Adler a Ron Shamir ukázali, že při rozumně široké množině pravděpodobnostních předpokladů roste očekávaný počet iterací vykonávaný určitou verzí simplexového algoritmu s druhou mocninou počtu lineárních nerovností. Stejný výsledek získal Michael Todd použitím vícerozměrných integrálů.

Richard Karp se pravděpodobnostní analýze kombinatorických optimalizačních algoritmů věnoval více než deset let. V roce 1975 bylo ještě velmi málo příkladů takové analýzy. V 80. letech 20.století jsou kombinatorické optimalizaci věnovány stovky článků a všechny klasické problémy kombinatorické optimalizace byly podrobeny pravděpodobnostní analýze. Výzkum v této oblasti je však omezen použitými technikami analýzy. Velká část zajímavých a úspěšných algoritmů stojí stále mimo rámec možností. Návrh praktických algoritmů má blíže k umění, než k vědě.

Systematické studium náhodných algoritmů začalo kolem roku 1976, ikdyž náhodné algoritmy se používaly od počátků vývoje výpočetní techniky. Zájem o studium náhodných algoritmů byl podmíněn překvapivou efektivností algoritmů na testování, zda číslo n je prvočíslo. Jeden z těchto algoritmů navrhli Robert Solovay a Volker Strassen a druhý navrhl Michael Rabin. Následný článek Michaela Rabina obsahoval další příklady a motivaci pro systematické studium náhodných algoritmů. Doktorská práce Johna Gilla pod vedením Manuela Bluma položila základy obecné teorie náhodných algoritmů.

Konkrétním příkladem náhodného algoritmu je algoritmus porovnávání vzoru, který vymysleli Michael Rabin a Richard Karp v roce 1980. Algoritmus porovnání vzoru je základním problémem při zpracování textu. Je dán n-bitový řetězec označovaný jako vzor a mnohem delší řetězec bitů označovaný jako text. Problémem je určit, zda se vzor nachází jako souvislý blok v textu. Metoda hrubé síly spočívá v porovnávání vzoru s každým n-bitovým blokem textu metodou posuvného n-bitového okna. V nejhorším případě je doba výpočtu rovna součinu délky vzoru a délky textu. Ve většině aplikací je taková metoda nepřijatelná, pokud vzor není velmi krátký. Rabinova a Karpova metoda tyto těžkosti odstraňuje jednoduchým trikem. Definuje se "otisková" funkce, která přiřadí každému řetězci n bitů mnohem kratší řetězec, nazývaný otisk. Tato funkce se definuje tak, aby bylo možno rychle určit otisk každého bloku délky n bitů. Potom místo porovnávání každého vzoru s každým takovým blokem textu se porovnává otisk vzoru s otiskem každého takového bloku. Pokud se otisk vzoru liší od otisku každého bloku, víme, že se vzor jako blok nenachází v textu.

Metoda porovnávání krátkých otisků místo dlouhých řetězců podstatně redukuje dobu výpočtu, ale obsahuje možnost chybných porovnání, pokud blok textu má stejný otisk jako vzor, ačkoliv vzor a blok textu nejsou shodné. Chybná porovnání představují závažný problém. Pro každou volbu otiskové funkce lze vytvořit takový příklad vzoru a textu, že chybné porovnání se objeví v každé pozici textu. Proto musí existovat ještě nějaká záložní metoda, která ochrání algoritmus proti chybným porovnáním.

Výhody této metody lze obnovit pomocí náhodnosti. Místo používání jediné otiskové funkce má náhodná metoda k dispozici velkou skupinu různých snadno vypočítatelných otiskových funkcí. Při zadání problému složeného ze vzoru a textu algoritmus vybere náhodně otiskovou funkci a použije ji pak pro porovnání vzoru a textu. Protože otisková funkce není dopředu známa, nelze vytvořit dopředu takový případ problému, který by vedl k chybným porovnáním. Pravděpodobnost chybného porovnání bez ohledu na výběr vzoru a textu je pak velmi malá. Například při vzoru 250 bitů dlouhém a textu dlouhém 4000 bitů lze pracovat s 32 funkcemi a pravděpodobnost chybného porovnání bude menší než tisícina.

Náhodné algoritmy však dosud neprokázaly svoji efektivnost v boji proti kombinatorické explozi NP-úplných problémů. Proto se budou zřejmě nadále používat jak náhodné tak nenáhodné algoritmy.

Literatura:

[1] Karp, Richard M.: Kombinatorika, zložitosť a náhodnosť. Pokroky matematiky, fyziky a astronomie, ročník 34 (1989), č.6, Academia, nakladatelství ČSAV překlad: Milan Ftáčnik, z angl. orig.: Karp, Richard M.: Combinatorics, Complexity and Randomness. Communication of the ACM, February 1986, Vol. 29, No 2.

(c) 1997 Intellectronics

časopis o přírodě, vědě a civilizaci