首页
登录
从业资格
在求解某问题时,经过分析发现该问题具有最优子结构性质,求解过程中子问题被重复求解
在求解某问题时,经过分析发现该问题具有最优子结构性质,求解过程中子问题被重复求解
免费题库
2022-08-02
36
问题
在求解某问题时,经过分析发现该问题具有最优子结构性质,求解过程中子问题被重复求解,则采用( )算法设计策略A.分治B.动态规划C.贪心D.回溯
选项
A.分治
B.动态规划
C.贪心
D.回溯
答案
B
解析
分治法的设计思想是将一个难以直接解决的大问题分解成一些规模较少的相同问题以便各个击破,分而治之。
动态规划法与分治法类似,其基本思想也是将待求解问题分解成若干个子问题,先求解子问题,然后从这些子问题的解得到原问题的解。与分治法不同的是,适合于用动态规划法求解的问题,经分解得到的子问题往往不是独立的。若用分治法来解这类问题,则相同的子问题会被求解多次,以至于最后解决原问题需要耗费指数级时间。
贪心法经常用于解决最优化问题,但他的最优往往是从局部最优来考虑的,每一步都选最优的方案,但这种方案不一定能得到整体上的最优解。回溯法是一种既带有系统性又带有跳跃性的搜索算法。它在包含问题的所有解的解空间树中,按照深度优先的策略,从根节点出发搜索解空间树。
题目描述中提到,需要解决的问题具有最优子结构性质,且求解过程中子问题被重复求解,这种情况下如果采用分治法,效率会很低,所以应采用动态规划法。而“以深度优先的方式搜索解空间”则明显是在采用回溯法。
转载请注明原文地址:https://tihaiku.com/congyezige/2407246.html
本试题收录于:
中级 软件设计师题库软件水平考试初中高级分类
中级 软件设计师
软件水平考试初中高级
相关试题推荐
以下软件质量保证的目标中,()是错误的。A.通过监控软件开发过程保证
传统编译器进行词法分析、语法分析、代码生成等步骤的处理时,前一阶段处理的输出是后
通用的风险分析表应包括()①风险问题②发生的可能性③影响的严重性④风险预测值⑤
某大型教育培训机构近期上线了在线网络学校系统,该系统拓扑结构如图1所示。企业信息
以下关于白盒测试的叙述中,不正确的是______。A.白盒测试仅与程序的内部结构
主要对与设计相关的软件体系结构的构造进行测试的是()。A.单元测试 B.集成测
在进行软件设计时,以下结构设计原则中,不正确的是()A.模块应具有较强的独立性,
在进行可用性测试时关注的问题应包括()。 ①安装过程是否困难②错误提
V模型描述了软件基本的开发过程和测试行为,描述了不同测试阶段与开发过程各阶段的对
测试过程中,正确的测试顺序应该是()。 ①单元测试②集成测试
随机试题
Americancitiesare【B1】______toothercitiesaroundtheworld.Ineverycou
Thestudyofspeechsoundsinlanguageoralanguagewithreferencetotheirdis
A、Theypaythesamewage.B、Theyinvolveworkingoutdoors.C、Theycanbesubstit
Frenchfries,washeddownwithapintofsoda,areafavoritepartoffast-f
16号全称()、43号文件的全称()
以下()材料可以作为半刚性基层的无机结合料。A.沥青 B.石灰 C.粉煤灰
连续式平整度仪的标准长度为3m。()
填入画横线部分最恰当的一组是: 某些意义上讲,与现代白话文一道_______于
()是破解资源瓶颈约束.保护生态环境的首要之策。A.节能减排 B.资源循环利
根据《建设工程工程量清单计价规范》GB50500—2013,下列清单中属于招标工
最新回复
(
0
)