我正在编写一个数独求解器并考虑一种算法来实现它。我知道回溯的时间复杂度为 O(n^m)，其中 n 是每个方 block 的可能性数，m 是空白的空间。但是我无法对舞蹈环节进行准确的分析。谁能解释一下这是什么？
最佳答案
我的 Donald Knuth 设计的 Dancing Links(算法 X)也是更糟糕的情况 O(N^N^2) 有点。实际上比这少得多。
我在编写两个数独解算器时发现了这一点，一个有 Dancing Links，一个没有。
如果您引入前向检查(在您尝试继续深度优先搜索之前检查以确保数字是有效的播放(这在搜索领域也称为修剪))，那么您可以避免算法浪费时间。如果这是您所做的唯一改进，那么您仍然可能遇到更糟糕的情况(即第一个数字是最大数字)。
Dancing Links，如果你愿意这样想的话，Dancing Links 是一个前向检查 - 优先队列 - 深度优先搜索。真正的速度来自于覆盖网格这种方式你不需要重新计算剩下的可能性(如果你正确地实现)，这将是你的数独解算器更耗时的过程。此外，您还可以设置算法来选择(点、行、列或框)剩余可能性最小的点，以减少分支大小。
以下是一些真正帮助我制作求解器的链接:
https://www.ocf.berkeley.edu/~jchu/publicportal/sudoku/0011047.pdf https://www.ocf.berkeley.edu/~jchu/publicportal/sudoku/sudoku.paper.html
这个问题的大 O 复杂度仍然是 O(n * n * n)，因为我们仍然从一个点到另一个点，并为那个点尝试最多 n 个值。恰好 Ω(x)，其中 x 是两种实现的空白空间的数量，但对于跳舞链接，每步的计算时间要少得多。
这看起来像 Dancing Links 只是一个 DFS 实现，因为它确实是。 4 x 4 的最坏情况是 4 * 3 * 2 * 3 * 2 * 2 * 2 * 2 * 2 这是由于启发式列，我们选择覆盖网格中具有最少数量的列防止大量分支。
关于algorithm - 舞蹈环节的复杂性，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/37715983/