学步园

  1、活动安排问题：
设有n个活动E={1,2,...,n}，其中每个活动都要求使用同一资源（如演讲会场等），且在同一时间内只有一个活动能使用这一资源。如果选择了执行活动i，则它在半开的时间区间[s[i],f[i])内占用资源，其中s[i]<f[i]，s[i]为其起始时间，f[i]为其结束时间。若区间[s[i],f[i])与[s[j],f[j])不相交，即s[i]>=f[j]或s[j]>=f[i]，则称活动i与活动j是相容的。活动安排问题就是要在所给的活动集合中选出最大的相容活动子集A。
  用贪心算法求解：
  （1）贪心选择性质：即原问题的最优解可以通过一系列局部最优的选择（称为贪心选择）来达到。这种选择并不依赖于子问题的解，这是与动态规划算法的主要区别，动态规划算法求解时需要用到子问题的解。每次贪心选择都是作出当前状态下的最好选择，原问题就简化为一个规模更小的子问题。
  这里的贪心选择就是每次总是选择具有最早结束时间且相容的活动。设各活动1,2,..,n按结束时间的非减序f[1]<=f[2]<=...<=f[n]排列，如果给出的活动未按此序排列，我们可以用O(nlogn)的时间将它重排。贪心选择从活动1开始，我们需要证明存在一个以贪心选择开始的最优解，并且每作一次贪心选择就将原问题简化为更小的子问题。基本思路是先考察一个全局最优解，然后证明可修改这个最优解，使其以贪心选择开始，选择后将原问题化一个更小的子问题。
  设A是原问题的一个最优解，且A中的活动也按结束时间非减序排列，第一个活动是k。若k=1,则A就是以贪心选择开始的最优解。若k>1，设B=A-{k}并{1}。由于f[1]<=f[k]，且A中活动互为相容，故B中活动也互为相容。又因|B|=|A|且A是最优解，故B也是最优解，且B以贪心选择活动1开始。
  （2）最优子结构性质：即原问题的最优解包含了作出贪心选择后的子问题的最优解。设B是包含活动1的一个原问题最优解，则B的子集C=B-{1}是子问题F={i属于E,且s[i]>=f[1]}的一个最优解。若不然，设D是子问题F的一个最优解，而C不是，则|D|>|C|，D中所有的活动与1相容。由于1不属于F，因此也不属于D。D并{1}是相容活动构成的集合，且元素个数大于B，这与B是原问题的最优解矛盾。
  算法如下：

//f中的元素按非减序排列f[1]<=f[2]<=...<=f[n]<br /> template<class Type><br /> void GreedySelector(int n,Type s[],Type f[],bool A[]){<br /> A[1]=true; //选择活动1<br /> int j=1; //j表示上一次选择的活动<br /> for(int i=2;i<=n;i++) //往后扫描所有的活动<br /> if(s[i]>=f[j]){ //若当前活动i和已选择的所有活动都相容（因为s[i]>=f[j]>=f[j-1]>=...>=f[1]）<br /> A[i]=true; //则选择该活动，将它加入到集合A中<br /> j=i;<br /> }else{<br /> A[i]=false;<br /> }<br /> }

  该算法的运行时间为O(n)。可见贪心选择可以依赖于过去所作的选择，但决不依赖于将来所作的选择，也不依赖于子问题的解。
  （3）最优解的证明：即证明每一步贪心选择最终能得到原问题的一个最优解。关键是要说明将子问题的最优解与所做的贪心选择合并后能得到原问题的最优解。一般是根据贪心选择性质和最优子结构性质，对贪心选择次数作数学归纳法，即可表明算法是正确的。
  这个问题我们也可以用等价类的思想来证明。设贪心选择出来的解为A={i[1]=1,i[2],...,i[m]}，实际上A中的各个活动把E划分成了不同的等价类。即E的每一段i[k],i[k]+1,...,i[k+1]-1中的所有活动都是两两不相容的(1<=k<=m)，最后一段为i[m],i[m+1],...,n-1,n。因为由贪心选择的过程可知，i[k]+1与i[k]不相容，i[k]+2与i[k]不相容，即s[i[k]+2]<=f[i[k]]<=f[i[k]+1]，因此i[k]+2与i[k]+1也不相容，同理可得段内每后一个活动与前面所有的活动都不相容，因此一个段内的所有活动都两两不相容。一个段相当于一个一个等价类，选择每个段中的第一个元素i[k](1<=k<=m)，恰好两两相容，构成了一个最优解A。否则如果某个段不选，则肯定不是最优解，如果再多选一个，则肯定有不相容的两个元素存在。注意如果选择段中的其他某个元素而不是第一个，则不能保证两两相容，因为段与段之间可能有元素不相容（但第一个元素肯定是相容的）。
  2、哈夫曼编码问题：
