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

admin2019-07-12 35

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

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

软考中级

在Linux中，要更改一个文件的权限设置可使用(32)________________命令。

在进行进度安排时，PERT图不能清晰地描述(1)，但可以给出哪些任务完成后才能开始另一任务。某项目X包含任务A、B、…、J，其PERT如下图所示(A=1表示该任务A的持续时间是1天)，则项目X的关键路路径是(2)。(2013年上半年试题)(2)

在进行进度安排时，PERT图不能清晰地描述(1)，但可以给出哪些任务完成后才能开始另一任务。某项目X包含任务A、B、…、J，其PERT如下图所示(A=1表示该任务A的持续时间是1天)，则项目X的关键路路径是(2)。(2013年上半年试题)(1)

下图为DARPA提供的公共入侵检测框架示意图，该系统由四个模块组成，其中模块①～④对应的正确名称为____________。

IEEE802．11标准采用的工作频段是___________。

在Linux中，可在()文件中修改Web服务器配置。

阅读以下说明和流程图(如图1所示)，回答问题1至问题4。【说明】本流程图是将中缀表示的算术表达式转换成后缀表示。如中缀表达式(A-(BC+D)E)/(F+G))的后缀表示为ABCD+E-FG+/为了方

利用存在的依赖关系构造一个图书馆的对象模型。张三到图书馆借阅一本书，两个月后，他把这本逾期的书返还给图书馆。画出这个场景的时序图。

工资支付保障制度是哪一确定工资法律途径的基本内容?()

影响企业成功开发新产品的因素有哪些?

Astudyofarthistorymightbeagoodwaytolearnmoreaboutaculturethanispossibletolearningeneralhistoryclasses.M

A．26%B．27%C．35%D．93%E．98%食物冷藏冷冻温度为0℃时，细菌的灭活率为

按照定额的编制程序和用途，建设工程定额可分为()。

习近平说“中国梦是民族的梦，也是每个中国人的梦。”为早日实现“中国梦”，我们一定要做到的三个“必须”有()。

Jeffhasthe______(习惯)oflisteningtomusicwhilereading.

随着科学技术的发展，人类已经制造出诸如醋纤维、基苯乙烯、合成橡胶等自然原本不存在的化合物，其数量已达数百万种。这一情况说明

下列选项(　　)不属于中国Internet互联管理单位。

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

软考中级

在Linux中，要更改一个文件的权限设置可使用(32)________________命令。

在进行进度安排时，PERT图不能清晰地描述(1)，但可以给出哪些任务完成后才能开始另一任务。某项目X包含任务A、B、…、J，其PERT如下图所示(A=1表示该任务A的持续时间是1天)，则项目X的关键路路径是(2)。(2013年上半年试题)(2)

在进行进度安排时，PERT图不能清晰地描述(1)，但可以给出哪些任务完成后才能开始另一任务。某项目X包含任务A、B、…、J，其PERT如下图所示(A=1表示该任务A的持续时间是1天)，则项目X的关键路路径是(2)。(2013年上半年试题)(1)

下图为DARPA提供的公共入侵检测框架示意图，该系统由四个模块组成，其中模块①～④对应的正确名称为____________。

IEEE802．11标准采用的工作频段是___________。

在Linux中，可在()文件中修改Web服务器配置。

阅读以下说明和流程图(如图1所示)，回答问题1至问题4。【说明】本流程图是将中缀表示的算术表达式转换成后缀表示。如中缀表达式(A-(B*C+D)*E)/(F+G))的后缀表示为ABC*D+E*-FG+/为了方

利用存在的依赖关系构造一个图书馆的对象模型。张三到图书馆借阅一本书，两个月后，他把这本逾期的书返还给图书馆。画出这个场景的时序图。

工资支付保障制度是哪一确定工资法律途径的基本内容?()

影响企业成功开发新产品的因素有哪些?

Astudyofarthistorymightbeagoodwaytolearnmoreaboutaculturethanispossibletolearningeneralhistoryclasses.M

A．26%B．27%C．35%D．93%E．98%食物冷藏冷冻温度为0℃时，细菌的灭活率为

按照定额的编制程序和用途，建设工程定额可分为()。

习近平说“中国梦是民族的梦，也是每个中国人的梦。”为早日实现“中国梦”，我们一定要做到的三个“必须”有()。

Jeffhasthe______(习惯)oflisteningtomusicwhilereading.

随着科学技术的发展，人类已经制造出诸如醋纤维、基苯乙烯、合成橡胶等自然原本不存在的化合物，其数量已达数百万种。这一情况说明

下列选项( )不属于中国Internet互联管理单位。

阅读以下说明和流程图(如图1所示)，回答问题1至问题4。【说明】本流程图是将中缀表示的算术表达式转换成后缀表示。如中缀表达式(A-(BC+D)E)/(F+G))的后缀表示为ABCD+E-FG+/为了方

下列选项(　　)不属于中国Internet互联管理单位。