Змея в коробке - Википедия - 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]

Примечания

^ Асимптотические оценки снизу см. Евдокимов (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.

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

[1]