Комбинаторный взрыв
В математике комбинаторный взрыв — это быстрый рост сложности задачи из-за того, как на комбинаторику задачи влияют входные данные, ограничения и границы задачи. Комбинаторный взрыв иногда используется для оправдания неразрешимости некоторых проблем. [1] [2] Примеры таких задач включают некоторые математические функции , анализ некоторых головоломок и игр, а также некоторые патологические примеры, которые можно смоделировать как функцию Аккермана .
Латинский квадрат порядка n представляет собой массив n × n с элементами из набора из n элементов со свойством, что каждый элемент набора встречается ровно один раз в каждой строке и каждом столбце массива. Пример латинского квадрата третьего порядка:
Типичным примером латинского квадрата может быть завершенная головоломка судоку . [3] Латинский квадрат является комбинаторным объектом (в отличие от алгебраического объекта), поскольку имеет значение только расположение элементов, а не то, что они представляют собой на самом деле. Количество латинских квадратов в зависимости от порядка (независимо от набора, из которого взяты записи) (последовательность A002860 в OEIS ) представляет собой пример комбинаторного взрыва, как показано в следующей таблице.
Комбинаторный взрыв также может произойти в некоторых головоломках, играемых на сетке, таких как судоку. [2] Судоку — это тип латинского квадрата с дополнительным свойством, состоящим в том, что каждый элемент встречается ровно один раз в подразделах размером √ n × √ n (называемых прямоугольниками ). Комбинаторный взрыв происходит по мере увеличения n , создавая ограничения на свойства судоку, которые можно построить, проанализировать и решить, как показано в следующей таблице.
Одним из примеров игры, в которой комбинаторная сложность приводит к пределу разрешимости, является решение шахмат (игра с 64 клетками и 32 фигурами). Шахматы - это не решаемая игра . В 2005 году были решены все окончания шахматной партии с шестью фигурами или меньше, показывая результат каждой позиции при идеальной игре. Потребовалось еще десять лет, чтобы завершить основу стола с добавлением еще одной шахматной фигуры, таким образом завершив основу стола из 7 фигур. Добавление еще одной фигуры к шахматному окончанию (таким образом, создание основы стола из 8 фигур) считается неразрешимым из-за дополнительной комбинаторной сложности. [9] [10]
Кроме того, перспектива решения более крупных шахматных игр становится все более сложной по мере увеличения размера доски, например, в больших вариантах шахмат и бесконечных шахматах . [11]
