迪杰斯特拉(Dijkstra)算法用于求解图上的单源点最短路径。本质上说,该算法是一种基于()策略的算法。A.分治B.动态规划C.贪心D.回溯

正确答案：C

正确答案：A
解析：本题考查最短路径问题。贪心算法通过一系列的选择得到问题的解。它所做出的每一次选择是当前状态下局部最优选择，即贪心选择。分治法的基本思想是把大问题分解成一些较小的问题，然后由小问题的解方便地构造出大问题的解。动态规划策略设计算法利用问题的最优子结构性质，以自底向上的方式递归地从子问题的最优解逐步构造出整个问题的最优解。回溯法也称为试探法，该方法首先暂时放弃关于问题规模大小的限制，并将问题的候选解按某种顺序逐一枚举和检验。迪杰斯特拉(Dijkstra)提出的按路径长度递增的次序产生最短路径的算法，其思想是把网中所有的顶点分成两个集合S和T，S集合的初态只包含顶点v0，T集合的初态为网中除v0之外的所有顶点。凡以v0为源点，已经确定了最短路径的终点并入S集合中；顶点集合T则是尚未确定最短路径的顶点的集合。按各顶点与v0间最短路径长度递增的次序，逐个把T集合中的顶点加入到S集合中去，使得从v0到S集合中各顶点的路径长度始终不大于从v0到T集合中各顶点的路径长度。从迪杰斯特拉算法求最短路径的过程可知，其算法策略属于贪心策略。

正确答案：C
试题61分析分治法：对于一个规模为n的问题，若该问题可以容易地解决（比如说规模n较小）则直接解决；否则将其分解为k个规模较小的子问题，这些子问题互相独立且与原问题形式相同，递归地解这些子问题，然后将各子问题的解合并得到原问题的解。动态规划法：这种算法也用到了分治思想，它的做法是将问题实例分解为更小的、相似的子问题，并存储子问题的解而避免计算重复的子问题。贪心算法：它是一种不追求最优解，只希望得到较为满意解的方法。贪心算法一般可以快速得到满意的解，因为它省去了为找到最优解而穷尽所有可能所必须耗费的大量时间。贪心算法常以当前情况为基础做最优选择，而不考虑各种可能的整体情况，所以贪心算法不要回溯。回溯算法（试探法）：它是一种系统地搜索问题的解的方法。回溯算法的基本思想是：从一条路往前走，能进则进，不能进则退回来，换一条路再试。其实现一般要用到递归和堆栈。针对单源最短路径问题，由Dijkstra提出了一种按路径长度递增的次序产生各顶点最短路径的算法。若按长度递增的次序生成从源点s到其他顶点的最短路径，则当前正在生成的最短路径上除终点以外，其余顶点的最短路径均已生成（将源点的最短路径看做是已生成的源点到其自身的长度为0的路径）。这是一种典型的贪心策略，就是每递增一次，经对所有可能的源点、目标点的路径都要计算，得出最优。带权图的最短路径问题即求两个顶点间长度最短的路径。其中：路径长度不是指路径上边数的总和，而是指路径上各边的权值总和。参考答案（61）C