Задача про змію в коробці в теорії графів і інформатиці розглядає пошук певного виду шляху вздовж ребер гіперкуба. Цей шлях починається з одного кута і проходить уздовж ребер стільки кутів, скільки може досягти. Після того як досягається новий кут, попередній кут і всі його сусіди стають неприпустимими для використання. Шлях ніколи не повинен проходити через кут після того, як він позначений як неприпустимий.
Іншими словами, змія з'єднана відкритим шляхом у гіперкубі, де кожен вузол шляху, за винятком голови (початок ланцюга) і хвоста (кінця ланцюга), має рівно двох сусідів, які також належать до змії. Хвіст і голова змії мають тільки по одному сусідові. Правило для утвороення змії полягає в тому, що вузол в гіперкубі може бути відвіданий, якщо він з'єднаний з поточним вузлом ребром і він не є сусідом будь-якого відвіданого вузла змії, відмінного від поточного положення.
В термінології теорії графів це називається знаходженням найдовшого можливого породженого шляху в гіперкубі. Це можна розглядати як спеціальний випадок . Існує схожа задача пошуку довгого породженого циклу в гіперкубах, що називається завданням про цикл у коробці.
Задачу про змію в коробці вперше описав Кауц і спонукальною причиною була теорія кодів, що виправляють помилки. Вершини розв'язку задачі про змію або про цикл у коробці можна використовувати як код Грея, який може виявити помилки в одному біті. Такі коди мають застосування в електротехніці, теорії кодування і комп'ютерних мережах. У цих застосуваннях важливо розробити якомога довший код для даної розмірності гіперкуба. Що довший код, то ефективніші його властивості.
Знайти найбільшу змію або цикл стає справді важко за зростання розмірності, а простір пошуку схильний до серйозного комбінаторного вибуху. Деякі техніки для визначення верхньої і нижньої меж для задачі про змію в кубі включають доведення, що використовують дискретну математику і теорію графів, повний перебір простору пошуку та евристичний пошук на основі еволюційних технік.
Відомі довжини і границі Максимальна довжина змії в коробці відома для розмірностей від одиниці до восьми
1, 2, 4, 7, 13, 26, 50, 98 .
Вище восьмої розмірності точна довжина найбільшої змії не відома. Кращі знайдені довжини для розмірностей від дев'яти до тринадцяти
190, 370, 712, 1373 2687.
Цикли (в коробці) не можуть існувати в гіперкубі розмірності менше двох. Максимальні довжини можливих циклів рівні
0, 4, 6, 8, 14, 26, 48, 96 .
Поза цими розмірностями точні довжини найдовших циклів невідомі. Кращі знайдені довжини для розмірностей від дев'яти до тринадцяти
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Для асимптотических нижних границ см. статьи Евдокимова , Войсичовски , Аббота и Качальски . Для верхних границ см. статьи Дугласа , Демера , Соловьёвой , Аббота и Качальски , Сневили и Земора ..
Див. також Задача про найдовший шлях
Примітки
Література
Посилання