c++ - 修剪：何时停止？

Question

何时修剪在深度优先搜索中不再有效？我一直在研究一种解决 N-Queens 问题的有效方法，并且我第一次考虑修剪。我已经为前两行实现了它，但是它什么时候不再有效？我应该修剪到多远？

Answer 1

N-Queens 问题通常是递归的。在一个深度实施修剪应该意味着在任何深度实施它。

答案取决于你正在做什么样的修剪。如果您正在修剪对称移动，那么当检查的成本超过评估整个分支的成本乘以分支对称的概率时，则不值得修剪。对于 N-Queens 问题，在前两行之后，对称性可能不是一种很有成效的修剪方法。

Answer 2

我曾经看到过这样的一句话，“尽早修剪；经常修剪。” 另一个，“不要做愚蠢的事；不要做两次。”

我认为你做的修剪量应该由你解决问题的目标，或者你对 N 的界限来决定。