《贪心算法实验总结》由会员分享，可在线阅读，更多相关《贪心算法实验总结（15页珍藏版）》请在金锄头文库上搜索。
1、为了适应公司新战略的发展，保障停车场安保新项目的正常、顺利开展，特制定安保从业人员的业务技能及个人素质的培训计划贪心算法实验总结算法分析与设计实验报告完成日期：实验目的(1)了解贪心算法思想(2)掌握贪心法典型问题，如背包问题、作业调度问题等。实验内容(1)编写一个简单的程序，实现单源最短路径问题。(2)编写一段程序，实现找零。【问题描述】当前有面值分别为2角5分，1角，5分，1分的硬币，请给出找n分钱的最佳方案。(3)编写程序实现多机调度问题【问题描述】要求给出一种作业调度方案，使所给的n个作业在尽可能短的时间内由m台机器加工处理完成。约定，每个作业均可在任何一台机器上加工处理，但未完工前不
2、允许中断处理。作业不能拆分成更小的子作业。算法思想分析所谓单源最短路径问题是指：已知图G，我们希望找出从某给定的源结点SV到V中的每个结点的最短路径。首先，我们可以发现有这样一个事实：如果P是G中从vs到vj的最短路，vi是P中的一个点，那么，从vs沿P到vi的路是从vs到vi的最短路。Dijkstra算法对于图G，如果所有Wij0的情形下，目前公认的最好的方法是由Dijkstra于1959年提出来的。例1已知如下图所示的单行线交通网，每弧旁的数字表示通过这条单行线所需要的费用，现在某人要从v1出发，通过这个交通网到v8去，求使总费用最小的旅行路线。Dijkstra方法的基本思想是从vs出发，
3、逐步地向外探寻最短路。执行过程中，与每个点对应，记录下一个数(称为这个点的标号)，它或者表示从vs到该点的最短路的权(称为P标号)、或者是从vs到该点的最短路的权的上界(称为T标号)，方法的每一步是去修改T标号，并且把某一个具T标号的改变为具P标号的点，从而使G中具P标号的顶点数多一个，这样至多经过n-1(n为图G的顶点数)步，就可以求出从vs到各点的最短路。在叙述Dijkstra方法的具体步骤之前，以例1为例说明一下这个方法的基本思想。例1中，s=1。因为所有Wij0，故有d(v1,v1)=0。这时，v1是具P标号的点。现在考察从v1发出的三条弧，(v1,v2),(v1,v3)和(v1,v4
4、)。如果某人从v1出发沿(v1,v2)到达v2，这时需要d(v1,v1)+w12=6单位的费用；如果他从v1出发沿(v1,v3)到达v3，这时需要d(v1,v1)+w13=3单位的费用；类似地，若沿(v1,v4)到达v4，这时需要d(v1,v1)+w14=1单位的费用。因为mind(v1,v1)+w12，d(v1,v1)+w13，d(v1,v1)+w14=d(v1,v1)+w14=1，可以断言，他从v1到v4所需要的最小费用必定是1单位，即从v1到v4的最短路是(v1,v4)，d(v1,v4)=1。这是因为从v1到v4的任一条路P，如果不是(v1,v4)，则必是先从v1沿(v1,v2)到达v2
5、，或者沿(v1,v3)到达v3。但如上所说，这时他已需要6单位或3单位的费用，不管他如何再从v2或从v3到达v4，所需要的总费用都不会比1小(因为所有wij0)。因而推知d(v1,v4)=1，这样就可以使v4变成具P标号的点。现在考察从v1及v4指向其余点的弧，由上已知，从v1出发，分别沿(v1,v2)、(v1,v3)到达v2,v3，需要的费用分别为6与3，而从v4出发沿(v4,v6)到达v6所需的费用是d(v1,v4)+w46=1+10=11单位。因mind(v1,v1)+w12，d(v1,v1)+w13，d(v1,v4)+w46=d(v1,v1)+w13=3。基于同样的理由可以断言，从v1
6、到v3的最短路是(v1,v3)，d(v1,v3)=3。这样又可以使点v3变成具P标号的点，如此重复这个过程，可以求出从v1到任一点的最短路。在下述的Dijstra方法具体步骤中，用P，T分别表示某个点的P标号、T标号，si表示第i步时，具P标号点的集合。为了在求出从vs到各点的距离的同时，也求出从Vs到各点的最短路，给每个点v以一个值，算法终止时(v)=m，表示在Vs到v的最短路上，v的前一个点是Vm；如果(v)=，表示图G中不含从Vs到v的路；(Vs)=0。Dijstra方法的具体步骤：初始化i=0S0=Vs，P(Vs)=0(Vs)=0对每一个vVs，令T(v)=+，(v)=+，k=s开始如
7、果Si=V，算法终止，这时，每个vSi，d(Vs,v)=P(v)；否则转入考察每个使(Vk,vj)E且vjSi的点vj。如果T(vj)P(vk)+wkj，则把T(vj)修改为P(vk)+wkj，把(vj)修改为k。令如果，则把的标号变为P标号，令，k=ji，i=i+1，转，否则终止，这时对每一个vSi，d(vs,v)=P(v)，而对每一个。找零问题根据常识，我们到店里买东西找钱时，老板总是先给我们最大面值的，要是不够再找面值小一点的，直到找满为止。如果老板都给你找分数的或者几角的，那你肯定不干，另外，他也可能没有那么多零碎的钱给你找。其实这就是一个典型的贪心选择问题。问题的算法设计与实现：先举
8、个例子，假如老板要找给我99分钱，他有上面的面值分别为25，10，5，1的硬币数，为了找给我最少的硬币数，那么他是不是该这样找呢，先看看该找多少个25分的，99253，好像是3个，要是4个的话，我们还得再给老板一个1分的，我不干，那么老板只能给我3个25分的拉，由于还少给我24，所以还得给我2个10分的和4个1分。多机调度1、把作业按加工所用的时间从大到小排序2、如果作业数目比机器的数目少或相等，则直接把作业分配下去3、如果作业数目比机器的数目多，则每台机器上先分配一个作业，如下的作业分配时，是选那个表头上s最小的链表加入新作业。分析与代码1.单源最短路径分析：基本思想：设置顶点集合S并不断地
9、作贪心选择来扩充这个集合。一个顶点属于集合S当且仅当从源到该顶点的最短路径长度已知。初始时，S中仅含有源节点。设u是G的某一个顶点，把从源到u且中间只经过S中顶点的路称为从源到u的特殊路径，用数组Di记录顶点i当前所对应的最短特殊路径长度。Dijkstra算法每次从V-S中取出具有最短特殊路长度的顶点u，将u添加到S中，同时对数组D作必要的修改。一旦S包含了所有V中顶点，dist就记录了从源到所有其它顶点之间的最短路径长度。代码如下：#includeusingnamespacestd;intconstVEX=5;/定义结点的个数intconstmaxpoint=15;intgraphmaxpo
10、int=0,10,-1,30,100,-1,0,50,-1,-1,-1,-1,0,-1,10,-1,-1,20,0,60,-1,-1,-1,-1,0;/邻接矩阵intRmaxpoint=0;intBmaxpoint;intDVEX;intPVEX;/定义数组D用来存放结点特殊距离，P数组存放父亲结点/初始时，红点集中仅有源结点0voidinstital(intR,intB,intD,intP)R0=1;B0=0;for(inti=1;iDmin+graphminj|Dj=-1)Dj=Dmin+graphminj;/每次迭代求最小值，最后一次即为到源点的最短路径Pj=min;voidmain()
11、instital(R,B,D,P);theshortestway(R,B,D,P);cout#include#include#include#include#include#defineOVERFLOW-2#defineOK1#defineERROR0typedefintElemType;typedefintStatus;/定义Huffmantreetypedefstructintweight;intparent;intlchild;intrchild;HTNode,*HuffmanTree;typedefchar*HuffmanCode;#defineCHLENGTH27#defineWLE
12、NGTH27voidHuffmanCoding(HuffmanTree&,HuffmanCode&,int*,int);/编码函数voidSelect(HuffmanTree,int,int&,int&);voidHuffmanDecoding(char*,HuffmanTree,HuffmanCode,int*,int*,int);/译码函数voidTreeprinting(char*,HuffmanTree,HuffmanCode,int*,int*,int);/打印HuffmanTreevoidpreorder(HuffmanTreeHT,introot,inti,intsum,int*
13、,int*,FILE*);/主函数voidmain(void)intchCHLENGTH=,A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P,Q,R,S,T,U,V,W,X,Y,Z;intwWLENGTH=186,64,13,22,32,103,21,15,47,57,1,5,32,20,57,63,15,1,48,51,80,23,8,18,1,16,1;inti=1;charbuff1025;charch1;intc;FILE*fp_1,*fp_2;intflag=1,legth=0;HuffmanTreeHT;HuffmanCodeHC;while(1)printf(*n);printf(1.进行编码n);printf(2.译码工作n);printf(3.打印n);printf(4.打印HuffmanTreen);printf(5.退出程序n);printf(*n);scanf(%d,&c);getchar();switch(c)case1:/编码HuffmanCoding(HT,HC,w,WLENGTH);if(fp_1=fopen(,w)=NULL)printf(cannotopenthefilen);getch();
