首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
利用动态规划法求解每对节点之间的最短路径问题时,设有向图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
46
问题
利用动态规划法求解每对节点之间的最短路径问题时,设有向图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
软件设计师上午基础知识考试
软考中级
相关试题推荐
IEEE802.11定义了无线局域网的两种工作模式,其中的(30)模式网络中,无线终端通过无线接入点访问有线网络的数据资源。
若信元在交换过程中出现拥塞,该信息被记录在信元头的(27)中。
在系统转换的过程中,旧系统和新系统一起工作一段时间,再由新系统代替旧系统的转换策略称为(15)。
RS-232C是(46)之间的接口标准,它规定的电平的表示方式为(47)。当使用RS-232C连接相关设备时,电缆的长度不应超过(48)m。当用RS-232C直接连接两台计算机时,采用零调制解调器方式,其连接方式为(49)。当计算机需要通过相连的M
MPLS采用标记分发协议(LDP),使MPLS节点为每个流加上标记。其中,LDP协议的(44)报文采用UDP协议传输。
Atypicalapplicationofthis(71)isADSL.Itisemergingasthetechnologyforhome-andsmall-officeInternetconnectivity.Itp
Packet-switching wireless networks are preferable(41)when transmissions are(42)because of the way charges are(43)per packet. Cir
BorderGatewayProtocol(BGP)isinter-autonomoussystem(71)protoc01.BGPisbasedonaroutingmethodcalledpathvectorrouting
Routingprotocolsusedifferenttechniquesforassigning(1)toindividualnetwork.Further,eachroutingprotocolformsametricag
Traditionalnetworklayerpacketforwardingreliesontheinformationprovidedbynetworklayer(71)protocols,orstaticrouting,
随机试题
企业建造办公大楼领用生产用原材料时,相关的增值税应借记的会计科目是()。
环磷酰胺细胞类可引起明显的骨髓抑制,应定期复查血象,当白细胞降到下列水平时,应停药
初戴全口义齿时,发现下总义齿左右撬动,加力时患者有痛感。在下述造成义齿撬动的原因中,首先考虑的原因应是
湿热熏蒸的面色是
该施工企业安全管理机构的第一责任人是()。根据施工安全技术措施计划的实施要求,下列各项中不属于安全技术交底主要内容的有()。
女职工生育享受不少于()天的产假。
根据《民事诉讼法》的规定,人民法院有权裁定终结执行的情形包括()。
RS449标准规格包括两个关于电气特性的子集标准,其中RS422是(5)。
Whyisitsodifficulttofallasleepwhenyouareovertired?Thereisnooneanswerthat【C1】______toeveryindividual.Butmany
IdentityTheftA)Identitytheftandidentityfraudaretermsusedtorefertoalltypesofcrimeinwhichsomeonewrongfullyobt
最新回复
(
0
)