首页
登录
从业资格
迪杰斯特拉(Dijkstra)算法用于求解图上的单源点最短路径。该算法按路径长度
迪杰斯特拉(Dijkstra)算法用于求解图上的单源点最短路径。该算法按路径长度
资格题库
2022-08-02
53
问题
迪杰斯特拉(Dijkstra)算法用于求解图上的单源点最短路径。该算法按路径长度递增次序产生最短路径,本质上说,该算法是一种基于( )策略的算法。A.分治B.动态规划C.贪心D.回溯
选项
A.分治
B.动态规划
C.贪心
D.回溯
答案
C
解析
分治法:对于一个规模为n的问题,若该问题可以容易地解决(比如说规模n较小)则直接解决;否则将其分解为k个规模较小的子问题,这些子问题互相独立且与原问题形式相同,递归地解这些子问题,然后将各子问题的解合并得到原问题的解。
动态规划法:这种算法也用到了分治思想,它的做法是将问题实例分解为更小的、相似的子问题,并存储子问题的解而避免计算重复的子问题。
贪心算法:它是一种不追求最优解,只希望得到较为满意解的方法。贪心算法一般可以快速得到满意的解,因为它省去了为找到最优解而穷尽所有可能所必须耗费的大量时间。贪心算法常以当前情况为基础做最优选择,而不考虑各种可能的整体情况,所以贪心算法不要回溯。
回溯算法(试探法):它是一种系统地搜索问题的解的方法。回溯算法的基本思想是:从一条路往前走,能进则进,不能进则退回来,换一条路再试。其实现一般要用到递归和堆栈。
针对单源最短路径问题,由Dijkstra提出了一种按路径长度递增的次序产生各顶点最短路径的算法。若按长度递增的次序生成从源点s到其他顶点的最短路径,则当前正在生成的最短路径上除终点以外,其余顶点的最短路径均已生成(将源点的最短路径看做是已生成的源点到其自身的长度为0的路径)。这是一种典型的贪心策略,就是每递增一次,经对所有可能的源点、目标点的路径都要计算,得出最优。
带权图的最短路径问题即求两个顶点间长度最短的路径。其中:路径长度不是指路径上边数的总和,而是指路径上各边的权值总和。
转载请注明原文地址:https://tihaiku.com/congyezige/2409997.html
本试题收录于:
中级 软件设计师题库软件水平考试初中高级分类
中级 软件设计师
软件水平考试初中高级
相关试题推荐
根据历史数据,确定一个就诊人员是否可能患心脏病,可以采用( )算法。A.C4.
关于聚类算法K-Means和DBSCAN的叙述中,不正确的是( )。A.K-M
聚类的典型应用不包括( ),( )是一个典型的聚类算法。 问题1选项 A
数据字典中“数据项”的内容包括:名称、编号、取值范围、长度和( )。A.处理频
以下加密算法中适合对大量的明文消息进行加密传输的是( )A.RSA B.SH
以下加密算法中适合对大量的明文消息进行加密传输的是() A.RSA B.
下列叙述中正确的是()。A.算法的效率只与问题规模有关,与存储结构无关 B.
算法的时间复杂度取决于()。 A.问题的规模 B.问题的困难度 C.待处
下面的说法中,只有()是正确的。A.字符串的长度是指串中包含的字母的个数 B
聚类的典型应用不包括(请作答此空),()是一个典型的聚类算法。A.商务应用中,
随机试题
()广告艺术()保健品广告[br]()广告文化()活页传单广告M、L
Loveisthemostwonderfulthingintheworld.Peoplealwayshopetoownthe
[originaltext]W:Iwasworkingonapaperaboutthedifferencesbetweenwomena
下列有关路面抗滑性能的说法中,正确的是() A.摆值BPN越大,抗滑性能
徽菜为全国八大菜系之一,起源于()。A.款县 B.宏村 C.黄山区 D.唐
多系统器官功能衰竭首先受累的器官是( )。A.心 B.肝 C.肺 D.肾
船舶运输过程中,通常货差是在( )发现的。 A.装货港 B.始发港
小芳失恋后情绪沮丧,几度寻死以求解脱,小芳的母亲向社会工作者大智求助。大智接案后
下列关于要约和承诺的说法,正确的是()。A.要约邀请是要约的必要准备工作
狼疮性肾炎一般不表现为A.急性肾炎 B.慢性肾炎 C.肾病综合征 D.慢性
最新回复
(
0
)