问题
单项选择题 共用题干题
在求解某问题时,经过分析发现该问题具有最优子结构性质,求解过程中子问题被重复求解,则采用(1)算法设计策略;若定义问题的解空间,以深度优先的方式搜索解空间,则采用(2)算法设计策略。
空白(1)处应选择()
A.分治
B.动态规划
C.贪心
D.回溯
答案
参考答案:B
解析:本题考查算法设计的基础知识。存在几种常用的算法设计策略:分治法、动态规划、贪心、回溯发和分支限界法等。其中,分治法一般用于将大问题分解为一个或多个规模较小的子问题,通常采用自顶向下的递归方法来求解。动态规划求解问题的特征是,问题具有最优子结构和重叠子问题,求解时一般采用自底向上的方法来进行。贪心法求解问题的特征是,问题具有最有子结构和贪心选择性质,求解时可以用自底向上或自项向下的方法进行。回溯法和分支限界法是系统搜索解空间来求解问题的方法,一般先定义解空间,前者以深度优先的方式搜索,后者通常以广度优先的方式搜索。