在“八皇后问题”的问题求解中,采用()。

不能,8皇后的解中不一定包含7皇后的解,所以不具备子问题同构条件

1)思想:采用试错的思想,它尝试分步的去解决一个问题。在分步解决问题的过程中,当它通过尝试发现现有的分步答案不能得到有效的正确的解答的时候,它将取消上一步甚至是上几步的计算,再通过其它的可能的分步解答再次尝试寻找问题的答案;

2)实现:通常用最简单的递归方法来实现;

3)结果:两种情况:(1) 找到一个可能存在的正确的答案  (2) 在尝试了所有可能的分步方法后宣告该问题没有答案;

4)时间复杂度:由于整个过程需要很多往返,所以时间复杂度最坏可能达到指数级;

八皇后思路假设某一行为当前状态,不断检查该行所有的位置是否能放一个皇后,检索的状态有两种:

(1)先从首位开始检查,如果不能放置,接着检查该行第二个位置,依次检查下去,直到在该行找到一个可以放置一个皇后的地方,然后保存当前状态,转到下一行重复上述方法的检索。

(2)如果检查了该行所有的位置均不能放置一个皇后,说明上一行皇后放置的位置无法让所有的皇后找到自己合适的位置,因此就要回溯到上一行,重新检查该皇后位置后面的位置。

我要回帖

更多关于 对立统一规律揭示了( ) 的文章

 

随机推荐