Змея в коробке

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

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

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

Проблема «змея в коробке» была впервые описана Каутцем (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 ^н для n -мерного ящика, асимптотически по мере увеличения n и ограниченного сверху 2 ^{п - 1}. Однако константа пропорциональности неизвестна, но наблюдается, что она находится в диапазоне 0,3–0,4 для наиболее известных на данный момент значений. ^[1]

Примечания

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

Ссылки

Эббот, Х.Л.; Качальски, М. (1988), «О задаче о змее в ящике», Журнал комбинаторной теории, серия B , 45 : 13–24, doi : 10.1016/0095-8956(88)90051-2
Эббот, Х.Л.; Качальски, М. (1991), «О построении кодов «змея в коробке», Utilitas Mathematica [ fr ] , 40 : 97–116
Эллисон, Дэвид; Паулусма, Дэниел (2016), Новые границы задачи «Змея в коробке» , arXiv : 1603.05119 , Bibcode : 2016arXiv160305119A
Биттерман, Д.С. (2004), Новые нижние границы проблемы «змея в коробке»: генетический алгоритм Пролога и эвристический подход к поиску (PDF) (дипломная работа магистра), факультет компьютерных наук, Университет Джорджии
Блаум, Марио; Эцион, Туви (2002), Использование готовых кодов для надежной идентификации дорожек в сервополях жесткого диска , патент США 6 496 312.
Казелла, Д.А.; Поттер, WD (2005), «Использование эволюционных методов для охоты на змей и катушек», Конгресс IEEE 2005 г. по эволюционным вычислениям (CEC2005) , том. 3, стр. 2499–2504.
Казелла, Д.А. (2005), Новые нижние границы для задач «Змея в коробке» и «Катушка в коробке» (PDF) (дипломная работа магистра), Факультет компьютерных наук, Университет Джорджии
Данцер, Л.; Клее, В. (1967), «Длина змей в коробках», Журнал комбинаторной теории , 2 (3): 258–265, doi : 10.1016/S0021-9800(67)80026-7
Дэвис, Д.В. (1965), «Самые длинные «отдельные» пути и петли в N -кубе», IEEE Transactions on Electronic Computers , EC-14 (2): 261, doi : 10.1109/PGEC.1965.264259
Деймер, Кнут (1985), «Новая верхняя граница длины змей», Combinatorica , 5 (2): 109–120, doi : 10.1007/BF02579373 , S2CID 30303683
Диас-Гомез, Пенсильвания; Хоуген, Д.Ф. (2006), «Проблема о змее в ящике: математическая гипотеза и подход с использованием генетических алгоритмов», Труды 8-й конференции по генетическим и эволюционным вычислениям , Сиэтл, Вашингтон, США, стр. 1409–1410, doi : 10.1145. /1143997.1144219 , S2CID 19239490 {{citation}}: CS1 maint: отсутствует местоположение издателя ( ссылка )
Дуглас, Роберт Дж. (1969), «Верхние границы длины цепей четного разброса в d -кубе», Journal of Combinatorial Theory , 7 (3): 206–214, doi : 10.1016/S0021-9800 (69 )80013-X
Evdokimov, A. A. (1969), "Maximal length of a chain in a unit n -dimensional cube", Matematicheskie Zametki , 6 : 309–319
Каутц, Уильям Х. (июнь 1958 г.), «Коды проверки ошибок на единичном расстоянии», IRE Transactions on Electronic Computers , EC-7 (2): 179–180, doi : 10.1109/TEC.1958.5222529 , S2CID 26649532
Ким, С.; Нойхофф, Д.Л. (2000), «Коды «змея в коробке» как надежные назначения индексов квантователя», Труды Международного симпозиума IEEE по теории информации , стр. 402, номер домена : 10.1109/ISIT.2000.866700 , ISBN 0-7803-5857-0 , S2CID 122798425
Кинни, Д. (2012), «Новый подход к проблеме змеи в коробке», Материалы 20-й Европейской конференции по искусственному интеллекту, ECAI-2012 , стр. 462–467.
Кинни, Д. (2012), «В поисках змей и катушек в Монте-Карло», Труды 6-го Международного форума по междисциплинарным тенденциям в области искусственного интеллекта, MIWAI-2012 , стр. 271–283.
Кли, В. (1970), «Какова максимальная длина d -мерной змеи?», American Mathematical Monthly , 77 (1): 63–65, doi : 10.2307/2316860 , JSTOR 2316860
Кочут, К.Дж. (1996), «Коды «змея в коробке» для измерения 7», Журнал комбинаторной математики и комбинаторных вычислений , 20 : 175–185.
Лукито, А.; ван Зантен, AJ (2001), «Новая неасимптотическая верхняя граница для кодов «змея в коробке», Журнал комбинаторной математики и комбинаторных вычислений , 39 : 147–156
Патерсон, Кеннет Г.; Тулиани, Джонатан (1998), «Некоторые новые схемные коды», IEEE Transactions on Information Theory , 44 (3): 1305–1309, doi : 10.1109/18.669420
Поттер, штат Вашингтон; Робинсон, RW; Миллер, Дж.А.; Кочут, К.Дж.; Редис, Д.З. (1994), «Использование генетического алгоритма для поиска змей в кодах коробки», Труды Седьмой международной конференции по промышленному и инженерному применению искусственного интеллекта и экспертных систем , Остин, Техас, США, стр. 421–426. {{citation}}: CS1 maint: отсутствует местоположение издателя ( ссылка )
Сневили, Х.С. (1994), «Проблема о змее в ящике: новая верхняя граница», Discrete Mathematics , 133 (1–3): 307–314, doi : 10.1016/0012-365X(94)90039- 6
Соловьева Ф.И. (1987), "Верхняя оценка длины цикла в n -мерном единичном кубе", Методы дискретного анализа , 45 : 71–76, 96–97.
Туохи, доктор медицинских наук; Поттер, штат Вашингтон; Казелла, Д.А. (2007), «Поиск кодов «змея в коробке» с помощью усовершенствованных моделей обрезки», Proceedings of 2007 Int. Конф. по генетическим и эволюционным методам (GEM'2007) , Лас-Вегас, Невада, США, стр. 3–9. {{citation}}: CS1 maint: отсутствует местоположение издателя ( ссылка )
Войцеховский Дж. (1989), «Новая нижняя граница для готовых кодов», Combinatorica , 9 (1): 91–99, doi : 10.1007/BF02122688 , S2CID 9450370
Ян, Юань Шэн; Солнце, Клык; Хан, Сун (2000), «Алгоритм обратного поиска для задачи о змее в коробке», Журнал Даляньского технологического университета , 40 (5): 509–511.
Земор, Жиль (1997), «Верхняя граница размера змеи в коробке», Combinatorica , 17 (2): 287–298, doi : 10.1007/BF01200911 , S2CID 1287549
Зиновик И.; Кренинг, Д.; Чебиряк, Ю. (2008), «Вычисление двоичных комбинаторных кодов Грея посредством исчерпывающего поиска с помощью решателей SAT», IEEE Transactions on Information Theory , 54 (4): 1819–1823, doi : 10.1109/TIT.2008.917695 , hdl : 20.500.11850 /11304 , S2CID 2854180

Внешние ссылки

Кинни, Дэвид (2012), Страница исследования «Змея в коробке» (Киотский университет)
Вайсштейн, Эрик В. , «Змея» , MathWorld

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

[1]