Задача про змію в коробці

Задача про змію в коробці в теорії графів і інформатиці розглядає пошук певного виду шляху вздовж ребер гіперкуба. Цей шлях починається з одного кута і проходить уздовж ребер стільки кутів, скільки може досягти. Після того як досягається новий кут, попередній кут і всі його сусіди стають неприпустимими для використання. Шлях ніколи не повинен проходити через кут після того, як він позначений як неприпустимий.

Малюнок змії в тривимірному гіперкубі .

Іншими словами, змія з'єднана відкритим шляхом у гіперкубі, де кожен вузол шляху, за винятком голови (початок ланцюга) і хвоста (кінця ланцюга), має рівно двох сусідів, які також належать до змії. Хвіст і голова змії мають тільки по одному сусідові. Правило для утвороення змії полягає в тому, що вузол в гіперкубі може бути відвіданий, якщо він з'єднаний з поточним вузлом ребром і він не є сусідом будь-якого відвіданого вузла змії, відмінного від поточного положення.

В термінології теорії графів це називається знаходженням найдовшого можливого породженого шляху в гіперкубі. Це можна розглядати як спеціальний випадок задачі про ізоморфізм породженому підграфу. Існує схожа задача пошуку довгого породженого циклу в гіперкубах, що називається завданням про цикл у коробці.

Задачу про змію в коробці вперше описав Кауц[1] і спонукальною причиною була теорія кодів, що виправляють помилки. Вершини розв'язку задачі про змію або про цикл у коробці можна використовувати як код Грея, який може виявити помилки в одному біті. Такі коди мають застосування в електротехніці, теорії кодування і комп'ютерних мережах. У цих застосуваннях важливо розробити якомога довший код для даної розмірності гіперкуба. Що довший код, то ефективніші його властивості.

Знайти найбільшу змію або цикл стає справді важко за зростання розмірності, а простір пошуку схильний до серйозного комбінаторного вибуху. Деякі техніки для визначення верхньої і нижньої меж для задачі про змію в кубі включають доведення, що використовують дискретну математику і теорію графів, повний перебір простору пошуку та евристичний пошук на основі еволюційних технік.

Відомі довжини і границі

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

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[2].

Примітки
  1. Kautz, 1958.
  2. Для асимптотических нижних границ см. статьи Евдокимова (Евдокимов, 1969), Войсичовски (Wojciechowski, 1989), Аббота и Качальски (Abbot, Katchalski, 1991). Для верхних границ см. статьи Дугласа (Douglas, 1969), Демера (Deimer, 1985), Соловьёвой (Соловьёва, 1987), Аббота и Качальски (Abbot, Katchalski, 1988), Сневили (Snevily, 1994) и Земора (Zémor, 1997).

