12

我对使用动态编程实现 8-queen 问题的想法感到非常困惑。对于 DP 来说，这似乎是不可能的“如果将问题分解为一系列子问题并找到每个子问题的最佳解决方案，那么最终的解决方案将通过这些子问题的解决方案来实现。一个问题没有这种结构的问题不能用动态规划来解决”（参考）。考虑到这一点，7x7 电路板的最佳解决方案可能不是 8x8 的最佳解决方案（甚至不正确）。因此，问题的结果可能无法通过子问题的最优解来实现。

另一方面，DP是针对回溯问题的优化......如果是这样，那么可以通过回溯解决8-queen问题......是否意味着通过仅存储死端可以将回溯解决方案转换为DP？如果是这样，那么可能 2,1 对于父 1,1 是不可行的，但对于 1,2 可能是可行的。

更新

有人知道使用动态规划是否可以解决 8-queen 或 n-queen 问题？如果是这样，那么您对上述观察结果有何评论？

4

2 回答 2

5

7x7 板的最佳解决方案对于 8x8 可能也不是最佳的（甚至不正确）。

是的，你是对的。但这不是解决问题的好方法。查看在他的答案中发布的论文 yi_H，定理 2.4，并查看算法描述。他们根据封闭线的集合（即受皇后威胁的线）将解决方案划分为等价类。定理 2.4 保证一旦他们解决了特定闭合线集上的子问题，他们可以单独解决其余的问题，然后组合结果！非常聪明。

于 2011-08-15T11:39:44.360 回答
2

只是发布明显的谷歌命中：

n皇后问题的动态规划解决方案

注意：对于大的 n，这仍然非常慢，O ( f(n)*8^n)，你最好使用其他算法：

N-Queens 问题的多项式时间算法

于 2011-08-14T15:20:20.083 回答