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

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

admin2018-10-14  3
问题 编号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算法的基本思路是：若序列(vs，v1，v2，…，vt—1，vt)是从vs到vt的最短路径，则序列(vs，v1，v2，…，vt—1)必为从vs到vt—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

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

软考高级

相关试题推荐
随机试题
最新回复(0)