算法设计与分析实验四

《算法设计与分析实验四》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、实验四：贪心法一、实验目的1、掌握贪心算法的基本设计思想与原则2、运用贪心法求解经典问题（验证性实验）二、实验原理1、优化问题有n个输入，而它的解就由这n个输入满足某些事先给定的约束条件的某个子集组成，而把满足约束条件的子集称为该问题的可行解。可行解一般来说是不唯一的。那些使目标函数取极值(极大或极小)的可行解，称为最优解。2、贪心法求优化问题算法思想：在贪心算法中采用逐步构造最优解的方法。在每个阶段，都作出一个看上去最优的决策（在一定的标准下）。决策一旦作出，就不可再更改。作出贪心决策的依据称为贪心准则（greedycriterion）。3、一般方法1）根据题意，选取一种量度标准。2

2、）按这种量度标准对这n个输入排序3）依次选择输入量加入部分解中。如果当前这个输入量的加入，不满足约束条件，则不把此输入加到这部分解中。procedureGREEDY(A，n)/*贪心法一般控制流程*///A(1：n)包含n个输入//solutions←φ//将解向量solution初始化为空／fori←1tondox←SELECT(A)ifFEASIBLE(solution，x)thensolutions←UNION(solution，x)endifrepeatreturn(solution)endGREEDY三、实验要求1、用C++/C完成算法设计和程序设计并上机调试通过。2、撰写实

3、验报告，提供实验结果和数据。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次合并操作，为了便于选取根结点权值最小的二叉树以及合并操作，设置一个数组huffTree[2n-1]保存哈夫曼树中各结点的信息，数组元素的结点结构如下图所示。weightlchildrchildparent图哈夫曼树的结点结构weight：该结点的权值；lchild：该结点的左孩子结点在数组中的下标；rchild：该结点的右孩子结点在数组中的下标；parent：该结点的双亲结点在数组中的下标。将数组元素的结点类型定义为：structelement{doubleweight;//字符出现的概率为实数intlchild,r

5、child,parent;};建立哈夫曼树的算法如下：算法——建立哈夫曼树voidHuffmanTree(elementhuffTree[],intw[],intn){for(i=0;i<2*n-1;i++)//初始化{huffTree[i].parent=-1;huffTree[i].lchild=-1;huffTree[i].rchild=-1;}for(i=0;i

6、中找权值最小的两个结点i1和i2huffTree[i1].parent=k;//将i1和i2合并，则i1和i2的双亲是khuffTree[i2].parent=k;huffTree[k].weight=huffTree[i1].weight+huffTree[i2].weight;huffTree[k].lchild=i1;huffTree[k].rchild=i2;}}Select函数用来在数组huffTree中选取两个权值最小的根结点，请读者自行完成。根据已建立的哈夫曼树，规定哈夫曼树的左分支代表0，右分支代表1，则哈夫曼编码即是从根结点到每个叶子结点所经过的路径组成的0和1的序列

7、。算法如下：算法7.11——哈夫曼编码voidHuffmanCode(elementhuffTree[],intn){for(i=0;i