Сложность танцевальных ссылок

Question

Я пишу sudoku solver и думаю об алгоритме для его реализации. Я знаю, что backtracking имеет временную сложность O (n^m), где n - количество возможностей для каждого квадрата и m - количество пробелов, которые пусты. Но я не смог получить точный анализ танцевальных ссылок. Может кто-нибудь объяснить, что это такое?

Answer 1

Dancing Links (Алгоритм X), разработанный моим Дональдом Кнутом, также хуже в случае O (N^N^2). На самом деле это намного меньше.

Я понял это, когда я написал два решателя судоку, один с одним и без танцевальных ссылок.

Если вы вводите предварительную проверку (убедитесь, что номер является действительным воспроизведением, прежде чем пытаться продолжить поиск по глубине (это также называется обрезкой в ​​мире поиска), тогда вы можете сохранить свой алгоритм из траты времени Если это единственное улучшение, которое вы делаете, то вы все равно можете столкнуться с худшим сценарием (т. Е. Первым номером является максимальное число).

Dancing Links, если вы хотели бы подумать об этом как это, Dancing Links - это Первичная проверка - очередь приоритетов - первый поиск глубины. Реальная скорость поступает из сетки обложки. Это не значит, что вам не нужно пересчитывать, какие возможности остаются (если вы его правильно реализуете), что будет более трудоемким процессом ваш решатель sudoku. Также вы можете настроить алгоритм t o выберите (точку, строку, столбец или поле) с наименьшими возможностями, оставшимися для уменьшения размера разветвления.

Вот несколько ссылок, которые действительно помогли мне сделать мой решатель:

https://www.ocf.berkeley.edu/~jchu/publicportal/sudoku/0011047.pdf https://www.ocf.berkeley.edu/~jchu/publicportal/sudoku/sudoku.paper.html

Сложность Big O этой проблемы все еще будет O (п * п * п), так как мы до сих пор переходя от места к месту и пробуя до n значений для этого места. Просто случается, что Ω (x), где x - количество пустых пространств для обеих реализаций, но время вычисления на шаг намного меньше для танцевальных ссылок.

Похоже, что Dancing Links - это просто реализация DFS, так как это так. В худшем случае для 4 на 4 будет 4 * 3 * 2 * 3 * 2 * 2 * 2 * 2 * 2. Именно из-за этой колонки Heuristic, где мы выбираем столбец сетки покрытия с наименьшим числом единиц в предотвратить массовое разветвление.