舞蹈环节的复杂性

Question

我正在写一个数独解算器，并考虑一个算法来实现它。我知道回溯的时间复杂度为O(n^m)，其中n是每个正方形的可能性数，m是空白空间的数量。但是我不能得到关于舞蹈环节的准确分析。有人能解释一下这是什么吗？

Answer 1

跳舞链接(算法X)设计了我的Donald Knuth也是更糟糕的情况O(N^N^2)有点。实际上，它比这个要少得多。

当我写了两个数独解算器时，我发现了这一点，一个有舞蹈链接，一个没有舞蹈链接。

如果你引入了前向检查(在尝试继续深度优先搜索之前，检查以确保数字是有效的游戏)(这在搜索世界中也称为剪枝)，那么你可以节省算法的时间。如果这是你做的唯一的改进，那么你仍然可以达到最坏的情况(即。第一个数字是最大数字)。

跳舞链接，如果你想这样想，跳舞链接是一个前向检查-优先级队列-深度优先搜索。真正的速度来自封面网格，这样你就不需要重新计算剩下的可能性(如果你正确地实现了它)，这将是你的数独解算器更耗时的过程。此外，您还可以设置算法来选取(点、行、列或框)，以减少分支大小的可能性。

这里有几个链接，它们真的帮助我做了我的求解器：

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是两种实现的空格数量，但是对于舞蹈链接，每一步的计算时间要少得多。

这看起来像是一个DFS实现，因为它确实是。对于4x4，最糟糕的情况是4*3*2*3*2*2*2*2*2*2*2，这是由于列启发式，我们选择具有最少数量的覆盖网格的列，以防止大规模分支。