首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
自考
如图，在V1到V9九个居民小区铺设煤气管道，如何使管道总长最短。
如图，在V1到V9九个居民小区铺设煤气管道，如何使管道总长最短。
admin
2017-01-21
18
问题
如图，在V
1
到V
9
九个居民小区铺设煤气管道，如何使管道总长最短。
选项
答案
按照克鲁斯喀尔的算法很轻松得出答案。 克鲁斯喀尔法(又称避圈法)(1)每次选择剩余边中长度最小的。 (2)后选的边与已经选好的边不能构成回路，若构成则舍弃。 (3)重复(1)(2)，直到把所有边选完。 从V
9
开始逆推，和V
9
相连的有V
4
、V
8
和V
3
，先选择距离短的为U
8
和V
8
相连的有V
5
、V
6
、V
7
，选择距离短的V
6
，这样完成第一步，因为每一个结点都要考虑在内，反过来和V
3
相连的有V
4
、V
6
、V
9
，选择短的V
4
和V
6
，相连的有V
5
、V
8
、V
3
，选择短的V
8
，这样相互的结点考虑两次就可以找到最优路线。但足不能成圈，距离即为所有结点距离之和，最短为30。 [*]
解析
转载请注明原文地址:https://kaotiyun.com/show/Qkjx777K
本试题收录于：
运筹学基础题库理工类分类
0
运筹学基础
理工类
相关试题推荐
关于急性心肌梗死患者进行溶栓治疗的相对禁忌证，下列说法正确的是【】
简述设计收集资料的方案前应考虑的问题。
选题过程中需要注意的问题()
女性，30岁，技术员。结婚5年与公婆关系处得不好，近3年来经常感到十分郁闷，总觉不开心但一直坚持上班，表现尚可。懒得做家务。重点护理目标【】
女性62岁中专文化已婚退休干部近三个月来说不清原因出现失眠、早醒、饮食差、体重明显减轻，做家务经常出错，近半个月加重，不愿意出门活动，在家总躺着，话少、来人看她也爱答不理，说自己乏力，得绝病了，活着没意思，不如死了，且不认为有病。因治
男性，32岁，公司职员，3年来无端怀疑自己不是父母亲生的，认为父母和妻子在自己的饭菜里下毒，认为自己的想法网上都知道了，为此恐惧紧张。经常失眠，有时整夜不睡，浑身大汗、心慌、憋气。患者人院一周后护士与患者沟通时应【】
“人均卫生费用”属于哪个与疾病及卫生政策有关的指标()
一个4位全加器如图1-7所示，当输入a3a2a1a0=0110，b3b2b1b0=0111时，则其输出的各进位信号c3c2c0=_________。
在长度为n的顺序表的表头插入一个元素时，其算法的时间复杂度是【】
下列函数的功能是求链表长度。请填空完成算法。structnode{charch；structnode*link；}；str(structnode*p){int①；whi
随机试题
肝中静脉()
Inthe1962movieLawrenceofArabia,onesceneshowsanAmericannewspaperreportereagerlysnappingphotosofmenlootingasa
A、脑干网状结构受压B、动眼神经受压C、海马沟被压D、环池阻塞或导水管闭塞E、四脑室受压小脑幕切迹疝患者的意识丧失是因为()
男性，70岁，脊柱手术后卧床2周，出现右侧小腿疼痛、紧束感，并逐渐出现水肿。预防该并发症的主要护理措施是
投资项目决策分析与评价阶段应考虑的外部环境方面可能存在的风险因素包括()。
自然人的民事行为能力因年龄(智力发育程度)或精神状态的差异，在法律上分别规定为有完全行为能力、()和无行为能力人。
在确定审计证据的可靠性时，下列表述中错误的是()。
甲商店为增值税一般纳税人，主要从事副食品批发、零售业务。2018年6月有关经营情况如下：(1)向枣农收购一批红枣，农产品收购发票上注明买价30000元。该批红枣一部分用于销售，一部分无偿赠送关联企业，一部分用于职工个人消费。(2)销售烟
给定资料1．有人撰文称：“以淘宝为代表的电子商务，正在一步一步摧毁实体经济。而造成这一切的罪魁祸首，就是互联网。”文中称：“淘宝的推出扼杀了中国很多产业的创新力。它造成了全国比价，进而无限压低利润空间，导致制造业凋零，‘中国创造’之路或将从此举步维艰。
f(χ1，χ2，χ3，χ4)＝XTAX的正惯性指数是2，且A2＝2A＝O，该二次型的规范形为_______．
最新回复
(
0
)
