Змея в коробке - Snake-in-the-box

Рисунок змея в трехмерном гиперкуб.

В змея в коробке проблема в теория графов и Информатика занимается поиском определенного пути по краям гиперкуб. Этот путь начинается с одного угла и проходит по краям до максимального количества углов. После того, как он перейдет в новый угол, предыдущий угол и все его соседи должны быть помечены как непригодные для использования. Путь никогда не должен доходить до угла, отмеченного как непригодный для использования.

Другими словами, змея - это связанный открытый путь в гиперкубе, где каждый узел, связанный с путем, за исключением головы (начало) и хвоста (конец), имеет ровно два соседа, которые также находятся в змейке. У змеи есть только одна голова и хвост. Правило создания змейки состоит в том, что узел в гиперкубе может быть посещен, если он подключен к текущему узлу и не является соседом какого-либо ранее посещенного узла в змейке, кроме текущего узла.

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

Проблема "змеи в коробке" была впервые описана Каутц (1958), мотивированный теорией коды с исправлением ошибок. Вершины решения задач змея или катушка в ящике можно использовать как Код Грея который может обнаруживать однобитовые ошибки. Такие коды имеют применение в электротехника, теория кодирования, и компьютер сетевые топологии. В этих приложениях важно разработать как можно более длинный код для данного измерения гиперкуб. Чем длиннее код, тем эффективнее его возможности.

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

Известные длины и границы

Максимальная длина для задачи «змея в коробке» известна для размеров с первого по восьмой; это

1, 2, 4, 7, 13, 26, 50, 98 (последовательность A099155 в OEIS ).

За пределами этой длины точная длина самой длинной змеи неизвестна; лучшая длина, найденная до сих пор для размеров с девятого по тринадцать, -

190, 370, 712, 1373, 2687.

Для циклов (проблема катушки в коробке) цикл не может существовать в гиперкубе размерности меньше двух. Максимальная длина максимально длинных циклов составляет

0, 4, 6, 8, 14, 26, 48, 96 (последовательность A000937 в OEIS ).

За пределами этой длины точная длина самого длинного цикла неизвестна; лучшая длина, найденная до сих пор для размеров с девятого по тринадцать, -

188, 366, 692, 1344, 2594.

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

4, 6, 8, 14, 26, 46.

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

94, 186, 362, 662, 1222, 2354.

Как для задач змейки, так и для катушки в коробке известно, что максимальная длина пропорциональна 2^п для п-мерный ящик, асимптотически при п становится большим и ограничивается сверху 2^{п − 1}. Однако коэффициент пропорциональности неизвестен, но наблюдается, что он находится в диапазоне 0,3–0,4 для наиболее известных текущих значений.^[1]

Примечания

1. Асимптотические оценки снизу см. Евдокимов (1969), Войцеховский (1989), и Аббат и Качальски (1991). Для верхних оценок см. Дуглас (1969), Деймер (1985), Соловьева (1987), Аббат и Качальски (1988), Сневилы (1994), и Земор (1997).

Рекомендации

