首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
(2012年上半年上午试题63、64)某货车运输公司有一个中央仓库和n个运输目的地,每天要从中央仓库将货物运输到所有运输目的地,到达每个运输目的地一次且仅一次,最后回到中央仓库。在两个地点i和j之间运输货物存在费用Cij,为求解旅行费用总和最小的运输路径,
(2012年上半年上午试题63、64)某货车运输公司有一个中央仓库和n个运输目的地,每天要从中央仓库将货物运输到所有运输目的地,到达每个运输目的地一次且仅一次,最后回到中央仓库。在两个地点i和j之间运输货物存在费用Cij,为求解旅行费用总和最小的运输路径,
admin
2021-01-13
31
问题
(2012年上半年上午试题63、64)某货车运输公司有一个中央仓库和n个运输目的地,每天要从中央仓库将货物运输到所有运输目的地,到达每个运输目的地一次且仅一次,最后回到中央仓库。在两个地点i和j之间运输货物存在费用C
ij
,为求解旅行费用总和最小的运输路径,设计如下算法:首先选择离中央仓库最近的运输目的地1,然后选择离运输目的地1最近的运输目的地2,……,每次在未访问过的运输目的地中选择离当前运输目的地最近的运输目的地,最后回到中央仓库。则该算法采用了______(63)算法设计策略,其时间复杂度为_____(64)。
(63)
选项
A、分治
B、动态规划
C、贪心
D、回溯
答案
C
解析
贪心算法不考虑整体情况,以当前情况为基础做出最优选择。很明显,题目中用到的是贪心算法。分治算法是将规模为n的问题分解为k个子问题,这些子问题相互独立,且与原问题相同,然后将子问题的解合并得到原问题的解。动态规划算法与分治算法类似,但分解后的子问题往往不是独立的。回溯法要在包含问题的所有解的解空间中,按照深度优先的策略,从根节点出发搜索解空间。
在选择路径时,首先选择离中央仓库最近的运输目的地1,需要将所有n个目的地到中央仓库的距离进行比较,选择最近的作为目的地1,相当于从n个数中选择一个最小数,此时比较了n-1次;然后选择离目的地1最近的目的地2,此时需要将其余n-1个目的地到目的地1的距离进行比较,相当于从n-1个数中选择一个最小数,此时比较了n-2次,以此类推,共需比较n-1+n-2+n-3+…+2+1=(n-1)(n-2)/2=(n
2
-3n+2)/2,算法的时间复杂度为Θ(n
2
)。
转载请注明原文地址:https://kaotiyun.com/show/yTCZ777K
本试题收录于:
软件设计师上午基础知识考试题库软考中级分类
0
软件设计师上午基础知识考试
软考中级
相关试题推荐
根据以下关于学校构成的说明回答问题1至问题3。【说明】学校中有若干系,每个系有若干班级和教研室,每个教研室有若干教员,其中有的教授和副教授各带有若干研究生;每个班有若干学生,每个学生选修若干课程,每门课可由若干学生选修。【问题1
企业信息整合、共享需要一个代表企业身份的信息,该信息应该具有唯一性和易管理性,上述表格中信息项(1)代表企业身份最合适。请将以下叙述中(2)~(5)空缺处的内容填写完整。随着WebService的成熟,现在的(2)(SOA)已经有所发
请认真阅读以下关于电子政务信息整合的叙述,根据要求回答问题1~问题4。[说明]公共服务、社会监督和宏观调控是我国政府的3个主要职能。实施电子政务建设,可以改善政府的公共服务质量,提高社会监管的效率和准确性,加强宏观经济调控的科学性。
图7-10中只有一个外部实体E1。使用[说明]中的词语,给出E1的名称。在进行系统分析与设计时,面向数据结构的设计方法(如Jackson方法)也被广泛应用。简要说明面向数据结构设计方法的基本思想及其适用场合。
阅读以下某图书管理系统的技术说明和数据流图,根据要求回答问题1~问题4。[说明]某图书管理系统的主要功能是图书管理和信息查询。对于初次借书的读者,系统自动生成读者号,并与读者基本信息(姓名、单位和地址等)一起写入读者文件。该系统的图
阅读以下说明和Java代码,将应填入(n)处的字句写在对应栏内。【说明】某绘图系统存在point、line、square三种图元,它们具有Shape接口,图元的类图关系如图13-12所示。现要将circle图元加入此绘图系统以实现功能扩充。已知
用回溯法求解此0—1背包问题,请填充下面伪代码中(1)~(4)处空缺。回溯法是一种系统的搜索方法。在确定解空间后,回溯法从根结点开始,按照深度优先策略遍历解空间树,搜索满足约束条件的解。对每一个当前结点,若扩展该结点已经不满足约束条件,则不再继续扩展。为
阅读下列函数说明和C代码,将应填入(n)处的字句写上。[说明]若要在N个城市之间建立通信网络,只需要N-1条线路即可。如何以最低的经济代价建设这个网络,是一个网的最小生成树的问题。现要在8个城市间建立通信网络,其问拓扑结构如图5-1所示
[说明]为了有效记录交通事故情况,欲设计一个交通事故记录系统。一辆汽车有一个唯一的“车牌号”,车主购买汽车时需要提供相关信息,包括身份证、姓名、年龄、性别、地址等。一个车主可以拥有多辆汽车,而一辆汽车只有一个车主。驾驶员不一定是车主,因此记
(2013年下半年下午试题二)阅读下列说明,回答问题1至问题3,将解答填入答题纸的对应栏内。【说明】某快递公司为了方便管理公司物品运送的各项业务活动,需要构建一个物品运送信息管理系统。【需求分析结果】(1)快递公司有
随机试题
关于T管护理叙述正确的是()
胸部CT扫描的适应证包括
对炎症细胞有趋化作用的补体裂解产物是
男,45岁。反复肝功能异常多年,尿少,双下肢水肿2年,加重2周。口服呋塞米20mg/d,1天来昏睡,呼之有反应,患者意识障碍最可能的原因是
导游带领游客到高原地区旅游,为预防他们发生高原反应,导游应提前告知游客()等。
“信息是与物质、意识并列的第三个更为广泛的概念”,这是()。
东汉时期杰出的科学家()在其《灵宪》一文中对月食现象做了经典的论述。
______tellsusthatthegovernmentwillgivesupporttoemployers,whoofferpart-timejobs?______saysthatmanyorganizations
Thereisnodoubtthatthe______ofthesegoodstotheothersiseasytosee.
A、Policeanddriver.B、Directorandactress.C、Performers.D、Colleagues.D
最新回复
(
0
)