В математике комбинаторный взрыв — это быстрый рост сложности проблемы из-за того, как ее комбинаторика зависит от входных данных, ограничений и границ. Комбинаторный взрыв иногда используется для оправдания неразрешимости определенных проблем. [1] [2] Примерами таких проблем являются определенные математические функции , анализ некоторых головоломок и игр, а также некоторые патологические примеры, которые можно смоделировать как функцию Аккермана .
Латинский квадрат порядка n — это массив n × n с записями из набора из n элементов, обладающий тем свойством, что каждый элемент набора встречается ровно один раз в каждой строке и каждом столбце массива. Пример латинского квадрата порядка три дается как,
Типичным примером латинского квадрата может служить завершенная головоломка судоку . [3] Латинский квадрат является комбинаторным объектом (в отличие от алгебраического объекта), поскольку имеет значение только расположение записей, а не то, что это за записи на самом деле. Количество латинских квадратов как функция порядка (независимо от набора, из которого взяты записи) (последовательность A002860 в OEIS ) дает пример комбинаторного взрыва, как показано в следующей таблице.
Комбинаторный взрыв может также произойти в некоторых головоломках, разыгрываемых на сетке, таких как судоку. [2] Судоку — это тип латинского квадрата с дополнительным свойством, что каждый элемент встречается ровно один раз в подсекциях размером √ n × √ n (называемых ящиками ). Комбинаторный взрыв происходит по мере увеличения n , создавая ограничения на свойства судоку, которые можно построить, проанализировать и решить, как показано в следующей таблице.
Одним из примеров игры, где комбинаторная сложность приводит к пределу разрешимости, является решение шахмат (игры с 64 клетками и 32 фигурами). Шахматы не являются решенной игрой . В 2005 году были решены все окончания шахматных игр с шестью или менее фигурами, показывающие результат каждой позиции при идеальной игре. Потребовалось еще десять лет, чтобы завершить базу таблицы с добавлением еще одной шахматной фигуры, таким образом завершив базу таблицы из 7 фигур. Добавление еще одной фигуры к шахматному окончанию (таким образом создавая базу таблицы из 8 фигур) считается неразрешимым из-за добавленной комбинаторной сложности. [6] [7]
Более того, перспектива решения более крупных шахматных игр становится более сложной по мере увеличения размера доски, например, в больших шахматных вариантах и бесконечных шахматах . [8]
Комбинаторный взрыв может произойти в вычислительных средах аналогично коммуникациям и многомерному пространству . Представьте себе простую систему с одной переменной, булевой переменной с именем A. У системы есть два возможных состояния: A = true или A = false. Добавление еще одной булевой переменной B даст системе четыре возможных состояния: A = true и B = true, A = true и B = false, A = false и B = true, A = false и B = false. Система с n булевыми значениями имеет 2 n возможных состояний, в то время как система из n переменных, каждая из которых имеет Z допустимых значений (а не просто 2 (true и false) булевых значений), будет иметь Z n возможных состояний.
Возможные состояния можно рассматривать как конечные узлы дерева высотой n , где каждый узел имеет Z потомков. Такое быстрое увеличение конечных узлов может быть полезным в таких областях, как поиск , поскольку многие результаты могут быть доступны без необходимости спускаться слишком далеко. Это также может быть помехой при манипулировании такими структурами.
Иерархию классов в объектно-ориентированном языке можно представить как дерево, в котором различные типы объектов наследуются от своих родителей. Если необходимо объединить различные классы, например, при сравнении (например, A < B ), то количество возможных комбинаций, которые могут возникнуть, резко возрастает. Если каждый тип сравнения необходимо запрограммировать, то это вскоре становится неразрешимым даже для небольшого количества классов. Множественное наследование может решить эту проблему, позволяя подклассам иметь несколько родителей, и, таким образом, можно рассматривать несколько родительских классов, а не каждого потомка, не нарушая при этом существующую иерархию.
Примером может служить таксономия, в которой различные овощи наследуют от своих предковых видов. Попытка сравнить вкусовые качества каждого овоща с другими становится неразрешимой, поскольку иерархия содержит только информацию о генетике и не упоминает вкусовые качества. Однако вместо того, чтобы писать сравнения для морковь/морковь, морковь/картофель, морковь/росток, картофель/картофель, картофель/росток, росток/росток, они все могут размножаться, наследуя от отдельного класса вкусных, сохраняя при этом свою текущую иерархию, основанную на предках, тогда все вышеперечисленное может быть реализовано только с помощью сравнения вкусный/вкусный.
Предположим, мы берем факториал числа n :
Тогда 1! = 1, 2! = 2, 3! = 6 и 4! = 24. Однако мы быстро приходим к чрезвычайно большим числам, даже для относительно малых n . Например, 100! ≈9,332 621 54 × 10 157 — число настолько большое, что его невозможно отобразить на большинстве калькуляторов, и оно значительно больше предполагаемого числа фундаментальных частиц в наблюдаемой Вселенной. [9]
В администрировании и вычислительной технике комбинаторный взрыв представляет собой быстро ускоряющийся рост линий связи по мере добавления организаций в процесс. (Этот рост часто небрежно описывают как «экспоненциальный», но на самом деле он полиномиальный .)
Если двум организациям необходимо общаться по определенной теме, проще всего общаться напрямую, в режиме ad hoc — требуется только один канал связи . Однако, если добавляется третья организация, требуются три отдельных канала. Добавление четвертой организации требует шесть каналов; пять, десять; шесть, пятнадцать и т. д.
В общем случае для n организаций потребуется линий связи , что равно числу 2- комбинаций из n элементов (см. также Биномиальный коэффициент ). [10]
Альтернативный подход заключается в том, чтобы понять, когда эта коммуникация не будет одноразовым требованием, и создать общий или промежуточный способ передачи информации. Недостаток в том, что это требует больше работы для первой пары, поскольку каждый должен преобразовать свой внутренний подход в общий, а не поверхностно более простой подход простого понимания другого.
