【软考】数据结构与算法基础 - 常见的算法设计思想（贪心算法）

我会带着你远行 2024-03-23 19:38 63阅读 0赞

## 一、贪心算法是什么？ ##

贪心算法是一种常见的算法设计思想  
贪心算法是一种简单而有效的算法设计思想  
贪心算法通过在每一步选择最优的解决方案来最大化算法的效率。

贪心算法是一种在每一步选择中都采取在当前状态下最好或最优（即最有利）的选择，从而希望导致结果是最好或最优的算法设计思想。

## 二、贪心算法的核心思想 ##

从问题的初始状态开始，在每一步的选择中，都尽可能地做出最优的决策（采取在当前状态下最优的选择），从而最终达到最优的结果，希望导致结果是最好或最优的。

## 三、贪心算法的应用场景 ##

贪心算法通常用于求解以下问题：

*  最小生成树问题：给定一个带权无向图，要求找出一个生成树，使得该生成树的权值之和最小。
 *  最短路径问题：给定一个带权有向图，要求找出两个顶点之间的最短路径。
 *  背包问题：给定一些物品和一个背包，每个物品都有自己的重量和价值，要求在不超过背包容量的情况下，使得背包中的总价值最大。
 *  最优装载问题：给定一些物品和一个船，每个物品都有自己的重量，要求装载船的物品重量不超过船的容量，并且装载的物品总价值最大。

## 四、贪心算法的实现方式 ##

首先，确定一个评价指标，用于评估每个解决方案的有效性。  
然后，在每一步选择评价指标最优的解决方案，并重复这个过程，直到找到最优的解决方案。

## 五、贪心算法的注意事项 ##

需要注意的是，贪心算法并不一定能够得到问题的最优解，它只能得到一个最优解或近似最优解。在实际应用中，需要根据具体问题进行分析和设计，选择合适的贪心策略和贪心对象，以保证算法的正确性和效率。

贪心算法通常用于解决问题的规模较小的情况，因为它的时间复杂度是线性级别的，对于规模较大的问题，贪心算法的效率会变得非常低，因此需要使用其他更高效的算法设计思想来解决问题。

## 六、贪心算法的常见应用 ##

### 6.1 求解最小生成树问题 ###

Question ：  
在一个带权的图中，找到一棵生成树，使得这棵生成树的边权和最小。  
给定一个带权无向图，要求找出一个生成树，使得该生成树的权值之和最小。

贪心算法的解决方案是：  
首先，选择一个顶点作为起点，并标记它已经被访问。  
然后，遍历所有的边，对于每条边，计算从起点到这条边的边权和，并选择边权和最小的边作为下一条边。  
如果已经访问了所有的顶点，就找到了一个有效的最小生成树。  
如果没有找到有效的最小生成树，就回溯到上一个顶点，并尝试其他的边作为下一条边。

### 6.2 求解最短路径问题 ###

Question ：  
在一个图中，找到从起点到终点的最短路径。  
给定一个带权有向图，要求找出两个顶点之间的最短路径。

贪心算法的解决方案是：  
首先，选择一个起点，并标记它已经被访问。  
然后，遍历所有的节点，对于每个节点，计算从起点到这个节点的距离，并选择距离最短的节点作为下一个节点。  
如果已经访问了所有的节点，就找到了一个有效的最短路径。  
如果没有找到有效的最短路径，就回溯到上一个节点，并尝试其他的节点作为下一个节点。

### 6.3 IPO问题 ###

### 6.4 路灯问题（头条原题） ###

### 6.5 字典序问题 ###

### 6.6 NIM博弈 ###

### 6.7 分金条问题 ###

发表评论取消回复

表情：

评论列表（有 0 条评论，63人围观）

还没有评论，来说两句吧...

相关阅读

相关【软考】数据结构与算法基础 - 常见的算法设计思想（摊还分析）

一、摊还分析是什么？摊还分析是一种非常有用的算法设计和分析技术摊还分析是算法设计的一种思想摊还分析一般需要根据具体问题进行分析和设计。摊还分析的具体实现

清疚/ 2024年03月24日 13:56/ 0 赞/ 53 阅读

相关【软考】数据结构与算法基础 - 常见的算法设计思想（回溯分析）

一、回溯法是什么？回溯分析是一种算法设计和分析技术回溯法可以帮助我们找到解决问题的所有可能的解决方案。回溯法是一种通过探索所有可能的候选解来找出所有解的算法

比眉伴天荒/ 2024年03月24日 13:56/ 0 赞/ 58 阅读

相关【软考】数据结构与算法基础 - 常见的算法设计思想（枚举算法）

一、枚举算法是什么？枚举算法是一种简单而有效的算法设计思想枚举算法是一种暴力破解的方法枚举算法通过列举所有可能的解决方案来解决问题。枚举算法是一种通过

淩亂°似流年/ 2024年03月24日 13:55/ 0 赞/ 79 阅读

相关【软考】数据结构与算法基础 - 常见的算法设计思想（动态规划）

一、动态规划算法是什么？动态规划是一种常用的算法设计思想动态规划通过在每一步解决子问题并将结果存储在表中来最大化算法的效率。动态规划是一种非常强大的算法设计

矫情吗；*/ 2024年03月23日 19:38/ 0 赞/ 35 阅读

相关【软考】数据结构与算法基础 - 常见的算法设计思想（贪心算法）

一、贪心算法是什么？贪心算法是一种常见的算法设计思想贪心算法是一种简单而有效的算法设计思想贪心算法通过在每一步选择最优的解决方案来最大化算法的效率。贪心

我会带着你远行/ 2024年03月23日 19:38/ 0 赞/ 64 阅读

相关【软考】数据结构与算法基础 - 常见的算法设计思想（随机划分算法）

一、随机划分算法是什么？随机划分算法是一种基于随机性的算法随机划分算法是一种用于解决一些基于概率的问题的算法。随机划分算法用于解决一些分类或聚类问题。

浅浅的花香味﹌/ 2024年03月23日 19:38/ 0 赞/ 25 阅读

相关【软考】数据结构与算法基础 - 常见的算法设计思想（回溯）

一、回溯算法是什么？回溯算法是一种用于解决一些复杂的问题的算法。回溯算法是一种有组织的系统最优化搜索技术回溯算法可以看作蛮力法穷举搜索的改进。二、回溯

喜欢ヅ旅行/ 2024年03月23日 19:37/ 0 赞/ 72 阅读

相关【软考】数据结构与算法基础 - 常见的算法设计思想（递归与暴力递归）

一、递归是什么？递归是一种算法设计思想二、递归算法的核心思想递归通过将问题分解为更小的子问题来解决问题，然后通过解决这些子问题来得到原问题的解决方案。递

àì夳堔傛蜴生んèń/ 2024年03月23日 19:04/ 0 赞/ 69 阅读

相关【软考】数据结构与算法基础 - 算法基础

一、算法的特点 1.有穷性：算法必须在执行有穷步之后结束 2.确定性：算法中每一条指令都必须有确切的含义，不能含糊不清 3.算法必须有0个及以上的输入 4.算

女爷i/ 2024年03月22日 06:14/ 0 赞/ 118 阅读

相关【数据结构与算法】【算法思想】贪心算法

贪心算法回溯算法分治算法动态规划四种基本的算法思想：贪心算法，分治算法，回溯算法，动态规划，他们不是具体算法，常用来指导我们设计具体的算法和编码等。

迈不过友情╰/ 2022年12月01日 09:59/ 0 赞/ 269 阅读