首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
某货车运输公司有一个中央仓库和n个运输目的地,每天要从中央仓库将货物运输到所有运输目的地,到达每个运输目的地一次且仅一次,最后回到中央仓库。在两个地点i和i之间运输货物存在费用Cij,为求解旅行费用总和最小的运输路径,设计如下算法:首先选择离中央仓库最近的
某货车运输公司有一个中央仓库和n个运输目的地,每天要从中央仓库将货物运输到所有运输目的地,到达每个运输目的地一次且仅一次,最后回到中央仓库。在两个地点i和i之间运输货物存在费用Cij,为求解旅行费用总和最小的运输路径,设计如下算法:首先选择离中央仓库最近的
admin
2019-07-12
15
问题
某货车运输公司有一个中央仓库和n个运输目的地,每天要从中央仓库将货物运输到所有运输目的地,到达每个运输目的地一次且仅一次,最后回到中央仓库。在两个地点i和i之间运输货物存在费用C
ij
,为求解旅行费用总和最小的运输路径,设计如下算法:首先选择离中央仓库最近的运输目的地l,然后选择离运输目的地l最近的运输目的地2,……,每次在来访问过的运输目的地中选择离当前运输目的地最近的运输目的地,最后回到中央仓库。则该算法采用了(63)算法设计策略,其时间复杂度为(64)。
(64)
选项
A、Θ(n
2
)
B、Θ(n)
C、Θ(nlgn)
D、Θ(1)
答案
A
解析
贪心算法不考虑整体情况,以当前情况为基础作出最优选择。很明显,题目中用到的是贪心算法。分值算法是将规模为n的问题分解为k个子问题,这些子问题相互独立,且与原问题相同,然后将子问题的解合并得到原问题的解。动态规划算法与分值算法类似,但分解后的子问题往往不是独立的。回溯法要在包含问题的所有解的解空间中,按照深度优先的策略,从根节点出发搜索解空间。
在选择路径时,首先选择离中央仓库最近的运输目的地1,需要将所有n个目的地到中央仓库的距离进行比较,选择最近的作为目的地1,相当于从n个数中选择一个最小数,此时比较了
转载请注明原文地址:https://kaotiyun.com/show/ybCZ777K
本试题收录于:
软件设计师上午基础知识考试题库软考中级分类
0
软件设计师上午基础知识考试
软考中级
相关试题推荐
在进行域名解析过程中,由______获取的解析结果耗时最短。
DHCP服务器给PC1分配IP地址时,默认网关地址是202.117.110.65/27,则PC1的地址可能是___________。
在下面4种病毒中,__________可以远程控制网络中的计算机。(2009年下半年试题)
下面能正确表示L2TP数据包的封装格式的是____________。
以下用于在网络应用层和传输层之间提供加密方案的协议是(36)。
某网络工程计划图如下所示,边上的标记为任务编码及其需要的完成时间(天),则整个工程的工期为(10)。
在Windows操作系统中,(37)文件可以帮助域名解析。
按照IEEE802.1d协议,当交换机端口处于__________状态时,既可以学习MAC帧中的源地址,又可以把接收到的MACI帧转发到适当的端口。(2010年上半年试题)
无线局域网标准IEEE 802.11i提出了新的TKIP协议来解决(66)中存在的安全隐患。
阅读以下说明和数据流图,回答问题1~3问题。[说明]干部信息管理系统(CMIS)是用于对干部信息进行管理的特定系统。利用该系统,干部科可以对本单位干部信息进行管理,根据不同命令对信息进行增、删、改、内部调动,打印人事表格,进行统计、检索。干
随机试题
可反映肝硬化患者肝功能的血清检查是()
对个人在初次分配过程中所获得的收人进行再调节的必要性在于()。
应用总流能量方程时,过流断面应选择()。
询价交易中,交易商可以匿名或实名方式申报。()
swim(现在分词)_______read(过去式)_______
WehavedoneallwecouldandnowourcherishedprojectisatthemercyofournewCEO.
JamesMartin认为,企业的业务活动过程可以由一个独立的部门来完成,也可以由若干个部门来共同完成,而不论如何,业务活动过程总是()。
ぜひ京都へいらっしやってください。私が________。
HowtoLovetheWorldAsItIs?[A]Itstruckmerecentlythatalotofpeoplethinktheyknowwhat’swrongwiththisworld,and
Oneofthethreemajorcommercialnetworks,CBSwereorganizedin1928whenitsfounderWilliam【M1】___________.Pal
最新回复
(
0
)