首页
登录
从业资格
迪杰斯特拉(Dijkstra)算法用于求解图上的单源点最短路径。该算法按路径长度
迪杰斯特拉(Dijkstra)算法用于求解图上的单源点最短路径。该算法按路径长度
资格题库
2022-08-02
26
问题
迪杰斯特拉(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.商务应用中,
随机试题
Whowroteahighly-acclaimedNovelMobyDick?A、WilliamJames.B、HermanMelville.
InLondon,overhalfofthehomesbuiltbetween1919and1980hadonegarage
A0-A4图纸宜横式使用,必要时也可立式使用。
(2018年真题)中国证监会及其派出机构可以对以下哪些主体的违法违规行为进行行政
学校组织运动会、老师让班级同学训练、同学之间相互监督、没有好好训练的可以举报给老
某施工企业按照2/10、77/30的条件购入货物20万元,如果该施工企业放弃折扣
下列描述中错误是A:注射剂贮存期约为2年B:糖浆剂贮存期约为1年C:酊剂贮存
代收代管单位挪用住宅专项维修资金的,由县级以上地方人民政府建设(房地产)主管部门
可摘局部义齿修复前口内检查的内容不包括A:缺牙区的部位和数目 B:缺牙区牙槽嵴
工程监理单位和被监理工程的()有隶属关系或其他利害关系的,不得承担该项建设
最新回复
(
0
)