修剪：什么时候停止？
在深度优先搜索中，剪枝何时不再有效？我一直在研究一种有效的方法来解决 N-Queens 问题，并且我第一次考虑修剪。我已经为前两行实现了它，但是它什么时候不再有效？我应该修剪多远？
When does pruning stop being efficient in a depth-first search? I've been working on an efficient method to solve the N-Queens problem and I'm looking at pruning for the first time. I've implemented it for the first two rows, but when does it stop being efficient? How far should I prune to?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
N 皇后问题通常是递归的。在某一深度实施剪枝应该意味着在任意深度实施剪枝。
答案取决于您正在进行哪种修剪。如果您要修剪对称移动，那么当检查成本大于评估整个分支的成本乘以分支对称的概率时，就不值得修剪。对于 N 皇后问题，在前两行之后，对称可能不是一种非常有效的修剪方法。
The N-Queens problem is typically recursive. Implementing pruning at one depth should mean implementing it at any depth.
The answer would depend on what sort of pruning you're doing. If you're pruning for symmetric moves, then it's not worth pruning when the cost of checking is more than the cost of evaluating a whole branch times the probability of the branch being symmetric. For the N-Queens problem, symmetry is probably not a very fruitful pruning method after the first two rows.
我曾经看到过这样一句话：“早修剪；经常修剪。”还有一句，“不要做任何愚蠢的事情；不要做两次事情。”
我认为你所做的修剪量应该由你的问题目标或你的 N 边界决定。
I once saw a quote regarding this, "Prune early; prune often." And another, "Don't do anything stupid; don't do anything twice."
I think that the amount of pruning that you do should be determined by your goals for the problem, or your boundaries on N.