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

admin2019-07-12 32

问题某货车运输公司有一个中央仓库和n个运输目的地，每天要从中央仓库将货物运输到所有运输目的地，到达每个运输目的地一次且仅一次，最后回到中央仓库。在两个地点i和i之间运输货物存在费用C_ij，为求解旅行费用总和最小的运输路径，设计如下算法：首先选择离中央仓库最近的运输目的地l，然后选择离运输目的地l最近的运输目的地2，……，每次在来访问过的运输目的地中选择离当前运输目的地最近的运输目的地，最后回到中央仓库。则该算法采用了(63)算法设计策略，其时间复杂度为(64)。
(64)

选项 A、Θ(n²)
B、Θ(n)
C、Θ(nlgn)
D、Θ(1)

答案A

解析贪心算法不考虑整体情况，以当前情况为基础作出最优选择。很明显，题目中用到的是贪心算法。分值算法是将规模为n的问题分解为k个子问题，这些子问题相互独立，且与原问题相同，然后将子问题的解合并得到原问题的解。动态规划算法与分值算法类似，但分解后的子问题往往不是独立的。回溯法要在包含问题的所有解的解空间中，按照深度优先的策略，从根节点出发搜索解空间。
在选择路径时，首先选择离中央仓库最近的运输目的地1，需要将所有n个目的地到中央仓库的距离进行比较，选择最近的作为目的地1，相当于从n个数中选择一个最小数，此时比较了

转载请注明原文地址:https://kaotiyun.com/show/ybCZ777K

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

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

软考中级

相关试题推荐

随机试题

最新回复(0)

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

软考中级

关于OSPF拓扑数据库，下面选项中正确的是(38)。

在Linux操作系统中，命令()可以正确关闭系统防火墙。

下面能正确表示L2TP数据包的封装格式的是____________。

在无线局域网中，AP的作用是(1)。新标准IEEE802．11n提供的最高数据速率可达到(2)。(1)

VLAN中继协议(VTP)有不同的工作模式，其中能够对交换机的VLAN信息进行添加、删除、修改等操作，并把配置信息广播到其他交换机上的工作模式是()。

开放系统的数据存储有多种方式，属于网络化存储的是__________。(2009年下半年试题)

ATM网是一种高速网技术，其核心技术主要取决于__________技术。

下面4种编码方式中属于差分曼彻斯特编码的是(15)。

在Windows操作系统中，(37)文件可以帮助域名解析。

在CPU中，(3)可用于传送和暂存用户数据，为ALU执行算术逻辑运算提供工作区。

腹部损伤常见受损内脏依次是

左向右分流型先心病最常见的合并症是

宜作为膜剂成膜材料的是

对于三条跑道改、扩建机场工程，测点数量可分别布设（）个飞机噪声测点。

路基施工测量采用GPS时，GPS网的基本形式有()。

下列各项中，应当采用成本法进行后续计量的金融资产是()。

记忆较长材料时，中间部分记忆效果最差，这主要受到()干扰。

计算下列定积分：