2. 自考
  3. 如图，在V1到V9九个居民小区铺设煤气管道，如何使管道总长最短。

如图，在V1到V9九个居民小区铺设煤气管道，如何使管道总长最短。

admin2017-01-21  17
问题 如图，在V1到V9九个居民小区铺设煤气管道，如何使管道总长最短。
选项
答案按照克鲁斯喀尔的算法很轻松得出答案。 克鲁斯喀尔法(又称避圈法)(1)每次选择剩余边中长度最小的。 (2)后选的边与已经选好的边不能构成回路，若构成则舍弃。 (3)重复(1)(2)，直到把所有边选完。 从V9开始逆推，和V9相连的有V4、V8和V3，先选择距离短的为U8和V8相连的有V5、V6、V7，选择距离短的V6，这样完成第一步，因为每一个结点都要考虑在内，反过来和V3相连的有V4、V6、V9，选择短的V4和V6，相连的有V5、V8、V3，选择短的V8，这样相互的结点考虑两次就可以找到最优路线。但足不能成圈，距离即为所有结点距离之和，最短为30。 [*]
解析
转载请注明原文地址:https://jikaoti.com/ti/6dWaFFFM
本试题收录于： 运筹学基础题库理工类分类
0

运筹学基础

理工类

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