(2012年上半年上午试题63、64)某货车运输公司有一个中央仓库和n个运输目的地，每天要从中央仓库将货物运输到所有运输目的地，到达每个运输目的地一次且仅一次，最后回到中央仓库。在两个地点i和j之间运输货物存在费用Cij，为求解旅行费用总和最小的运输路径，

admin2021-01-13 55

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

选项 A、分治
B、动态规划
C、贪心
D、回溯

答案C

解析贪心算法不考虑整体情况，以当前情况为基础做出最优选择。很明显，题目中用到的是贪心算法。分治算法是将规模为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://kaotiyun.com/show/yTCZ777K

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

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

软考中级

相关试题推荐

随机试题

最新回复(0)

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

软考中级

指出哪张图的哪些文件可以不必画出。数据流图4中缺少2条数据流，请直接在图中添加。

阅读以下关于某订单管理系统的技术说明、部分UML类图及Java程序，将Java程序中(1)～(5)空缺处的语句填写完整。[说明]某订单管理系统的部分UML类图如图5-16所示。在图5-16中，Product表示产品，Pro

图7-10中只有一个外部实体E1。使用[说明]中的词语，给出E1的名称。在进行系统分析与设计时，面向数据结构的设计方法(如Jackson方法)也被广泛应用。简要说明面向数据结构设计方法的基本思想及其适用场合。

图7-10中只有一个外部实体E1。使用[说明]中的词语，给出E1的名称。使用[说明]中的词语，给出图7-11中的数据存储D1～D4的名称。

在(1)空缺处填入所需的实体、联系及其属性，完成概念模型设计。对于[问题2]所完成的各实体关系模式，以下画线指出其主键和外键。

数据流图13-6中有两条数据流是错误的，请指出这两条数据流的起点和终点。数据流图13-7中缺少三条数据流，请指出这三条数据流的起点和终点。

政府及其所属部门滥用行政权力，强制经营者从事法律所禁止的排除或限制市场竞争的行为称为【】

上消化道出血

肉眼血尿反复发作，最常见的肾小球疾病是

在项目目标动态控制的纠偏措施中，调整管理职能分工属于()。

下列行为没有违法的是()。

下列筹资方式中，没有筹资费用，但是财务风险较小，资本成本较高的筹资方式是()。

某案的两名凶手在以下五人中，经过公安部门的侦查后得知：①只有甲是凶手，乙才是凶手②只要丁不是凶手，丙就不是凶手③或乙是凶手，或丙是凶手④丁没有戊为帮凶，就不会作案⑤戊没有作案时间这件案件中的凶手是：

我国现场检查的原则是()。