首页
登录
从业资格
在求解某问题时,经过分析发现该问题具有最优子结构性质,求解过程中子问题被重复求解
在求解某问题时,经过分析发现该问题具有最优子结构性质,求解过程中子问题被重复求解
免费题库
2022-08-02
39
问题
在求解某问题时,经过分析发现该问题具有最优子结构性质,求解过程中子问题被重复求解,则采用( )算法设计策略A.分治B.动态规划C.贪心D.回溯
选项
A.分治
B.动态规划
C.贪心
D.回溯
答案
B
解析
分治法的设计思想是将一个难以直接解决的大问题分解成一些规模较少的相同问题以便各个击破,分而治之。
动态规划法与分治法类似,其基本思想也是将待求解问题分解成若干个子问题,先求解子问题,然后从这些子问题的解得到原问题的解。与分治法不同的是,适合于用动态规划法求解的问题,经分解得到的子问题往往不是独立的。若用分治法来解这类问题,则相同的子问题会被求解多次,以至于最后解决原问题需要耗费指数级时间。
贪心法经常用于解决最优化问题,但他的最优往往是从局部最优来考虑的,每一步都选最优的方案,但这种方案不一定能得到整体上的最优解。回溯法是一种既带有系统性又带有跳跃性的搜索算法。它在包含问题的所有解的解空间树中,按照深度优先的策略,从根节点出发搜索解空间树。
题目描述中提到,需要解决的问题具有最优子结构性质,且求解过程中子问题被重复求解,这种情况下如果采用分治法,效率会很低,所以应采用动态规划法。而“以深度优先的方式搜索解空间”则明显是在采用回溯法。
转载请注明原文地址:https://tihaiku.com/congyezige/2407246.html
本试题收录于:
中级 软件设计师题库软件水平考试初中高级分类
中级 软件设计师
软件水平考试初中高级
相关试题推荐
以下软件质量保证的目标中,()是错误的。A.通过监控软件开发过程保证
传统编译器进行词法分析、语法分析、代码生成等步骤的处理时,前一阶段处理的输出是后
通用的风险分析表应包括()①风险问题②发生的可能性③影响的严重性④风险预测值⑤
某大型教育培训机构近期上线了在线网络学校系统,该系统拓扑结构如图1所示。企业信息
以下关于白盒测试的叙述中,不正确的是______。A.白盒测试仅与程序的内部结构
主要对与设计相关的软件体系结构的构造进行测试的是()。A.单元测试 B.集成测
在进行软件设计时,以下结构设计原则中,不正确的是()A.模块应具有较强的独立性,
在进行可用性测试时关注的问题应包括()。 ①安装过程是否困难②错误提
V模型描述了软件基本的开发过程和测试行为,描述了不同测试阶段与开发过程各阶段的对
测试过程中,正确的测试顺序应该是()。 ①单元测试②集成测试
随机试题
Asheetofmetalwasshakento________thesoundofthunder.A、stimulateB、simul
Mostchildrenwithhealthyappetitesarereadytoeatalmostanythingthati
Theroomisinaterriblemess;it______(can’tclean).can’thavebeencleaned情
InEuropeandAsia,thefirst"mediumofexchange"or"standardofvalue"was
Radiosignalsforthenextgenerationofmobilephoneservicescancausehead
HowtoDuckCabinFeversandOtherAchesonaPlane?[A]Onthef
大多数寒凉药具有的药理作用是A.兴奋中枢神经系统功能B.兴奋交感神经系统功能C.
患者,女,53岁。阵发性腹部绞痛2天入院,入院诊断胆道结石。入院后2小时,患者表
患者女性,28岁,自高处坠下,额部着地,双眼眶青紫淤血。鼻腔有血性液体流出,主诉
配置冬季施工和抗硫酸盐腐蚀施工的混凝土的水泥宜采用()。A.铝酸盐水泥
最新回复
(
0
)