用于数据文件压缩。对文件中的不同字符使用01串来编码，通过给出现频率高的字符较短的编码，出现频率较低的字符以较长的编码，可以大大缩短总码长，获得一个最优编码方案。编码时采用前缀码形式，即任一字符的代码都不是其他字符代码的前缀。这样译码就会非常简单，直接从编码文件中不断取出代表某一字符的前缀码，转换为原字符即可，由于一个编码不会是另一个编码的前缀，因此不会出现译错的情况。为了不使一个编码成为另一个编码的前缀，需要采用二叉树来存储字符的前缀码。树叶代表给定的的字符，到左儿子的树枝用0标记，到右儿子的树枝用1标记，则字符的前缀码由树根到树叶道路上的01串构成。
  给定字符集C及其频率分布f，即C中任一字符c以频率f(c)在数据文件中出现。C的一个前缀编码方案对应一棵二叉树T。字符c在树T中的深度记为dT(c)，也称为其前缀码的长度。该编码方案的平均码长定义为B(T)=f(c[1])*dT(c[1])+f(c[2])*dT(c[2])+...+f(c[n])*dT(c[n])，即各字符的频率与码长乘积之和。平均码长最小的编码方案称为最优前缀码（哈夫曼编码）。我们的问题就是要构造出最优前缀码的二叉树T。
  用贪心算法来构造：由哈夫曼提出，称为哈夫曼算法。每次总是选择当前最小频率的结点来合并成一棵新树。
  （1）贪心选择性质：设二叉树T表示C的一个最优前缀码，x和y是C中具有最小频率的两个字符。我们要证明可对T作修改，得到新的二叉树T2仍然是最优前缀码，且T2中x和y是最深叶子且为兄弟（即两者具有最长码长且仅最后一位编码不同）。设b和c是T的最深叶子且为兄弟。不失一般性，可设f(b)<=f(c)，f(x)<=f(y)。显然我们有f(x)<=f(b)，f(y)<=f(c)。
  T中的叶子x肯定在b的上面，y也在c的上面，即dT(b)>dT(x)，dT(c)>dT(y)。我们首先交换b和x的位置得到树T1。则B(T)-B(T1)=f(x)*dT(x)+f(b)*dT(b)-f(x)*dT1(x)-f(b)*dT1(b)
=f(x)*dT(x)+f(b)*dT(b)-f(x)*dT(b)-f(b)*dT(x)=(f(b)-f(x))(dT(b)-dT(x))>=0。同理，在T1中交换y和c的位置得到树T2，可得B(T1)>=B(T2)。从而B(T2)<=B(T1)<=B(T)。因为T表示最优前缀码，可见B(T2)=B(T)，树T2也表示最优前缀码，且从最小频率的两个结点合并开始。
  （2）最优子结构性质：设x和y是T中的两个叶子且为兄弟，z是它们的父亲。将z看作是具有频率f(z)=f(x)+f(y)的字符，则树T1=T-{x,y}就表示字符集C1=C-{x,y}∪{z}的一个最优前缀码。
  先证明B(T)可以用B(T1)来表示。对任意c∈C-{x,y}，有dT(c)=dT1(c)，故f(c)*dT(c)=f(c)*dT1(c)。另一方面，dT(x)=dT(y)=dT1(z)+1，则f(x)*dT(x)+f(y)*dT(y)=(f(x)+f(y))(dT1(z)+1)=f(x)+f(y)+f(z)dT1(z)。这样我们就有B(T)=B(T1)+f(x)+f(y)。
  若T1不是C1的最优前缀码，设T2是C1的最优前缀码，则B(T2)<B(T1)。由于z被看作是C1中的一个字符，故z在T2中是叶子。若将x和y加入树T2中作为z的儿子，则得到表示字符集C的前缀码的二叉树T3，且有B(T3)=B(T2)+f(x)+f(y)<B(T1)+f(x)+f(y)=B(T)，这与T是C的最优前缀码矛盾，故T1是子问题C1的最优前缀码，证毕。
  算法如下：

