首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
自考
设u1，u2u3，u4，u5各点之间的距离表如下： 求由某一点出发，遍历每个点各一次，最后又返回出发点的最短路径。
设u1，u2u3，u4，u5各点之间的距离表如下： 求由某一点出发，遍历每个点各一次，最后又返回出发点的最短路径。
admin
2015-01-12
51
问题
设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
物流数学
理工类
相关试题推荐
某系统是最小相位系统，且对数幅频渐近线如图所示，其对应的传递函数是【】
已知系统开环频率特性的奈奎斯特图如图所示，则该系统的型次为【】
时分多路复用可分为同步时分多路复用和异步时分多路复用，若时隙与用户(或各路信号)之间没有固定的对应关系，必须在用户数据中加上用户的标识，以标记是哪个用户的数据，则称为______。
面向连接服务包括建立连接、传输数据和________三个阶段。
UDP是一种不可靠的传输层协议，它非常适合于速率要求_________、而对精确度要求相对较低的网络应用，如视频会议、视频点播和网络电话等。
IP地址具有固定规范的格式，一个IPv4也址的二进制位数为【】
HTTP规定的用户使用浏览器访问万维网的过程可以分为哪几个步骤?
IEEE802委员会为局域网制定了一系列标准，其中，【】是无线局域网介质访问控制方法及物理层技术规范。
处理借书的过程如下：接受读者递交的索书单，首先查看读者记录进行读者鉴别，并存储借阅记录文件，再查询图书文件，进行存书查询。如果图书未借出，向书库发出库单，并修改借阅记录文件和图书文件；如果图书已借出，向读者发出拒绝借阅通知。请根据上述过程绘制数据流程图。
分析题26图所示的时序逻辑电路。要求：(1)写出各触发器的驱动方程和状态方程；(2)画出状态转换图；(3)检查电路能否自启动。
随机试题
患者男，21岁。眼黄乏力、排茶色尿4天。查体：面色苍黄，皮肤及巩膜黄染。血常规：Hb72g／L，Ret16．2％，WBC5．6×109／L，PLT129×109／L；总胆红素58．5μmol／L，未结合胆红素54．4μmol／L，最可能的诊断是
在一所医院的200名吸烟男医生中，有50人自动戒烟，150人继续吸烟，研究者进行了20年的随访观察，以确定两组肺癌的发生与死亡情况，这种研究属于
A．绞窄性肠梗阻B．单纯性肠梗阻C．麻痹性肠梗阻D．痉挛性肠梗阻E．慢性肠梗阻肠扭转属于
枳实导滞丸的功用为
房地产投资信托基金按信托性质分类，可分为()。
【背景材料】某公司承建一座市政桥梁工程，桥梁上部结构为9孔30m后张法预应力混凝土T梁，桥宽横断面布置T梁12片，T梁支座中心线距梁端600mm，T梁横截面如图3所示。项目部进场后，拟在桥位线路上现有城市次干道旁租地建设T梁预制场，平面布置如图4所示，
铁路施工中常用的降水措施有（）。
下列各项中，属于社会主义国民收入再分配途径的有()。
当经济发展缓慢或处于低潮时，增加社会保障开支()。
相邻关系，可以发生在()之间。
最新回复
(
0
)
