在求解某问题时,经过分析发现该问题具有最优子结构性质,求解过程中子问题被重复求解,则采用 (64)

Question

在求解某问题时，经过分析发现该问题具有最优子结构性质，求解过程中子问题被重复求解，则采用 （64）算法设计策略；若定义问题的解空间，以深度优先的方式搜索解空间，则采用（65）算法设计策略。

A.分治

B.动态规划

C.贪心

D.回溯

Answer 1

正确答案：B
分治法的设计思想是将一个难以直接解决的大问题分解成一些规模较少的相同问题以便各个击破，分而治之。动态规划法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。与分治法不同的是，适合于用动态规划法求解的问题，经分解得到的子问题往往不是独立的。若用分治法来解这类问题，则相同的子问题会被求解多次，以至于最后解决原问题需要耗费指数级时间。贪心法经常用于解决最优化问题，但他的最优往往是从局部最优来考虑的，每一步都选最优的方案，但这种方案不一定能得到整体上的最优解。回溯法是一种既带有系统性又带有跳跃性的搜索算法。它在包含问题的所有解的解空间树中，按照深度优先的策略，从根节点出发搜索解空间树。题目描述中提到，需要解决的问题具有最优子结构性质，且求解过程中子问题被重复求解，这种情况下如果采用分治法，效率会很低，所以应采用动态规划法。而“以深度优先的方式搜索解空间”则明显是在采用回溯法。