首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
某货车运输公司有一个中央仓库和n个运输目的地,每天要从中央仓库将货物运输到所有运输目的地,到达每个运输目的地一次且仅一次,最后回到中央仓库。在两个地点i和i之间运输货物存在费用Cij,为求解旅行费用总和最小的运输路径,设计如下算法:首先选择离中央仓库最近的
某货车运输公司有一个中央仓库和n个运输目的地,每天要从中央仓库将货物运输到所有运输目的地,到达每个运输目的地一次且仅一次,最后回到中央仓库。在两个地点i和i之间运输货物存在费用Cij,为求解旅行费用总和最小的运输路径,设计如下算法:首先选择离中央仓库最近的
admin
2019-07-12
12
问题
某货车运输公司有一个中央仓库和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://jikaoti.com/ti/lrG7FFFM
本试题收录于:
软件设计师上午基础知识考试题库软考中级分类
0
软件设计师上午基础知识考试
软考中级
相关试题推荐
在进行域名解析过程中,由______获取的解析结果耗时最短。
在快速以太网物理层标准中,使用两对五类无屏蔽双绞线的是__________。(2009年上半年试题)
在Linux操作系统中,命令()可以正确关闭系统防火墙。
DNS正向搜索区的功能是将域名解析为IP地址,WindowsXP系统中用于测试该功能的命令是____________。
不同VLAN的数据帧必须通过__________传输。
在WindowsServer2003环境中有本地用户和域用户两种用户。其中本地用户信息存储在(46)。
FTP提供了丰富的命令,用来更改本地计算机工作目录的命令是(36)。
某单位局域网配置如下图所示,PC2发送到Internet上的报文源IP地址为(40)。
阅读以下说明和数据流图,回答问题1~问题3。[说明]职工信息管理系统是用于对职工相关信息进行检索、统计、工资管理、内部调动管理等的系统。利用该系统,人事科可以对本单位职工信息进行管理,根据不同命令对信息进行增、删、改、内部调动,打印人事表格,进行
国际标准MPEG—Ⅱ采用了分层的编码体系,提供了4种技术,它们是(46)。数字音频采样和量化过程所用的主要硬件是:(47)。AC-3数字音频编码提供了5个声道的频率范围是:(48)。要把一台普通的计算机变成多媒体计算机要解决的关键技术是:(
随机试题
瓦窑堡会议提出的新政策是()
标准库函数fputs(p1,p2)的功能是()。
甲亢青年女性,心率106次/min,血压108/72mmHg,应属于
下列与腹水有关的体征不包括
在体内合成胆固醇的直接原料是
孟子从______论阐述其人性观点,荀子从______论阐述其人性观点。
国民经济核算中的经济领土是指由政府管理的地理领土组成,在这个地理领土内,人员、商品、资本可以自由流动。根据以上定义,试判断下列不属于中国经济领土的是()
Imagineaworldinwhichchildrenwouldbetherulersandcoulddecidenotonlytheoutcomeofeachandeveryoccurrence,butal
Oneofthemosteminentofpsychologists,ClarkHull,claimedthattheessenceofreasoningliesintheputtingtogetheroftwo
【B1】【B3】
最新回复
(
0
)