//表示一个结点为根的树<br /> template<class Type><br /> class Huffman{<br /> private:<br /> friend BinaryTree<int> HuffmanTree(Type[],int);<br /> BinaryTree<int> tree; //本结点为根的树<br /> Type weight; //结点的频率<br /> public:<br /> operator Type() const{<br /> return weight;<br /> }<br /> };<br /> template<class Type><br /> BinaryTree<int> HuffmanTree(Type f[],int n){<br /> //生成单结点的树<br /> Huffman<Type>* w=new Huffman<Typ>[n+1];<br /> BinaryTree<int> z,zero;<br /> for(int i=1;i<=n;i++){<br /> z.MakeTree(i,zero,zero); //创建表示单结点w[i]的树<br /> w[i].weight=f[i];<br /> w[i].tree=z;<br /> }</p> <p> //建优先队列<br /> MinHeap<Huffman<Type> > Q(1);<br /> Q.Initialize(w,n,n); //用表示各个字符频率f(c)的结点来初始化该队列</p> <p> //反复合并最小频率树<br /> for(int i=1;i<n;i++){<br /> Q.DeleteMin(x);<br /> Q.DeleteMin(y); //取出最小频率的两棵树放到x和y中<br /> z.MakeTree(0,x.tree,y.tree); //将x和y合并成一棵新树z，x为其左儿子，y为其右儿子<br /> x.weight+=y.weight;<br /> x.tree=z; //合并后的树放到x.tree中，频率为两子结点频率之和<br /> Q.Insert(x);<br /> }</p> <p> Q.DeleteMin(x);<br /> Q.Deactivate();<br /> delete[] w;<br /> return x.tree;<br /> }

  由贪心选择性质和最优子结构性质立即可推出哈夫曼算法是正确的。算法代码中的n-1次合并使优先队列中只剩下一棵树，即为所求的T。优先队列一般用最小堆来实现，初始化它需要O(n)时间，DeleteMin和Insert只需O(logn)时间，因此算法运行时间为O(nlogn)。
  3、最优装载问题：
有一批集装箱要装上一艘载重量为c的轮船。其中集装箱i的重量为w[i]。应如何装载才能使轮船上的集装箱数目达到最大（装载体积没有限制）。即求max{x[1]+x[2]+...+x[n]}，约束条件为w[1]x[1]+w[2]x[2]+...+x[n]x[n]<=c，x[i]∈{0,1}，1<=i<=n。x[i]=0表示不装上去，x[i]=1表示装上去。
  用贪心算法求解：每次总是选择重量最轻的集装箱装到轮船上。
  （1）贪心选择性质：设集装箱已按重量从小到大排序，(x[1],x[2],...,x[n])是最优装箱问题的一个最优解，k=min{i | x[i]=1}，即k为装上轮船的最轻集装箱。若k=1，则(x[1],...,x[n])是从贪心选择开始的最优解。若k>1，则x[1]=0。我们取y[1]=1,y[k]=0,y[i]=x[i],1<i<=n,i!=k，则有w[1]y[1]+...+w[n]y[n]=w[1]-w[k]+w[1]x[1]+...+w[n]x[n]<=w[1]x[1]+...+w[n]x[n]<=c，y[1]+y[2]+...+y[n]=x[1]+x[2]+...+x[n]，因此(y[1],...,y[n])是原问题的一个最优解，且从贪心选择开始。
  （2）最优子结构性质：设(x[1],x[2],...,x[n])是原问题的一个满足贪心选择性质的最优解，即x[1]=1。则(x[2],...,x[n])是轮船重量为c-w[1]，集装箱为{2,3,...,n}的相应子问题的最优解。若不然，设子问题的一个最优解，可很快地构造出原问题的一个更优解，导致矛盾。
  算法如下：

template<class Type><br /> void Loading(int x[],Type w[],Type c,int n){<br /> int* t=new int[n];<br /> Sort(w,t,n); //对重量从小到大排序，t[i]记录了排序后的数组元素下标，即w[t[i]]为数组w中第i小的元素<br /> for(int i=0;i<n;i++)<br /> x[i]=0;<br /> for(int i=0;i<n && w[t[i]]<=c;i++){ //w[t[i]]为当前的最轻重量<br /> x[t[i]]=1; //选择当前最轻的重量<br /> c-=w[t[i]];<br /> }<br /> }

  算法的主要计算量在于将重量排序，故计算时间为O(nlogn)。
  另外，像单源最短路径的Dijkstra算法、构造带权图的最小生成树的Prim算法、Kruskal算法等，都是贪心算法的典型应用。
  贪心算法的基本特征：贪心选择性质（存在一个以贪心选择开始的最优解）、最优子结构性质。
  贪心算法的基本思想：常用于解最优化问题。找出贪心选择性质和最优子结构性质、根据性质构造贪心算法。