Kombinatorická exploze - Combinatorial explosion
V matematice je kombinatorická exploze rychlý růst složitosti problému v důsledku toho, jak je kombinatorika problému ovlivněna vstupem, omezeními a hranicemi problému. K ospravedlnění neřešitelnosti určitých problémů se někdy používá kombinatorický výbuch. Mezi příklady takových problémů patří určité matematické funkce , analýza některých hádanek a her a některé patologické příklady, které lze modelovat jako Ackermannovu funkci .
Příklady
Latinské čtverce
Latinské čtverce řádu n je n x n pole položkami z množiny n prvků s vlastností, že každý prvek z množiny vyskytuje právě jednou v každém řádku a každém sloupci matice. Příklad latinského čtverce řádu tři uvádí:
1 2 3 2 3 1 3 1 2
Běžným příkladem latinského čtverce by byla dokončená sudoku . Latinský čtverec je kombinatorický objekt (na rozdíl od algebraického objektu), protože záleží pouze na uspořádání záznamů a ne na tom, jaké záznamy ve skutečnosti jsou. Počet latinských čtverců jako funkce pořadí (nezávislý na sadě, ze které jsou položky čerpány) (sekvence A002860 v OEIS ) poskytuje příklad kombinatorické exploze, jak ukazuje následující tabulka.
| n | Počet latinských čtverců řádu 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 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 |
Sudoku
Kombinatorický výbuch může také nastat v některých hádankách hraných na mřížce, jako je sudoku. Sudoku je druh latinského čtverce s další vlastností, že každý prvek se vyskytuje přesně jednou v dílčích částech velikosti √ n × √ n (nazývaných rámečky ). Ke kombinačnímu výbuchu dochází, když se zvyšuje n , což vytváří limity vlastností Sudokus, které lze konstruovat, analyzovat a řešit, jak ukazuje následující tabulka.
| n | Počet mřížek sudoku řádu n (krabice mají velikost √ n × √ n ) |
Počet latinských čtverců řádu n (pro srovnání) |
|---|---|---|
| 1 | 1 | 1 |
| 4 | 288 | 576 |
| 9 | 6 670 903 752 021 072 936 960 | 5 524 751 496 156 892 842 531 225 225 600 |
| 16 | 5,96 × 10 98 ( odhad ) | - |
| 25 | 4,36 × 10 308 ( odhad ) | - |
| ( n = 9 je běžně používané sudoku 9 × 9. Puzzle neobsahuje mřížky, kde √ n je iracionální .) | ||
Hry
Jeden příklad ve hře, kde kombinatorická složitost vede k limitu řešitelnosti, je řešení šachů (hra se 64 políčky a 32 figurkami). Šachy nejsou vyřešenou hrou . V roce 2005 byly vyřešeny všechny šachové partie se šesti a méně figurami, které ukazovaly výsledek každé pozice, pokud byly odehrány perfektně. Trvalo dalších deset let, než byla dokončena základní deska s přidanou další šachovou figurkou, čímž byla dokončena 7dílná základní deska. Přidání dalšího kusu na šachovou koncovku (tedy vytvoření 8dílného stolu) je považováno za neřešitelné kvůli přidané kombinatorické složitosti.
Kromě toho se vyhlídka na řešení větších šachových her stává obtížnější, protože se zvětšuje velikost desky, například ve velkých šachových variantách , a nekonečné šachy .
Výpočetní
Ke kombinatorické explozi může ve výpočetním prostředí dojít způsobem analogickým komunikacím a vícerozměrnému prostoru . Představte si, že jednoduchý systém s jedinou proměnnou, je logickou zvané . Systém má dva možné stavy, A = true nebo A = false. Přidání další booleovské proměnné B poskytne systému čtyři možné stavy: A = true a B = true, A = true a B = false, A = false a B = true, A = false a B = false. Systém s n booleány má 2 n možných stavů, zatímco systém n proměnných, z nichž každá má povolené hodnoty Z (spíše než jen 2 (pravdivé a nepravdivé) booleů), bude mít Z n možných stavů.
Možné stavy si lze představit jako listové uzly stromu o výšce n , kde každý uzel má Z potomků. Tento rychlý nárůst listových uzlů může být užitečný v oblastech, jako je vyhledávání , protože k mnoha výsledkům lze přistupovat, aniž byste museli sestupovat příliš daleko. Může to být také překážkou při manipulaci s takovými strukturami.
Hierarchie tříd v objektově orientovaném jazyce, si lze představit jako strom, s různými typy objektů dědí od svých rodičů. Pokud je třeba kombinovat různé třídy, například při porovnávání (jako A < B ), počet možných kombinací, které mohou nastat, exploduje. Pokud je třeba naprogramovat každý typ srovnání, pak se to brzy stane neřešitelným i pro malý počet tříd. Vícenásobná dědičnost to může vyřešit tím, že umožní podtřídám mít více rodičů, a proto lze uvažovat o několika rodičovských třídách než o každém dítěti, aniž by došlo k narušení jakékoli stávající hierarchie.
Příkladem je taxonomie, kde různé druhy zeleniny dědí po svých předchůdcích. Pokus o srovnání chuti každé zeleniny s ostatními se stává neřešitelným, protože hierarchie obsahuje pouze informace o genetice a nezmiňuje chuť. Místo toho, aby museli psát srovnání pro mrkev/mrkev, mrkev/brambor, mrkev/výhonek, brambor/brambor, brambor/výhonek, výhonek/výhonek, mohou se všichni množit a dědí z oddělené třídy chutných, přičemž si zachovají svého současného předka- založenou na hierarchii, pak lze všechny výše uvedené implementovat pouze s chutným/chutným porovnáním.
Aritmetický
Předpokládejme, že bereme faktoriál o n :
Pak 1! = 1, 2! = 2, 3! = 6 a 4! = 24. Rychle se však dostáváme k extrémně velkým číslům, a to i pro relativně malá n . Například 100! ≈9,332 621 54 × 10 157 , číslo tak velké, že jej nelze zobrazit na většině kalkulaček, a výrazně větší než odhadovaný počet základních částic ve vesmíru.
Sdělení
V administrativě a výpočetní technice je kombinatorická exploze rychle se zrychlujícím nárůstem komunikačních linek, jak jsou organizace přidávány do procesu. (Tento růst je často náhodně popisován jako „exponenciální“, ale ve skutečnosti je polynomický .)
Pokud dvě organizace potřebují komunikovat o konkrétním tématu, může být nejjednodušší komunikovat přímo ad hoc - stačí pouze jeden komunikační kanál . Pokud je však přidána třetí organizace, jsou vyžadovány tři samostatné kanály. Přidání čtvrté organizace vyžaduje šest kanálů; pět deset; šest patnáct; atd.
Obecně platí, že bude trvat komunikační linky pro n organizace, které je právě počet 2- kombinací z n prvků (viz také Binomické koeficient ).
Alternativním přístupem je uvědomit si, kdy tato komunikace nebude jednorázovým požadavkem, a vytvořit obecný nebo střední způsob předávání informací. Nevýhodou je, že to vyžaduje více práce pro první dvojici, protože každý musí převést svůj vnitřní přístup na společný, spíše než povrchně jednodušší přístup pouhého porozumění druhému.