首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
(2012年上半年上午试题63、64)某货车运输公司有一个中央仓库和n个运输目的地,每天要从中央仓库将货物运输到所有运输目的地,到达每个运输目的地一次且仅一次,最后回到中央仓库。在两个地点i和j之间运输货物存在费用Cij,为求解旅行费用总和最小的运输路径,
(2012年上半年上午试题63、64)某货车运输公司有一个中央仓库和n个运输目的地,每天要从中央仓库将货物运输到所有运输目的地,到达每个运输目的地一次且仅一次,最后回到中央仓库。在两个地点i和j之间运输货物存在费用Cij,为求解旅行费用总和最小的运输路径,
admin
2021-01-13
43
问题
(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
软件设计师上午基础知识考试
软考中级
相关试题推荐
阅读下列C++程序和程序说明,将应填入(n)处的字句写在答题纸的对应栏内。【说明】构造最优二叉查找树。具有n个结点的有序序列a1,a2,…,an存在于数组元素a[1]、a[2],…,a[n]之中,a[0]未被使用。结点a1,a2
阅读下列说明和有关图表,回答问题1至问题3。【说明】A公司决定开发一套公共交通自动售票系统,系统要求如下所述。(1)乘客能按以下3步操作购票:选定目的地,投入钱币,获得一张票。(2)并且仅当乘客选定目的地后,系统才接收投钱
需求分析是一个包括创建和维持系统需求文档所必需的一切活动的过程。一个通用的需求分析过程模型如图6-16所示,请从以下供选择的答案中选择合适的内容填写到图6-16中相应的位置中。[供选择的答案]A.用户需求和功能需求B.需求
阅读以下技术说明以及Java程序,将Java程序中(1)~(5)空缺处的语句填写完整。[说明]用创建Thread类的子类的方法实现多线程,判断一个数是否是素数。如果是,打印“是素数”,如果不是,则打印“不是素数”,如果没有参数输入,显示“
数据流图13-6中有两条数据流是错误的,请指出这两条数据流的起点和终点。数据流图13-7中缺少三条数据流,请指出这三条数据流的起点和终点。
阅读以下标准书号校验码的技术说明和程序流程图,根据要求回答问题1至问题3。[说明]为实现图书的国际统一编码,便于实现计算机化的图书管理,每本正式出版的图书都印有国际标准书号。标准书号由“ISBN”、10个数字(0~9)组成,其格式如下。
[说明]为了有效记录交通事故情况,欲设计一个交通事故记录系统。一辆汽车有一个唯一的“车牌号”,车主购买汽车时需要提供相关信息,包括身份证、姓名、年龄、性别、地址等。一个车主可以拥有多辆汽车,而一辆汽车只有一个车主。驾驶员不一定是车主,因此记
[说明]为了有效记录交通事故情况,欲设计一个交通事故记录系统。一辆汽车有一个唯一的“车牌号”,车主购买汽车时需要提供相关信息,包括身份证、姓名、年龄、性别、地址等。一个车主可以拥有多辆汽车,而一辆汽车只有一个车主。驾驶员不一定是车主,因此记
(2013年上半年下午试题二)阅读下列说明,回答问题1至问题3,将解答填入答题纸的对应栏内。【说明】某电视台拟开发一套信息管理系统,以方便对全台的员工、栏目、广告和演播厅等进行管理。【需求分析】(1)系统需要维护全台
随机试题
LeicesterSocietyofArts—121stArtsFestivalGuidetoEventsAllevents
橘皮散主要用于
肝癌的组织学类型,最多见的是
医嘱“安定5mg,sos”,护士正确执行该医嘱的方法是
工程建设项目设计招标的评标因素包括技术因素、商务因素、经济因素三个方面,其中工程建设项目设计招标的评标经济因素一般包括()。
导游讲解“虚实结合法”中的“虚”指的是与景观有关的()。
科学发展观的根本方法是()。
Fordecades,postersdepictingrabbitswithinflamed,reddenedeyessymbolizedcampaignsagainstthetestingofcosmeticsonani
LookatparagraphsC,D,andEand,usingtheinformationinthepassage,completetheflowchartbelow.Writeyouranswersinb
Sincethedawnofe-mail,usingsarcasmindigitalcommunicationhascreatedstrifeandconfusionbetweenfriends,colleaguesan
最新回复
(
0
)