使用动态规划的8-皇后问题
使用动态规划的8-皇后问题
提问于 2011-08-14 08:51:21
我对用动态规划实现8皇后问题的想法很困惑.如果将问题分解成一系列子问题，并找到每个子问题的最优解，则可以通过求解这些子问题来实现，没有这种结构的问题不能用动态规划(参考文献)来解决。考虑到这一点，7x7板的最优解对于8x8也可能不是最优的(甚至不正确)。因此，问题的结果可能无法通过子问题的最优解来实现.
另一方面，DP是回溯问题的优化.如果是这样的话，八皇后问题可以通过回溯解决.这是否意味着只存储死胡同就可以将回溯解决方案转换为DP？如果是这样，则可能2,1对亲本1,1不可行，但对1,2可能可行。
更新
有人认为用动态规划可以解决8皇后问题还是n皇后问题？如果是的话，你对上述意见的评论是什么？
回答 2
Stack Overflow用户
回答已采纳
发布于 2011-08-15 11:39:44
7x7板的最优解对于8x8也可能不是最优的(甚至不正确)。
是的，你是对的。但这不是解决问题的好办法。查看H张贴在他的答复中，定理2.4，并查看算法描述。它们根据封闭线的集合(即受到皇后威胁的线)将解划分为等价类。定理2.4保证，一旦解决了特定闭线集上的子问题，就可以分别求解其余的问题，然后将结果结合起来非常聪明！非常聪明。
Stack Overflow用户
发布于 2011-08-14 15:20:20
我刚刚发布了谷歌的热门文章：
N-皇后问题的动态规划解
注意:对于大型n，O( f(n)*8^n)，这仍然非常慢，最好使用其他一些算法：
N-皇后问题的多项式时间算法
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/7055891
复制相关文章
相似问题
腾讯云开发者
