1 Введение 5
2 Основные определения 6
3 Способы задания цепей и циклов 7
4 Постановка задачи 8
5 Базовый алгоритм К. Kochut для к=2 8
6 Примеры, демонстрирующие работу алгоритма 10
7 Модификация алгоритма К. Kochut для к>2 12
8 История и состояние вопроса в настоящее время 15
9 Современные верхние и нижние оценки длин цепей и цик¬
лов 16
10 Связь (п, к)-кодов с кодами, исправляющими ошибки 18
11 Обзор приближенных алгоритмов 19
11.1 Обрезка ветвей 19
11.2 Эвристические алгоритмах 20
12 Выбор алгоритма 23
13 Численные результаты 25
13.1 Количество и длины найденных цепей 25
13.2 Время поиска первой максимальной цепи 26
13.3 Изменчивость разрядов максимальных цепей 27
13.4 Сводная таблица результатов
14 Заключение 30
Литература
Задача, известная как Snake-in-the-Box problem («змея в ящике») заключается в поиске самого длинного незамкнутого (цепей) или замкнутого (цикл) пути без самопересечений по вершинам гиперкуба Qn. В настоящей работе рассматривается обобщение этой задачи, в котором ищутся цепи и циклы, где каждая пара вершин, находящихся на расстоянии не менее к в пути или цикле, также находится на расстоянии не менее к в Qn.
Впервые данная задача была описана в связи с теорией кодов, исправляющих ошибки. Чем длинней цепь, тем больший алфавит можно закодировать, и чем больше к, тем больше вероятности обнаружения ошибок.
Для размерностей от п = 1 до п = 7 змеи максимальной длины были найдены с помощью полного перебора, но при п > 7 пространство решений становится слишком велико. В случае п = 7 цикл максимальной длины был найден К. Kochut в 2009 г. экономным полным перебором (раздел 5).
В связи с этим в работе ставятся и решаются следующие задачи:
• Дать обзор точных и приближенных методов построения и поиска цепей и циклов наибольшей длины в п-мерном гиперкубе.
• Представить современные оценки максимальных длин и попытаться получить цепи с длинами, максимально близкими к этим оценкам.
• Реализовать алгоритм исчерпывающего поиска канонических цепей, предложенный К. Kochut для цепей размаха к = 2. Изучить его расширения для к > 2.
• Исследовать возможности модификаций алгоритмов приближенного поиска цепей при больших п. Реализовать один из вариантов.
• Провести численные расчеты для п = 5, 6,..., 15 и к = 2,3,..., 9.
• Изучить применение к данной задаче нескольких эвристических алгоритмов.
• Рассмотреть связь длинных цепей с кодами, исправляющими ошибки.
Все перечисленные цели были реализованы.
В работе были написаны две программы: одна (раздел 7) реализует алгоритм исчерпывающего поиска в усеченном пространстве решений, вторая (раздел 12) — алгоритм стохастической обрезки ветвей. По причине недостаточной вычислительной мощности компьютера вычисления для больших размерностей после 1, 5 — 2 часов работах программ.
Проведенные вычисления позволили расширить таблицу известных длин максимальных цепей для к = 8 и к = 9.
На основании полученных расчетов и сопоставления результатов алгоритмов можно сделать вывод, что алгоритм обрезки ветвей работает хорошо для поставленной задачи. Но для каждой пары (п, к) векторы вероятностей подбираются индивидуально, что может увеличить время исследования.
Все поставленные работе цели были достигнуты. В дальнейшем хотелось бы добавить в алгоритм еще несколько критериев отказа от неперспективных цепей.
Из обозначенных эвристических методов наиболее перспективным для реализации кажется муравьиный алгоритм, так как он естественно подходит для данной задачи.
К задаче «змея в ящике» продолжают применять все новые и новые методы и подходы, ожидаются новые рекорды.
