【贪婪技术】

知识框架

No.1 贪婪技术

一、问题引入

题目：找零问题

题意：用指定面额为d1>d2>…>dm的最少数量的硬币找出金额为n的零钱；

(就是说从给定的面额的硬币 使用 最少数量的硬币 凑出 金额 n)

d1=5角，d2=2角，d3=1角 ，d4=5分，d5=2分，d6=1分

当n=0.48的时候，请确定一种最佳选择序列的逻辑策略？

( 贪心的思想也就是 直接从最大的往下减；)

二、基本思想

贪婪法：通过一系列步骤来构造问题的解，每一步对目前构造的部分解做一个扩展，直到获得问题的完整解为止。

1. 可行的：必须满足问题的约束
2. 局部最优：是当前步骤中所有可行选择中最佳的局部选择
3. 不可取消：选择一旦做出，在算法的后面步骤中就无法改变

在每一步中，它要求“贪婪”地选择最佳操作，并希望通过一系列局部的最优选择，能够产生一个整个问题（全局）的最优解

贪婪技术是否有效？

1. 的确存在某类问题：一系列局部最优选择对于它们的每一个实例都能够产生一个最优解
2. 或者我们关心的是近似解，或者只能满足于近似解

三、问题实例：连续背包问题

问题描述：

已知有n种物品和一个可容纳W重量的背包，每种物品I的重量为wi，假定将物品I的某一部分xi放入背包就会得到pi*xi的效益(0≤xi≤1, pi>0) ，采用怎样的装包方法才会使装入背包物品的总效益为最大呢？

下面的方案体现从不同角度进行的贪心，在局部最优解的情况下；有时候可能得到全局最优解的；

1. 方案1：按物品价值降序装包；（贪心思想）
2. 方案2：按物品重量升序装包；（贪心思想）
3. 方案3：按物品价值与重量比值的降序装包；（贪心思想）

No.2 最小生成树问题

一、基本思想

给定n个点，把它们按照一种成本最低的方式连接起来，使得每一对点之间都有一条路径。这个问题可以表示成最小生成树问题。

（就是说有n个点，然后让你连接 n-1 条边使得这些点与点之间互通到达；使得连通成本最低）

1. 连通图的一棵生成树是包含图的所有顶点的连通无环子图（也就是一棵树）
2. 加权连通图的一棵最小生成树是图的权重最小的生成树
3. 最小生成树问题：就是求给定的加权连通图的最小生成树问题

用穷举法来解决不现实；

1. 随着图的规模增长，生成树的数量呈指数增加
2. 生成一个给定图的所有生成树并非易事

二、Prim算法

1、主要思想和步骤

主要思想：Prim算法通过一系列不断扩张的子树来构造一棵最小生成树。

方法步骤：

1. 从图的顶点集合V中任选一个单顶点，作为序列中的初始子树。
2. 每一次迭代时，以一种贪婪的方式来扩张当前的生成树，即简单地把不在树中的最近顶点添加到树中（以一条权重最小的边和树中的顶点相连，树的形状是无所谓的）
3. 当图的所有顶点都包含在所构造的树中以后，算法停止：每次只对树扩展一个顶点

方法要求：

1. 对于每个不在当前树中的顶点，必须知道它连接树中顶点的最短边的信息；
2. 每一个顶点附加两个标记：树中最近顶点的名称、相应边的权重（这两个标记在代码中是遍历来找最近顶点的）；

Prim算法是否能产生一个最优解？

答案是肯定的

2、算法效率

Prim算法的实际运用算法效率 还是主要靠你使用的数据结构决定的；

1. 表示图本身的数据结构
2. 表示集合V-VT的优先队列的数据结构

如果图是由邻接链表表示的，并且优先队列是由最小堆实现的，那么该算法的运行时间属于O(|E|log|V|)

1. 因为该算法进行了|V|-1次删除最小元素的操作，
2. 并且进行了|E|次验证，每一种操作都是O(log|V|)

如果使用更先进的可能算法效率会更好！

三、Kruskal算法

1、主要思想和步骤

1. Kruskal算法把一个加权连通图G=<V,E>的最小生成树看作是一个具有|V|-1条边的无环子图，并且边的权重和是最小的。
2. 该算法通过对子图的一系列扩展来构造一棵最小生成树，这些子图总是无环的，但在算法的中间阶段，并不一定是连通的。
3. 贪心到极致。

方法步骤：

1. 首先，按照权重的非递减顺序对图中的边进行排序
2. 然后，从一个空子图开始，扫描有序列表，试图把列表中的下一条边加到当前的子图中。（必须保证该添加不会导致一个回路）
3. 必须要不成环才能加入；

算法详解：

