使用动态规划的8王后问题 [英] 8-queen problem using Dynamic programming

问题描述

我很困惑，使用动态编程实现8皇后问题的想法。现在看来，这是不可能的一端为DP如果这个问题是分解成一系列的子问题，并为每个子问题的最佳解决方案被发现，然后将所得溶液将通过溶液与这些子问题来实现。一个问题不具有这样的结构不能与动态规划求解（<一href="http://stackoverflow.com/questions/4278188/good-examples-articles-books-for-understanding-dynamic-programming">Reference).通过采取这一帐户，为7x7的板的最佳解决方案可能不是最佳的，以及（即使不正确的）为8×8，因此，问题的结果可能不通过的子问题的最优解实现

I am quite confused with idea of implementing 8-queen problem using dynamic programming. It seems it is not possible at one end as for DP " if the problem was broken up into a series of subproblems and the optimal solution for each subproblem was found, then the resulting solution would be realized through the solution to these subproblems. A problem that does not have this structure cannot be solved with dynamic programming" (Reference). By taking this in account, the optimal solution for 7x7 board might not optimal as well (even incorrect) for 8x8. So, the result of problem might not realize through optimal solution of sub-problem.

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

At the other hand, DP is optimization for backtracking problems... if so then 8-queen problem can be solved by backtracking... does it mean that by storing only dead-ends can convert backtracking solution into DP? If so, then might 2,1 is not feasible for parent 1,1 but might feasible for 1,2.

更新

任何人有想法，无论是8皇后或n皇后问题可以通过使用动态规划来解决？如果是的话，这将是你在上面给出意见的评论？

anyone have idea that whether 8-queen or n-queen problem can be solved by using dynamic programming? If so then what will be your comments on observations given above?

推荐答案

为7x7的板最佳解决方案可能不是最优的，以及（甚至是不正确的）为8×8。的

是的，你是正确的。但是，这是不是一个好办法来分割问题。看看纸yi_H张贴在他的回答，定理2.4 ，并期待在算法描述。他们划分方案为等价类根据封闭线（即线，由皇后的威胁）的集合。定理2.4保证一旦他们解决特定的一套封闭线子问题，它们可以单独解决其余部分，然后结合的结果！非常聪明。

Yes, you are correct. But this is not a good way to split the problem. Look into paper yi_H posted in his answer, theorem 2.4, and look at the algorithm description. They divide the solutions into equivalence classes according to the sets of closed lines (i.e. lines which are threatened by queens). The theorem 2.4 guarantees that once they solve the sub-problem on the particular set of closed lines, they can solve the rest separately and then combine the result! Very clever.

这篇关于使用动态规划的8王后问题的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！