Алгоритм "Танцующие звенья" - объяснение, которое не так объяснительно, но больше касается реализации?
Я работал над Решателем Судоку, мой текущий решатель использует алгоритм возврата, но он все еще занимает слишком много времени.
В большинстве случаев я надеюсь уменьшить его до секунды. Поэтому я решил переписать его с помощью алгоритма танцующих связей, понимая, что это один из лучших методов грубой силы, который хорошо работает, особенно с такой проблемой ограничения, как головоломка Судоку.
Я попытался прочитать статью Вики и Кнута об этом, однако оба они довольно сложны для понимания и чрезвычайно многословны.
Я также прочитал версию Судопедии об этом, и кажется, что как только она добралась до реализации Судоку, она стала слишком абстрактной.
Может кто-нибудь попытаться объяснить алгоритм Dancing Links не с точки зрения его происхождения, а с точки зрения его реализации? (было бы здорово использовать судоку в качестве примера)
Спасибо!
2 ответа
Вас может заинтересовать моя реализация в javascript.
Во-первых, вы должны понять Точное покрытие. Точная проблема покрытия - это проблема, когда вам предоставляется набор вариантов, и набор ограничений, и ваша задача состоит в том, чтобы выбрать набор вариантов, которые заполнят каждое ограничение ровно один раз.
Например, рассмотрим случай, когда кто-то создает свою рутину танца на льду. У них есть целый ряд трюков, которые они должны показать судьям, и они не хотят выполнять какие-либо трюки более одного раза. У них есть несколько последовательностей, которые представляют собой группы уловок, которые можно собрать вместе, и они хотят выбрать идеальный выбор последовательностей, чтобы охватить все уловки один раз. В этом примере ограничения заключаются в том, что они должны выполнять каждый трюк. Выбор - это возможные последовательности, которые они могут включить в свою рутину.
Хороший способ представить проблемы такого рода - нарисовать таблицу, в которой ограничения - это столбцы, а выборы - строки, и у вас есть большой X в ячейках, где конкретный выбор удовлетворяет этому ограничению.
Как выясняется, учитывая правильные ограничения и выбор, судоку можно описать как проблему точного покрытия.
Хорошо, если у вас это есть, теперь вам нужно понять алгоритм X. Кнут сказал об этом: "Алгоритм X - это просто утверждение очевидного метода проб и ошибок. (Действительно, я не могу думать о каком-либо другом разумном способ сделать работу, в общем.)". Итак, вот мое описание алгоритма X:
- Если в вашей таблице нет столбцов, остановитесь - вы решили это. Если у вас есть частичное решение, то на самом деле это реальное решение, верните его.
- Выберите столбец (представляющий ограничение).
- Найдите строку с крестиком в этом столбце (представляющую выбор, который удовлетворяет этому ограничению). Добавьте его к какой-то структуре, где вы храните потенциальные решения. Если вы не можете найти строку, сдавайтесь - нет решений.
- Предположим, что строка, найденная в 3, находится в решении, поэтому удалите все столбцы, в которых есть X в этой строке. При удалении всех этих столбцов, также удалите все строки, которые имеют X в столбцах, которые вы удаляете (потому что вы уже выполнили ограничение, поэтому вам запрещено выбирать что-то, что могло бы удовлетворить его снова).
- Теперь рекурсивно попробуйте решить сокращенную таблицу. Если вы не можете, удалите строку, которую вы пробовали, из структуры потенциального решения, восстановите все строки и столбцы, которые вы удалили в шагах 3 и 4, и попробуйте другую строку. Если у вас кончились строки, то сдавайтесь - решений нет.
Теперь, когда вы понимаете это, вы можете понимать танцевальные ссылки. Dancing Links - это способ эффективной реализации этого алгоритма. Ключевым моментом танцующих ссылок является то, что в связанном списке, когда вы удаляете узел (что можно эффективно сделать, изменяя указатели на его соседей), удаленный вами узел имеет всю информацию, необходимую для его добавления обратно. к связанному списку (в случае, если окажется, что вы ошиблись, когда догадались, что это часть решения). Это плюс тот факт, что если вы сделаете все свои связанные списки круглыми, то внезапно вы потеряете много особых случаев - это почти все танцевальные ссылки.
Хотя этот вопрос очень старый, я решил добавить:
Эта страница делает алгоритм очень простым для понимания: рецензия на Zendoku. Пока я не читал об этом по той ссылке, я думал, что это должен быть супер продвинутый алгоритм, но на самом деле, когда вы сможете его визуализировать, это просто действительно оригинальное, но простое решение.
Также моя реализация на C# должна быть довольно легко читаемой... было бы полезно разделить различные классы на разные файлы, я уверен.
Это в основном прямая реализация из pdf Кнута, но с несколькими объектно-ориентированными оптимизациями (фактически, с тех пор, как я сделал это несколько месяцев назад, я не совсем помню, насколько сильно я отклонился от pdf)
Я создал этот визуализатор Sudoku Solver Visualizer, который реализует " Танцующие ссылки" и несколько других алгоритмов, включая Greedy Best First Search и Backtracking. Может быть, вы найдете это полезным.
Код можно найти здесь, хотя он довольно запутанный. Я рекомендую проверить только визуализатор.