Cesko.wiki Kombinatorická exploze
Technology
12 hours ago
8
4
2
Author
Albert FloresKombinatorická 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
Počet latinských čtverců
Latinský čtverec je čtvercová síť n \times n, do které jsou vepsána přirozená čísla od 1 do n 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í n roste velice rychle:
| n | right| Počet latinských čtverců velikosti n |
|---|---|
| right| 1 | right| 1 |
| right| 2 | right| 2 |
| right| 3 | right| 12 |
| right| 4 | right| 576 |
| right| 5 | right| 161 280 |
| right| 6 | right| 812 851 200 |
| right| 7 | right| 61 479 419 904 000 |
| right| 8 | right| 108 776 032 459 082 956 800 |
| right| 9 | right| 5 524 751 496 156 892 842 531 225 600 |
| right| 10 | right| 9 982 437 658 213 039 871 725 064 756 920 320 000 |
| right| 11 | right| 776 966 836 171 770 144 107 444 346 734 230 682 311 065 600 000 |
Šachy
Š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. +more 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ů.