Танцевальные ссылки

Продолжительность: 50 секунд. 0:50

Алгоритм Dancing Links решает из поликуба головоломку

В информатике ) — «танцующие ссылки» ( DLX это метод добавления и удаления узла из циклического двусвязного списка . Это особенно полезно для эффективной реализации алгоритмов поиска с возвратом , таких как алгоритм X Кнута для задачи точного покрытия . Алгоритм X — это рекурсивный , недетерминированный , в глубину , поиска с возвратом алгоритм который находит все решения задачи точного покрытия . Некоторые из наиболее известных задач на точное покрытие включают в себя мозаику , задачу n ферзей и судоку .

Название «танцующие ссылки» , предложенное Дональдом Кнутом , связано с тем, как работает алгоритм, поскольку итерации алгоритма заставляют ссылки «танцевать» с партнерскими ссылками, напоминая «изысканно поставленный танец». Кнут считает, что Хироши Хитоцумацу и Кохей Ношита изобрели эту идею в 1979 году. но именно его газета популяризировала это.

Выполнение

Поскольку в оставшейся части статьи обсуждаются детали метода реализации алгоритма X, читателю настоятельно рекомендуется об алгоритме X. сначала прочитать статью

Основные идеи

Идея DLX основана на наблюдении, что в циклическом двусвязном списке узлов

x.left.right ← x.right;
x.right.left ← x.left;

удалит узел x из списка, а

x.left.right ← x;
x.right.left ← x;

восстановит позицию x в списке, предполагая, что x.right и x.left остались неизмененными. Это работает независимо от количества элементов в списке, даже если это число равно 1.

Кнут заметил, что наивная реализация его алгоритма X потратит слишком много времени на поиск единиц. При выборе столбца приходилось искать единицы по всей матрице. При выборе строки приходилось искать единицы по всему столбцу. После выбора строки в этой строке и ряде столбцов необходимо было выполнить поиск единиц. Чтобы сократить время поиска со сложности O(n) до O(1), Кнут реализовал разреженную матрицу , в которой хранятся только единицы.

Каждый узел в матрице всегда будет указывать на соседние узлы слева и справа (1 в той же строке), сверху и снизу (1 в том же столбце) и заголовок своего столбца (описано ниже). Каждая строка и столбец матрицы будут состоять из кругового двусвязного списка узлов.

Заголовок

Изображение танцующих звеньев.

Каждый столбец будет иметь специальный узел, известный как «заголовок столбца», который будет включен в список столбцов и будет формировать специальную строку («контрольную строку»), состоящую из всех столбцов, которые все еще существуют в матрице.

Наконец, каждый заголовок столбца может дополнительно отслеживать количество узлов в своем столбце, так что сложность поиска столбца с наименьшим количеством узлов составляет O( n ), а не O( n × m ), где n — количество столбцов и m — количество строк. Выбор столбца с небольшим количеством узлов — это эвристика, которая в некоторых случаях повышает производительность, но не является существенной для алгоритма.

Исследование

В алгоритме X строки и столбцы регулярно удаляются из матрицы и восстанавливаются в ней. Исключения определяются путем выбора столбца и строки в этом столбце. Если в выбранном столбце нет строк, текущая матрица неразрешима и ее необходимо вернуть. При исключении удаляются все столбцы, для которых выбранная строка содержит 1, а также все строки (включая выбранную строку), содержащие 1 в любом из удаленных столбцов. Столбцы удаляются, поскольку они заполнены, а строки удаляются, поскольку они конфликтуют с выбранной строкой. Чтобы удалить один столбец, сначала удалите заголовок выбранного столбца. Затем для каждой строки, где выбранный столбец содержит 1, пройдите по строке и удалите ее из других столбцов (это делает эти строки недоступными и предотвращает конфликты). Повторите удаление столбца для каждого столбца, в котором выбранная строка содержит 1. Такой порядок гарантирует, что любой удаленный узел будет удален ровно один раз и в предсказуемом порядке, поэтому его можно будет соответствующим образом отследить. Если в полученной матрице нет столбцов, то все они заполнены и выбранные строки образуют решение.

Возврат

Чтобы вернуться назад, описанный выше процесс необходимо обратить вспять, используя второй алгоритм, указанный выше. Одним из требований использования этого алгоритма является то, что обратный поиск должен выполняться как точное обращение исключений. Статья Кнута дает четкое представление об этих отношениях и о том, как работает удаление и повторная вставка узла, а также обеспечивает небольшое ослабление этого ограничения.

Дополнительные ограничения

Также возможно решать задачи с одним покрытием, в которых определенное ограничение является необязательным, но может быть удовлетворено не более одного раза. Dancing Links включает в себя основные столбцы, которые необходимо заполнить, и второстепенные столбцы, которые являются необязательными. Это изменяет проверку решения алгоритма с матрицы, не имеющей столбцов, на матрицу, не имеющую основных столбцов, и если используется эвристика минимума единиц в столбце, то ее необходимо проверять только в пределах основных столбцов. Кнут обсуждает необязательные ограничения применительно к проблеме n ферзей . Диагонали шахматной доски представляют собой необязательные ограничения, поскольку некоторые диагонали могут быть не заняты. Если диагональ занята, то ее можно занять только один раз.

См. также

• Алгоритмы решения судоку

Внешние ссылки

• Распределенная реализация Dancing Links на Hadoop MapReduce. примере
• Бесплатная программная реализация решателя Exact Cover на C - использует алгоритм X и Dancing Links. Включает примеры судоку и логических головоломок.
• Пакет DlxLib NuGet — библиотека классов C#, реализующая DLX.
• пакет dlxlib npm — библиотека JavaScript, реализующая DLX.
• dance-links-c++ — библиотека C++, реализующая DLX.
• go-dancing-links — библиотека GoLang, реализующая DLX
• Оригинальная реализация танцующих ссылок Дональда Кнута, написанная на CWEB. (См. также его интерфейс для решения головоломок судоку .)
• 24-я ежегодная рождественская лекция Дональда Кнута: Dancing Links