设如图5-6所示的是5个城市的航线图，每个结点表示1个城市，2个结点之间边的权值表示2个城市之间直达航线的票价(单位：元)。若某人打算旅游一个城市各一次，并且返回到出发点，则旅行的最低总票价为______元。
- A875
- B1045
- C1285
- D1525
问题
设如图5-6所示的是5个城市的航线图，每个结点表示1个城市，2个结点之间边的
参考解析：
解析：这是一个求最短哈密尔顿回路的问题。因为该图只有5个结点，比较简单，只需使用观察法就能很快得出正确答案。首先注意的是，在本图中所有的“三角形”线路都满足三角形边长的规则：“任何两边的和大于第三边”，因此凡是有直通的航线，就不要中转。假设从图的最上方那个城市开始，首先选择189，然后选择379(因为279+209＞379)，再选择69，179，最后选择229，则结果为189+379+69+179+229=1045。
分类：其他
相关推荐
-
1、如图8-43（a）所示的UML类图描绘的是设计模式中的（1）模式。如图8-
如图8-43（a）所示的UML类图描绘的是设计模式中的（1）模式。如图8-43（b）所示的UML类图描述了该模式的一种应用，其中与图8-43（a）中的"Abstraction"对应的类是（2）。空白（2...
-
如图所示的展开图表示的是（）图。A合闸回路B分闸回路C中央信号回路D直流绝缘监察装置
-
3、编号1、2、3、4、5、6的6个城市的距离矩阵如表2所示，设推销员从1城出
编号1、2、3、4、5、6的6个城市的距离矩阵如表2所示，设推销员从1城出发，经过每个城市一次且仅一次，最后回到1城，选择适当的路线，推销员最短的行程是（）公里AA、75BB、78CC、80DD、100
-
4、如图所示的图形,其下边水平，下列几个坐标不正确的是()。
如图所示的图形,其下边水平，下列几个坐标不正确的是()。A从a到b绘制，(@500B从b到c绘制，(@500C从b到c绘制，(@500D从c到d绘制，(@500
-
将如图所示的E-R图转换成二维表，正确的是（）。ABCD
-
6、如图8-40（a）所示的UML类图描绘的是设计模式中的（1）模式。如图8-
如图8-40（a）所示的UML类图描绘的是设计模式中的（1）模式。如图8-40（b）所示的UML类图描述了该模式的一种应用，其中与图8-40（a）中的"Creator"对应的类是（2）。空白（2）处...