如何为回溯算法获得更严格的界限？
How to get tighter bounds for Backtracking algorithms?
最近，我使用回溯法解决了一些问题（数独求解器、N 皇后问题）。虽然我可以直观地理解回溯优于蛮力，但我无法推理出来 mathematically/asymptotically。例如，假设我们正在为 N * N 网格实现数独求解器，其中有 K 个空槽需要填充。这里：
- N * N个网格有NK个结束状态
- 在填充每个槽结束时，我们检查它是否仍然有效并且此验证需要 O(N) 时间。
[蛮力方法是使用 N 个数字中的任何一个填充所有 K 个槽，然后检查最终状态是否为有效网格。]
总而言之，我们推断它需要 O(NK*NK) = O(KNK+1)
好吧，对于蛮力算法来说，这是一个足够公平的界限，但在回溯算法中，我们在填充过程的早期就删除了很多无效状态。显然，与蛮力实施相比，回溯算法在实践中非常快。我搜索了类似的问题并找到了这个 one，但它使用与蛮力相同的边界。我们如何渐进地证明这种回溯算法优于蛮力算法呢？
编辑：
由于人们投票决定将此问题关闭为 "Too-Broad"，我重申我正在寻找上述数独求解器的具体情况。
但是，您可以分享您通常用来渐近推理的任何想法，即给定的回溯问题比蛮力方法更快。
渐近回溯通常与蛮力相同。
这样做的原因是很难争论您将在实践中看到的最坏情况下的优化。对于数独，您可能会争辩说，在最坏的情况下（空板）您的表现将是 O(N! * N-1! * N-2! ...)（因为您不会尝试明显错误的选项） .然而，这与一般情况相差甚远，在这种情况下，可能有很多点只有一个合格值，您只需要在几个槽中尝试几个合格值（少于空槽数）。所以对于一个 20*20 的拼图，你只有 10 个槽，每个槽有 3 个符合条件的值，你的表现看起来更像是 3^10 而不是 20!*19!*18!... 不能保证，但实际上它更快对于大多数情况。
这类似于其他算法，在这些算法中，最坏的情况可能非常糟糕，但平均情况非常好。例如，QSort 是 O(N^2)，因为您总是可以选择最差的枢轴。然而，这不太可能，所以平均性能更像 NlogN。
最近，我使用回溯法解决了一些问题（数独求解器、N 皇后问题）。虽然我可以直观地理解回溯优于蛮力，但我无法推理出来 mathematically/asymptotically。例如，假设我们正在为 N * N 网格实现数独求解器，其中有 K 个空槽需要填充。这里：
- N * N个网格有NK个结束状态
- 在填充每个槽结束时，我们检查它是否仍然有效并且此验证需要 O(N) 时间。
[蛮力方法是使用 N 个数字中的任何一个填充所有 K 个槽，然后检查最终状态是否为有效网格。]
总而言之，我们推断它需要 O(NK*NK) = O(KNK+1)
好吧，对于蛮力算法来说，这是一个足够公平的界限，但在回溯算法中，我们在填充过程的早期就删除了很多无效状态。显然，与蛮力实施相比，回溯算法在实践中非常快。我搜索了类似的问题并找到了这个 one，但它使用与蛮力相同的边界。我们如何渐进地证明这种回溯算法优于蛮力算法呢？
编辑： 由于人们投票决定将此问题关闭为 "Too-Broad"，我重申我正在寻找上述数独求解器的具体情况。 但是，您可以分享您通常用来渐近推理的任何想法，即给定的回溯问题比蛮力方法更快。
渐近回溯通常与蛮力相同。
这样做的原因是很难争论您将在实践中看到的最坏情况下的优化。对于数独，您可能会争辩说，在最坏的情况下（空板）您的表现将是 O(N! * N-1! * N-2! ...)（因为您不会尝试明显错误的选项） .然而，这与一般情况相差甚远，在这种情况下，可能有很多点只有一个合格值，您只需要在几个槽中尝试几个合格值（少于空槽数）。所以对于一个 20*20 的拼图，你只有 10 个槽，每个槽有 3 个符合条件的值，你的表现看起来更像是 3^10 而不是 20!*19!*18!... 不能保证，但实际上它更快对于大多数情况。
这类似于其他算法，在这些算法中，最坏的情况可能非常糟糕，但平均情况非常好。例如，QSort 是 O(N^2)，因为您总是可以选择最差的枢轴。然而，这不太可能，所以平均性能更像 NlogN。