首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
利用动态规划法求解每对节点之间的最短路径问题时,设有向图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
47
问题
利用动态规划法求解每对节点之间的最短路径问题时,设有向图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
软件设计师上午基础知识考试
软考中级
相关试题推荐
某局域网的Internet接入拓扑图如图7-5所示。由于用户在使用telnet登录网络设备或服务器时所使用的用户名和口令在网络中是以明文传输的,很容易被网络上的非法协议分析设备截获。因此需要定义一条规则号为110,禁止所有外网主机和内网主机进行远程登录的访
某公司为方便远程客户访问公司的某些数据资源,允许客户通过Internet访问公司的FTP服务器,其网络拓扑结构如图7—1所示。在客户机与FTP服务器之间采用(44)协议,可方便地实现在网络层对数据进行加密。
RSA算法的一个比较知名的应用是(41),其协商层利用RSA公钥进行身份认证,记录层涉及到对应用程序提供的信息的分段、压缩、数据认证和加密。
若信元在交换过程中出现拥塞,该信息被记录在信元头的(27)中。
TCP是一个面向连接的协议,它提供连接的功能是(31)的,采用(32)来实现可靠数据流的传送。为了提高效率,又引入了滑动窗口协议,协议规定重传(33)的分组,这种分组的数量最多可以(34),TCP协议采用滑动窗口协议解决了(35)。
IEEE802.5令牌环(TokenRing)网中,时延是由(1)决定。要保证环网的正常运行,环的时延必须有一个最低限度,即(2)。如果达不到这个要求,可以采用的一种办法是通过增加电缆长度,人为地增加时延来解决。设有某一个令牌环网长度为400m
Atypicalapplicationofthis(71)isADSL.Itisemergingasthetechnologyforhome-andsmall-officeInternetconnectivity.Itp
Inthefollowingessay,eachblankhasfourchoices.Choosethebestanswerandwritedownontheanswersheet.Microwavecom
Traditionalnetworklayerpacketforwardingreliesontheinformationprovidedbynetworklayer(71)protocols,orstaticrouting,
随机试题
下列关于针刺捻转法的说法。错误的是
当混凝土结构施工质量不符合要求时,经()检测鉴定达到设计要求的检验批,应予以验收。
下面()属于可变更或撤销的合同。
2018年2月,教育部等五部门印发《教师教育振兴行动计划(2018—2022年)》提出要将学习贯彻习近平总书记对教师的殷切希望和要求作为()的首要任务和重点内容。
公安机关的人民警察以()名义开展公安工作。
鸦片战争后,中国逐步被卷入资本主义世界市场。得出该结论的主要依据不包括()。
阅读下列材料,回答问题。材料一:2017年6月27日,夏季达沃斯论坛在大连开幕。“在第四次工业革命中实现包容性增长”是本次夏季达沃斯论坛的主题,同时也为新工业革命时代中的全球经济增长设置了新航标。当前,以“人工智能”“工业4.0”等新兴
[2000年GRK真题](1)一(2)题基于以下题干:小李:如果在视觉上不能辨别艺术复制品和真品之间的差异,那么复制品就应该和真品的价值一样。因为如果两件艺术品在视觉上无差异,那么它们就有相同的品质。要是它们有相同的品质,它们的价格就应该相等。小王:你对艺
下列叙述中正确的是
【B1】【B6】
最新回复
(
0
)