Танцы Links - Dancing Links

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

В Информатика, танцевальные ссылки это метод отмены операции удаления узла из циркуляра двусвязный список. Это особенно полезно для эффективной реализации возврат алгоритмы, такие как Дональд Кнут с Алгоритм X для проблема с точным покрытием.[1] Алгоритм X - это рекурсивный, недетерминированный, в глубину, возврат алгоритм который находит все решения точное покрытие проблема. Некоторые из наиболее известных проблем с точным покрытием включают черепица, то п проблема королев, и Судоку.

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

Выполнение

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

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

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

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

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

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

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

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

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

Заголовок

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

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

Изучение

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

Возврат

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

Необязательные ограничения

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

Смотрите также

Рекомендации

  1. ^ Кнут, Дональд (2000). «Танцующие звенья». Тысячелетние перспективы компьютерных наук. P159. 187. arXiv:cs / 0011047. Bibcode:2000cs ....... 11047K. Получено 2006-07-11.
  2. ^ Хитотумату, Хироси; Ношита, Кохей (30 апреля 1979 г.). «Методика реализации алгоритмов обратного отслеживания и ее применение». Письма об обработке информации. 8 (4): 174–175. Дои:10.1016/0020-0190(79)90016-4.

внешняя ссылка