Комбинаторный взрыв - Combinatorial explosion

В математике , А комбинаторный взрыв является быстрым ростом сложности проблемы из - за того , каким образом комбинаторики этой проблемы зависят от входных, ограничения и пределов этой проблемы. Комбинаторный взрыв иногда используется для оправдания неразрешимости определенных проблем. Примеры таких проблем включают определенные математические функции , анализ некоторых головоломок и игр, а также некоторые патологические примеры, которые можно смоделировать как функцию Аккермана .

Примеры

Латинские квадраты

Латинский квадрат порядка $п$ является $п \times п$ массива с элементами из множества $п$ элементов , обладающего свойством , что каждый элемент множества встречается ровно один раз в каждой строке и в каждом столбце массива. Пример латинского квадрата третьего порядка дается следующим образом:

1	2	3
2	3	1
3	1	2

Типичным примером латинского квадрата является завершенная головоломка судоку . Латинский квадрат - это комбинаторный объект (в отличие от алгебраического объекта), поскольку имеет значение только расположение записей, а не то, что они на самом деле представляют. Количество латинских квадратов как функция порядка (независимо от набора, из которого взяты записи) (последовательность A002860 в OEIS ) представляет собой пример комбинаторного взрыва, как показано в следующей таблице.

$п$	Количество латинских квадратов порядка $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

Судоку

Комбинаторный взрыв может также произойти в некоторых головоломках, разыгрываемых на сетке, таких как судоку. Судоку - это тип латинского квадрата с дополнительным свойством, что каждый элемент встречается ровно один раз в подразделах размера $\sqrt n \times \sqrt n$ (называемых блоками ). Комбинаторный взрыв происходит по мере увеличения $n$ , создавая пределы свойств судоку, которые могут быть построены, проанализированы и решены, как показано в следующей таблице.

$п$	Количество сеток судоку порядка $n$ (размер ящиков $\sqrt n \times \sqrt n$ )	Количество латинских квадратов порядка $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,600
16	5,96 × 10 ⁹⁸ ( оценка )	-
25	4,36 × 10 ³⁰⁸ ( оценка )	-
( $n$ = 9 - это судоку размером 9 × 9, в который обычно играют. Головоломка не включает сетки, в которых $\sqrt n$ является иррациональным .)

Игры

Одним из примеров игры, в которой комбинаторная сложность приводит к пределу разрешимости, является решение шахмат (игра с 64 клетками и 32 фигурами). Шахматы - это не решаемая игра . В 2005 году все концовки шахматной партии с шестью или менее фигурами были решены с указанием результата каждой позиции при безупречной игре. Потребовалось еще десять лет, чтобы завершить основание стола, добавив еще одну шахматную фигуру, таким образом завершив основание стола из 7 частей. Добавление еще одной фигуры к шахматной концовке (таким образом, создавая основу стола из 8 фигур) считается неразрешимым из-за дополнительной комбинаторной сложности.

Кроме того, перспектива решения более крупных шахматных игр становится более трудной по мере увеличения размера доски, например, в больших шахматных вариантах и бесконечных шахматах .

Вычисление

Комбинаторный взрыв может происходить в вычислительной среде аналогично коммуникациям и многомерному пространству . Представьте себе простую систему только один переменные, логическое значение называется . Система имеет два возможных состояния: A = true или A = false. Добавление еще одной логической переменной B даст системе четыре возможных состояния: A = true и B = true, A = true и B = false, A = false и B = true, A = false и B = false. Система с n логическими значениями имеет 2 ⁿ возможных состояний, в то время как система из n переменных, каждая из которых имеет Z разрешенных значений (а не только 2 (истина и ложь) логических значений), будет иметь Z ⁿ возможных состояний.

Возможные состояния можно рассматривать как листовые узлы дерева высотой n , где каждый узел имеет Z дочерних элементов . Это быстрое увеличение количества листовых узлов может быть полезно в таких областях, как поиск , поскольку многие результаты могут быть доступны без необходимости спускаться очень далеко. Также это может быть помехой при манипуляциях с такими конструкциями.

Иерархию классов в объектно-ориентированном языке можно рассматривать как дерево, с различными типами объекта наследования от своих родителей. Если необходимо объединить разные классы, например, при сравнении (например, A < B ), то количество возможных комбинаций, которые могут возникнуть, резко возрастает. Если нужно запрограммировать каждый тип сравнения, то это скоро станет непреодолимым даже для небольшого числа классов. Множественное наследование может решить эту проблему, позволяя подклассам иметь несколько родителей, и, таким образом, можно рассматривать несколько родительских классов, а не каждый дочерний элемент, без нарушения какой-либо существующей иерархии.

Примером может служить таксономия, в которой разные овощи унаследованы от своих предков. Попытка сравнить вкус каждого овоща с другими становится непреодолимой, поскольку иерархия содержит только информацию о генетике и не упоминает о вкусе. Однако вместо того, чтобы писать сравнения для моркови / моркови, моркови / картофеля, моркови / ростков, картофеля / картофеля, картофеля / ростков, ростков / ростков, все они могут наследоваться от отдельного класса вкусностей, сохраняя при этом своего текущего предка. основанная на иерархии, то все вышеперечисленное может быть реализовано только путем сравнения «вкусно» и «вкусно».

Арифметика

Предположим, мы берем факториал числа n :

${\ Displaystyle п! = п \ cdot (п-1) \ cdot \ ldots \ cdot 2 \ cdot 1}$

Тогда 1! = 1, 2! = 2, 3! = 6 и 4! = 24. Однако мы быстро приходим к очень большим числам даже для относительно малых n . Например, 100! ≈9,332 621 54 × 10 ¹⁵⁷ , число настолько велико, что его невозможно отобразить на большинстве калькуляторов, и намного больше, чем предполагаемое количество элементарных частиц во Вселенной.

Коммуникация

Используя отдельные линии связи, четыре организации нуждаются в шести каналах

При использовании посредника требуется только один канал на организацию.

В администрации и вычислительной технике , А комбинаторный взрыв является быстрым ускорением увеличения линий связи при добавлении организации в процессе. (Этот рост часто называют «экспоненциальным», но на самом деле он полиномиальный .)

Если двум организациям необходимо обмениваться информацией по определенной теме, проще всего будет общаться напрямую в специальной манере - требуется только один канал связи . Однако при добавлении третьей организации потребуются три отдельных канала. Для добавления четвертой организации требуется шесть каналов; пять десять; шесть пятнадцать; и т.п.

В общем, это потребует линий связи для n организаций, что представляет собой просто количество 2-х комбинаций из n элементов (см. Также Биномиальный коэффициент ). ${\ displaystyle l = {\ frac {n (n-1)} {2}} = {n \ select 2}}$

Альтернативный подход состоит в том, чтобы понять, когда это общение не будет одноразовым требованием, и создать общий или промежуточный способ передачи информации. Недостатком является то, что это требует большей работы для первой пары, поскольку каждая из них должна преобразовать свой внутренний подход в общий, а не на более простой подход, заключающийся в простом понимании друг друга.

Languages

In other projects