Задача о змее в коробке

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

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

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

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

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

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

Максимальная длина змеи в коробке известна для размерностей от единицы до восьми

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.

Для обеих задач, змея в коробке и цикл в коробке, известно, что максимальная длина пропорциональна 2n для n-мерной коробки при росте n и ограничена сверху значением 2n-1. Однако константа пропорциональности не известна, но для текущих лучших известных значений наблюдается где-то в пределах 0,3 — 0,4.