首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
利用动态规划法求解每对节点之间的最短路径问题时,设有向图G=<V,E>共有n个节点,节点编号1~n,设C是G的成本邻接矩阵,用Dk(i,j)表示从i到j并且不经过编号比k还大的节点的最短路径的长度(Dn(i,j)即为图G中节点i到j的最短路径长度),则求解
利用动态规划法求解每对节点之间的最短路径问题时,设有向图G=<V,E>共有n个节点,节点编号1~n,设C是G的成本邻接矩阵,用Dk(i,j)表示从i到j并且不经过编号比k还大的节点的最短路径的长度(Dn(i,j)即为图G中节点i到j的最短路径长度),则求解
admin
2009-05-15
52
问题
利用动态规划法求解每对节点之间的最短路径问题时,设有向图G=<V,E>共有n个节点,节点编号1~n,设C是G的成本邻接矩阵,用D
k
(i,j)表示从i到j并且不经过编号比k还大的节点的最短路径的长度(D
n
(i,j)即为图G中节点i到j的最短路径长度),则求解该问题的递推关系式为(28)。
选项
A、D
k
(i,j)=D
k
-1(i,j)+C(i,j)
B、D
k
(i,j)=min{D
k
-1(i,j),D
k
-1(i,j)+C(i,j)}
C、D
k
(i,j)=D
k
-1(i,k)+D
k
-1(k,j)
D、D
k
(i,j)=min{D
k
-1(i,j),D
k
-1(i,k)+D
k
-1(k,j)}
答案
D
解析
从“D
k
(i,j)表示从i到j并且不经过编号比k还大的节点的最短路径的长度”中,我们得到一个提示,在求i,j之间最短路径的时候,会考虑它经过哪些节点能缩短原来的路径。在 D
k
(i,j)=min{D
k
-1(i,j),D
k
-1(i,k)+D
k
-1(k,j)}中,D
k
(i,j)表示i到j不经过k的路径长度,而 Dk-1(I,k)+Dk-1(k,j)表示i到j经过k的路径长度,且min()函数用于找最小值,所以此式正确。
转载请注明原文地址:https://kaotiyun.com/show/hwxZ777K
本试题收录于:
软件设计师上午基础知识考试题库软考中级分类
0
软件设计师上午基础知识考试
软考中级
相关试题推荐
在系统转换的过程中,旧系统和新系统一起工作一段时间,再由新系统代替旧系统的转换策略称为(15)。
某请求分页存储管理系统中,容量为1MB的主存被划分为512块,其页表如表7-1所示。若给定一十进制逻辑地址为7058,其十进制物理地址是(11)。
文件系统采用多重索引结构搜索文件内容。设块长为512字节,每个块号长3字节,如果不考虑逻辑块号在物理块中所占的位置,那么两级索引时可寻址的文件最大长度为(4)。
TCP是一个面向连接的协议,它提供连接的功能是(31)的,采用(32)来实现可靠数据流的传送。为了提高效率,又引入了滑动窗口协议,协议规定重传(33)的分组,这种分组的数量最多可以(34),TCP协议采用滑动窗口协议解决了(35)。
WhiletheInternetisinherentlyinsecure,businessesstillneedtopreservetheprivacyofdataasittravelsoverthenetwork.
Networkscanbeinterconnectedbydifferentdevices.Inthephysicallayer,networkscanbeconnectedby(66)orHubs,whichjust
Networkmanagershavelongawaitedpracticalvoice-over-IP(VOIP)solutions.VOIPpromiseseasenetworkmanagementanddecreases(6
Inthefollowingessay,eachblankhasfourchoices.Choosethebestanswerandwritedownontheanswersheet.Microwavecom
Inthefollowingessay,eachblankhasfourchoices.Choosethebestanswerandwritedownontheanswersheet.Microwavecom
BorderGatewayProtocol(BGP)isinter-autonomoussystem(71)protoc01.BGPisbasedonaroutingmethodcalledpathvectorrouting
随机试题
试述太平天国农民战争的意义。
阅读《答李翊书》中的一段文字,然后回答问题。气,水也;言,浮物也。水大而物之浮者大小毕浮。气之与言犹是也,气盛则言之短长与声之高下者皆宜。……“气”和“言”指的是什么?
关于犯罪嫌疑人、被告人逃匿、死亡案件违法所得的没收程序,下列哪一说法是正确的?(2012年试卷2第38题)
以下对爆破作业描述不正确的是()。(1)雷雨季节宜采用电雷管起爆法起爆。(2)炸药反应不完全时,不会引起有毒气体含量增加。(3)同一爆破网络应使用同厂、同批、同型号的电雷管。(4)处理盲炮时进行安全警戒。
行业的成长实际上是指( )。
企业会计方法和程序前后各期( )。
某公司正处于快速发展时期,急需高素质人才加盟,为此人力资源部门和多家猎头公司签订了合作协议,开始进行大张旗鼓的人才招募选拔。该公司人才招募选拔的流程是:猎头公司推荐候选人,候选人资料经人力资源部经理筛选后交总经理审阅,由总经理决定是否面试,再由人力资源部和
根据《企业所得税法》及其实施条例的有关规定,不得提取折旧的固定资产是()。
出境旅游领队带领旅游团入中国境的服务包括()
(2015·河南)既是课程标准的具体化,也是师生进行教学的主要依据的是教科书。()
最新回复
(
0
)