使用动态编程的8-queen问题

Question

我对使用动态编程实现8-queen问题的想法很困惑.似乎DP的一端不可能"如果问题被分解为一系列子问题并且找到了每个子问题的最优解,那么所得到的解决方案将通过这些子问题的解决方案来实现.没有这种结构的动态编程无法解决"(参考).考虑到这一点,7x7电路板的最佳解决方案可能也不是8x8的最佳解决方案(甚至不正确).因此,问题的结果可能无法通过子问题的最优解来实现.

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

更新

任何人都知道使用动态编程是否可以解决8-queen或n-queen问题？如果是,那么您对上述观察的评论是什么？

Answer 1

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

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