贪心算法学习总结_贪心算法的基本思想和特点。

目录

前言

一、贪心算法的基本特性

1、贪心选择性质

2、最优子结构性质

 二、贪心算法的例题

单源最短路径——Dijkstra算法

会场安排问题

---

前言

 贪心算法是大家十分熟悉的算法，字如其名，贪心算法是一种对某些求最优解问题的更简单、更迅速的设计技术。贪心算法特点是一步一步地进行，常以当前情况为基础根据某个优化测度作最优选择，而不考虑各种可能的整体情况，省去了为找最优解要穷尽所有可能而必须耗费的大量时间。近两周我们学习了贪心的算法，现在让我们来看一下贪心算法的相关知识点。

一、贪心算法的基本特性

1、贪心选择性质

一个问题的整体最优解可通过一系列局部的最优解的选择达到，并且每次的选择可以依赖以前作出的选择，但不依赖于后面要作出的选择。这就是贪心选择性质。对于一个具体问题，要确定它是否具有贪心选择性质，必须证明每一步所作的贪心选择最终导致问题的整体最优解 。

2、最优子结构性质

当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质。问题的最优子结构性质是该问题可用贪心法求解的关键所在。在实际应用中，至于什么问题具有什么样的贪心选择性质是不确定的，需要具体问题具体分析 。同时我们可以发现，贪心算法局部最优解也便是全局的最优解，这也是贪心选择算法与动态规划算法最大的区别。

 二、贪心算法的例题

单源最短路径——Dijkstra算法

算法介绍：

迪杰斯特拉(Dijkstra)算法是典型最短路径算法，用于计算一个节点到其他节点的最短路径。 
它的主要特点是以起始点为中心向外层层扩展(广度优先搜索思想)，直到扩展到终点为止。

基本思想：

 通过Dijkstra计算图G中的最短路径时，需要指定起点s(即从顶点s开始计算)。

     此外，引进两个集合S和U。S的作用是记录已求出最短路径的顶点(以及相应的最短路径长度)，而U则是记录还未求出最短路径的顶点(以及该顶点到起点s的距离)。

     初始时，S中只有起点s；U中是除s之外的顶点，并且U中顶点的路径是"起点s到该顶点的路径"。然后，从U中找出路径最短的顶点，并将其加入到S中；接着，更新U中的顶点和顶点对应的路径。 然后，再从U中找出路径最短的顶点，并将其加入到S中；接着，更新U中的顶点和顶点对应的路径。 ... 重复该操作，直到遍历完所有顶点。

操作步骤：

(1) 初始时，S只包含起点s；U包含除s外的其他顶点，且U中顶点的距离为"起点s到该顶点的距离"[例如，U中顶点v的距离为(s,v)的长度，然后s和v不相邻，则v的距离为∞]。

(2) 从U中选出"距离最短的顶点k"，并将顶点k加入到S中；同时，从U中移除顶点k。

(3) 更新U中各个顶点到起点s的距离。之所以更新U中顶点的距离，是由于上一步中确定了k是求出最短路径的顶点，从而可以利用k来更新其它顶点的距离；例如，(s,v)的距离可能大于(s,k)+(k,v)的距离。

(4) 重复步骤(2)和(3)，直到遍历完所有顶点。

 如下是相关题目链接：大家可以试试自己能不能把这个题目给做出来。

e849. Dijkstra求最短路 I - AcWing题库

会场安排问题

通过这一个经典贪心算法问题，我们来证明一下贪心的性质和问题的求解思路。

假设要在足够多的会场里安排一批活动，并希望使用尽可能少的会场。设计一个有效的贪心算法进行安排。对于给定的k个待安排的活动，计算使用最少会场的时间表。
输入：
第1行有1个正整数k，表示有k个待安排的活动。下来的k行中，每行有2个正整数，分别表示k个待安排的活动的开始时间和结束时间。时间以0点开始的分钟计。
输出：
将计算出的最少会场数输出。

思路：首先能够衔接的会议必定是下一个活动的开始时间必定是大于上一个活动的结束时间，而下一个活动的结束时间必定是大于上一个活动的结束时间的，如果存在两个活动互斥，但是都能够跟下一个活动衔接，那么我们就不需要考虑这些互斥的活动了，可以把这些互斥的活动算作一个单位。假如存在一个更小的活动，可以跟这些互斥的活动中的一个或两个衔接，那么这个更小的活动的结束时间必然都小于互斥活动的开始时间和结束时间，又因为这些活动的数据输入时是无序的，所以首先要做的就是对所有活动进行排序。

所以我们按会场开始的时间进行排序，然后遍历，尽量使会场能放下更多的场次。如果上一个活动在t时间结束，下一个活动最早应该在t+1时间开始

如下是相关题目链接：大家可以试试自己能不能把这个题目给做出来。

http://acm.nyist.edu.cn/JudgeOnline/problem.php?pid=14