试题详情
简答题算法设计中的分治策略、贪心策略、动态规划策略、回溯策略以及分支定界策略的基本思想是什么？
  • 分治策略的基本思想是把一个规模为n的问题划分为若干个规模较小、且与原问题相似的子问题，然后分别求解这些子问题，最后把各子结果合并得到整个问题的解。分解的子问题通常与原问题相似，所以可以递归地使用分治策略来求解。
    贪心策略的基本思想是把一个整体最优问题分解为一系列的最优选择问题，决策一旦做出，就不能再更改。它是通过若干次的贪心选择而得出最优解（或较优解）的一种解题策略。
    动态规划策略与贪心策略类似，将一个问题划分为重复的子问题，通过对相同子问题的求解来解决较大问题，即将一个问题的解决方案视为一系列决策的结果。不同的是，在贪心策略中，每采用一次贪心准则便做出一个不可撤回的决策，可能得不到问题的最优解。而在动态规划中，处理要按照某种规则进行选择，还要考察每个最优决策序列中是否包含一个最优子序列，目的是得到问题的最优解。
    回溯策略也叫试探法，它的基本思想是：在一些问题求解进程中，先选择某一种可能情况向前探索，当发现所选用的试探性操作不是最佳选择，需退回一步，重新选择继续进行试探，直到找到问题的解或者证明问题无解。
    分支定界策略也经常被称为分支限界策略，它的基本思想是：首先确定目标值的上下界，然后一边搜索一边剪掉空间树的某些不可能产生最优解的分支，提高搜索效率。

  • 关注下方微信公众号，在线模考后查看

热门试题