Eksplozja kombinatoryczna - Combinatorial explosion

W matematyce , o kombinatorycznej eksplozji jest gwałtowny wzrost złożoności problemu ze względu na to, jak kombinatoryki problemu jest dotknięte wejściowych, ograniczeń i granic problemu. Eksplozja kombinatoryczna jest czasami używana do uzasadnienia nierozwiązywalności pewnych problemów. Przykładami takich problemów są pewne funkcje matematyczne , analiza niektórych łamigłówek i gier oraz niektóre patologiczne przykłady, które można modelować jako funkcję Ackermanna .

Przykłady

kwadraty łacińskie

Kwadratu łacińskiego porządku n jest n  x  n tablicę z wpisów ze zbioru n elementów o tej własności, że każdy element zestawu występuje tylko raz w każdym rzędzie i każdej kolumnie tablicy. Przykład kwadratu łacińskiego rzędu trzeciego podaje:

1 2 3
2 3 1
3 1 2

Typowym przykładem kwadratu łacińskiego byłaby ukończona łamigłówka Sudoku . Kwadrat łaciński to obiekt kombinatoryczny (w przeciwieństwie do obiektu algebraicznego), ponieważ liczy się tylko układ wpisów, a nie to, jakie hasła faktycznie są. Liczba kwadratów łacińskich jako funkcja kolejności (niezależnie od zbioru, z którego pochodzą hasła) (sekwencja A002860 w OEIS ) stanowi przykład eksplozji kombinatorycznej, co ilustruje poniższa tabela.

n Liczba kwadratów łacińskich rzę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 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

Kombinatoryczna eksplozja może również wystąpić w niektórych łamigłówkach rozgrywanych na siatce, takich jak Sudoku. Sudoku to rodzaj kwadratu łacińskiego z dodatkową właściwością, że każdy element występuje dokładnie raz w podsekcjach o rozmiarze n  ×  n (zwanych polami ). Eksplozja kombinatoryczna występuje wraz ze wzrostem n , tworząc granice właściwości Sudoku, które można konstruować, analizować i rozwiązywać, jak pokazano w poniższej tabeli.

n Liczba siatek Sudoku rzędu n
(pudełka mają rozmiar n × n )
Liczba kwadratów łacińskich rzędu n
(dla porównania)
1 1  1
4 288 576
9 6 670 903 752 021 072 936 960 5 524 751 496 156 892 842 531 225 600
16 5,96 × 10 98 ( szacowany )
25 4,36 × 10 308 ( szacowany )
( n = 9 to powszechnie grane Sudoku 9 × 9. Układanka nie zawiera siatek, w których n jest niewymierne .)

Gry

Jednym z przykładów w grze, w której kombinatoryczna złożoność prowadzi do granicy rozwiązania, jest rozwiązywanie szachów (gra z 64 kwadratami i 32 pionkami). Szachy nie są grą rozwiązaną . W 2005 roku rozwiązano wszystkie zakończenia partii szachów z sześcioma lub mniej bierkami, pokazując wynik na każdej pozycji, jeśli gra się perfekcyjnie. Skompletowanie podstawy stołu zajęło jeszcze dziesięć lat, dodając jeszcze jedną figurę szachową, tworząc w ten sposób 7-częściową podstawę. Dodanie jeszcze jednego kawałka do szachowego zakończenia (a tym samym stworzenie 8-częściowej podstawy stołu) jest uważane za niewykonalne ze względu na dodatkową kombinatoryczną złożoność.

Co więcej, perspektywa rozwiązywania większych gier podobnych do szachów staje się trudniejsza, gdy zwiększa się rozmiar planszy, na przykład w dużych wariantach szachowych i szachach nieskończonych .

Przetwarzanie danych

Eksplozja kombinatoryczna może wystąpić w środowiskach obliczeniowych w sposób analogiczny do komunikacji i przestrzeni wielowymiarowej . Wyobraź sobie prosty system z tylko jedną zmienną, boolean o nazwie A . System ma dwa możliwe stany, A = prawda lub A = fałsz. Dodanie kolejnej zmiennej logicznej B da systemowi cztery możliwe stany: A = prawda i B = prawda, A = prawda i B = fałsz, A = fałsz i B = prawda, A = fałsz i B = fałsz. System z n wartościami boolowskimi ma 2 n możliwych stanów, podczas gdy system n zmiennych, z których każda ma Z dozwolonych wartości (a nie tylko 2 (prawda i fałsz) wartości logicznych) będzie miał Z n możliwych stanów.

