В математике , А комбинаторный взрыв является быстрым ростом сложности проблемы из - за того , каким образом комбинаторики этой проблемы зависят от входных, ограничения и пределов этой проблемы. Комбинаторный взрыв иногда используется для оправдания неразрешимости определенных проблем. [1] [2] Примеры таких проблем включают определенные математические функции , анализ некоторых головоломок и игр, а также некоторые патологические примеры, которые можно смоделировать как функцию Аккермана .
Примеры [ править ]
Латинские квадраты [ править ]
Латинский квадрат порядка п является п × п массива с элементами из множества п элементов , обладающего свойством , что каждый элемент множества встречается ровно один раз в каждой строке и в каждом столбце массива. Пример латинского квадрата третьего порядка дает
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] [5] | 576 |
| 9 | 6 670 903 752 021 072 936 960 [4] [6] | 5,524,751,496,156,892,842,531,225,600 |
| 16 | 5,96 × 10 98 ( оценка ) [7] | - |
| 25 | 4,36 × 10 308 ( оценка ) [8] | - |
| ( n = 9 - это судоку размером 9 × 9, в который обычно играют. Головоломка не включает сетки, где √ n является иррациональным.) | ||
Игры [ править ]
Одним из примеров игры, в которой комбинаторная сложность приводит к пределу разрешимости, является решение шахмат (игра с 64 клетками и 32 фигурами). Шахматы - это не решаемая игра . В 2005 году все концовки шахматной партии с шестью или менее фигурами были решены, показывая результат каждой позиции при идеальной игре. Потребовалось еще десять лет, чтобы завершить основание стола, добавив еще одну шахматную фигуру, таким образом завершив основание стола из 7 частей. Добавление еще одной фигуры к шахматной концовке (таким образом, создавая основу стола из 8 фигур) считается неразрешимым из-за дополнительной комбинаторной сложности. [9] [10]
Кроме того, перспектива решения более крупных шахматных игр становится более трудной по мере увеличения размера доски, например, в вариантах больших шахмат и бесконечных шахматах . [11]
Вычисления [ править ]
Комбинаторный взрыв может происходить в вычислительной среде аналогично коммуникациям и многомерному пространству . Представьте себе простую систему только с одной переменной, булевым именем 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 (истина и ложь) логических значений), будет иметь Z n возможных состояний.
Возможные состояния можно рассматривать как листовые узлы дерева высотой n , где каждый узел имеет Z дочерних элементов . Такое быстрое увеличение конечных узлов может быть полезно в таких областях, как поиск , поскольку многие результаты могут быть доступны без необходимости спускаться очень далеко. Также это может быть помехой при манипуляциях с такими конструкциями.
Иерархию классов в объектно-ориентированном языке можно рассматривать как дерево, с различными типами объекта наследования от своих родителей. Если необходимо объединить разные классы, например, при сравнении (например, A < B ), то количество возможных комбинаций, которые могут возникнуть, резко возрастает. Если нужно запрограммировать каждый тип сравнения, то это скоро станет непреодолимым даже для небольшого числа классов. Множественное наследование может решить эту проблему, позволяя подклассам иметь несколько родителей, и, таким образом, можно рассматривать несколько родительских классов, а не каждый дочерний, без нарушения какой-либо существующей иерархии.
Примером может служить таксономия, в которой разные овощи унаследованы от своих предков. Попытка сравнить вкус каждого овоща с другими становится непреодолимой, поскольку иерархия содержит только информацию о генетике и не упоминает о вкусе. Однако вместо того, чтобы писать сравнения для моркови / моркови, моркови / картофеля, моркови / ростков, картофеля / картофеля, картофеля / ростков, ростков / ростков, все они могут наследоваться от отдельного класса вкусностей, сохраняя при этом своего текущего предка. основанная на иерархии, то все вышеперечисленное может быть реализовано только путем сравнения «вкусно / вкусно».
Арифметика [ править ]
Предположим, мы берем факториал за n :
Тогда 1! = 1, 2! = 2, 3! = 6 и 4! = 24. Однако мы быстро приходим к очень большим числам даже для относительно малых n . Например, 100! ≈ 9,33262154 × 10 157 , число настолько велико, что его невозможно отобразить на большинстве калькуляторов, и намного больше, чем предполагаемое количество элементарных частиц во Вселенной. [12]
Эта статья требует дополнительных ссылок для проверки . ( сентябрь 2014 г. ) ( Узнайте, как и когда удалить этот шаблон сообщения ) |
Используя отдельные линии связи, четырем организациям требуется шесть каналов | При использовании посредника требуется только один канал на организацию |
Связь [ править ]
В администрации и вычислительной технике , А комбинаторный взрыв является быстрым ускорением увеличения линий связи при добавлении организации в процессе. (Этот рост часто называют «экспоненциальным», но на самом деле он полиномиальный .)
Если двум организациям необходимо обмениваться информацией по определенной теме, проще всего будет общаться напрямую в специальной манере - требуется только один канал связи . Однако при добавлении третьей организации потребуются три отдельных канала. Для добавления четвертой организации требуется шесть каналов; пять десять; шесть пятнадцать; и Т. Д.
В общем, для этого потребуются линии связи для n организаций, что составляет всего лишь количество 2-х комбинаций из n элементов (см. Также биномиальный коэффициент ). [13]
Альтернативный подход состоит в том, чтобы понять, когда это общение не будет разовым требованием, и создать общий или промежуточный способ передачи информации. Недостатком является то, что это требует большей работы для первой пары, поскольку каждая из них должна преобразовать свой внутренний подход в общий, а не на внешне более простой подход, заключающийся в простом понимании друг друга.
См. Также [ править ]
- Проблема дня рождения
- Экспоненциальный рост
- Закон меткалфа
- Проклятие размерности
- Сложность (сложность)
- Вторая половина шахматной доски
Ссылки [ править ]
- ^ Криппендорф, Клаус. «Комбинаторный взрыв» . Интернет-словарь кибернетики и систем . PRINCIPIA CYBERNETICA WEB . Проверено 29 ноября 2010 года .
- ^ a b http: //intelligence.worldofcomputing/combinatorial-explosion Combinatorial Explosion.
- ^ Все завершенные головоломки представляют собой латинские квадраты, но не все латинские квадраты могут быть завершенными головоломками, поскольку в головоломке судоку есть дополнительная структура.
- ^ а б Слоан, Н. Дж. А. (ред.). «Последовательность A107739 (Количество (завершенных) судоку (или судоку) размером n ^ 2 X n ^ 2)» . Он -лайн энциклопедия целочисленных последовательностей . Фонд OEIS . Проверено 14 апреля 2017 года .
- ^ «Математика судоку - могут ли смертные решить это для квадрата 2x2?: Общие» . Forum.enjoysudoku.com . Проверено 20 октября 2013 .
- ^ «Проблемы с перечислением судоку» . Afjarvis.staff.shef.ac.uk . Проверено 20 октября 2013 года .
- ^ «Математика Су-Доку: Общие - Страница 36» . Forum.enjoysudoku.com . Проверено 20 октября 2013 .
- ^ "Алгоритм подсчета полос RxC Sudoku: Общие" . Forum.enjoysudoku.com . Проверено 20 октября 2013 .
- ^ http://chessok.com/Lomonosov Endgame Tablebases Таблицы для эндшпиля Ломоносова.
- ^ "7-фигурный эндшпиль-стол (шахматы)" . Обмен стеками .
- ^ Авиэзри Френкель; Д. Лихтенштейн (1981), «Вычисление идеальной стратегии для шахмат n × n требует экспоненциального времени по n», J. Combin. Теория Сер. , 31 (2): 199-214, DOI : 10,1016 / 0097-3165 (81) 90016-9
- ^ http://www.physicsoftheuniverse.com/numbers.html
- ^ Бенсон, Тим. (2010). Принципы совместимости здоровья HL7 и SNOMED . Нью-Йорк: Спрингер. п. 23. ISBN 9781848828032. OCLC 663097524 .
