《算法设计与分析实验四.doc》由会员分享，可在线阅读，更多相关《算法设计与分析实验四.doc（14页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
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）比原来距离（不经
11、过顶点k）短，则修改顶点u的距离值，修改后的距离值的顶点k的距离加上边上的权。 （4）重复步骤（2）和（3）直到所有顶点都包含在S中。 5、多机调度问题 要求给出一种作业调度方案，使所给的n个作业在尽可能短的时间内由m台机器加工处理完成。约定，每个作业均可在任何一台机器上加工处理，但未完工前不允许中断处理。作业不能拆分成更小的子作业。 步骤：1）把作业按加工所用的时间从大到小排序 2）如果作业数目比机器的数目少或相等，则直接把作业分配下去 3）如果作业数目比机器的数目多，则每台机器上先分配一个作业，如下的作业分配时，是选那个表头上s最小的链表加入新作业。五、参考程序 2、背包问题贪心算法#in
12、clude struct goodinfo float p; /物品效益 float w; /物品重量 float X; /物品该放的数量 int flag; /物品编号;/物品信息结构体void Insertionsort(goodinfo goods,int n) int j,i; for(j=2;jgoodsi.p) goodsi+1=goodsi; i-; goodsi+1=goods0; /按物品效益，重量比值做升序排列void bag(goodinfo goods,float M,int n) float cu; int i,j; for(i=1;i=n;i+) goodsi.X=
13、0; cu=M; /背包剩余容量 for(i=1;icu)/当该物品重量大与剩余容量跳出 break; goodsi.X=1; cu=cu-goodsi.w;/确定背包新的剩余容量 if(i=n) goodsi.X=cu/goodsi.w;/该物品所要放的量for(j=2;j=n;j+) goods0=goodsj; i=j-1; while (goods0.flaggoodsi.flag) goodsi+1=goodsi; i-; goodsi+1=goods0; cout最优解为:endl; for(i=1;i=n;i+) cout第i件物品要放:; coutgoodsi.Xendl; v
14、oid main() cout|-运用贪心法解背包问题-|endl; cout|-|endl; int j; int n; float M; goodinfo *goods;/定义一个指针 while(j) coutn; goods=new struct goodinfo n+1;/ coutM; coutendl; int i; for(i=1;i=n;i+) goodsi.flag=i; cout请输入第igoodsi.w; cout请输入第igoodsi.p; goodsi.p=goodsi.p/goodsi.w;/得出物品的效益，重量比 coutendl; Insertionsort(
15、goods,n); bag(goods,M,n); coutpress to run agianendl; coutpress to exitj; 3、最小生成树的prim算法#include #include #include #define INFINITY INT_MAX #define MAX_VERTEX_NUM 20 typedef int VRType;typedef int InfoType;typedef char VerTexType;typedef struct ArcCell VRType adj; InfoType *info; ArcCell, AdjMatrixM
16、AX_VERTEX_NUMMAX_VERTEX_NUM;typedef struct VerTexType vexsMAX_VERTEX_NUM; AdjMatrix arcs; int vexnum, arcnum; MGraph;typedef struct VerTexType adjvex; VRType lowcost;closedgeMAX_VERTEX_NUM;void CreateGraph(MGraph &G);void MiniSpanTree_PRIM(MGraph G, VerTexType u);int LocateVex(MGraph G, VerTexType u
17、);int minimum(closedge close);void main( void ) int i, j; MGraph G; CreateGraph(G); for(i = 0; i G.vexnum; i+) for(j = 0; j G.vexnum; j+) coutG.arcsij.adj; cout ; coutendl; MiniSpanTree_PRIM(G, a);void CreateGraph(MGraph &G) int weigh; int i, j = 0, k = 0; char hand, tide; coutG.vexnumG.arcnum; for(
18、i = 0; i G.vexnum; i+) for(j = 0; j G.vexnum; j+) G.arcsij.adj = 88; coutendl; coutinputG.vexnumchar for vexs:; for(i=0; i G.vexsi; coutendl; coutinputG.arcnumarc(char,char,weigh):endl; j = 0; k = 0; for(i=0; i G.arcnum; i+) coutihand; cintide; cinweigh; while (hand != G.vexsj) j+; while (tide != G.
19、vexsk) k+; G.arcsjk.adj = weigh; G.arcskj.adj = weigh; j = 0; k = 0; coutendl; void MiniSpanTree_PRIM(MGraph G,VerTexType u) int i, j, k = 0; closedge close; k = LocateVex ( G, u ); for ( j = 0; j G.vexnum; j+ ) if (j != k) closej.adjvex = G.vexsk; closej.lowcost = G.arcskj.adj; closej.lowcost = 88;
20、 closej.adjvex = 0; closek.lowcost = 0; closek.adjvex = u; for (i = 1; i G.vexnum; i+) k = minimum(close); coutclosek.adjvex; cout; coutG.vexsk ; coutclosek.lowcostendl; closek.lowcost = 0; for (j=0; jG.vexnum; j+) if (G.arcskj.adj closej1.lowcost & closej1.lowcost != 0) client = closej1.lowcost; j2
21、 = j1; j1+; return j2;4、最短路径问题 #include #include using namespace std; const int MaxNum=; /边权最大值 int n; /节点数目 int dist501; /到节点1的最短路径值 bool state501; /节点被搜索过状态指示 int data501501; /邻接矩阵 /查找权值最小的节点 int findmin() int minnode=0, min=MaxNum; for(int i=1; i=n; i+) if (disti n; for(int p=1; p=n; p+) for(int
22、q=1; q datapq; if (datapq=0) datapq=MaxNum; /初始化 for(int i=1; i=n; i+) disti=data1i; state1=true; int done=1; while (donen) int node=findmin(); if (node!=0) done+; /找到的点的数目加1 statenode=true; /标记已经找到了从节点1到节点node的最短路径 for(int i=1; idistnode+datanodei) & (!statei) disti=distnode+datanodei; else break;
23、for(int k=1; k=n; k+) if (distk=MaxNum) out-1; else outdistk; if (k=n) outendl; else out ; in.close(); out.close(); return 0; 5、多机调度问题typedef struct Job int ID;/作业号 int time;/作业所花费的时间Job;typedef struct JobNode /作业链表的节点 int ID; int time; JobNode *next;JobNode,*pJobNode;typedef struct Header /链表的表头 int s; pJobNode next;Header,pHeader;int SelectMin(Header* M,int m) int k=0; for(int i=1;im;i+) if(Mi.smk.s)k=i; return k;