《算法设计与分析实验四》由会员分享，可在线阅读，更多相关《算法设计与分析实验四（14页珍藏版）》请在金锄头文库上搜索。
1、实验四：贪心法一、实验目的 1、掌握贪心算法的基本设计思想与原则 2、运用贪心法求解经典问题（验证性实验）二、实验原理 1、优化问题 有n个输入，而它的解就由这n个输入满足某些事先给定的约束条件的某个子集组成，而把满足约束条件的子集称为该问题的可行解。可行解一般来说是不唯一的。那些使目标函数取极值(极大或极小)的可行解，称为最优解。 2、贪心法求优化问题 算法思想：在贪心算法中采用逐步构造最优解的方法。在每个阶段，都作出一个看上去最优的决策（在一定的标准下）。决策一旦作出，就不可再更改。作出贪心决策的依据称为贪心准则（greedy criterion）。 3、一般方法1）根据题意，选取一种量度
2、标准。2）按这种量度标准对这n个输入排序3）依次选择输入量加入部分解中。如果当前这个输入量的加入，不满足约束条件，则不把此输入加到这部分解中。procedure GREEDY(A，n) /*贪心法一般控制流程*/ /A(1：n)包含n个输入/ solutions /将解向量solution初始化为空 for i1 to n do xSELECT(A) if FEASIBLE(solution，x) then solutionsUNION(solution，x) endif repeat return(solution)end GREEDY三、实验要求 1、用C+/C完成算法设计和程序设计并上机
3、调试通过。 2、撰写实验报告，提供实验结果和数据。 3、分析算法，要求给出具体的算法分析结果，包括时间复杂度和空间复杂度，并简要给出算法设计小结和心得。四、实验内容 1、哈夫曼编码 设需要编码的字符集为d1, d2, , dn，它们出现的频率为w1, w2, , wn，应用哈夫曼树构造最短的不等长编码方案。 设需要编码的字符集为d1, d2, , dn，它们出现的频率为w1, w2, , wn，以d1, d2, , dn作为叶子结点，w1, w2, , wn作为叶子结点的权值，构造一棵哈夫曼编码树，规定哈夫曼编码树的左分支代表0，右分支代表1，则从根结点到每个叶子结点所经过的路径组成的0和1的
4、序列便为该叶子结点对应字符的编码即为哈夫曼编码。考虑到哈夫曼树中共有2n-1个结点，并且进行n-1次合并操作，为了便于选取根结点权值最小的二叉树以及合并操作，设置一个数组huffTree2n-1保存哈夫曼树中各结点的信息，数组元素的结点结构如下图所示。weight lchild rchild parent图 哈夫曼树的结点结构weight：该结点的权值；lchild：该结点的左孩子结点在数组中的下标；rchild：该结点的右孩子结点在数组中的下标；parent：该结点的双亲结点在数组中的下标。将数组元素的结点类型定义为：struct element double weight; /字符出现的概
5、率为实数 int lchild, rchild, parent; 建立哈夫曼树的算法如下：算法建立哈夫曼树void HuffmanTree(element huffTree , int w , int n ) for (i=0; i2*n-1; i+) /初始化 huffTree i.parent= -1;huffTree i.lchild= -1;huffTree i.rchild= -1; for (i=0; in; i+) /构造n棵只含有根结点的二叉树huffTree i.weight=wi; for (k=n; k2*n-1; k+) /n-1次合并 Select(huffTree,
6、 i1, i2); /在huffTree中找权值最小的两个结点i1和i2huffTreei1.parent=k; /将i1和i2合并，则i1和i2的双亲是khuffTreei2.parent=k; huffTreek.weight= huffTreei1.weight+huffTreei2.weight;huffTreek.lchild=i1; huffTreek.rchild=i2;Select函数用来在数组huffTree中选取两个权值最小的根结点，请读者自行完成。根据已建立的哈夫曼树，规定哈夫曼树的左分支代表0，右分支代表1，则哈夫曼编码即是从根结点到每个叶子结点所经过的路径组成的0和1
7、的序列。算法如下：算法7.11哈夫曼编码 void HuffmanCode(element huffTree , int n ) for (i=0; icu then exit endif X(i) 1 cucu-W(i) repeat if in then X(i) cu/ W(i) endif end GREEDY-KNAPSACKprocedure prim(G,)status“unseen” / T为空 status1“tree node” / 将1放入Tfor each edge(1,w) do statusw“fringe” / 找到T的邻接点 dadw 1; /w通过1与T建立联
8、系 distw weight(1,w) /w到T的距离 repeatwhile statust “tree node” do pick a fringe u with min distw / 选取到T最近的节点 statusu“tree node” for each edge(u,w) do 修改w和T的关系 repeatrepeat 3、最小生成树的prim算法PrimMST(G，T，r) /求图G的以r为根的MST，结果放在T=(U，TE)中 InitCandidateSet()；/初始化：设置初始的轻边候选集，并置T=(r，) for(k=0；ki(1,i之间存在边) or +无穷大(1
9、.i之间不存在边) 2）在S中，令d(j)=mind(i),i属于S，令S=S-j，若S为空集则算法结束，否则转3） 3）对全部i属于S,如果存在边j-i，那么置d(i)=mind(i), d(j)+Wj-i，转2） Dijkstra算法思想为：设G=(V,E)是一个带权有向图，把图中顶点集合V分成两组，第一组为已求出最短路径的顶点集合（用S表示，初始时S中只有一个源点，以后每求得一条最短路径 , 就将 加入到集合S中，直到全部顶点都加入到S中，算法就结束了），第二组为其余未确定最短路径的顶点集合（用U表示），按最短路径长度的递增次序依次把第二组的顶点加入S中。在加入的过程中，总保持从源点v到
10、S中各顶点的最短路径长度不大于从源点v到U中任何顶点的最短路径长度。此外，每个顶点对应一个距离，S中的顶点的距离就是从v到此顶点的最短路径长度，U中的顶点的距离，是从v到此顶点只包括S中的顶点为中间顶点的当前最短路径长度。 算法具体步骤： （1）初始时，S只包含源点，即S，v的距离为0。U包含除v外的其他顶点，U中顶点u距离为边上的权（若v与u有边）或 ）（若u不是v的出边邻接点）。 （2）从U中选取一个距离v最小的顶点k，把k，加入S中（该选定的距离就是v到k的最短路径长度）。 （3）以k为新考虑的中间点，修改U中各顶点的距离；若从源点v到顶点u（u U）的距离（经过顶点k）比原来距离（不经过顶点k）短，则修改顶点u的距离值，修改后的距离值的顶点k的距离加上边上的权。 （4）重复步骤（2）
