首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
(2012年上半年上午试题63、64)某货车运输公司有一个中央仓库和n个运输目的地,每天要从中央仓库将货物运输到所有运输目的地,到达每个运输目的地一次且仅一次,最后回到中央仓库。在两个地点i和j之间运输货物存在费用Cij,为求解旅行费用总和最小的运输路径,
(2012年上半年上午试题63、64)某货车运输公司有一个中央仓库和n个运输目的地,每天要从中央仓库将货物运输到所有运输目的地,到达每个运输目的地一次且仅一次,最后回到中央仓库。在两个地点i和j之间运输货物存在费用Cij,为求解旅行费用总和最小的运输路径,
admin
2021-01-13
26
问题
(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。【说明】A公司决定开发一套公共交通自动售票系统,系统要求如下所述。(1)乘客能按以下3步操作购票:选定目的地,投入钱币,获得一张票。(2)并且仅当乘客选定目的地后,系统才接收投钱
在程序流程图(见图6-21)中,若要某个房间I被选中,则需要满足什么条件?如果限制该算法最多输出K个可供选择的房间号,则在程序流程图(见图6-21)中“I>N”(a所指向的判断框中)应修改为(4)。
阅读以下函数说明和C代码,将C程序中(1)~(5)空缺处的语句填写完整。[说明]函数intToplogical(LinkedWDigraphG)的功能是对图G中的顶点进行拓扑排序,并返回关键路径的长度。其中,图G表示一个具有n个顶点的A
阅读下列C++程序和程序说明,将应填入(n)处的字句写在对应栏内。【说明】C++语言本身不提供对数组下标越界的判断。为了解决这一问题,在程序6中定义了相应的类模板,使得对厂任意类型的二维数组,可以在访问数组元素的同时,对行下标和列下标进行越
请用100字以内的文字简要说明逻辑数据流图(LogicalDataFlowDiagram)和物理数据流图(PhysicalDataFlowDiagram)之间的主要差别。该图书管理系统的第0层DFD图(见图2-22)有两条数据流是错误的,请
请将图3-25中的(1)~(3)空缺处的内容填写完整。假设有6个作业job1,job2,…,job6;完成作业的收益数组p=(p[1],p[2],p[3],p[4],p[5],p[6])=(90,80,50,30,20,10);每个作业
阅读以下某前台销售子系统的技术说明和UML图,根据要求回答问题1~问题4。[说明]某超市管理系统的前台销售子系统以最基本的方式处理销售业务。系统的功能需求如下:①记录每种商品的编号、单价和现有数量;②为顾客选购的商品计价、收
[说明]为了有效记录交通事故情况,欲设计一个交通事故记录系统。一辆汽车有一个唯一的“车牌号”,车主购买汽车时需要提供相关信息,包括身份证、姓名、年龄、性别、地址等。一个车主可以拥有多辆汽车,而一辆汽车只有一个车主。驾驶员不一定是车主,因此记
(2013年下半年下午试题二)阅读下列说明,回答问题1至问题3,将解答填入答题纸的对应栏内。【说明】某快递公司为了方便管理公司物品运送的各项业务活动,需要构建一个物品运送信息管理系统。【需求分析结果】(1)快递公司有
随机试题
TheName"UnitedNations"Thename"UnitedNations"was【C1】______(probable)devisedbyU.S.【C2】______(preside)FranklinD.
为防止原文档损坏,Excel2010提供创建文档的备份副本的策略,可在每次保存文件时生成一个扩展名为wbk的副本文件。
“文章的布局也就是一种阵势,每一段就是一个队伍,摆在最得力的地位才可以发生最大效用”,这句话的修辞方法是
下列关于溃疡性结肠炎的肠外表现中,随肠炎控制或结肠切除后可以缓解或恢复的是
下列关于尸检说法错误的是
患者男性,36岁,工人,在车间工作时被机器扎伤右前臂来急诊。注射破伤风抗毒素预防破伤风的机制是
孙某的以下行为,行为无效的是?
某施工单位承包了一项通信局站的电源系统安装工程,施工单位编制了施工组织计划,其中资源配备计划包括机具及仪表使用计划、材料需求计划;电源系统的接地系统有交流接地系统、工作接地系统、保护接地系统和防雷接地系统。工程完工后,施工单位编制了竣工材料,包括竣工图、
个人所购商用房为商住两用房的,贷款额度不得超过所购商用房价值的()。
设函数z=f(x,y)在点(1,1)处可微,且f(1,1)=1,φ(x)=f(x,f(x,x)).求φ3(3)|x=1.
最新回复
(
0
)