Танцующие звенья
-
Метод танцующих ссылок (DLX)
- Метод добавления и удаления узлов из кругового двусвязного списка
- Полезен для эффективной реализации алгоритмов обратного отслеживания
- Алгоритм X Кнута для задачи точного покрытия
-
История и название
- Название предложено Дональдом Кнутом
- Идея предложена Хироси Хитоцумацу и Кохэй Ношита в 1979 году
-
Реализация алгоритма X
- Кнут реализовал разреженную матрицу для сокращения времени поиска
- Каждый узел указывает на соседние узлы и заголовок столбца
- Заголовок столбца отслеживает количество узлов и формирует контрольную строку
-
Процесс удаления и восстановления
- Удаление столбцов и строк для исключения заполненных и противоречащих узлов
- Удаление заголовка столбца и строк из других столбцов
- Возвращение назад для точного аннулирования исключений
-
Необязательные ограничения
- Возможность решения задач с необязательными ограничениями
- Изменение теста решения на матрицу без первичных столбцов
- Пример: задача о n королевах с диагоналями шахматной доски
-
Дополнительные ресурсы
- Алгоритмы решения судоку
- Рекомендации и внешние ссылки
- Реализация распределенных Dancing Links в Hadoop MapReduce
- Бесплатные программные реализации на C, C#, JavaScript, C++, GoLang
- Оригинальная реализация Дональда Кнута на CWEB