Цепные коды и Snake-in-the-Box Problem

Статья написана по материалам пленарного доклада “Цепные коды и Snake-in-the-Box Problem: современное состояние, обобщения, приложения”, сделанного на XVII Международной конференции “Проблемы теоретической кибернетики”, Казанский федеральный университет, июнь, 2014 г. В статье мы обсуждаем современное состояние исследований по этой хорошо известной комбинаторной проблеме и её обобщениям. Даётся обзор результатов по нижним и верхним оценкам наибольшей длины цепи (snake) и цикла в $n$-мерном булевом кубе. Сравниваются известные методы конструирования змей и верхние оценки их максимальной длины. Приводится таблица точных значений наибольших длин для $n<9$ и оценки для $n=10,11$ и $12$. Описана простая конструкция змеи длины $\mathrm{const}\cdot2^n$ со значением $\mathrm{const}>0.26$. Анализируются свойства конструкций, влияющие на величину константы. Даётся обзор результатов по обобщающим змеи цепным кодам. Приводятся некоторые нерешённые задачи.