Література
  • Abbot H. L., Katchalski M. On the snake in the box problem // Journal of Combinatorial Theory, Series B. — 1988. — Т. 45. — С. 13–24. — DOI:10.1016/0095-8956(88)90051-2.
  • Abbot H. L., Katchalski M. On the construction of snake-in-the-box codes // Utilitas Mathematica. — 1991. — Т. 40. — С. 97–116.
  • David Allison, Daniel Paulusma. New Bounds for the Snake-in-the-Box Problem. — 2016. — arXiv:1603.05119. — Bibcode: 2016arXiv160305119A.
  • Bitterman D. S. New Lower Bounds for the Snake-In-The-Box Problem: A Prolog Genetic Algorithm and Heuristic Search Approach. — Department of Computer Science, University of Georgia, 2004. — (M.S. thesis).
  • Mario Blaum, Tuvi Etzion. Use of snake-in-the-box codes for reliable identification of tracks in servo fields of a disk drive. — 2002.
  • Casella D. A., Potter W. D. Using Evolutionary Techniques to Hunt for Snakes and Coils // 2005 IEEE Congress on Evolutionary Computation (CEC2005). — 2005. — Т. 3. — С. 2499–2504.
  • Casella D. A. New Lower Bounds for the Snake-in-the-Box and the Coil-in-the-Box Problems. — Department of Computer Science, University of Georgia, 2005. — (M.S. thesis).
  • Danzer L., Klee V. Length of snakes in boxes // Journal of Combinatorial Theory. — 1967. — Т. 2, вип. 3. — С. 258–265. — DOI:10.1016/S0021-9800(67)80026-7.
  • Davies D. W. Longest 'separated' paths and loops in an N-cube // IEEE Transactions on Electronic Computers. — 1965. — Т. EC-14, вип. 2. — С. 261. — DOI:10.1109/PGEC.1965.264262.
  • Knut Deimer. A new upper bound for the length of snakes // Combinatorica. — 1985. — Т. 5, вип. 2. — С. 109–120. — DOI:10.1007/BF02579373.
  • Diaz-Gomez P. A., Hougen D. F. The snake in the box problem: mathematical conjecture and a genetic algorithm approach // Proc. 8th Conf. Genetic and Evolutionary Computation. — Seattle, Washington, USA, 2006. — С. 1409–1410. — DOI:10.1145/1143997.1144219.
  • Robert J. Douglas. Upper bounds on the length of circuits of even spread in the d-cube // Journal of Combinatorial Theory. — 1969. — Т. 7, вип. 3. — С. 206–214. — DOI:10.1016/S0021-9800(69)80013-X.
  • Евдокимов А. А. О максимальной длине цепи в единичном n-мерном кубе // Матем. заметки. — 1969. — Т. 6. — С. 309–319.
  • William H. Kautz. Unit-distance error-checking codes // IRE Transactions on Electronic Computers. — 1958. — Т. 7. — С. 177–180.
  • Kim S., Neuhoff D. L. Proceedings of the IEEE International Symposium on Information Theory. — 2000. — С. 402. — DOI:10.1109/ISIT.2000.866700.
  • Kinny D. Proceedings of the 20th European Conference on Artificial Intelligence, ECAI-2012. — 2012. — С. 462–467.
  • Kinny D. Proceedings of the 6th International WS on Multi-disciplinary Trends in Artificial Intelligence, MIWAI-2012. — 2012. — С. 271–283.
  • Klee V. What is the maximum length of a d-dimensional snake? // American Mathematical Monthly. — 1970. — Т. 77, вип. 1. — С. 63–65. — DOI:10.2307/2316860. — JSTOR 2316860.
  • Kochut K. J. Snake-in-the-box codes for dimension 7 // Journal of Combinatorial Mathematics and Combinatorial Computing. — 1996. — Т. 20. — С. 175–185.
  • Lukito A., van Zanten A. J. A new non-asymptotic upper bound for snake-in-the-box codes // Journal of Combinatorial Mathematics and Combinatorial Computing. — 2001. — Т. 39. — С. 147–156.
  • Kenneth G. Paterson, Jonathan Tuliani. Some new circuit codes // IEEE Transactions on Information Theory. — 1998. — Т. 44, вип. 3. — С. 1305–1309. — DOI:10.1109/18.669420.
  • Potter W. D., Robinson R. W., Miller J. A., Kochut K. J., Redys D. Z. Proceedings of the Seventh International Conference on Industrial & Engineering Applications of Artificial Intelligence and Expert Systems. — Austin, Texas, USA, 1994. — С. 421–426.
  • Snevily H. S. The snake-in-the-box problem: a new upper bound // Discrete Mathematics. — 1994. — Т. 133. — С. 307–314. — DOI:10.1016/0012-365X(94)90039-6.
  • Соловьёва Ф. И. Верхняя граница длины цикла в n-мерном единичном кубе // Методы дискретного анализа в решении комбинаторных задач: Сб. науч. Тр.. — Новосибирск : Ин-т математики СО АН СССР, 1987. — Т. 45. — С. 71–76, 96–97.
  • Tuohy D. R., Potter W. D., Casella D. A. Proceedings of the 2007 Int. Conf. on Genetic and Evolutionary Methods (GEM'2007). — Las Vegas, Nevada, USA, 2007. — С. 3–9.
  • Wojciechowski J. A new lower bound for snake-in-the-box codes // Combinatorica. — 1989. — Т. 9, вип. 1. — С. 91–99. — DOI:10.1007/BF02122688.
  • Yuan Sheng Yang, Fang Sun, Song Han. A backward search algorithm for the snake in the box problem // Journal of the Dalian University of Technology. — 2000. — Т. 40, вип. 5. — С. 509–511.
  • Gilles Zémor. An upper bound on the size of the snake-in-the-box // Combinatorica. — 1997. — Т. 17, вип. 2. — С. 287–298. — DOI:10.1007/BF01200911.
  • Zinovik I., Kroening D., Chebiryak Y. Computing binary combinatorial gray codes via exhaustive search with SAT solvers // IEEE Transactions on Information Theory. — 2008. — Т. 54, вип. 4. — С. 1819–1823. — DOI:10.1109/TIT.2008.917695.

Посилання
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.