多阶段决策过程（multistepdecisionprocess）是指这样一类特殊的.doc

第四部分 贪心算法（Greedy Algorithm）41 贪心算法的基本思想顾名思义，贪心算法总是作出在当前看来最好的选择。也就是说贪心算法并不从整体最优考虑，它所作出的选择只是在某种意义上的局部最优选择。当然，希望贪心算法得到的最终结果也是整体最优的。虽然贪心算法不能对所有问题都得到整体最优解，但对许多问题它能产生整体最优解。如单源最短路经问题，最小生成树问题等。在一些情况下，即使贪心算法不能得到整体最优解，其最终结果却是最优解的很好近似。基本思想：通过一系列选择步骤来构造问题的解，每一步都是对当前部分解的一个扩展，直至获得问题的完整解。所做的每一步选择都必须满足：1) 可行的：必须满足问题的约束。2) 局部最优：当前所有可能的选择中最佳的局部选择。3) 不可取消: 选择一旦做出，在后面的步骤中就无法改变了。贪心算法是通过做一系列的选择来给出某一问题的最优解，对算法的每一个决策点，做一个当时（看起来）是最佳的选择。这种启发式策略并不总是能产生出最优解。4 2基于贪心算法的实例求解421活动选择问题活动安排问题：设有n个活动a1, a2, , an , 每个活动都要求使用同一资源，而同一时间内只允许一个活动使用这一资源。已知活动ai要求使用该资源的起始时间为si，结束时间为fi，且si= fi 。要求在a1, a2, , an中选出最大的相容活动子集。两活动ai , aj (ij)相容是指：。例：n=4 , 活动： a1 a2 a3 a4 si： 4 2 1 8 fi： 7 4 5 10贪心选择策略：按结束时间从早到晚安排活动，每次选择与已选出的活动相容的结束时间尽可能早的活动。局部最优性：每次为资源留下尽可能多的时间以容纳其它活动。贪心算法：算法 ACTIVITY_ARRANGEMENT输入：活动数n，表示n个活动起始时间和结束时间的数组s1.n和f1.n。输出：这n个活动的最大的相容活动子集A。/对f1.n按升序地址排序，排序结果返回到数组d1.n中,/使得fd1=fd2=fj then A=A+di/在A中加入活动di。 j=di end if end for return Aend ACTIVITY_ARRANGEMENT该算法的时间复杂性：(nlogn)(主要为排序的时间) 贪心算法的特点：贪心算法往往效率高，一般时间复杂性为多项式阶。贪心算法一般较简单，其关键和难点在于贪心选择策略的确定，更困难的是证明某贪心算法确实可求出最优解。活动安排问题的贪心选择策略的正确性证明：证明贪心算法ACTIVITY_ARRANGEMENT求出的解为最优解。证明思路：任意一个最优解都可通过替换变成该贪心算法求出的解，而且解的最优性不变。422 哈夫曼编码Huffman codes哈夫曼编码是广泛地用于数据文件压缩的十分有效的编码方法。其压缩率通常在20%90%之间。哈夫曼编码算法用字符在文件中出现的频率表来建立一个用0，1串表示各字符的最优表示方式。 给出现频率高的字符较短的编码，出现频率较低的字符以较长的编码，可以大大缩短总码长。 例如一个包含100,000个字符的文件，各字符出现频率不同，如下表所示。定长变码需要300,000位，而按表中变长编码方案，文件的总码长为： （451+133+123+163+94+54）1000=224,000。比用定长码方案总码长较少约45%。 对每一个字符规定一个0,1串作为其代码，并要求任一字符的代码都不是其它字符代码的前缀。这种编码称为前缀码。 编码的前缀性质可以使译码方法非常简单。 表示最优前缀码的二叉树总是一棵完全二叉树，即树中任一结点都有2个儿子结点。 平均码长定义为： 使平均码长达到最小的前缀码编码方案称为给定编码字符集C的最优前缀码。哈夫曼提出构造最优前缀码的贪心算法，由此产生的编码方案称为哈夫曼编码。 哈夫曼算法以自底向上的方式构造表示最优前缀码的二叉树T。 算法以|C|个叶结点开始，执行|C|1次的“合并”运算后产生最终所要求的树T。HUFFMAN(c)1 n|c|2 QC3 for i to n-14 do allocate a new code z5 leftzxEXTRACT-MIN(Q)6 rightzyEXTRACT-MIN(Q)7 fz=fx+fy8 INSERT(Q,z)9 return EXTRACT-MIN(Q) 图4.1 哈夫曼算法的操作步骤时间分析，我们假设Q是作为最小二叉堆实现的。对包含个字符的集合C，第二行中对Q的初始化可用在前面建堆章节中介绍所用的时间O(n)内完成。第3-8行中的for循环执行了n-1次，又因每一次堆操作需要O（lgn）时间，故整个循环需要O（nlgn）时间。这样，作用于n个字符集合的HUFFMAN的总的运行时间为O（nlgn）。423 最小生成树Minimum spanning trees 假设已知一无向连通图G=(V,E)，其加权函数为w:ER，我们希望找到图G的最小生成树。后文所讨论的两种算法都运用了贪心方法，但在如何运用贪心法上却有所不同。 下列的算法GENERNIC-MIT正是采用了贪心策略，每步形成最小生成树的一条边。算法设置了集合A，该集合一直是某最小生成树的子集。在每步决定是否把边(u,v)添加到集合A中，其添加条件是A(u,v)仍然是最小生成树的子集。我们称这样的边为A的安全边，因为可以安全地把它添加到A中而不会破坏上述条件。 GENERNIC-MIT(G,W)1. A2. while A没有形成一棵生成树3 do 找出A的一条安全边(u,v);4. AA(u,v);5. return A注意从第1行以后，A显然满足最小生成树子集的条件。第2-4行的循环中保持着这一条件，当第5行中返回集合A时，A就必然是一最小生成树。算法最棘手的部分自然是第3行的寻找安全边。必定存在一生成树，因为在执行第3行代码时，根据条件要求存在一生成树T，使AT，且若存在边(u,v)T且(u,v)A，则(u，v)是A的安全边。定理4.1设图G(V,E)是一无向连通图，且在E上定义了相应的实数值加权函数w，设A是E的一个子集且包含于G的某个最小生成树中，割(S,V-S)是G的不妨害A的任意割且边(u,v)是穿过割(S,V-S)的一条轻边，则边(u,v)对集合A是安全的。下面介绍两个算法：Kruskal算法和Prim算法 Kruskal算法是直接基于上面中给出的一般最小生成树算法的基础之上的。该算法找出森林中连结任意两棵树的所有边中具有最小权值的边(u,v)作为安全边，并把它添加到正在生长的森林中。设C1和C2表示边(u,v)连结的两棵树。因为(u,v)必是连C1和其他某棵树的一条轻边，所以由推论2可知(u,v)对C1是安全边。Kruskal算法同时也是一种贪心算法，因为算法每一步添加到森林中的边的权值都尽可能小。 Kruskal算法的实现类似于计算连通支的算法。它使用了分离集合数据结构以保持数个互相分离的元素集合。每一集合包含当前森林中某个树的结点，操作FIND-SET(u)返回包含u的集合的一个代表元素，因此我们可以通过FIND-SET(v)来确定两结点u和v是否属于同一棵树，通过操作UNION来完成树与树的联结。 MST-KRUSKAL(G,w)1. A2. for 每个结点v VG 3. do MAKE-SET(v)4. 根据权w的非递减顺序对E的边进行排序5. for 每条边(u,v)E，按权的非递减次序6. do if FIND-SET(u) FIND-SET(v)7. then AA(u,v)8. UNION(u,v)9 return A(a) (b) (c) (d) (e) (f) (g) (h) (i) (j) (k) (l) (m) (n) 图4.2 Kruskal算法在图4.1所示的图上的执行流程 Kruskal算法在图G=(V,E)上的运行时间取决于分离集合这一数据结构如何实现。我们采用在分离集合中描述的按行结合和通路压缩的启发式方法来实现分离集合森林的结构，这是由于从渐近意义上来说，这是目前所知的最快的实现方法。初始化需占用时间O(V)，第4行中对边进行排序需要的运行时间为O(EE)；对分离集的森林要进行O(E)次操作，总共需要时间为O(Ea(E,V)，其中a函数为Ackerman函数的反函数。因为a(E,V)=O(E)，所以KruskaI算法的全部运行时间为O(EE)。 正如Kruskal算法一样，Prim算法也是第上面中讨论的一般最小生成树算法的特例。Prim算法的执行非常类似于寻找图的最短通路的Dijkstra算法。Prim算法的特点是集合A中的边总是只形成单棵树。因为每次添加到树中的边都是使树的权尽可能小的边，因此上述策略也是贪心的。 有效实现Prim算法的关键是设法较容易地选择一条新的边添加到由A的边所形成的树中，在下面的伪代码中，算法的输入是连通图G和将生成的最小生成树的根r。在算法执行过程中，不在树中的所有结点都驻留于优先级基于key域的队列Q中。对每个结点v，keyv是连接v到树中结点的边所具有的最小权值；按常规，若不存在这样的边则keyv=。域pv说明树中v的“父母”。在算法执行中，GENERIC-MST的集合A隐含地满足： A=(v,pv)|vV-r-Q当算法终止时，优先队列Q为空，因此G的最小生成树A满足: A=(v,pv)|v V-r (a) (b) (c) (d) (e) (f) (g) (h) (i) 图4.3 Prim算法在图4.1所示的图上的执行流程 MST-PRIM(G,w,r)1. QVG2. for 每个uQ3. do keyu4. keyr05. prNIL6. while Q7. do uEXTRACT-MIN(Q)8. for 每个vAdju9. do if vQ and w(u,v)keyv10. then pvu11. keyvw(u,v)Prim算法的性能取决于我们如何实现优先队列Q。若用二叉堆来实现Q,我们可以使用过程BUILD-HEAP来实现第1-4行的初始化部分，其运行时间为O(V)。循环需执行|V|次，且由于每次EXTRACT-MIN操作需要O(V)的时间，所以对EXTRACT-MIN的全部调用所占用的时间为O(VV)。第8-11行的for循环总共要执行O(E)次，这是因为所有邻接表的长度和为2|E|。在for循环内部，第9行对队列Q的成员条件进行测试可以在常数时间内完成，这是由于我们可以为每个结点空出1位(bit)的空间来记录该结点是否在队列Q中，并在该结点被移出队列时随时对该位进行更新。第11行的赋值语句隐含一个对堆进行的DECREASE-KEY操作，该操作在堆上可用0(V)的时间完成。因此，Prim算法的整个运行时间为O(VV+EV)=O(EV)，从渐近意义上来说，它和实现Kruskal算法的运行时间相同。 通过使用Fibonacci堆，Prim算法的渐近意义上的运行时间可得到改进。在Fibonacci堆中我们己经说明，如果|V|个元素被组织成Fibonacci堆，可以在O(V)的平摊时间内完成EXTRACT-MIN操作，在O(1)的平摊时间里完成DECREASE-KEY操作（为实现第11行的代码），因此，若我们用Fibonacci堆来实现优先队列Q，Prim算法的运行时间可以改进为O(E+VV)。4.2.4背包问题问题描述：设有一个容量为C的背包，n个物品的集合U=u1, u2, , un，物品ui的体积和价值分别为sj和vj，C, sj, vj都是正实数。在U中选择物品装入背包，使得装入背包的物品总价值最大。设允许取每种物品的一部分装入背包。 数学模型： z=max v1x1+ v2x2+ vnxn s1x1+ s2x2+ snxn=C 0= xi =yd2=ydn。 d=sort(y, n) for i=1 to n xi=0 /对x1.n初始化。 i=1; maxv=0; rc=C /以下rc表示当前背包的剩余容量。while rc0 and i=nj=di / uj为当前考虑选择的物品 if sj=rc then xj=1; rc=rc-sj /物品uj全部装入背包。 else xj=rc/sj /选择物品uj的一部分将背包填满。 rc=0 end if maxv=maxv+vj*xji=i+1 end while return maxv, x1.nend GREEDY_KNAPSACK 算法的时间复杂性：(nlogn) (主要为排序的时间)43 参考代码/* 活动选择的问题 */templatevoid greedyselector(int n, type s 1, type f , bool a a 1 = true;int j = 1;for (int i=2;i=fj) ai = true; j=i;else ai= false;/* Huffman编码问题的设计和实现 */#include #include #include #define MAXLEN 100#define MAXVALUE 10000/* 结点结构定义 */typedef struct int weight; /*权值*/ int flag; /*标记*/ int parent; /*指向父结点的指针*/ int lchild; int rchild;HuffNode;/*Huffman 编码结构*/typedef struct char bitMAXLEN; int len; int weight;Code;/* HuffTree 初始化 */void HuffmanInit(int weight, int n, HuffNode hufftree) int i; /* huffman结构初始化，n个叶结点的二叉树有2n-1个结点 */ for(i = 0; i 2 * n - 1; i+) hufftreei.weight = (i n) ? weighti : 0; hufftreei.parent = -1; /*根，无父结点 */ hufftreei.flag = 0; hufftreei.lchild = -1; /* i不可能是某个结点的左子树或右子树*/ hufftreei.rchild = -1; /*建立权值为weight0.n-1的n个结点的HuffTree */void Huffman(int weight, int n, HuffNode hufftree) int i, j, m1, m2, x1, x2; HuffmanInit(weight, n, hufftree); /*初始化 */ /* 构造n - 1个非叶结点 */ for(i = 0; i n - 1; i+) m1 = m2 = MAXVALUE; /* m1 = m2 */ x1 = x2 = 0; for(j = 0; j n + i; j+)/*在森林中找两个权值最小的结点*/ if(hufftreej.flag = 0) /* 该结点未加入到huffman树中 */ if(hufftreej.weight m1) m2 = m1; x2 = x1; m1 = hufftreej.weight; x1 = j; else if(hufftreej.weight m2) m2 = hufftreej.weight; x2 = j; hufftreex1.parent = n + i; hufftreex2.parent = n + i; hufftreex1.flag = 1; hufftreex2.flag = 1; hufftreen + i.weight = hufftreex1.weight + hufftreex2.weight; hufftreen + i.lchild = x1; hufftreen + i.rchild = x2; /* huffman编码函数 */void HuffmanCode(HuffNode hufftree, int n, Code huffcode) Code cd; int i, j, child, parent; for(i = 0; i n; i+) /* 求第i个结点的Huffman编码 */ cd.len = 0; cd.weight = hufftreei.weight; child = i; parent = hufftreei.parent; /* 准备往上爬 */ while(parent != -1) /* 不到?*/ cd.bitcd.len+ = (hufftreeparent.lchild = child) ?0 : 1; child = parent; parent = hufftreechild.parent; for(j = 0; j cd.len; j+) huffcodei.bitj = cd.bitcd.len - 1 - j; huffcodei.bitcd.len = 0; huffcodei.len = cd.len; huffcodei.weight = cd.weight; /* 打印huffman编码 */void PrintCode(Code c, int n) int i; printf(OutPut code :n); for(i = 0; i n; i+) printf(weight = %d code %sn, ci.weight, ci.bit);/* 测试程序 */void main(void) int w = 3, 1, 4, 8, 2, 5, 7; HuffNode huff100; Code hcode10; Huffman(w, 7, huff); HuffmanCode(huff, 7, hcode); PrintCode(hcode, 7); getch();/ 图的存储结构以 数组邻接矩阵表示, 用普里姆（Prim）算法构造图的最小生成树。#include #include #include #include #define TRUE 1#define FALSE 0#define NULL 0#define OVERFLOW -2#define OK 1#define ERROR 0typedef int Status;typedef int VRType;typedef char InfoType; /弧相关的信息typedef char VertexType10; /顶点的名称为字符串#define INFINITY 32767 /INT_MAX 最大整数#define MAX_VERTEX_NUM 20 /最大顶点数 typedef enumDG,DN,AG,AN GraphKind; /有向图,有向网,无向图,无向网typedef struct ArcCell VRType adj; / VRType 是顶点的关系情况,对无权图用1或0表示有关系否,对带权图(网), / 则填权值。InfoType *info; / 指向该弧相关信息的指针。 ArcCell, AdjMatrixMAX_VERTEX_NUM MAX_VERTEX_NUM ;typedef struct VertexType vexsMAX_VERTEX_NUM; / 顶点数据元素AdjMatrix arcs; / 二维数组作邻接矩阵int vexnum, arcnum; / 图的当前顶点数和弧数 GraphKind kind; / 图的种类标志 MGraph;Status CreateGraph(MGraph &G, GraphKind kd)/ 采用数组邻接矩阵表示法，构造图G Status CreateDG(MGraph &G); Status CreateDN(MGraph &G); Status CreateAG(MGraph &G); Status CreateAN(MGraph &G); G.kind=kd; switch(G.kind) case DG: return CreateDG(G); /构造有向图G case DN: return CreateDN(G); /构造有向网G case AG: return CreateAG(G); /构造无向图G case AN: return CreateAN(G); /构造无向网G default: return ERROR;/CreateGraphStatus CreateDG(MGraph &G)return OK;Status CreateDN(MGraph &G)return OK;Status CreateAG(MGraph &G)return OK;Status CreateAN(MGraph &G)/构造无向网G int i,j,k;/char v3, w3 , vwinfo10= ; /边有关信息置空 char v103=v1,v1,v2,v2,v5,v5,v6,v6,v4,v4; char w103=v2,v3,v5,v3,v6,v3,v4,v3,v1,v3;int q10= 6, 1, 3, 5, 6, 6, 2, 4, 5, 5 ; char vwinfo10= ; printf(输入要构造的网的顶点数和弧数：n);/scanf(%d,%d,&G.vexnum,&G.arcnum);G.vexnum=6; G.arcnum=10; printf(依次输入网的顶点名称v1 v2 .等等：n);/ for (i=0; iG.vexnum; i+) scanf(%s,G.vexsi);/构造顶点数据 strcpy(G.vexs0,v1); strcpy(G.vexs1,v2); strcpy(G.vexs2,v3); strcpy(G.vexs3,v4); strcpy(G.vexs4,v5); strcpy(G.vexs5,v6); for (i=0; iG.vexnum; i+) for (j=0; jG.vexnum; j+) G.arcsij.adj=INFINITY; G.=NULL;/初始化邻接矩阵 printf(按照： 顶点名1 顶点名2 权值 输入数据:n); for (k=0; kG.arcnum; k+)/ scanf(%s %s %d,v,w,&q); for(i=0;iG.vexnum; i+) if(strcmp(G.vexsi,vk)=0) break;/查找出v在vexs中的位置i if(i=G.vexnum) return ERROR; for(j=0;jG.vexnum; j+) if(strcmp(G.vexsj,wk)=0) break;/查找出v在vexs中的位置j if(j=G.vexnum) return ERROR;G.arcsij.adj=qk; /邻接矩阵对应位置置权值G.arcsji.adj=qk; /邻接矩阵对称位置置权值G.=(char *)malloc(10); strcpy(G.,vwinfo);/置入边有关信息 return OK;void PrintMGraph(MGraph &G)int i,j;switch(G.kind) case DG: for (i=0; iG.vexnum; i+) for (j=0; jG.vexnum; j+) printf( %d | ,G.arcsij.adj); if(G.=NULL) printf(NULL); else printf(%s路,G.); printf(n); break; case DN: for (i=0; iG.vexnum; i+) for (j=0; jG.vexnum; j+) if(G.arcsij.adj!=0) printf( %d | ,G.arcsij.adj); else printf( | ); printf(n); break; case AG: for (i=0; iG.vexnum; i+) for (j=0; jG.vexnum; j+) printf( %d | ,G.arcsij.adj); printf(n); break; case AN: for (i=0; iG.vexnum; i+) for (j=0; jG.vexnum; j+) if(G.arcsij.adjINFINITY) printf( %d | ,G.arcsij.adj); else printf( | ); printf(n); return;Status MiniSpanTree_PRIM(MGraph G, VertexType u) int i, j, k, r, min;struct VertexType adjvex;VRType lowcost;closedgeMAX_VERTEX_NUM; /定义辅助数组/k=LocateVex(G,u);for(i=0;iG.vexnum; i+) if(strcmp(G.vexsi,u)=0) break;/查找出v在vexs中的位置i if(i=G.vexnum) return ERROR; k=i;for(j=0; jG.vexnum; +j) /辅助数组初始化if(j!=k) strcpy(closedgej.adjvex,u); closedgej.lowcost=G.arcskj.adj;closedgek.lowcost=0; /初始, U=0, 即v1for(i=1; iG.vexnum; +i)/ k=mininum(closedge); /求权值最小的顶点 min=INFINITY; for(r=0; r 0 & closedger.lowcost %sn,k,closedgek.adjvex, G.vexsk); /输出边 closedgek.lowcost=0; /第顶点并入 U 集for(int j=0; jG.vexnum; +j) if(G.arcskj.adj closedgej.lowcost) /新顶点并入 U 集后,重新选择最小边 strcpy(closedgej.adjvex,G.vexsk); closedgej.lowcost=G.arcskj.adj;return OK; void main()