首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
(2012年上半年上午试题63、64)某货车运输公司有一个中央仓库和n个运输目的地,每天要从中央仓库将货物运输到所有运输目的地,到达每个运输目的地一次且仅一次,最后回到中央仓库。在两个地点i和j之间运输货物存在费用Cij,为求解旅行费用总和最小的运输路径,
(2012年上半年上午试题63、64)某货车运输公司有一个中央仓库和n个运输目的地,每天要从中央仓库将货物运输到所有运输目的地,到达每个运输目的地一次且仅一次,最后回到中央仓库。在两个地点i和j之间运输货物存在费用Cij,为求解旅行费用总和最小的运输路径,
admin
2021-01-13
29
问题
(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)XX图中遗漏了XX加工(或文件)流向XX加工(或文件)的XX数据流;(2)XX图中XX加工遗漏了XX输入(或输出)数据流。
阅读下列说明和数据流图,回答问题1-问题3。【说明】某医院收费系统的主要功能是收取病人门诊的各项费用。系统的收费功能分为3个方面:病历收费、挂号收费和根据处方单内容收取检查或药物费用。1.病
在程序流程图(见图6-21)中,若要某个房间I被选中,则需要满足什么条件?如果等级为r的房间每人每天的住宿费为RATE(r),其中RATE为数组,则为使该算法在输出每个候选的房间号RM(J)后,再输出这批散客每天所需的总住宿费DAYRENT(J),在程
识别关联的多重度是面向对象建模过程中的一个重要步骤。请根据说明中给出的描述,将如图6-18所示中(1)~(6)空缺处的内容填写完整。该电子商务公司还对外开放一项出租图书和唱碟的业务。由于业务需求,该公司委托软件开发公司A开发一套信息管理系统。该系统将记
请用100字以内的文字简要说明逻辑数据流图(LogicalDataFlowDiagram)和物理数据流图(PhysicalDataFlowDiagram)之间的主要差别。该图书管理系统的第0层DFD图(见图2-22)有两条数据流是错误的,请
阅读下列说明与相关类图,填空并回答问题。【说明】装饰者模式动态地给一个对象添加一些额外的职责,就扩展功能而言,该模式比生成子类方式更加灵活。装饰模式的提出有助于解决滥用继承的问题。例如,一个名叫星巴兹(Starbuzz)的咖啡连锁
阅读下列函数说明和C代码,将应填入(n)处的字句写上。[说明]若要在N个城市之间建立通信网络,只需要N-1条线路即可。如何以最低的经济代价建设这个网络,是一个网的最小生成树的问题。现要在8个城市间建立通信网络,其问拓扑结构如图5-1所示
分析车辆的状态和事件,指出图2-1中的(1)、(2)、(3)、(4)分别是什么?指出UML中活动图的含义,并说明活动图和状态图的区别与联系。
阅读下列函数说明和C代码,[说明]所谓货郎担问题,是指给定一个无向图,并已知各边的权,在这样的图中,要找一个闭合回路,使回路经过图中的每一个点,而且回路各边的权之和最小。应用贪婪法求解该问题,程序先计算由各点构成的所有边的长度(
阅读下列说明和C代码,回答问题1至问题3,将解答写在答题纸的对应栏内。【说明】对有向图进行拓扑排序的方法是:(1)初始时拓扑序列为空:(2)任意选择一个入度为0的顶点,将其放入拓扑序列中,同时从图中删除该顶点以及从该顶点出发的弧;(3)重复(2),
随机试题
下列各句中画线词使用恰当的一项是:
下列关于衣原体网状体的叙述正确的是
在进行口腔健康调查前,技术组专家告诫调查人员,出现信息偏倚性的重要原因是()
案情:楚某系原浙江省顺民县人大常委会委员。2006年4月25日,楚某到温州市龙湾区参加龙湾区人大常委会召开的“横向联系会议”。26日晚9时许,楚某独自一人来到温州市金江路,在大榕树下石凳处遇到了暗娼李某。楚某主动与李某搭讪,问明其身份和嫖宿价格后,将李某带
混凝土小型空心砌块、蒸压加气混凝土砌块等轻质墙体,当墙长大于5m时,应增设间距不大于3m的构造柱;每层墙高的中部应增设高度为120mm,与墙体同宽的混凝土腰梁,砌体无约束的端部必须增设(),预留的门窗洞口应采取()加强。
根据证券法律制度的规定,下列选项中有权发行优先股的有()。
A、 B、 C、 D、 D
2014年12月31日,上海外滩发生踩踏事件引起全国各地广泛关注。假如你市定于正月十五在市郊公园举办一场大型群众性活动——“猜灯谜,迎新春”主题灯会,由你负责警力配备。你认为在下列选项中,不用布置过多警力的地点为()。
A、Youngdogs.B、Dogsthatcatchbirds.C、Dogs.A1月12日的日记里面出现了“puppies”这个词,后面有破折号,想必破折号后面的JigsandReels是它们的名字了。而且从这天的日记里我们知道它们吃的
OnFoodSafety,aLongListbutLittleMoneyA)Thissummertherehasbeenadrumbeatoffood-relatedillnesses.Strawberries
最新回复
(
0
)