Комбинаторный взрыв
 | Эта статья нуждается в дополнительных цитатах для проверки . ( сентябрь 2014 г. ) |
В математике комбинаторный взрыв — это быстрый рост сложности задачи из-за того, как ее комбинаторика зависит от входных данных, ограничений и границ. Комбинаторный взрыв иногда используется для оправдания неразрешимости определенных проблем. [1] [2] Примеры таких задач включают определенные математические функции , анализ некоторых головоломок и игр, а также некоторые патологические примеры, которые можно смоделировать как функцию Аккермана .
Примеры
[ редактировать ]Латинские квадраты
[ редактировать ]Латинский квадрат порядка n — это массив размера n × n с элементами из набора из n элементов, обладающий тем свойством, что каждый элемент набора встречается ровно один раз в каждой строке и каждом столбце массива. Пример латинского квадрата третьего порядка:
1 2 3 2 3 1 3 1 2
Типичным примером латинского квадрата может служить завершенная головоломка судоку . [3] Латинский квадрат — это комбинаторный объект (в отличие от алгебраического объекта), поскольку имеет значение только расположение записей, а не то, чем они на самом деле являются. Количество латинских квадратов в зависимости от порядка (независимо от набора, из которого взяты записи) (последовательность 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 |
Судоку
[ редактировать ]Комбинаторный взрыв также может произойти в некоторых головоломках с сеткой, таких как судоку. [2] Судоку — это тип латинского квадрата с дополнительным свойством, заключающимся в том, что каждый элемент встречается ровно один раз в подразделах размером √ n × √ n (называемых ящиками ). Комбинаторный взрыв происходит по мере увеличения n , создавая ограничения на свойства судоку, которые можно строить, анализировать и решать, как показано в следующей таблице.
| н | Количество сеток судоку порядка n (размер коробок √ n × √ n ) | Количество латинских квадратов порядка n (для сравнения) |
|---|---|---|
| 1 | 1 | 1 |
| 4 | 288 [4] | 576 |
| 9 | 6,670,903,752,021,072,936,960 [4] [5] | 5,524,751,496,156,892,842,531,225,600 |
| ( n = 9 — это обычное судоку размером 9 × 9. В головоломке нет сеток, где 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 переменных, каждая из которых имеет Z разрешенных значений (а не только 2 (истина и ложь) логических значений), будет иметь Z н возможные состояния.
Возможные состояния можно рассматривать как конечные узлы дерева высоты n , где каждый узел имеет Z дочерних элементов. Такое быстрое увеличение количества конечных узлов может быть полезно в таких областях, как поиск , поскольку ко многим результатам можно получить доступ без необходимости спускаться очень далеко. Это также может быть помехой при манипулировании такими структурами.
Иерархию классов в объектно-ориентированном языке можно представить как дерево, в котором различные типы объектов наследуются от своих родителей. Если необходимо объединить разные классы, например, при сравнении (например, A < B ), тогда количество возможных комбинаций резко возрастает. Если необходимо запрограммировать каждый тип сравнения, то это вскоре становится невозможным даже для небольшого числа классов. Множественное наследование может решить эту проблему, позволяя подклассам иметь несколько родительских классов, и, таким образом, можно рассматривать несколько родительских классов, а не каждый дочерний класс, не нарушая при этом существующую иерархию.
Примером может служить таксономия, в которой разные овощи наследуют виды своих предков. Попытка сравнить вкусовые качества каждого овоща с другими становится трудноразрешимой, поскольку иерархия содержит только информацию о генетике и не упоминает вкусовые качества. Однако вместо того, чтобы писать сравнения морковь/морковь, морковь/картофель, морковь/росток, картофель/картофель, картофель/росток, росток/росток, все они могут многократно наследовать от отдельного класса вкусностей, сохраняя при этом своего текущего предка. на основе иерархии, то все вышеперечисленное можно реализовать только с помощью сравнения «вкусно/вкусно».
Арифметика
[ редактировать ]мы берем факториал n Предположим , :
Тогда 1! = 1, 2! = 2, 3! = 6 и 4! = 24. Однако мы быстро приходим к чрезвычайно большим числам даже при относительно малых n . Например, 100! ≈ 9,332 621 54 × 10 157 , число настолько велико, что его невозможно отобразить на большинстве калькуляторов, и оно намного превышает предполагаемое количество фундаментальных частиц в наблюдаемой Вселенной. [9]
Коммуникация
[ редактировать ] |  |
В администрировании и вычислительной технике комбинаторный взрыв — это быстро ускоряющееся увеличение количества линий связи по мере добавления организаций в процесс. (Этот рост часто называют «экспоненциальным», но на самом деле он полиномиален .)
Если двум организациям необходимо обсудить конкретную тему, проще всего общаться напрямую, в специальной манере — только один канал связи требуется . Однако если добавляется третья организация, потребуются три отдельных канала. Для добавления четвертой организации требуется шесть каналов; пять, десять; шесть, пятнадцать; и т. д.
В общем, это займет линий связи для n организаций, что и есть число 2- комбинаций из n элементов (см. также Биномиальный коэффициент ). [10]
Альтернативный подход заключается в том, чтобы осознать, что такое общение не будет разовым требованием, и создать общий или промежуточный способ передачи информации. Недостаток заключается в том, что это требует больше работы для первой пары, поскольку каждый должен преобразовать свой внутренний подход в общий, а не в более простой на первый взгляд подход, заключающийся в простом понимании другого.
См. также
[ редактировать ]Ссылки
[ редактировать ]- ^ Криппендорф, Клаус. «Комбинаторный взрыв» . Веб-словарь кибернетики и систем . ПРИНЦИПИЯ КИБЕРНЕТИКА ВЕБ. Архивировано из оригинала 6 августа 2010 года . Проверено 29 ноября 2010 г.
- ^ Перейти обратно: а б http://intelligence.worldofcomputing/combinatorial-explosion. Архивировано 23 августа 2011 г. в Wayback Machine Combinatorial Explosion.
- ^ Все завершенные головоломки представляют собой латинские квадраты, но не все латинские квадраты могут быть собраны в головоломки, поскольку в головоломке судоку есть дополнительная структура.
- ^ Перейти обратно: а б Слоан, Нью-Джерси (ред.). «Последовательность A107739 (Количество (завершенных) судоку (или судоку) размера n^2 X n^2)» . Электронная энциклопедия целочисленных последовательностей . Фонд ОЭИС . Проверено 14 апреля 2017 г.
- ^ «Проблемы перечисления судоку» . Afjarvis.staff.shef.ac.uk . Проверено 20 октября 2013 г.
- ^ http://chessok.com/Lomonosov Таблицы эндшпиля Базы таблиц эндшпиля Ломоносова
- ^ «База стола из 7 фигур (шахматы)» . Обмен стеками .
- ^ Авиезри Френкель; Д. Лихтенштейн (1981), «Вычисление идеальной стратегии для шахмат n × n требует экспоненты времени от n», Дж. Комбин. Теория Сер. А , 31 (2): 199–214, doi : 10.1016/0097-3165(81)90016-9
- ^ «Вселенная в цифрах — физика Вселенной» . www.physicalsoftheuniverse.com . Проверено 27 августа 2021 г.
- ^ Бенсон, Тим. (2010). Принципы совместимости здоровья HL7 и SNOMED . Нью-Йорк: Спрингер. п. 23. ISBN 9781848828032 . OCLC 663097524 .