首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
自考
设u1，u2u3，u4，u5各点之间的距离表如下： 求由某一点出发，遍历每个点各一次，最后又返回出发点的最短路径。
设u1，u2u3，u4，u5各点之间的距离表如下： 求由某一点出发，遍历每个点各一次，最后又返回出发点的最短路径。
admin
2015-01-12
56
问题
设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://www.kaotiyun.com/show/LSVx777K
本试题收录于：
物流数学题库理工类分类
0
物流数学
理工类
相关试题推荐
已知长度为n的线性表A采用顺序存储结构，并且数据元素按值的大小非递减排列，写一算法，删除该线性表中值相同的多余元素(该算法完成后，线性表中数据元素严格按值递增排列)。
下列fsum()函数的功能是求带头节点的单链表中各节点数据域中数值的和，填空完成程序。structnode{floatx；structnode*next；}；f10atfsum(structnod
机械系统如图所示，其中外力f(t)为系统的输入，位移x(t)为系统的输出，m为物体的质量，k为弹簧的弹性系数，B为阻尼器的阻尼系数，试求系统的传递函数。
已知单位负反馈系统的开环传递函数为G(s)=，则其在单位阶跃输入下的稳态误差为________。
UNIX操作系统是典型的【】位多用户多任务的网络操作系统。
______是指对于网络中两个相邻结点之间传输的数据进行加密保护。
关系数据库的数据与更新必须遵循三类完整性规则，下列不是其中一项的是()
某汽车制造厂年产汽车12000辆，故年需用发动机12000台套。经过计算和修匀调整，应每月订货和进货发动机1000台套。设每台发动机的进厂价为20000元，试计算发动机的平均库存量和平均存货额。
_________是设计测试用例的一种工具，它着重检查各种输入条件的组合。
在结构化分析方法中，定义了数据流图中每一图形元素的描述工具是()
随机试题
奠定了林德布洛姆在决策的渐进理论分析上的地位，使其成为这一理论的代表人物的作品是其发在《公共行政评论》上的
Inourcountryeachboyandeachgirl_____therighttoreceiveagoodeducation.
划定基本农田图件中没有的图件比例尺为()。
某新建2×300MW燃煤发电厂，高压厂用电系统标称电压为6kV，其中性点为高电阻接地。每台机组设二台高压厂用无励磁调压双绕组变压器，容量为35MVA，阻抗值为10．5％，6．3kV单母线接线，设A段、B段。6kV系统电缆选为ZR—YJV22—6／6kV。
将原材料转变为产品的全过程，称之为( )。
下列关于期货公司委托业务的表述正确的有( )。
合伙企业的投资者可以以个人劳务出资，只要经全体合伙人协商一致。( )
依照《铁路交通事故应急救援和调查处理条例》，铁路运输企业应当承担赔偿责任的，对每名旅客人身伤亡的赔偿责任限额为人民币()。
美国首先提出建立国际联盟，后来却没有参加，其根本原因在于()。
DearMr.Black,Weareamid-sizedaccountingfirm.Ourstaffmembersarenothappywithourcurrentinsuranceplan,sowear
最新回复
(
0
)
