2. 计算机
  3. 设如图5-6所示的是5个城市的航线图，每个结点表示1个城市，2个结点之间边的权值表示2个城市之间直达航线的票价(单位：元)。若某人打算旅游一个城市各一次，并且返回到出发点，则旅行的最低总票价为______元。

设如图5-6所示的是5个城市的航线图，每个结点表示1个城市，2个结点之间边的权值表示2个城市之间直达航线的票价(单位：元)。若某人打算旅游一个城市各一次，并且返回到出发点，则旅行的最低总票价为______元。

admin2018-04-25  52
问题 设如图5-6所示的是5个城市的航线图，每个结点表示1个城市，2个结点之间边的权值表示2个城市之间直达航线的票价(单位：元)。若某人打算旅游一个城市各一次，并且返回到出发点，则旅行的最低总票价为______元。
选项 A、875
B、1045
C、1285
D、1525
答案B
解析 这是一个求最短哈密尔顿回路的问题。因为该图只有5个结点，比较简单，只需使用观察法就能很快得出正确答案。首先注意的是，在本图中所有的“三角形”线路都满足三角形边长的规则：“任何两边的和大于第三边”，因此凡是有直通的航线，就不要中转。假设从图的最上方那个城市开始，首先选择189，然后选择379(因为279+209＞379)，再选择69，179，最后选择229，则结果为189+379+69+179+229=1045。
转载请注明原文地址:https://www.kaotiyun.com/show/XxLZ777K
本试题收录于： 系统分析师上午综合知识考试题库软考高级分类
0

系统分析师上午综合知识考试

软考高级

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