首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
自考
设u1，u2u3，u4，u5各点之间的距离表如下： 求由某一点出发，遍历每个点各一次，最后又返回出发点的最短路径。
设u1，u2u3，u4，u5各点之间的距离表如下： 求由某一点出发，遍历每个点各一次，最后又返回出发点的最短路径。
admin
2015-01-12
30
问题
设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://jikaoti.com/ti/JCLaFFFM
本试题收录于：
物流数学题库理工类分类
0
物流数学
理工类
相关试题推荐
无向图和_________的邻接矩阵是一个对称阵。
已知C语言程序段如下：structsa{intnum；charname[10]；floatf；}stu[3]={{5，"liming"，85．0}，{6，"liuliang"，91．5}，(7，"wa
下面程序的时间复杂度为【】for(i=1；i
若要求从键盘输入含有空格字符的字符串，应使用函数【】
已知系统开环频率特性的奈奎斯特图如图所示，则该系统的型次为【】
机械工程控制论的研究对象和任务是什么?
IP地址具有固定规范的格式，一个IPv4也址的二进制位数为【】
_____不仅可以检测出误码，还可以确定差错位置，并直接加以纠正。
IEEE802委员会为局域网制定了一系列标准，其中，【】是无线局域网介质访问控制方法及物理层技术规范。
如图所示某数控机床位置随动系统的结构图，试求：(1)系统的自然频率ωn及阻尼比ζ。(2)系统对单位阶跃响应的最大超调量σ％及调整时间Ts(取△＝±5％)。(3)系统的静态误差系数Kp、Kv。
随机试题
Thenumberofpermanentstaffis________.
实体完整性规则要求关系中主键值不能为______。
将函数f(x)=展开为(x-1)的幂级数，并写出其收敛域．
闭路电视监控系统中，当传输距离较远时宜采用()传输信号。
光学水准仪在机电设备安装中主要用于()等。
Word中选定表格的某一行，再从“编辑”菜单中选择“清除”命令(或按Del键)将()。
甲某购买了某公司的股票1000股，每股票面金额32元，预期每年可以获得6．0％的股息，而当时银行存款的利息率为3．0％。如果没有其他因素的影响，一年后甲某购买的1000股股票的价格是()元。
一个实心立体图形如图所示从中挖掉一个圆柱体，然后从任意面剖开，下面哪一项不可能是该立体图形的截面?
MaryandIbought______someoranges.
Theygotooneoftheworld’smostprestigiousuniversitiesandpridethemselvesontheirsuperiorintellectbutalmosthalfof
最新回复
(
0
)
