Из Википедии, бесплатной энциклопедии
Перейти к навигации Перейти к поиску

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

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

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

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

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

Заметки [ править ]

  1. ^ Об асимптотических оценках снизу см. Евдокимов (1969) , Войцеховский (1989) и Abbot & Katchalski (1991) . Для верхних граней, см Дуглас (1969) , Deimer (1985) , Соловьева (1987) , Abbot & Katchalski (1988) , Snevily (1994) , и Zémor (1997) .

Ссылки [ править ]

  • Abbot, HL; Качальски, М. (1988), «О проблеме змеи в ящике», Журнал комбинаторной теории, серия B , 45 : 13–24, DOI : 10.1016 / 0095-8956 (88) 90051-2
  • Abbot, HL; Качальски, М. (1991), "О построении кодов" змея в коробке ", Utilitas Mathematica  [ fr ] , 40 : 97–116
  • Эллисон, Дэвид; Паулюсма, Даниэль (2016), Новые границы для проблемы «Змея в коробке» , arXiv : 1603.05119 , Bibcode : 2016arXiv160305119A
  • Биттерман, Д.С. (2004), Новые нижние границы для проблемы «змея в коробке»: генетический алгоритм пролога и подход эвристического поиска (PDF) (магистерская диссертация), Департамент компьютерных наук, Университет Джорджии
  • Блаум, Марио; Etzion, Tuvi (2002), Использование кодов змейки в коробке для надежной идентификации дорожек в сервополях дисковода , Патент США 6,496,312.
  • Casella, DA; Поттер, В. Д. (2005), «Использование эволюционных методов для охоты на змей и катушек», Конгресс IEEE 2005 по эволюционным вычислениям (CEC2005) , 3 , стр. 2499–2504
  • Казелла, Д.А. (2005), Новые нижние границы для задач «змея в коробке» и «катушка в коробке» (PDF) (магистерская диссертация), Департамент компьютерных наук, Университет Джорджии
  • Danzer, L .; Кли, В. (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
  • Deimer, Кнут (1985), "Новая верхняя граница для длины змея", Combinatorica , 5 (2): 109-120, DOI : 10.1007 / BF02579373
  • Диас-Гомес, Пенсильвания; Hougen, DF (2006), «Проблема змеи в коробке: математическая гипотеза и подход на основе генетического алгоритма», Труды 8-й конференции по генетическим и эволюционным вычислениям , Сиэтл, Вашингтон, США, стр. 1409–1410, DOI : 10.1145 /1143997.1144219
  • Дуглас, Роберт Дж (1969), «Верхние оценки длины цепей даже распространения в г -куба», Журнал комбинаторной теории , 7 (3): 206-214, DOI : 10.1016 / S0021-9800 (69 ) 80013-X
  • Евдокимов, А.А. (1969), "Максимальная длина цепи в единичном n- мерном кубе", Математические заметки , 6 : 309–319;
  • Каутц, Уильям Х. (июнь 1958 г.), «Коды проверки ошибок на единичном расстоянии», IRE Transactions on Electronic Computers , EC-7 (2): 179–180, doi : 10.1109 / TEC.1958.5222529 , S2CID  26649532
  • Kim, S .; Neuhoff, DL (2000), «Коды« змея в коробке »как надежные присвоения индексов квантователя», Труды Международного симпозиума IEEE по теории информации , стр. 402, DOI : 10.1109 / ISIT.2000.866700
  • Кинни, Д. (2012), «Новый подход к проблеме« змея в коробке », Труды 20-й Европейской конференции по искусственному интеллекту, ECAI-2012 , стр. 462–467
  • Кинни, Д. (2012), «Монте-Карло: поиск змей и катушек», Труды 6-го Международного семинара по многопрофильным тенденциям в области искусственного интеллекта, MIWAI-2012 , стр. 271–283
  • Клее, В. (1970), "Какова максимальная длина г - мерного змея?", American Mathematical Monthly , 77 (1): 63-65, DOI : 10,2307 / 2316860 , JSTOR  2316860
  • Кочут, KJ (1996), "Коды змеи в коробке для размерности 7", Журнал комбинаторной математики и комбинаторных вычислений , 20 : 175–185
  • Лукито, А .; ван Зантен, AJ (2001), "Новая неасимптотическая верхняя граница для кодов" змея в коробке ", Журнал комбинаторной математики и комбинаторных вычислений , 39 : 147–156
  • Патерсон, Кеннет Дж .; Tuliani, Джонатан (1998), "Некоторые новые коды схемы", IEEE Transactions по теории информации , 44 (3): 1305-1309, DOI : 10,1109 / 18,669420
  • Поттер, WD; Робинсон, RW; Miller, JA; Кочут, KJ; Редис, Д.З. (1994), «Использование генетического алгоритма для поиска кодов змей в коробке», Труды Седьмой Международной конференции по промышленным и инженерным приложениям искусственного интеллекта и экспертных систем , Остин, Техас, США, стр. 421–426
  • Snevily, HS (1994), "Проблема змея-в-коробке: новая верхняя граница", Дискретная математика , 133 (1-3): 307-314, DOI : 10.1016 / 0012-365X (94) 90039- 6
  • Соловьева Ф.И. (1987), "Верхняя оценка длины цикла в n- мерном единичном кубе", Методы Дискретного анализа , 45 : 71–76, 96–97.
  • Туохи, Д.Р .; Поттер, WD; Казелла, Д.А. (2007), «Поиск кодов« змея в коробке »с помощью усовершенствованных моделей сокращения», Труды 2007 Int. Конф. по генетическим и эволюционным методам (GEM'2007) , Лас-Вегас, Невада, США, стр. 3–9.
  • Войцеховски, Дж. (1989), «Новая нижняя граница для кодов« змея в коробке », Combinatorica , 9 (1): 91–99, doi : 10.1007 / BF02122688
  • Ян, Юань Шэн; Солнце, Клык; Хан, Сонг (2000), "Алгоритм обратного поиска для задачи" змея в коробке ", Журнал Даляньского технологического университета , 40 (5): 509–511
  • Земор, Жиль (1997), «Верхняя граница размера змеи в коробке», Combinatorica , 17 (2): 287–298, doi : 10.1007 / BF01200911
  • Зиновик, И .; Kroening, D .; Chebiryak, Y. (2008), "Вычисление двоичных кодов комбинаторных серые через перебор с SAT решателями", IEEE Transactions по теории информации , 54 (4): 1819-1823, DOI : 10,1109 / TIT.2008.917695 , ЛВП : 20.500.11850 / 11304

Внешние ссылки [ править ]

  • Кинни, Дэвид (2012). "Страница исследования змеи в коробке (Киотский университет)" .
  • Поттер, WD (2011). «Список текущих записей по проблеме« змея в коробке »(UGA)» .
  • Вайсштейн, Эрик В. «Снейк» . MathWorld .