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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

### 6.3 IPO问题 ###

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

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

### 6.6 NIM博弈 ###

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

发表评论取消回复

表情：

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

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

相关阅读

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

一、Dijkstra算法是什么？ Dijkstra算法是一种用于解决带权重图的最短路径问题的经典算法。二、Dijkstra算法的基本原理以下是Dijkstra

短命女/ 2024年03月26日 22:17/ 0 赞/ 63 阅读

相关【数据结构与算法之贪心算法】贪心算法的基本思想

【数据结构与算法之贪心算法】贪心算法的基本思想文章目录【数据结构与算法之贪心算法】贪心算法的基本思想贪心算法的优点是效率较高，实现较为简单

深碍√TFBOYSˉ_/ 2024年03月25日 19:16/ 0 赞/ 65 阅读

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

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

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

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

一、排序算法排序算法是数据结构中的重要部分之一排序算法用于将一组数据按照特定的顺序排列。排序可以算是最基本，最常用的算法，也是笔试面试中最常被考的算法。

男娘i/ 2024年03月24日 12:36/ 0 赞/ 44 阅读

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

相关软考自查：数据结构与算法基础

数据结构与算法基础内容提要数组与矩阵线性表广义表树与二叉树图排序与查找算法基础及常见的算法 ------

谁践踏了优雅/ 2021年12月21日 04:03/ 0 赞/ 338 阅读