编号1、2、3、4、5、6的6个城市的距离矩阵如下表所示。设推销员从1城出发，经过每个城市一次且仅一次，最后回到1城。选择适当的路线，推销员最短的行程是( )公里。

admin2018-10-14 29

问题编号1、2、3、4、5、6的6个城市的距离矩阵如下表所示。设推销员从1城出发，经过每个城市一次且仅一次，最后回到1城。选择适当的路线，推销员最短的行程是( )公里。

选项 A、75
B、78
C、80
D、100

答案C

解析这是一个旅行商问题(Traveling Salesman Problem，TSP)，也叫旅行推销员问题、货郎担问题，简称为TSP问题。
TSP问题属于NP完全问题(NP—Complete)，是世界七大数学难题之一。NP(Nondeteministic Polvnomial)，即多项式复杂程度的非确定性问题。
注意，这是一张有向图，例如，从1到2的距离是12公里，而从2到1的距离是10公里。
这道题的真正难点在于，标准的TSP算法，对于考场上只有纸和笔的考生来说，太过复杂而无法施用。
实践证明，在Dijkstra最短路径算法的思想指引下，绘图，然后手工进行路径探索是考场上最有效的办法。
Dijkstra算法的基本思路是：若序列(v_s，v₁，v₂，…，v_t—1，v_t)是从v_s到v_t的最短路径，则序列(v_s，v₁，v₂，…，v_t—1)必为从v_s到v_t—1的最短路径。
出发时从1到2最近，回来时从3到1最短，4到3最短，5到4最短，6到5最短。
最短路线是：1→3→4→5→6→2→1，路程=23+4+10+12+2l+10=80公里。
有同学选B，路线如下：1→2→3→4→5→6→2→1，路程=12+9+4+10+12+21+10=78公里，错了，TSP问题要求经过每个城市一次且仅一次。

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

本试题收录于：信息系统项目管理师上午综合知识考试题库软考高级分类

信息系统项目管理师上午综合知识考试

软考高级

相关试题推荐

随机试题

最新回复(0)

编号1、2、3、4、5、6的6个城市的距离矩阵如下表所示。设推销员从1城出发，经过每个城市一次且仅一次，最后回到1城。选择适当的路线，推销员最短的行程是( )公里。

信息系统项目管理师上午综合知识考试

软考高级

甲公司支出20万元购买了某市场预测信息，由于此信息的采纳，甲公司多得到了100万元的利润，对甲公司而言，这个市场预测信息的(35)。

数据处理流水线如图1-4所示。若每隔△t流入一个数据，连续流入四个数据，则该流水线的实际吞吐率为(68)。

软件测试是为了发现错误而执行程序的过程。检验软件是否满足用户需求的测试称为(114)。(115)是维护中常用的方法，其目的是检验修改所引起的副作用。黑盒测试法主要根据(116)来设计测试用例。

一般来说，在软件维护过程中，大部分工作是由(49)引起的。在软件维护的实施过程中，为了正确、有效地修改程序，需要经历以下三个步骤：分析和理解程序、修改程序和(50)。(51)的修改不归结为软件的维护工作。

在密码学中，单向Hash函数具有(48)所描述的特性。

宝钢的激励机制是以以下哪一理论为基础的?

下列哪项操作的后果无法达到良好的抗力形

治疗外科低血容量性休克的基本措施是补充血容量，一般宜首选

凡在居民密集区进行强噪声施工作业时，要严格控制施工作业时间，晚间作业不超过(　　)时，早晨作业不早于(　　)时。

下列施工成本材料费的控制中，可以影响材料价格的因素是()。

根据我国《合同法》的规定，当事人对合同变更的内容约定不明确的，(　　)。

杜威所主张的教育思想被称作是()(淄博文昌湖)

TodayistheanniversaryofthatafternooninAprilayearagothatIfirstsawthestrangeandappealingdollinthewindowof

Thegovernmentistobanpaymentstowitnessesbynewspapersseekingtobuyuppeopleinvolvedinprominenteases【C1】______the

Successoftendependsonyourperformanceataninterview.Forthosewhoarewellprepared,itcanbeapositiveexperience,and

编号1、2、3、4、5、6的6个城市的距离矩阵如下表所示。设推销员从1城出发，经过每个城市一次且仅一次，最后回到1城。选择适当的路线，推销员最短的行程是( )公里。

信息系统项目管理师上午综合知识考试

软考高级

甲公司支出20万元购买了某市场预测信息，由于此信息的采纳，甲公司多得到了100万元的利润，对甲公司而言，这个市场预测信息的(35)。

数据处理流水线如图1-4所示。若每隔△t流入一个数据，连续流入四个数据，则该流水线的实际吞吐率为(68)。

软件测试是为了发现错误而执行程序的过程。检验软件是否满足用户需求的测试称为(114)。(115)是维护中常用的方法，其目的是检验修改所引起的副作用。黑盒测试法主要根据(116)来设计测试用例。

一般来说，在软件维护过程中，大部分工作是由(49)引起的。在软件维护的实施过程中，为了正确、有效地修改程序，需要经历以下三个步骤：分析和理解程序、修改程序和(50)。(51)的修改不归结为软件的维护工作。

在密码学中，单向Hash函数具有(48)所描述的特性。

宝钢的激励机制是以以下哪一理论为基础的?

下列哪项操作的后果无法达到良好的抗力形

治疗外科低血容量性休克的基本措施是补充血容量，一般宜首选

凡在居民密集区进行强噪声施工作业时，要严格控制施工作业时间，晚间作业不超过( )时，早晨作业不早于( )时。

下列施工成本材料费的控制中，可以影响材料价格的因素是()。

根据我国《合同法》的规定，当事人对合同变更的内容约定不明确的，( )。

杜威所主张的教育思想被称作是()(淄博文昌湖)

TodayistheanniversaryofthatafternooninAprilayearagothatIfirstsawthestrangeandappealingdollinthewindowof

Thegovernmentistobanpaymentstowitnessesbynewspapersseekingtobuyuppeopleinvolvedinprominenteases【C1】______the

Successoftendependsonyourperformanceataninterview.Forthosewhoarewellprepared,itcanbeapositiveexperience,and

凡在居民密集区进行强噪声施工作业时，要严格控制施工作业时间，晚间作业不超过(　　)时，早晨作业不早于(　　)时。

根据我国《合同法》的规定，当事人对合同变更的内容约定不明确的，(　　)。