• Abbot, H.L .; Качальски, М. (1988), "О проблеме змеи в ящике", Журнал комбинаторной теории, серия B, 45: 13–24, Дои:10.1016/0095-8956(88)90051-2
• Abbot, H.L .; Качальски, М. (1991), "О построении кодов" змея в коробке ", Utilitas Mathematica [fr ], 40: 97–116
• Эллисон, Дэвид; Паулюсма, Даниэль (2016), Новые границы проблемы "змея в коробке", arXiv:1603.05119, Bibcode:2016arXiv160305119A
• Биттерман, Д. С. (2004), Новые нижние границы для задачи «змея в коробке»: генетический алгоритм Пролога и подход эвристического поиска (PDF) (Кандидатская диссертация), кафедра компьютерных наук, Университет Джорджии
• Блаум, Марио; Эцион, Туви (2002), Использование кодов змейки в коробке для надежной идентификации треков в сервополях дисковода, Патент США 6,496,312
• Casella, D.A .; Поттер, В. Д. (2005), "Использование эволюционных методов для охоты на змей и катушек", 2005 Конгресс IEEE по эволюционным вычислениям (CEC2005), 3, стр. 2499–2504
• Казелла, Д. А. (2005), Новые нижние границы для задач "змея в коробке" и "катушка в коробке" (PDF) (Кандидатская диссертация), кафедра компьютерных наук, Университет Джорджии
• Danzer, L .; Клее, В. (1967), "Длина змей в коробках", Журнал комбинаторной теории, 2 (3): 258–265, Дои:10.1016 / S0021-9800 (67) 80026-7
• Дэвис, Д. В. (1965), «Самые длинные« разделенные »пути и петли в N-куб », Транзакции IEEE на электронных компьютерах, ИС-14 (2): 261, Дои:10.1109 / PGEC.1965.264259
• Деймер, Кнут (1985), "Новая верхняя граница длины змей", Комбинаторика, 5 (2): 109–120, Дои:10.1007 / BF02579373
• Diaz-Gomez, P.A .; Хуген, Д. Ф. (2006), "Проблема змеи в коробке: математическая гипотеза и подход на основе генетического алгоритма", Труды 8-й конференции по генетическим и эволюционным вычислениям, Сиэтл, Вашингтон, США, стр. 1409–1410, Дои:10.1145/1143997.1144219
• Дуглас, Роберт Дж. (1969), "Верхние границы длины цепей равномерного распределения в d-куб », Журнал комбинаторной теории, 7 (3): 206–214, Дои:10.1016 / S0021-9800 (69) 80013-X
• Евдокимов А.А. (1969), «Максимальная длина цепи в блоке. п-мерный куб », Математические заметки, 6: 309–319
• Каутц, Уильям Х. (Июнь 1958 г.), "Коды проверки ошибок на единичном расстоянии", Операции IRE на электронных компьютерах, ИС-7 (2): 179–180, Дои:10.1109 / TEC.1958.5222529, S2CID  26649532
• Kim, S .; Neuhoff, D. L. (2000), "Коды" змея в коробке "как надежные присвоения индексов квантователя", Материалы Международного симпозиума IEEE по теории информации, п. 402, г. Дои:10.1109 / ISIT.2000.866700
• Кинни, Д. (2012), "Новый подход к проблеме" змея в коробке ", Материалы 20-й Европейской конференции по искусственному интеллекту, ECAI-2012, стр. 462–467
• Кинни, Д. (2012), "Монте-Карло Поиск змей и катушек", Труды 6-го Международного WS по мультидисциплинарным тенденциям в области искусственного интеллекта, MIWAI-2012, стр. 271–283
• Клее, В. (1970), "Какова максимальная длина d-мерная змея? ", Американский математический ежемесячный журнал, 77 (1): 63–65, Дои:10.2307/2316860, JSTOR  2316860
• Кочут, К. Дж. (1996), "Коды змеи в ящике для измерения 7", Журнал комбинаторной математики и комбинаторных вычислений, 20: 175–185
• Лукито, А .; Ван Зантен, А. Дж. (2001), "Новая неасимптотическая верхняя граница для кодов" змея в коробке ", Журнал комбинаторной математики и комбинаторных вычислений, 39: 147–156
• Paterson, Kenneth G .; Тулиани, Джонатан (1998), «Некоторые новые коды схем», IEEE Transactions по теории информации, 44 (3): 1305–1309, Дои:10.1109/18.669420
• Potter, W. D .; Робинсон, Р. У .; Miller, J. A .; Kochut, K. J .; Редис, Д. З. (1994), "Использование генетического алгоритма для поиска кодов змей в коробке", Труды седьмой международной конференции по промышленным и инженерным приложениям искусственного интеллекта и экспертных систем, Остин, Техас, США, стр. 421–426.
• Сневилый, Х.С. (1994), "Проблема змеи в коробке: новая оценка сверху", Дискретная математика, 133 (1–3): 307–314, Дои:10.1016 / 0012-365X (94) 90039-6
• Соловьева Ф. И. (1987) "Оценка сверху длины цикла в п-мерный единичный куб », Методы Дискретного анализа (на русском), 45: 71–76, 96–97
• Tuohy, D. R .; Potter, W. D .; Каселла, Д. А. (2007), «Поиск кодов« змея в коробке »с помощью усовершенствованных моделей сокращения», Материалы Междунар. Конф. по генетическим и эволюционным методам (GEM'2007), Лас-Вегас, Невада, США, стр. 3–9.
• Войцеховски, J. (1989), "Новая нижняя граница для кодов змейки в коробке", Комбинаторика, 9 (1): 91–99, Дои:10.1007 / BF02122688
• Ян, Юань Шэн; Солнце, Клык; Хан, Сонг (2000), "Алгоритм обратного поиска проблемы" змея в коробке ", Журнал Даляньского технологического университета, 40 (5): 509–511
• Земор, Жиль (1997), "Верхняя граница размера змейки в коробке", Комбинаторика, 17 (2): 287–298, Дои:10.1007 / BF01200911
• Зиновик, И .; Kroening, D .; Чебиряк, Ю. (2008), "Вычисление двоичных комбинаторных кодов Грея с помощью исчерпывающего поиска с помощью SAT-решателей", IEEE Transactions по теории информации, 54 (4): 1819–1823, Дои:10.1109 / TIT.2008.917695, HDL:20.500.11850/11304

внешняя ссылка

• Кинни, Дэвид (2012). "Страница исследования змеи в коробке (Киотский университет)".

• Поттер, В. Д. (2011). «Список текущих записей по проблеме« змея в коробке »(UGA)».

• Вайсштейн, Эрик В. "Змея". MathWorld.