2. 计算机
  3. 要在8×8的棋盘上摆放8个“皇后”，要求“皇后”之间不能发生冲突，即任何两个“皇后”不能在同一行、同一列和相同的对角线上，则一般采用______来实现。

要在8×8的棋盘上摆放8个“皇后”，要求“皇后”之间不能发生冲突，即任何两个“皇后”不能在同一行、同一列和相同的对角线上，则一般采用______来实现。

admin2019-06-12  56
问题 要在8×8的棋盘上摆放8个“皇后”，要求“皇后”之间不能发生冲突，即任何两个“皇后”不能在同一行、同一列和相同的对角线上，则一般采用______来实现。
选项 A、分治法
B、动态规划法
C、贪心法
D、回溯法
答案D
解析 8皇后问题等价于要求在一个8×8格的棋盘上放置8个皇后，使得任意两个皇后不能放在同一行或同一列或同一斜线上。求解过程从空棋盘开始，设在第1行至第m行都已经正确放置了m个皇后的基础上，再在第m+1行上找合适的位置放置第m+1个皇后，直至第8行也找到合适的位置放置第8个皇后。在任一行上都有8种选择，开始时，位置在第1列，以后改变时，顺序选择第2列、第3列、…、第8列。当第8列也不是一个合适的位置时，就要回溯，去改变前一行的位置。
    分治法将复杂的大问题分解成规模小的问题以各个击破。归并排序等算法是采用分治法实现的。动态规划法与分治法类似，基本思想也是将待求解问题分解成若干子问题，先求解子问题，然后从这些子问题的解得到原问题的解，背包问题、LCS问题等是采用动态规划法实现的。贪心法跟动态规划法一样，也是用来解决最优问题的，但贪心法并不从整体最优考虑，它所做出的选择只是某种意义上的局部最优。
转载请注明原文地址:https://kaotiyun.com/show/CsCZ777K
本试题收录于： 软件设计师上午基础知识考试题库软考中级分类
0

软件设计师上午基础知识考试

软考中级

相关试题推荐
随机试题
最新回复(0)