Kombinatorická exploze

Z Wikipedie, otevřené encyklopedie
Skočit na navigaci Skočit na vyhledávání

Kombinatorická exploze je v matematice neformální označení jevu, kdy složitost daného problému silně vzrůstá spolu s tím, jak se vzhledem k rostoucímu vstupu velice rychle rozšiřuje kombinatorické jádro problému, typicky počet kombinací, které by mohly být řešením.

Příklady[editovat | editovat zdroj]

Počet latinských čtverců[editovat | editovat zdroj]

Latinský čtverec je čtvercová síť , do které jsou vepsána přirozená čísla od 1 do takovým způsobem, že každé číslo je v každém řádku i sloupci právě jednou. Počet různých latinských čtverců pro rostoucí roste velice rychle:

n Počet latinských čtverců velikosti n
1 1
2 2
3 12
4 576
5 161 280
6 812 851 200
7 61 479 419 904 000
8 108 776 032 459 082 956 800
9 5 524 751 496 156 892 842 531 225 600
10 9 982 437 658 213 039 871 725 064 756 920 320 000
11 776 966 836 171 770 144 107 444 346 734 230 682 311 065 600 000

Šachy[editovat | editovat zdroj]

Šachy nejsou vyřešená hra, tedy není známá optimální strategie ani pro jednoho hráče, která by zaručeně vedla k vítězství. Problémem je právě velikost stavového prostoru. V roce 2005 se povedlo dopočítat všechny koncovky s nejvýše šesti kameny, dalších deset let trvalo, než se podařilo dopočítat všechny koncovky s nejvýše sedmi kameny a výsledná databáze má velikost 140 terabajtů.

Reference[editovat | editovat zdroj]

V tomto článku byl použit překlad textu z článku Combinatorial explosion na anglické Wikipedii.