某货车运输公司有一个中央仓库和n个运输目的地，每天要从中央仓库将货物运输到所有运输目的地，到达每个运输目的地一次且仅一次，最后回到中央仓库。在两个地点i和j之间运输货物存在费用Gij，为求解旅行费用总和最小的运输路径，设计如下算法：首先选择离中央仓库最近的

admin2019-04-22 30

问题某货车运输公司有一个中央仓库和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²)。

转载请注明原文地址:https://jikaoti.com/ti/G3f7FFFM

本试题收录于：软件设计师上午基础知识考试题库软考中级分类

软件设计师上午基础知识考试

软考中级

相关试题推荐

随机试题

最新回复(0)

软件设计师上午基础知识考试

软考中级

DMA工作方式下，在____________之间建立直接的数据通信。

一个项目为了修正一个错误而进行了变更。这个错误被修正后，却引起以前可以正确运行的代码出错。()最可能发现这一问题。

Intemet采用__________方式进行数据传输。

下图所示为一种数字签名方案，网上传送的报文是(43)，防止A抵赖的证据是(44)。 (44)

某公司网络的地址是192．168．192．0／20，要把该网络分成32个子网，则对应的子网掩码应该是(54)，每个子网可分配的主机地址数是(55)。

在异步通信中，每个字符包含1位起始位、7位数据位、1位奇偶位和1位终止位，每秒传送200个字符，采用DPSK调制，则码元速率为(1)，有效数据速率为(2)。(2)

X、Y为逻辑变量，与逻辑表达式等价的是__________。(2012年下半年试题)

阅读以下说明和Java代码，将应填入(n)处的字句写在答题纸的对应栏内。说明类Queue表示队列，类中的方法如下表所示。类Node表示队列中的元素；类EmptyQueueException给出了队列操作中的异常处理操作。Java代码

阅读下列C++程序和程序说明,将应填入(n)处的字句写在答题纸的对应栏内。【说明】构造最优二叉查找树。具有n个结点的有序序列a1,a2,…,an存在于数组元素a[1]、a[2],…,a[n]之中,a[0]未被使用。结点a1,a2

Everyonehasgottwopersonalities—theonethatisshowntotheworldandtheotherthatissecretandreal.Youdon’tshowyour

下列哪项不是处方书写时应当符合的规则

男，60岁，夜间突发右肢体活动障碍，语言不利。查体：血压170／95mmHg，发病前2周曾有“TIA”发作3次。除外出血性脑血管病，应首选

拟建项目进行投资估算时应该采用()。

可满足设备材料采购需要的建设工程设计文件是()。

保证合同不能为（）。

在一次工作总结大会上。张局长点名表扬了你，而和你同期入职的同事李峰却没有得到表扬，会上他突然对你说身体有点不舒服。要离开会场。此时你会怎么说?请现场模拟。

存款货币银行(商业银行为代表)与其他金融机构的根本区别在哪里?与其他金融机构相比，它与中央银行的关系又有什么不同?

按操作系统的分类，UNIX操作系统是()。

软件设计师上午基础知识考试

软考中级

DMA工作方式下，在____________之间建立直接的数据通信。

一个项目为了修正一个错误而进行了变更。这个错误被修正后，却引起以前可以正确运行的代码出错。()最可能发现这一问题。

Intemet采用__________方式进行数据传输。

下图所示为一种数字签名方案，网上传送的报文是(43)，防止A抵赖的证据是(44)。 (44)

某公司网络的地址是192．168．192．0／20，要把该网络分成32个子网，则对应的子网掩码应该是(54)________________，每个子网可分配的主机地址数是(55)________________。

在异步通信中，每个字符包含1位起始位、7位数据位、1位奇偶位和1位终止位，每秒传送200个字符，采用DPSK调制，则码元速率为(1)，有效数据速率为(2)。(2)

X、Y为逻辑变量，与逻辑表达式等价的是__________。(2012年下半年试题)

阅读以下说明和Java代码，将应填入(n)处的字句写在答题纸的对应栏内。说明类Queue表示队列，类中的方法如下表所示。类Node表示队列中的元素；类EmptyQueueException给出了队列操作中的异常处理操作。Java代码

阅读下列C++程序和程序说明,将应填入(n)处的字句写在答题纸的对应栏内。【说明】构造最优二叉查找树。具有n个结点的有序序列a1,a2,…,an存在于数组元素a[1]、a[2],…,a[n]之中,a[0]未被使用。结点a1,a2

Everyonehasgottwopersonalities—theonethatisshowntotheworldandtheotherthatissecretandreal.Youdon’tshowyour

下列哪项不是处方书写时应当符合的规则

男，60岁，夜间突发右肢体活动障碍，语言不利。查体：血压170／95mmHg，发病前2周曾有“TIA”发作3次。除外出血性脑血管病，应首选

拟建项目进行投资估算时应该采用()。

可满足设备材料采购需要的建设工程设计文件是()。

保证合同不能为（）。

在一次工作总结大会上。张局长点名表扬了你，而和你同期入职的同事李峰却没有得到表扬，会上他突然对你说身体有点不舒服。要离开会场。此时你会怎么说?请现场模拟。

存款货币银行(商业银行为代表)与其他金融机构的根本区别在哪里?与其他金融机构相比，它与中央银行的关系又有什么不同?

按操作系统的分类，UNIX操作系统是()。

某公司网络的地址是192．168．192．0／20，要把该网络分成32个子网，则对应的子网掩码应该是(54)，每个子网可分配的主机地址数是(55)。