首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
利用动态规划方法求解每对结点之间的最短路径问题(a11 pairs shortest path problem)时,设有向图G=<V,E>共有n个结点,结点编号1~n,设C是G的成本邻接矩阵,用Dk(i,j)表示从i到j并且不经过编号比众还大的结点的最短路
利用动态规划方法求解每对结点之间的最短路径问题(a11 pairs shortest path problem)时,设有向图G=<V,E>共有n个结点,结点编号1~n,设C是G的成本邻接矩阵,用Dk(i,j)表示从i到j并且不经过编号比众还大的结点的最短路
admin
2021-01-13
36
问题
利用动态规划方法求解每对结点之间的最短路径问题(a11 pairs shortest path problem)时,设有向图G=<V,E>共有n个结点,结点编号1~n,设C是G的成本邻接矩阵,用D
k
(i,j)表示从i到j并且不经过编号比众还大的结点的最短路径的长度(D
n
(i,j即为图G中结点i到j的最短路径长度),则求解该问题的递推关系式为(56)。
选项
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
(i,j)
D、D
k
(i,j);min{D
k-1
(i,j),D
k-1
(i,k)+D
k-1
(k,j)}
答案
D
解析
设p
k
(i,j)表示从i到j并且不经过编号比k还大的结点的最短路径,那么p
k
(i,j)有以下两种可能:
①p
k
(i,j)经过编号为k的结点,此时p
k
(i,j)可以分为从i到k和从k到j的两段,易知产p
k
(i,j)的长度为D
k-1
(i,k)+D
k-1
(k,j)。
②p
k
(i,j)不经过编号为k的结点,此时产p
k
(i,j)的长度为D
k-1
(i,j)。
转载请注明原文地址:https://kaotiyun.com/show/53CZ777K
本试题收录于:
软件设计师上午基础知识考试题库软考中级分类
0
软件设计师上午基础知识考试
软考中级
相关试题推荐
阅读下列说明和图,回答问题1至问题3,将解答填入答题纸的对应栏内。【说明】图书管理系统详细记录图书库存情况、读者信息以及读者借阅记录(包括借书日期和还书日期)。新书入库时要为该书编制图书卡片,包括分类目录号、图书流水号(要保证每本书都有唯一的流水号,即
阅读下列说明和图,回答问题1至问题4,将解答填入答题纸的对应栏内。【说明】某学校开发图书管理系统,以记录图书馆藏图书及其借出和归还情况,提供给借阅者借阅图书功能,提供给图书馆管理员管理和定期更新图书表功能。主要功能的具体描述如下:(1)处理借阅。借阅者
阅读下列说明和图,回答问题1至问题3,将解答填入答题纸的对应栏内。【说明】某会议策划公司为了方便客户,便于开展和管理各项业务活动,需要构建一个基于网络的会议预定系统。【需求分析】(1)会议策划公司设有受理部、策划部和其他部门,部门信息包括部门号、部
阅读下列说明和C代码,回答问题1~问题3,将解答写在答题纸的对应栏内。【说明】设有n个货物要装入若干个容量为C的集装箱以便运输,这n个货物的体积分别为{S1,S2,…,Sn},且有si≤C(1≤i≤n)。为节省运输成本,用尽可能少的集装
阅读下列说明和图,回答问题l~问题3,将解答填入答题纸的对应栏内。【说明】Pay&Drive系统(开多少付多少)能够根据驾驶里程自动计算应付的费用。系统中存储了特定区域的道路交通网的信息。道路交通网由若干个路段(RoadSegment)构成,每个路段
ARP协议的作用是(61),ARP报文封装在(62)中传送。
由值为29、12、15、6、23的五个叶子结点构造的哈夫曼树为(64),其带权路径长度为(65)。
国际标准MPEG—Ⅱ采用了分层的编码体系,提供了4种技术,它们是(46)。数字音频采样和量化过程所用的主要硬件是:(47)。AC-3数字音频编码提供了5个声道的频率范围是:(48)。要把一台普通的计算机变成多媒体计算机要解决的关键技术是:(
OOA(Object-Oriented Analysis)模型由5个层次和5个活动组成,5个层次不包括(51),5个活动不包括(52)。OOA在定义属性的同时,还要识别实例连接。实例连接是一个实例对象与另一个实例对象的(53)关系。
王某是M国际运输有限公司计算机系统管理员。任职期间,王某根据公司的业务要求开发了“海运出口业务系统”,并由公司使用,随后,王某向国家版权局申请了计算机软件著作权登记,并取得了《计算机软件著作权登记证书》。证书明确软件名称是“海运出口业务系统V1.0”,著作
随机试题
能够引起心脏兴奋的平喘药有
《中华人民共和国劳动法》规定劳动者对用人单位管理人员违章指挥、强令冒险作业,有权()。
A.滑石粉B.硬脂酸镁C.氢化植物油D.聚乙二醇类E.微粉硅胶主要作为助流剂使用,可将颗粒表面的凹陷填满补平,改善颗粒流动性的辅料是
制作可摘局部义齿印模,选择的托盘与牙弓内外侧应有多大间隙
某小型写字楼的购买价格为50万元,其中投资者投入的权益资本为20万元,另外30万元年利率为7.5%、期限为30年、按年等额还款的抵押贷款。建筑物的价值为40万元,按有关规定可在25年内直线折旧。预计该写字楼的年毛租金收入为10万元,空置和收租损失为毛租金收
水准测量中,一个测站的观测需要检查的限差包括()。
按()的不同,会计报表分为资产负债表、利润表和现金流量表。
当下,我们的商界精英必须清醒地意识到,企业固然要顾及股东的利益.尽可能实现股东利益的最大化,但是获得社会资源进行生产的同时,也就承担了社会各方面利益相关者的责任。能否充分考虑这些利益相关者的利益,也日益成为评价企业业绩和企业伦理的重要尺度。对这段文字概括最
清朝晚期,被今人誉为“开眼看世界第一人”的是谁()
有的人说日本人礼节周到,但我觉得实际上未必就是那样。
最新回复
(
0
)