Введение
Техника программирования на связных списках
В информатике, "танцующие ссылки" (DLX) — это техника добавления и удаления узла из двусвязного циклического списка. Она особенно полезна для эффективной реализации алгоритмов поиска с возвратом, таких как алгоритм Кнута X для задачи точного покрытия. Алгоритм X — это рекурсивный, недетерминированный, с поиском в глубину, алгоритм поиска с возвратом, который находит все решения задачи точного покрытия. Некоторые из наиболее известных задач точного покрытия включают в себя замощение плоскости, задачу о n ферзях и Судоку. Название "танцующие ссылки", предложенное Дональдом Кнутом, отражает принцип работы алгоритма: итерации алгоритма заставляют ссылки "танцевать" с парными ссылками, напоминая "искусно поставленный танец". Кнут отмечает, что идея была изобретена Хироси Хитоцумацу и Кохей Носита в 1979 году, однако именно его работа популяризировала эту технику.
Реализация
Поскольку остальная часть этой статьи посвящена подробностям реализации алгоритма X, читателю настоятельно рекомендуется сначала ознакомиться со статьей, описывающей алгоритм X.
Исследование
В алгоритме X строки и столбцы регулярно исключаются из матрицы и восстанавливаются в ней. Исключение определяется выбором столбца и строки в этом столбце. Если в выбранном столбце нет строк, текущая матрица не имеет решения и требует возврата к предыдущему состоянию. При исключении удаляются все столбцы, для которых выбранная строка содержит 1, а также все строки (включая выбранную строку), которые содержат 1 в любом из удаленных столбцов. Столбцы удаляются, поскольку они заполнены, а строки – поскольку они конфликтуют с выбранной строкой. Чтобы удалить один столбец, сначала удалите заголовок выбранного столбца. Затем, для каждой строки, в которой выбранный столбец содержит 1, пройдитесь по строке и удалите ее из других столбцов (это делает эти строки недоступными и предотвращает конфликты). Повторите это удаление столбца для каждого столбца, в котором выбранная строка содержит 1. Такой порядок гарантирует, что каждый удаленный элемент удаляется ровно один раз и в предсказуемом порядке, что позволяет правильно вернуться к предыдущему состоянию. Если в результирующей матрице не осталось столбцов, значит, все они заполнены, и выбранные строки образуют решение.
Отслеживание
Чтобы вернуться к предыдущему состоянию, описанный выше процесс необходимо обратить, используя второй указанный выше алгоритм. Одно из требований к использованию этого алгоритма заключается в том, что откат должен выполняться как точное обращение действий по исключению. В статье Кнута чётко показаны эти взаимосвязи и принцип работы удаления и повторного добавления узлов, а также приводится незначительное смягчение этого ограничения.
Факультативные ограничения
Также можно решать задачи покрытия, в которых определенное ограничение является необязательным, но может быть удовлетворено не более одного раза. Dancing Links обрабатывает такие случаи с помощью первичных столбцов, которые необходимо заполнить, и вторичных столбцов, которые являются необязательными. Это изменяет критерий завершения алгоритма с проверки на отсутствие столбцов в матрице на проверку на отсутствие первичных столбцов в матрице, и если используется эвристика выбора столбца с минимальным количеством единиц, то ее следует применять только к первичным столбцам. Кнут рассматривает необязательные ограничения на примере задачи о n ферзях. Диагонали шахматной доски представляют собой необязательные ограничения, поскольку некоторые диагонали могут оставаться незанятыми. Если диагональ занята, она может быть занята только один раз.