首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
利用动态规划法求解每对节点之间的最短路径问题时,设有向图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
24
问题
利用动态规划法求解每对节点之间的最短路径问题时,设有向图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://jikaoti.com/ti/OPa7FFFM
本试题收录于:
软件设计师上午基础知识考试题库软考中级分类
0
软件设计师上午基础知识考试
软考中级
相关试题推荐
信源用户A通过卫星链路向用户B传送帧长为2Kb的数据,链路传播延迟为80ms。若采用后退N帧ARQ协议通信,发送窗口为8,且要求最大链路利用率达到0.95,则数据传输速率至少为(25)kb/s,
文件系统采用多重索引结构搜索文件内容。设块长为512字节,每个块号长3字节,如果不考虑逻辑块号在物理块中所占的位置,那么两级索引时可寻址的文件最大长度为(4)。
在X.25网络中,通常用户计算机与网络的(41)相连接。X.25网络的数据链路层使用的标准是(42),它允许在收到应答前连续发送(43)帧数据,为用户提供的最高速率为(44)Kbps。两个X.25网络之间互联时使用(45)协议。
在X.25网络中,通常用户计算机与网络的(41)相连接。X.25网络的数据链路层使用的标准是(42),它允许在收到应答前连续发送(43)帧数据,为用户提供的最高速率为(44)Kbps。两个X.25网络之间互联时使用(45)协议。
IEEE802.5令牌环(TokenRing)网中,时延是由(1)决定。要保证环网的正常运行,环的时延必须有一个最低限度,即(2)。如果达不到这个要求,可以采用的一种办法是通过增加电缆长度,人为地增加时延来解决。设有某一个令牌环网长度为400m
WhiletheInternetisinherentlyinsecure,businessesstillneedtopreservetheprivacyofdataasittravelsoverthenetwork.
Networkmanagershavelongawaitedpracticalvoice-over-IP(VOIP)solutions.VOIPpromiseseasenetworkmanagementanddecreases(6
Networkscanbeinterconnectedbydifferentdevices.Inthephysicallayer,networkscanbeconnectedby(66)orHubs,whichjustmo
BorderGatewayProtocol(BGP)isinter-autonomoussystem(71)protoc01.BGPisbasedonaroutingmethodcalledpathvectorrouting
Routingprotocolsusedifferenttechniquesforassigning(1)toindividualnetwork.Further,eachroutingprotocolformsametricag
随机试题
能利尿通淋散瘀止血,且宜于血淋的药为
研究藏象学说的主要思维方法是
下列情形中,不视为侵犯专利权的是()。
在一列国际列车上,来自英、意、日、德四国的甲、乙、丙、丁四位旅客恰好相聚在某个车厢中。他们每人除了会说本国语言外,还会说其他三国语言中的一种,有一种语言三个人都会说。这四位旅客交谈的有关情况如下:(1)乙不会说英语,当甲与丙交谈时,他却能替他们做翻译。(2
国家培养青年、少年、儿童在品德、智力、体质等方面全面发展,这个规定出自()。
晶莹美丽的珍珠,其中心不过是颗砂粒,正所谓“病蚌成珠”。降雨全靠空气中的尘埃作为凝聚中心,倘若天空绝对干净,水汽再多也不会下雨,当然就没有植物和动物,更不可能有人类。同类之物彼此相差无几,谁也难成中心。异类的介入打破了无差异的均衡,“中心”应运而生,有序的
[*]
AnarticlepublishedrecentlyintheprestigiousscientificjournalNatureissheddingnewlightonanimportant,buthithertol
Whenyou’retryingtodobusiness,youneedtoconsiderthecultureofyourcustomersandtheirexpectations.Americansare
A、Thebestrelationshipbetweenco-workers.B、Athirdwayofaccomplishinggoals.C、Usefulinformationtobesharedamongco-wor
最新回复
(
0
)