Объяснение терминов для алгоритма танцевальных связей Д. Кнута
Я скачал с сайта Д.Кнута алгоритм DLX. В первом разделе, в котором D.Knuth дает обзор проблемы, столбцы разделяются на "основной" и другие столбцы. Каковы эти "основные" столбцы? Заранее спасибо.
1 ответ
Решение
Это небольшое обобщение Exact Cover. Как отмечено на соответствующей странице википедии, это обобщение проводит различие между "первичными столбцами", для которых правила такие же, как в базовом точном покрытии ("ровно один"), и "вторичными столбцами", которые "не более один". Причиной такого обобщения является то, что Dancing Links может напрямую и эффективно обрабатывать его, в то время как преобразование его в эквивалентную обычную задачу Exact Cover менее эффективно.
В статье Кнутса о Танцующих связях есть больше деталей.