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

Перейти к навигацииПерейти к поиску
Рисунок змеи в трёхмерном гиперкубе.

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

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

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

Задачу о змее в коробке впервые описал Кауц[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. — Bibcode: 2016arXiv160305119A. — arXiv:1603.05119.
  • 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. Архивировано 5 ноября 2013 года.
  • Kinny D. Proceedings of the 6th International WS on Multi-disciplinary Trends in Artificial Intelligence, MIWAI-2012. — 2012. — С. 271–283. Архивировано 16 января 2018 года.
  • 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.

Ссылки