首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
自考
设u1，u2u3，u4，u5各点之间的距离表如下： 求由某一点出发，遍历每个点各一次，最后又返回出发点的最短路径。
设u1，u2u3，u4，u5各点之间的距离表如下： 求由某一点出发，遍历每个点各一次，最后又返回出发点的最短路径。
admin
2015-01-12
32
问题
设u
1
，u
2
u
3
，u
4
，u
5
各点之间的距离表如下：
求由某一点出发，遍历每个点各一次，最后又返回出发点的最短路径。
选项
答案
(1)距离矩阵的各行分别减去该行的最小数，各列也分别减去该列的最小数得：[*] (2)求最优路径： (i)从第一行开始依次检查，找出只有一个0元素没有加标记的行，给这个0元素加标记“*”，与这个加标记“0”同列的0元素全划去。重复此过程，直到每一行没有未加标记的0元素或至少有两个未加标记的0。(ii)从第一列开始依次检查各列，找出只有一个未加标记的0元素的列，将这个0元素加上标记“*”，并将与这个“0”同行的0元素全划去。重复此过程，直到每一列没有尚未加标记的0或者至少有两个未加标记的0元素。(iii)重复(i)，(ii)，直到矩阵中没有未加标记的0元素为止。[*] 由上面的矩阵可以看出：v
1
→v
2
v
2
→v
4
，v
4
→v
1
，v
3
→v
5
，v
5
→v
3
总距离为：2+4+2+2+5=15 (3)打开节点个数少的环路，令d
35
=∞或d
53
=∞，调整过程如下：(i)令d
35
=∞，[*] 可得：v
1
→v
2
→v
5
→v
3
→v
4
→v
1
无环路，于是总距离为：2+5+3+2+5=17(ii)令d
53
=∞，得[*] 得路径v
1
→v
2
→v
1
，v
3
→v
5
→v
4
→v
3
总路径为：2+3+2+5+6=18若再打开节点最少得环路求解，其点距离必大于或等于18，故无需再计算了。所以最优路径为：v
1
→v
2
→v
5
→v
3
→v
4
→v
1
总距离为17。
解析
转载请注明原文地址:https://kaotiyun.com/show/LSVx777K
本试题收录于：
物流数学题库理工类分类
0
物流数学
理工类
相关试题推荐
算法的时间复杂度与下列哪些因素有关【】
系统从一种稳定状态达到另一种稳定状态所需的时间称为_________。
IP地址具有固定规范的格式，一个IPv4也址的二进制位数为【】
IEEE802．11协议标准规定了WLAN的最小单位为基本服务集(BSS)，其中包括【】个AP。
______是由IBM公司所开发的网络管理综合平台，能够为用户提供强大的网络管理功能。
在人事管理信息系统的输入设计中，为了保证年龄数据的正确性，规定输入的年龄应在30～50之间，如果输入的数据超出此范围，则认为是错误的，这种数据校验方式属于()
为保证在规定时间内完成项目的管理是()
PDCA循环在质量管理中得到了广泛的应用，P、D、C、A分别代表计划、执行、检查和________。
在题37的网络图上确定关键路线并用双线(或粗黑线)表示出来，指明总工期以及A、B、C、D四项活动的最早开始时间。
随机试题
下列关于传播学经验学派与批判学派的说法不正确的是
A．梨形心B．靴形心C．烧瓶形心D．普大形心E．缩窄形心二尖瓣狭窄()
最可能的诊断是本例免疫球蛋白分型肯定不是
重病后的恢复期多属于病后转为迁延性或慢性病症的称为
颧颞部软组织出血，若采用压迫止血，应该压迫的动脉是
根据《中华人民共和国药品管理法实施条例》，实行政府定价或政府指导价的药品是
在中国境内无住所,但居住满1年而未超过5年的个人,其来源于中国境外的所得,经主管税务机关批准,可以只就由中国境内公司，企业以及其他经济组织或个人支付的部分缴纳个人所得税。()
2011年是中国共产党成立90周年。下面是几个关于在党的历史中具有标志性意义的地点的描述：①井冈山一一中国第一个革命根据地；②瑞金——中国历史上第一个全国性工农民主政权临时中央政府诞生地；③延安——召开八七会议，中国革命从此开始由大革命失败到土地革命
主要用来描述和反映学生的进步状况，强调学生对作品的自我评估与反思，适合对学生长程学习、深层学习结果进行评价的是()。
与第一次国民革命统一战线相比较，抗日民族统一战线具有新特点，下列不属于抗日民族统一战线新特点的是
最新回复
(
0
)