Możliwe stany można traktować jako węzły liści drzewa o wysokości n , gdzie każdy węzeł ma Z dzieci. Ten szybki wzrost węzłów liści może być przydatny w obszarach takich jak wyszukiwanie , ponieważ wiele wyników można uzyskać bez konieczności schodzenia bardzo daleko. Może również stanowić przeszkodę podczas manipulowania takimi konstrukcjami.

Hierarchii klas w języku obiektowym można traktować jak drzewo, z różnymi rodzajami obiektu dziedziczy od rodziców. Jeśli trzeba połączyć różne klasy, na przykład w porównaniu (jak A  <  B ), liczba możliwych kombinacji, które mogą wystąpić, eksploduje. Jeśli każdy rodzaj porównania musi być zaprogramowany, to wkrótce staje się to niewykonalne dla nawet małej liczby klas. Dziedziczenie wielokrotne może rozwiązać ten problem, pozwalając podklasom mieć wielu rodziców, a zatem można rozważyć kilka klas nadrzędnych, a nie każde dziecko, bez naruszania istniejącej hierarchii.

Przykładem jest taksonomia, w której różne warzywa dziedziczą po swoich przodkach. Próba porównania smakowitości każdego warzywa z innymi staje się niewykonalna, ponieważ hierarchia zawiera tylko informacje o genetyce i nie wspomina o smaku. Jednak zamiast pisać porównania dla marchewki / marchewki, marchwi / ziemniaka, marchewki / kiełków, ziemniaków / ziemniaków, ziemniaków / kiełków, kiełków / kiełków, wszystkie mogą pomnożyć dziedziczenie z oddzielnej klasy smacznych, zachowując ich obecnego przodka- opartej na hierarchii, to wszystkie powyższe mogą być zaimplementowane tylko za pomocą smacznego/smacznego porównania.

Arytmetyka

Załóżmy, że bierzemy silni z n :

Wtedy 1! = 1, 2! = 2, 3! = 6 i 4! = 24. Szybko jednak dochodzimy do bardzo dużych liczb, nawet dla stosunkowo małych n . Na przykład 100! ≈9.332 621 54 × 10 157 , liczba tak duża, że ​​nie można jej wyświetlić na większości kalkulatorów, i znacznie większa niż szacowana liczba fundamentalnych cząstek we wszechświecie.


Komunikacja

Korzystając z oddzielnych linii komunikacji, cztery organizacje potrzebują sześciu kanałów
Korzystając z pośrednika, wymagany jest tylko jeden kanał na organizację

W przypadku podawania i przetwarzania , A kombinatorycznej eksplozji jest szybko przyspiesza wzrost linii komunikacyjnych organizacji dodaje się w procesie. (Ten wzrost jest często opisywany jako „wykładniczy”, ale w rzeczywistości jest wielomianowy ).

Jeśli dwie organizacje muszą komunikować się na określony temat, najłatwiej jest komunikować się bezpośrednio w sposób doraźny — wymagany jest tylko jeden kanał komunikacji . Jeśli jednak zostanie dodana trzecia organizacja, wymagane są trzy oddzielne kanały. Dodanie czwartej organizacji wymaga sześciu kanałów; pięć dziesięć; Sześć piętnaście; itp.

Na ogół, potrzeba linie komunikacyjne dla n organizacji, która jest po prostu liczbą 2- kombinacji z n elementów (patrz Binomial współczynnik ).

Alternatywnym podejściem jest uświadomienie sobie, kiedy taka komunikacja nie będzie jednorazowym wymogiem, i stworzenie ogólnego lub pośredniego sposobu przekazywania informacji. Wadą jest to, że wymaga to więcej pracy dla pierwszej pary, ponieważ każda musi zmienić swoje wewnętrzne podejście na wspólne, zamiast pozornie łatwiejszego podejścia polegającego na zrozumieniu drugiej.

Zobacz też

Bibliografia