Kombinatorický výbuch

Kombinatorická exploze je termín používaný k popisu efektu prudkého ("výbušného") zvýšení časové složitosti algoritmu se zvětšením velikosti vstupních dat problému [1] .

Přesněji to znamená, že uvažovaný algoritmus není polynomiální, to znamená, že čas na vyřešení problému není omezen žádným polynomem v délce vstupu. Tyto problémy mají obvykle exponenciální nebo dokonce superexponenciální složitost.

Původ názvu je dán tím, že nelze najít jiný způsob, jak problém vyřešit. , kromě kompletního výčtu všech možných možností. V tomto případě je čas potřebný k řešení úměrný počtu všech možných konfigurací, který je určen z určitých kombinatorických úvah (kombinace, permutace).

K obejití problému kombinatorické exploze se hledají speciální metody řešení, zejména se používají heuristické algoritmy .

Příklady

Kombinatorická exploze se vyskytuje v mnoha úlohách hledání [2] , v úlohách sekvenčního výpočtu řešených metodami hrubé síly . [3] [4]

Problém cestujícího obchodníka

V klasickém problému obchodního cestujícího je potřeba najít optimální sled návštěv měst obchodním cestujícím. Jediný přesný způsob, jak problém vyřešit, je projít všechny možné trasy a vybrat si tu, která zabere nejméně času. Složitost řešení problému obchodního cestujícího se tedy ukazuje jako úměrná počtu všech možných sekvencí měst, který je dán permutačním vzorcem:

Šachy

Takže je například hypoteticky možné spočítat všechny možnosti tahů v deskové hře šachy od začátku partie do konce úplným výčtem všech kombinací. V současnosti a v blízké budoucnosti [2] je však řešení takového problému prakticky nemožné. Například u počítače schopného vypočítat milion herních kombinací za sekundu s eliminací zjevně neoptimálních větví bude výpočet 6 tahů dopředu trvat 1 sekundu, 11 dní pro 12 tahů a asi 32 000 let pro 18 tahů. [2]

Poznámky

  1. ↑ Webový slovník kybernetiky a systémů . Datum zpřístupnění: 29. května 2010. Archivováno z originálu 6. srpna 2010.
  2. ↑ 1 2 3 Slovník výpočetní techniky . Datum přístupu: 29. května 2010. Archivováno z originálu 8. června 2013.
  3. ↑ Články o umělé inteligenci . Získáno 29. května 2010. Archivováno z originálu dne 23. srpna 2011.
  4. ↑ Denys Duchier, Claire Gardent a Joachim Niehren. Souběžné programování s omezením v zemi Oz pro zpracování přirozeného jazyka . Datum přístupu: 29. května 2010. Archivováno z originálu 12. srpna 2011.