首页 > 试题广场 >

下面哪些使用的是贪心算法

[不定项选择题]

下面哪些使用的是贪心算法

```
单源最短路径中的Dijkstra算法
```
```
最小生成树的Prim算法
```
```
最小生成树的Kruskal算法
```

计算每对顶点最短路径的Floyd-Warshall算法

```
字符串匹配中的KMP算法
```

查看正确选项

南宫语萱

D、E使用的是动态规划。

发表于 2014-11-13 21:20:00 回复(1)

🍁201803202213509

贪心算法（又称贪婪算法）是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的是在某种意义上的局部最优解。
A.单源最短路径中的Dijkstra算法：Dijkstra提出按各顶点与源点v间的路径长度的递增次序，生成到各顶点的最短路径的算法。既先求出长度最短的一条最短路径，再参照它求出长度次短的一条最短路径，依次类推，直到从源点v 到其它各顶点的最短路径全部求出为止。

B.最小生成树的Prim算法:Prim算法基于贪心算法设计，其从一个顶点出发，选择这个顶点发出的边中权重最小的一条加入最小生成树中，然后又从当前的树中的所有顶点发出的边中选出权重最小的一条加入树中，以此类推，直到所有顶点都在树中，算法结束。
C.最小生成树的Kruskal算法按照权值从小到大的顺序选择n-1条边，并保证这n-1条边不构成回路。

发表于 2018-08-17 09:52:53 回复(0)

GoAshore

prim和dijkstra基本思想是差不多的

发表于 2022-12-07 17:13:23 回复(0)

cyer

单源最短路径中的Dijkstra算法 
每次都会选取当前距离最小的点，并且固定住当前距离为源点到这个点的最短距离，然后去更新邻居。

B 每次选取 到当前span tree 各个节点距离最小的一个点，添加到span tree 节点里面
C 每次选取一个长度最小，且不会造成回路的边，添加到span tree里面

发表于 2016-12-05 22:38:46 回复(0)