1. 对包含给定图的所有顶点和某些边的一系列森林所做的连续动作
   1. 初始森林是由|V|棵只有根结点的树构成的
   2. 最终的森林是由一棵树构成的，它就是该图的最小生成树
   3. 每次迭代的时候，从图的边的有序列表中取出下一条边(u,v)，并找到包含顶点u和v的树，如果他们不是同一棵树，通过加入边(u,v)把这两棵树连成一棵更大的树

No.3 Dijkstra算法

一、主要思想

单起点最短路径问题：对于加权连通图的一个称为起点的给定顶点，求出它到所有其他顶点之间的一系列最短路径。

（也就是说给了一个起源点，就能够通过这个算法求得起源点到其它各个顶点的最短路径，是属于一步到位的）

方法步骤：

Dijkstra算法按照从给定起点到图中顶点的距离，顺序求出最短的路径。

1. 首先，它求出从起点到最接近起点的顶点之间的最短路径
2. 然后，求出第二近的，依此类推

二、问题实例：

主要针对的是边上权值非负情形的单源最短路径问题。

问题的提法：

给定一个带权有向图D与源点 v，求从 v 到D中其他顶点的最短路径。限定各边上的权值大于或等于0。

问题的解决步骤：（每次看的都是到源点v的距离比较）

为求得这些最短路径, Dijkstra提出按路径长度的递增次序, 逐步产生最短路径的算法。首先求出长度最短的一条最短路径，再参照它求出长度次短的一条最短路径，依次类推，直到从顶点v到其它各顶点的最短路径全部求出为止。

1. 引入辅助数组dist。它的每一个分量dist[i]表示当前找到的从源点 v0到终点 vi 的最短路径的长度。初始状态：
   1. 若从源点v0到顶点 vi 有边, 则dist[i]为该边上的权值；
   2. 若从源点v0到顶点 vi 无边, 则dist[i]为∞。
2. 假设 S 是已求得的最短路径的终点的集合，则可证明：下一条最短路径必然是从v0 出发，中间只经过 S 中的顶点便可到达的那些顶点vx (vx∈V-S )的路径中的一条。
3. 每次求得一条最短路径后, 其终点vk 加入集合S，然后对所有的vi∈V-S，修改其 dist[i]值。

代码：

void dij(int index){//初始化vis，dis，以及main上面的变量；；memset(vis,0,sizeof(vis));memset(dis,inf,sizeof(dis));for(int i=0;i<n;i++)dis[i]=mp[index][i];dis[index]=0;way[index]=index;//初始化的人员，初始化的道路选择；；num[index]=people[index];cnt[index]=1;//找n个最短点，一个for找到一个点，vis【点】=1；//显然，第一个点是自己本身dis【index】=0；//第一部分：找最短的for(int i=0;i<n;i++){int u=-1,minn=inf;for(int j=0;j<n;j++){if(vis[j]==0&&dis[j]<minn){u=j;minn=dis[j];}}if(u==-1)break;vis[u]=1;//第二部分：更新距离for(int j=0;j<n;j++){if(vis[j]==0&&dis[j]>dis[u]+mp[u][j]){dis[j]=dis[u]+mp[u][j];num[j]=num[u]+people[j];way[j]=u;cnt[j]=cnt[u];//c出现下面这个条件啊，就会再出来一个最优判断。}else if(vis[j]==0&&dis[j]==dis[u]+mp[u][j]){cnt[j]=cnt[u]+cnt[j];if(num[j]<num[u]+people[j]){way[j]=u;num[j]=num[u]+people[j];}}}}
}

Dijkstra算法的步骤详细解释：

1. 在第i次迭代开始以前，该算法已经确定了i-1条连接起点和离起点最近顶点之间的最短路径。他们构成了一棵子树Ti

   1. 和Ti的顶点相邻的顶点集合成为“边缘顶点”，以它们为候选对象，选出下一个最接近起点的顶点。
   2. 对于每一个边缘顶点u，该算法求出它到最近的树中顶点v的距离
   3. 给每个顶点附加两个标记
      1. 数字标记d指出目前为止该算法求出的从起点到该顶点间最短路径的长度
      2. 另一个指出在这条路径上倒数第二个顶点的名字。

2. 在确定了加入树中的顶点u*以后，还需要做两个操作：

   1. 把u*从边缘集合中移到顶点集合
   2. 对于余下的每个边缘顶点u，如果通过权重为w(u*,u)的边和u相连，当du+w(u*,u)<du时，把u的标记分别更新为u和du+w(u*,u)

3. 虽然从算法的标记和结构，Dijkstra算法和Prim算法的用法十分相似，且他们都会从余下顶点的优先队列中选择下一个顶点，但他们解决的是不同的问题。

No.4 哈夫曼问题

一、哈夫曼树