首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
利用动态规划法求解每对节点之间的最短路径问题时,设有向图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
70
问题
利用动态规划法求解每对节点之间的最短路径问题时,设有向图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
软件设计师上午基础知识考试
软考中级
相关试题推荐
信源用户A通过卫星链路向用户B传送帧长为2Kb的数据,链路传播延迟为80ms。若采用后退N帧ARQ协议通信,发送窗口为8,且要求最大链路利用率达到0.95,则数据传输速率至少为(25)kb/s,
在系统转换的过程中,旧系统和新系统一起工作一段时间,再由新系统代替旧系统的转换策略称为(15)。
在X.25网络中,通常用户计算机与网络的(41)相连接。X.25网络的数据链路层使用的标准是(42),它允许在收到应答前连续发送(43)帧数据,为用户提供的最高速率为(44)Kbps。两个X.25网络之间互联时使用(45)协议。
用户李四给数据库服务器发命令,要求将文件“张三.dbf”删除。数据库服务器上的认证机制需要确定的主要问题是(33)。
WhiletheInternetisinherentlyinsecure,businessesstillneedtopreservetheprivacyofdataasittravelsoverthenetwork.
WhiletheInternetisinherentlyinsecure,businessesstillneedtopreservetheprivacyofdataasittravelsoverthenetwork.
设某单位路由器建立了以下的路由表,若收到分组的目的IP地址为128.96.37.151,则转发的端口是(63),若收到分组的目的IP是128.96.35.151,则转发的端口是(64),若该路由器是该单位与Internet连接的路由器,则该单位分得的IP地
Inthefollowingessay,eachblankhasfourchoices.Choosethebestanswerandwritedownontheanswersheet.Microwavecom
BorderGatewayProtocol(BGP)isinter-autonomoussystem(71)protoc01.BGPisbasedonaroutingmethodcalledpathvectorrouting
Routingincircuit-switchingnetworkshastraditionallyinvolvedastaticroutingstrategywiththeuseof(1)pathstorespond
随机试题
A.维拉帕米B.胺碘酮C.美西律D.拉贝洛尔E.普鲁卡因胺属于延长动作电位时程药(第Ⅲ类)的抗心律失常药是
上病例诊断为:内治选用方剂为:
病因判定标准中应该放弃的是
(用户名:25;账套:505;操作日期:2012年1月31日)核销客户名为“华美公司"的所有销售发票。
复式记账的基本内容包括()。
金融外汇与银行结算不属于外贸跟单员的知识范围,因此外贸跟单员不需要掌握这方面知识。()
通报的适用范围是()。
设某计算机的逻辑地址空间和物理地址空间均为64KB,按字节编址。若某进程最多需要6页(Page)数据存储空间,页的大小为1KB,操作系统采用固定分配局部置换策略为此进程分配4个页框(PageFrame)。在时刻260前的该进程访问情况见下表(访问位即使用
一切物质在本质上都具有类似感觉的反映特性是()。
A—cornerB—halfwaylineC—goalD—centerforwardE—penaltyF—netG—r
最新回复
(
0
)