В информатике , танцы связи является метод возвращаясь операции удаления узла из круглой двусвязному списка . Это особенно полезно для эффективного внедрения отслеживания алгоритмов, таких как Дональд Кнут «ы алгоритма X для точной задачи крышки . [1] Алгоритм Х является рекурсивным , недетерминирован , в глубине , возвраты алгоритма , который находит все решения для точной крышки проблемы. Некоторые из наиболее известных проблем с точным покрытием включают в себя мозаику, проблема n королев и судоку .
Название « танцующие ссылки» , предложенное Дональдом Кнутом , связано с принципом работы алгоритма, поскольку итерации алгоритма приводят к тому, что связи «танцуют» с партнерскими связями, напоминая «изысканно поставленный танец». Кнут считает, что Хироши Хитоцумацу и Кохей Ношита изобрели эту идею в 1979 году [2], но популяризовала ее именно его статья.
Реализация [ править ]
Поскольку в оставшейся части этой статьи обсуждаются детали методики реализации алгоритма 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), Кнут реализовал разреженную матрицу, в которой хранятся только единицы.
Все время каждый узел в матрице будет указывать на соседние узлы слева и справа (единицы в одной строке), сверху и снизу (единицы в одном столбце) и заголовок своего столбца (описанный ниже). Каждая строка и столбец в матрице будут состоять из кругового двусвязного списка узлов.
Заголовок [ править ]
Каждый столбец будет иметь специальный узел, известный как «заголовок столбца», который будет включен в список столбцов и будет формировать специальную строку («контрольную строку»), состоящую из всех столбцов, которые все еще существуют в матрице.
Наконец, каждый заголовок столбца может дополнительно отслеживать количество узлов в своем столбце, так что поиск столбца с наименьшим количеством узлов имеет сложность O ( n ), а не O ( n × m ), где n - количество столбцов и m - количество строк. Выбор столбца с небольшим количеством узлов - это эвристика, которая в некоторых случаях повышает производительность, но не является существенной для алгоритма.
Изучение [ править ]
В алгоритме X строки и столбцы регулярно удаляются из матрицы и восстанавливаются в ней. Исключения определяются путем выбора столбца и строки в этом столбце. Если в выбранном столбце нет строк, текущая матрица неразрешима и должна быть возвращена. Когда происходит исключение, все столбцы, для которых выбранная строка содержит 1, удаляются вместе со всеми строками (включая выбранную строку), которые содержат 1 в любом из удаленных столбцов. Столбцы удаляются, потому что они были заполнены, а строки удаляются, потому что они конфликтуют с выбранной строкой. Чтобы удалить один столбец, сначала удалите заголовок выбранного столбца. Затем для каждой строки, где выбранный столбец содержит 1, просмотрите строку и удалите ее из других столбцов (это делает эти строки недоступными и позволяет предотвращать конфликты).Повторите это удаление столбца для каждого столбца, в котором выбранная строка содержит 1. Этот порядок гарантирует, что любой удаленный узел будет удален ровно один раз и в предсказуемом порядке, чтобы его можно было отследить соответствующим образом. Если в итоговой матрице нет столбцов, значит, все они заполнены, и выбранные строки образуют решение.
Возврат [ править ]
Чтобы вернуться назад, описанный выше процесс должен быть отменен с использованием второго алгоритма, указанного выше. Одно из требований использования этого алгоритма состоит в том, что обратное отслеживание должно выполняться как точное обращение исключений. Статья Кнута дает четкое представление об этих отношениях и о том, как работает удаление и повторная вставка узлов, и дает небольшое ослабление этого ограничения.
Необязательные ограничения [ править ]
Также возможно решить проблемы с одним покрытием, в которых конкретное ограничение является необязательным, но может быть удовлетворено не более одного раза. Dancing Links включает в себя основные столбцы, которые необходимо заполнить, и дополнительные столбцы, которые являются необязательными. Это изменяет проверку решения алгоритма с матрицы без столбцов на матрицу без основных столбцов, и если используется эвристика минимального значения в столбце, то ее необходимо проверять только в пределах основных столбцов. Кнут обсуждает необязательные ограничения применительно к проблеме n ферзей . Диагонали шахматной доски представляют собой необязательные ограничения, так как некоторые диагонали могут быть не заняты. Если диагональ занята, она может быть занята только один раз.
См. Также [ править ]
Ссылки [ править ]
- ^ Кнут, Дональд (2000). «Танцующие звенья» . Тысячелетние перспективы в компьютерных науках . P159. 187 . arXiv : cs / 0011047 . Bibcode : 2000cs ....... 11047K . Проверено 11 июля 2006 . CS1 maint: обескураженный параметр ( ссылка )
- ^ Хитотумату, Хироси; Ношита, Кохей (30 апреля 1979 г.). «Методика реализации алгоритмов обратного отслеживания и ее применение». Письма об обработке информации . 8 (4): 174–175. DOI : 10.1016 / 0020-0190 (79) 90016-4 .
Внешние ссылки [ править ]
- Распределены Танцевальные ссылки реализации как Hadoop MapReduce , например
- Реализация решателя Exact Cover в C в свободном программном обеспечении - использует алгоритм X и Dancing Links. Включает примеры судоку и головоломок с логической сеткой.
- Пакет DlxLib NuGet - библиотека классов C #, реализующая DLX
- dlxlib npm package - библиотека JavaScript, реализующая DLX
- dancing-links-c ++ - библиотека C ++, реализующая DLX
- go-dancing-links - библиотека GoLang, реализующая DLX
- Оригинальная реализация танцевальных ссылок Дональда Кнута, написанная на CWEB. (См. Также его интерфейс для решения головоломок судоку .)
- 24-я ежегодная рождественская лекция Дональда Кнута: Ссылки на танцы
