首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
某货车运输公司有一个中央仓库和n个运输目的地,每天要从中央仓库将货物运输到所有运输目的地,到达每个运输目的地一次且仅一次,最后回到中央仓库。在两个地点i和j之间运输货物存在费用Gij,为求解旅行费用总和最小的运输路径,设计如下算法:首先选择离中央仓库最近的
某货车运输公司有一个中央仓库和n个运输目的地,每天要从中央仓库将货物运输到所有运输目的地,到达每个运输目的地一次且仅一次,最后回到中央仓库。在两个地点i和j之间运输货物存在费用Gij,为求解旅行费用总和最小的运输路径,设计如下算法:首先选择离中央仓库最近的
admin
2019-04-22
27
问题
某货车运输公司有一个中央仓库和n个运输目的地,每天要从中央仓库将货物运输到所有运输目的地,到达每个运输目的地一次且仅一次,最后回到中央仓库。在两个地点i和j之间运输货物存在费用G
ij
,为求解旅行费用总和最小的运输路径,设计如下算法:首先选择离中央仓库最近的运输目的地1,然后选择离运输目的地1最近的运输目的地2,…,每次在来访问过的运输目的地中选择离当前运输目的地最近的运输目的地,最后回到中央仓库。则该算法采用了
(1)
算法设计策略,其时间复杂度为
(2)
。
(2)
选项
A、
B、
C、
D、
答案
A
解析
贪心算法不考虑整体情况,以当前情况为基础做出最优选择。很明显,题目中用到的是贪心算法。分值算法是将规模为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*-3n+2)/2,算法的时间复杂度为
(n
2
)。
转载请注明原文地址:https://kaotiyun.com/show/ClRZ777K
本试题收录于:
软件设计师上午基础知识考试题库软考中级分类
0
软件设计师上午基础知识考试
软考中级
相关试题推荐
下面哪个设备可以转发不同VLAN之间的通信?(61)
一个项目为了修正一个错误而进行了变更。这个错误被修正后,却引起以前可以正确运行的代码出错。()最可能发现这一问题。
采用海明码进行差错校验,信息码字为1001011,为纠正一位错,则需要__________位冗余位。(2008年下半年试题)
在网络运行中,发现设备CPU长时间占用过高,经检查发现下图中的“Numberoftopologychanges”值频繁变化,可初步判断该故障由(48)导致,可能的原因是(49)。(49)
RIPv2对RIPvl协议的改进之一为路由器有选择地将路由表中的信息发送给邻居,而不是发送整个路由表。具体地说,一条路由信息不会被发送给该信息的来源,这种方案称为(25),其作用是(26)。(26)
主机甲向主机乙发送了一个TCP报文段,SYN字段为“1”,序列号字段的值为2000,若主机乙同意建立连接,则发送给主机甲的报文段可能为(22),若主机乙不同意建立连接,则(23)字段置“1”。(22)
进度安排的常用图形描述方法有Gantt图和PERT图。Gantt图不能清晰地描述(2):PERT图可以给出哪些任务完成后才能开始另一些任务。下图所示的PERT图中,事件6的最晚开始时刻是(3)。(3)
王某是某公司的软件设计师,完成某项软件开发后按公司规定进行软件归档,以下有关该软件的著作权的叙述中,正确的是(5)________________。
帧中继的地址格式中,表示虚电路标识符的是(15)。
根据这张通知书所提供的信息,设计了一个E-R模型,如图12-6所示。请将(n)处补充完整。将问题1中的E-R模型(图12-6)转换成4个关系数据模型,要求标注主码和外码。
随机试题
正常血细胞的过氧化物酶染色阳性最强的是
A.黄芪B.黄柏C.黄芩D.羚羊角资源处于衰竭状态的重要野生药材物种是()。
恶性肿瘤最早出现的症状是()
教师品质有时也是影响学生学习的重要因素,下列属于我国学生不喜欢的教师品质的是()。
A、 B、 C、 D、 D第一列的方块数每次增加1,第二列和第三列的方块数保持不变,按此规律选D。
0.5,1,2,5,17,107,()
阅读下列材料,谈谈如何理解教师主导作用,这位教师全面发挥主导作用了吗?某教师回到办公室说:“二年级二班的学生真笨,这堂课我连续讲了三遍,他们还是不会。我是发挥了教师的主导作用了,他们不会我有什么办法”。
[2003年]已知平面上三条不同直线的方程分别为l1:ax+2by+3c=0,l2:bx+2cy+3a=0,l3:cx+2ay+3b=0.试证这三条直线交于一点的充分必要条件为a+b+c=0.
Theplaintiffcouldonlyrecoverpaymentforherservicesiftherewasevidenceofanimpliedorexpresscontractto______herfo
Whenwasthelasttimeyousawafrog?Chancesare,ifyouliveinacity,youhavenotseenoneforsometime.Eveninwetarea
最新回复
(
0
)