Задача « змея в коробке» в теории графов и информатике связана с поиском определенного вида пути вдоль ребер гиперкуба . Этот путь начинается в одном углу и проходит по краям до максимально возможного количества углов. После того, как он доберется до нового угла, предыдущий угол и все его соседи должны быть помечены как непригодные для использования. Путь никогда не должен доходить до угла, который помечен как непригодный для использования.
Другими словами, змея — это связный открытый путь в гиперкубе, где каждый узел, связанный с путем, за исключением головы (начала) и хвоста (финиша), имеет ровно двух соседей, также находящихся в змейке. У головы и хвоста у змеи только один сосед. Правило создания змеи заключается в том, что узел в гиперкубе можно посетить, если он соединен с текущим узлом и не является соседом какого-либо ранее посещенного узла в змейке, кроме текущего узла.
Проблема «змея в коробке» была впервые описана Каутцем (1958) на основании теории кодов, исправляющих ошибки . Вершины решения задач «змея» или «катушка в ящике» можно использовать в качестве кода Грея , который может обнаруживать однобитовые ошибки. Такие коды находят применение в электротехнике , теории кодирования и топологиях компьютерных сетей . В этих приложениях важно разработать как можно более длинный код для данного измерения гиперкуба . Чем длиннее код, тем эффективнее его возможности.
Поиск самой длинной змеи или катушки становится общеизвестно трудным, поскольку размерное число увеличивается, а пространство поиска подвергается серьезному комбинаторному взрыву . Некоторые методы определения верхних и нижних границ задачи «змея в коробке» включают доказательства с использованием дискретной математики и теории графов , исчерпывающий поиск в пространстве поиска и эвристический поиск с использованием эволюционных методов.
Известные длины и границы
Максимальные длины змей ( L s ) и витков ( L c ) в задаче «змеи в коробке» для размерностей n от 1 до 4
Максимальная длина задачи «змея в коробке» известна для размеров с первого по восьмой; это
За пределами этой длины точная длина самой длинной змеи неизвестна; Наилучшие длины, найденные на данный момент для размеров с девятого по тринадцатый, составляют
190, 370, 712, 1373, 2687.
Что касается циклов (проблема «катушка в коробке»), цикл не может существовать в гиперкубе размерностью меньше двух. Максимальная длина самых длинных возможных циклов равна
За пределами этой длины точная длина самого длинного цикла неизвестна; Наилучшие найденные на данный момент длины для размеров с девятого по тринадцатый составляют
188, 366, 692, 1344, 2594.
Двойные катушки представляют собой особый случай: циклы, вторая половина которых повторяет структуру первой половины, также известные как симметричные катушки . Для размеров со второго по седьмой длины максимально длинных сдвоенных витков равны
4, 6, 8, 14, 26, 46.
Кроме того, лучшие найденные на данный момент длины для размеров с восьмого по тринадцатый составляют
94, 186, 362, 662, 1222, 2354.
Как для задач о змее, так и для задач о катушке в ящике известно, что максимальная длина пропорциональна 2 n для n -мерного ящика, асимптотически по мере увеличения n и ограничена сверху 2 n - 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
Деймер, Кнут (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
Евдокимов А. А. (1969), "Максимальная длина цепочки в единичном n -мерном кубе", Математические заметки , 6 : 309–319.
Ким, С.; Нойхофф, Д.Л. (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), Страница исследования «Змея в коробке» (Киотский университет)
