《算法设计与实验报告讲解.doc》由会员分享，可在线阅读，更多相关《算法设计与实验报告讲解.doc（21页珍藏版）》请在三一办公上搜索。
1、算法设计与分析实验报告 学院：信息学院专业：物联网1101 姓名：黄振亮 学号：20113379 2013年11月目录作业1 0-1背包问题的动态规划算法101.1算法应用背景101.2算法原理101.3算法描述101.4程序实现及程序截图111.4.1程序源码111.4.2程序截图131.5学习或程序调试心得14作业2 0-1背包问题的回溯算法102.1算法应用背景102.2算法原理102.3算法描述102.4程序实现及程序截图112.4.1程序源码112.4.2程序截图132.5学习或程序调试心得14作业3循环赛日程表的分治算法103.1算法应用背景103.2算法原理103.3算法描述10
2、3.4程序实现及程序截图113.4.1程序源码113.4.2程序截图133.5学习或程序调试心得14作业4活动安排的贪心算法104.1算法应用背景104.2算法原理104.3算法描述104.4程序实现及程序截图114.4.1程序源码114.4.2程序截图134.5学习或程序调试心得14作业1 0-1背包问题的动态规划算法1.1算法应用背景从计算复杂性来看,背包问题是一个NP难解问题。半个世纪以来,该问题一直是算法与复杂性研究的热点之一。另外,背包问题在信息加密、预算控制、项目选择、材料切割、货物装载、网络信息安全等应用中具有重要的价值。如果能够解决这个问题那么则具有很高的经济价值和决策价值，在
3、上述领域可以获得最大的价值。本文从动态规划角度给出一种解决背包问题的算法。1.2算法原理 1.2.1、问题描述：给定n种物品和一背包。物品i的重量是wi，其价值为vi，背包的容量为C。问:应如何选择装入背包的物品，使得装入背包中物品的总价值最大?形式化描述：给定c 0, wi 0, vi 0 , 1in.要求找一n元向量(x1,x2,xn,), xi0,1, wi xic,且 vi xi达最大.即一个特殊的整数规划问题。1.2.2、最优性原理：设(y1,y2,yn)是 (3.4.1)的一个最优解.则(y2,yn)是下面相应子问题的一个最优解:证明:使用反证法。若不然,设(z2,z3,zn)是上
4、述子问题的一个最优解,而(y2,y3,yn)不是它的最优解。显然有 vizi viyi (i=2,n) 且 w1y1+ wizi viyi, (i=1,n) 说明(y1,z2, z3,zn)是(3.4.1)0-1背包问题的一个更优解,导出(y1,y2,yn)不是背包问题的最优解,矛盾。1.2.3、递推关系：设所给0-1背包问题的子问题的最优值为m(i，j)，即m(i，j)是背包容量为j，可选择物品为i，i+1，n时0-1背包问题的最优值。由0-1背包问题的最优子结构性质，可以建立计算m(i，j)的递归式:注:(3.4.3)式此时背包容量为j，可选择物品为i。此时在对xi作出决策之后,问题处于两
5、种状态之一: (1)背包剩余容量是j,没产生任何效益； (2)剩余容量j-wi,效益值增长了vi ；1.3算法描述int m100100;/前i个物品装入容量为j的背包中获得的最大价值 int s;/获得的最大价值 int w15;/物品的重量 int v15;/物品的价值 int x15;/物品的选取状态，1表示被选中 0表示未选中 int n,i; int c;/背包最大容量int max(int a,int b)/获得最大值int min(int a,int b)/获得最小值void KnapSack(int n,int w,int v,int c)/背包问题主算法先为mnj 初始化初值
6、然后根据递归方程式进行穷举递归直到 m1c， m1c 即为所获得的最大价值。void Traceback(int n,int w,int x,int c)/回溯算法，依次标注被选中的物品通过一个循环过程检验装入第i个物品与装入i+1个物品的价值如果相同，则xi=0。1.4程序实现及程序截图1.4.1程序源码#includeusing namespace std;int m100100;/前i个物品装入容量为j的背包中获得的最大价值int max(int a,int b) if(a=b) return a; else return b;int min(int a,int b) if(a=b) r
7、eturn b; else return a;void KnapSack(int n,int w,int v,int c) int i,j; int jMax=min(wn-1,c); for(j=0;j=jMax;j+) mnj=0; for(j=wn;j1;i-) jMax=min(wi-1,c); for(j=0;j=jMax;j+) mij=mi+1j; for(j=wi;j=w1) m1c=max(m1c,m2c-w1+v1);void Traceback(int n,int w,int x,int c) int i; for(i=1;in;i+) if(mic=mi+1c) xi=
8、0; elsexi=1;c-=wi; xn=(mnc)?1:0;int main() int s;/获得的最大价值 int w15;/物品的重量 int v15;/物品的价值 int x15;/物品的选取状态 int n,i; int c;/背包最大容量 cout 请输入背包的最大容量:c; cout输入物品数:nn; cout请分别输入物品的重量:endl; for(i=1;iwi; cout请分别输入物品的价值:endl; for(i=1;ivi; KnapSack(n,w,v,c); Traceback(n,w,x,c); s=m1c; cout最大物品价值为:endl; coutsen
9、dl; cout选中的物品为：endl; for(i=1;i=n;i+) cout0；wi0；pi0。满足约束条件的任何向量都是一个可行解，而使得目标函数达到最大的那个可行解则为最优解。 给定n 种物品和1个背包。物品i 的重量是wi，其价值为pi，背包的容量为M。问应如何装入背包中的物品，使得装人背包中物品的总价值最大？在选择装人背包的物品时，对每种物品i只有两种选择，即装入背包、不装入背包。不能将物品i 装人背包多次，也不能只装入部分的物品i。该问题称为0-1背包问题。0-1背包问题的符号化表示是，给定M0， w i 0， pi 0，1in ，要求找到一个n元0-1向量向量(x1，x2xn
10、)， X i =0 或1 , 1in, 使得 ，而且达到最大。2.2.2算法分析1、问题的解空间：应用回溯法解问题时，首先应明确定义问题的解空间。问题的解空间应到少包含问题的一个（最优）解。2、回溯法的基本思想：确定了解空间的组织结构后，回溯法就从开始结点（根结点）出发，以深度优先的方式搜索整个解空间。这个开始结点就成为一个活结点，同时也成为当前的扩展结点。在当前的扩展结点处，搜索向纵深方向移至一个新结点。这个新结点就成为一个新的活结点，并成为当前扩展结点。如果在当前的扩展结点处不能再向纵深方向移动，则当前扩展结点就成为死结点。换句话说，这个结点不再是一个活结点。此时，应往回移动（回溯）至最近
11、的一个活结点处，并使这个活结点成为当前的扩展结点。回溯法即以这种工作方式递归地在解空间中搜索，直至找到所要求的解或解空间中已没有活结点时为止。运用回溯法解题通常包含以下三个步骤：（1）针对所给问题，定义问题的解空间；（2）确定易于搜索的解空间结构；（3）以深度优先的方式搜索解空间，并且在搜索过程中用剪枝函数避免无效搜索；3、递归回溯：由于回溯法是对解空间的深度优先搜索，因此在一般情况下可用递归函数来实现回溯法。问题的一般描述是：旅行者背包登山，背包的最大承重为M，现有n个物品可供选择装入背包，第i个物品莺量为wi，价值为pi，假定物品i的一部分xi(0xi1)放人背包，获得价值为xipi，由于
12、背包最大承重为M，要求装入物品总质量不过超过M，问旅行者应该如何选择物品装入背包，使得装入物品的价值总和达到最大值。背包问题的数学描述如下：要求找到一个n元向量(x1，x2xn)，在满足约束条件：情况下，使得目标函数，其中，1in；M0；wi0；pi0。满足约束条件的任何向量都是一个可行解，而使得目标函数达到最大的那个可行解则为最优解。 给定n 种物品和1个背包。物品i 的重量是wi，其价值为pi，背包的容量为M。问应如何装入背包中的物品，使得装人背包中物品的总价值最大？在选择装人背包的物品时，对每种物品i只有两种选择，即装入背包、不装入背包。不能将物品i 装人背包多次，也不能只装入部分的物品
13、i。该问题称为0-1背包问题。0-1背包问题的符号化表示是，给定M0， w i 0， pi 0，1in ，要求找到一个n元0-1向量向量(x1，x2xn)， X i =0 或1 , 1in, 使得 ，而且达到最大。1、问题的解空间：应用回溯法解问题时，首先应明确定义问题的解空间。问题的解空间应到少包含问题的一个（最优）解。2、回溯法的基本思想：确定了解空间的组织结构后，回溯法就从开始结点（根结点）出发，以深度优先的方式搜索整个解空间。这个开始结点就成为一个活结点，同时也成为当前的扩展结点。在当前的扩展结点处，搜索向纵深方向移至一个新结点。这个新结点就成为一个新的活结点，并成为当前扩展结点。如果
14、在当前的扩展结点处不能再向纵深方向移动，则当前扩展结点就成为死结点。换句话说，这个结点不再是一个活结点。此时，应往回移动（回溯）至最近的一个活结点处，并使这个活结点成为当前的扩展结点。回溯法即以这种工作方式递归地在解空间中搜索，直至找到所要求的解或解空间中已没有活结点时为止。运用回溯法解题通常包含以下三个步骤：（1）针对所给问题，定义问题的解空间；（2）确定易于搜索的解空间结构；（3）以深度优先的方式搜索解空间，并且在搜索过程中用剪枝函数避免无效搜索；3、递归回溯：由于回溯法是对解空间的深度优先搜索，因此在一般情况下可用递归函数来实现回溯法。 回溯法是一种系统地搜索问题解答的方法。为了实现回溯
15、，首先需要为问题定义一个解空间，这个解空间必须至少包含问题的一个解(可能是最优的)。一旦定义了解空间的组织方要选择一个对象的子集，将它们装人背包，以便获得的收益最大，则解空间应组织成子集树的形状。首先形成一个递归算法，去找到可获得的最大收益。然后，对该算法加以改进，形成代码。改进后的代码可找到获得最大收益时包含在背包中的对象的集合。左子树表示一个可行的结点，无论何时都要移动到它，当右子树可能含有比当前最优解还优的解时，移动到它。一种决定是否要移动到右子树的简单方法是r为还未遍历的对象的收益之和，将r加到cp (当前节点所获收益)之上，若( r+cp) bestp(目前最优解的收益)，则不需搜索
16、右子树。一种更有效的方法是按收益密度vi/wi对剩余对象排序，将对象按密度递减的顺序去填充背包的剩余容量， 当遇到第一个不能全部放人背包的对象时， 就使用它的一部分。2.3算法描述概要设计01背包问题是一个子集选取问题，适合于用子集树表示01背包问题的解空间。在搜索解空间树是，只要其左儿子节点是一个可行结点，搜索就进入左子树，在右子树中有可能包含最优解是才进入右子树搜索。否则将右子树剪去。int c;/背包容量int n; /物品数int *w;/物品重量数组int *p;/物品价值数组int cw;/当前重量int cp;/当前价值int bestp;/当前最优值int *bestx;/当前
17、最优解int *x;/当前解int Knap:Bound(int i)/计算上界void Knap:Backtrack(int i)/回溯int Knapsack(int p,int w,int c,int n) /为Knap:Backtrack初始化 2.4程序实现及程序截图2.4.1程序源码#include using namespace std; class Knap friend int Knapsack(int p,int w,int c,int n ); public: void print() for(int m=1;m=n;m+) coutbestxm ; coutendl;
18、; private: int Bound(int i); void Backtrack(int i); int c;/背包容量 int n; /物品数 int *w;/物品重量数组 int *p;/物品价值数组 int cw;/当前重量 int cp;/当前价值 int bestp;/当前最优值 int *bestx;/当前最优解 int *x;/当前解 ; int Knap:Bound(int i) int cleft=c-cw;/剩余容量 int b=cp; while(i=n&wi=cleft) cleft-=wi; b+=pi; i+; if(in) if(bestpcp) for(i
19、nt j=1;j=n;j+) bestxj=xj; bestp=cp; return; if(cw+wibestp)/搜索右子树 xi=0; Backtrack(i+1); class Object friend int Knapsack(int p,int w,int c,int n); public: int operator=a.d); private: int ID; float d; ; int Knapsack(int p,int w,int c,int n) /为Knap:Backtrack初始化 int W=0; int P=0; int i=1; Object *Q=new
20、Objectn; for(i=1;i=n;i+) Qi-1.ID=i; Qi-1.d=1.0*pi/wi; P+=pi; W+=wi; if(W=c) return P;/装入所有物品 float f; for( i=0;in;i+) for(int j=i;jn;j+) if(Qi.dQj.d) f=Qi.d; Qi.d=Qj.d; Qj.d=f; Knap K; K.p = new intn+1; K.w = new intn+1; K.x = new intn+1; K.bestx = new intn+1; K.x0=0; K.bestx0=0; for( i=1;i=n;i+) K.
21、pi=pQi-1.ID; K.wi=wQi-1.ID; K.cp=0; K.cw=0; K.c=c; K.n=n; K.bestp=0; /回溯搜索 K.Backtrack(1); K.print(); delete Q; delete K.w; delete K.p; return K.bestp; void main() int *p; int *w; int c=0; int n=0; int i=0; char k; while(k) cout请输入背包容量(c)：c; cout请输入物品的个数(n)：n; p=new intn+1; w=new intn+1; p0=0; w0=0;
22、 cout请输入物品的价值(p)：endl; for(i=1;ipi; cout请输入物品的重量(w)：endl; for(i=1;iwi; cout最优解为(bestx)：endl; cout最优值为(bestp)：endl; coutKnapsack(p,w,c,n)endl; couts 重新开始endl; coutq 退出k; 2.4.2程序截图2.5学习或程序调试心得回溯算法的运行时间取决于它在搜索过程中所生成的结点数,而限界函数可以大量减少所生成的结点个数,省去许多无谓的搜索, 使得搜索速度更快 ,其调用限界函数计算上界需花费O(n)时间 ,最坏情况下有O()个结点需调用限界函数
23、,需花费O(n)时间,所以该算法的时间复杂度为O(n)。 回溯法的另一个重要特性就是在搜索执行的同时产生解空间 在搜索期间的任何时刻 仅保留从开始结点到当前可扩展结点的路径其空间需求为O(从开始结点起最长路径的长度),所以 ,此处该算法的空间复杂度为O(n),回溯法是算法设计的基本方法之一 ,它适用于解一些涉及到寻找一组解的问题或者求满足某些约束条件的最优解的问题,且适用于求解组合数量较大的问题。作业3 循环赛日程表的分治算法3.1算法应用背景分治法是一个比较典型也很常见的计算机算法，它不仅可以用来设计各种算法，而且在其他方面也有广泛应用。例如可以用分治思想来构造电路进行数学证明等。设计循环赛
24、日程表即是分治策略的一个具体应用。3.2算法原理3.2.1问题描述：设有n=2k个运动员要进行网球循环赛。现要设计一个满足以下要求的比赛日程表：(1)每个选手必须与其他n-1个选手各赛一次； (2)每个选手一天只能参赛一次； (3)循环赛在n-1天内结束。请按此要求将比赛日程表设计成有n行和n-1列的一个表。在表中的第i行，第j列处填入第i个选手在第j天所遇到的选手。其中1in，1jn-1。8个选手的比赛日程表如下图：3.2.2算法思路：按分治策略，我们可以将所有的选手分为两半，则n个选手的比赛日程表可以通过n/2个选手的比赛日程表来决定。递归地用这种一分为二的策略对选手进行划分，直到只剩下两
25、个选手时，比赛日程表的制定就变得很简单。这时只要让这两个选手进行比赛就可以了。如上图，所列出的正方形表是8个选手的比赛日程表。其中左上角与左下角的两小块分别为选手1至选手4和选手5至选手8前3天的比赛日程。据此，将左上角小块中的所有数字按其相对位置抄到右下角，又将左下角小块中的所有数字按其相对位置抄到右上角，这样我们就分别安排好了选手1至选手4和选手5至选手8在后4天的比赛日程。依此思想容易将这个比赛程表推广到具有任意多个选手的情形。3.3算法描述(1)用一个for循环输出日程表的第一行 for(int i=1;i=N;i+) a1i = i(2)然后定义一个m值，m初始化为1，m用来控制每一
26、次填充表格时i（i表示行）和j（j表示列）的起始填充位置。(3)用一个for循环将问题分成几部分，对于k=3，n=8，将问题分成3大部分，第一部分为，根据已经填充的第一行，填写第二行，第二部分为，根据已经填充好的第一部分，填写第三四行，第三部分为，根据已经填充好的前四行，填写最后四行。for (ints=1;s=k;s+) N/=2; (4)用一个for循环对中提到的每一部分进行划分for(intt=1;t=N;t+)对于第一部分，将其划分为四个小的单元，即对第二行进行如下划分同理，对第二部分（即三四行），划分为两部分，第三部分同理。 (5)最后，根据以上for循环对整体的划分和分治法的思想，
27、进行每一个单元格的填充。填充原则是：对角线填充for(int i=m+1;i=2*m;i+) /i控制行for(int j=m+1;j=2*m;j+) /j控制列aij+(t-1)*m*2= ai-mj+(t-1)*m*2-m;/*右下角的值等于左上角的值 */aij+(t-1)*m*2-m =ai-mj+(t-1)*m*2;/*左下角的值等于右上角的值 */ 运行过程：(1)由初始化的第一行填充第二行(2)由s控制的第一部分填完。然后是s+，进行第二部分的填充(3)最后是第三部分的填充3.4程序实现及程序截图3.4.1程序源码#include #include using namespace
28、 std;void Table(int k,int n,int *a);void input(int &k);void output(int *a,int n);int main() int k; input(k); int n=1; /n=2k(k=1)个选手参加比赛 for(int i=1; i=k; i+) n *= 2; /根据n动态分配二维数组a int *a = new int *n+1; for(int i=0;i=n;i+) ai = new intn+1; Table(k,n,a); cout循环赛事日程表为：endl; output(a,n); /释放空间 for(int
29、i=0;i=n;i+) delete ai; delete a; return 0;void input(int &k) cout请输入k值：k;void output(int *a,int n) for(int i=1; i=n; i+) for(int j=1; j=n; j+) coutaij ; coutendl; void Table(int k,int n,int *a) for(int i=1; i=n; i+) a1i=i;/设置日程表第一行 int m = 1;/每次填充时，起始填充位置 for(int s=1; s=k; s+) n /= 2; for(int t=1; t
30、=n; t+) for(int i=m+1; i=2*m; i+)/控制行 for(int j=m+1; j=2*m; j+)/控制列 aij+(t-1)*m*2 = ai-mj+(t-1)*m*2-m;/右下角等于左上角的值 aij+(t-1)*m*2-m = ai-mj+(t-1)*m*2;/左下角等于右上角的值 m *= 2; 3.4.2程序截图3.5学习或程序调试心得按分治策略，我们可以将所有的选手分为两半，则n个选手的比赛日程表可以通过n/2个选手的比赛日程表来决定。递归地用这种一分为二的策略对选手进行划分，直到只剩下两个选手时，比赛日程表的制定就变得很简单。这时只要让这两个选手进行
31、比赛就可以了。分治法解决问题的关键在于将大的问题转化为小的问题，是分而治之的思想。而且分成的小问题往往与原问题相同，用递归的方法解决子问题。用递归方法编写的问题解决程序具有结构清晰，可读性强等优点，且递归算法的设计比非递归算法的设计往往要容易一些，所以当问题本身是递归定义的，或者问题所涉及到的数据结构是递归定义的，或者是问题的解决方法是递归形式的时候，往往采用递归算法来解决。递归可以说是一种通用之法。作业4 活动安排的贪心算法4.1算法应用背景在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的仅是在某种意义上的局部最优解。贪心算法不是对所有问题都能得到
32、整体最优解，但对范围相当广泛的许多问题他能产生整体最优解或者是整体最优解的近似解。活动安排是可以用贪心算法求解的很好例子。该问题要求高效的安排一系列争用某一公共资源的活动。贪心算法提供了一个简单、漂亮的方法，是尽可能多的活动能兼容地使用同一公共资源。4.2算法原理 4.2.1 问题描述:设有n个活动的集合E=1,2,n，其中每个活动都要求使用同一资源，如演讲会场等，而在同一时间内只有一个活动能使用这一资源。每个活动i都有一个要求使用该资源的起始时间si和一个结束时间fi,且si fi。如果选择了活动i，则它在半开时间区间si, fi)内占用资源。若区间si, fi)与区间sj, fj)不相交,
33、则称活动i与活动j是相容的。也就是说，当sifj或sjfi时，活动i与活动j相容。活动安排问题就是要在所给的活动集合中选出最大的相容活动子集合。4.2.2算法思路：贪心算法采用自顶向下，以迭代的方法做出相继的贪心选择，每做一次贪心选择就将所求问题简化为一个规模更小的子问题，通过每一步贪心选择，可得到问题的一个最优解，虽然每一步上都要保证能获得局部最优解，但由此产生的全局解有时不一定是最优的，所以贪婪法不要回溯。所谓贪心选择性质是指所求问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来达到。这是贪心算法可行的第一个基本要素。贪心算法则通常以自顶向下的方式进行，以迭代的方式作出相继的贪心选
34、择，每作一次贪心选择就将所求问题简化为规模更小的子问题。4.3算法描述将活动按照结束时间进行从小到大排序。然后用i代表第i个活动，si代表第i个活动开始时间，fi代表第i个活动的结束时间。按照从小到大排序，挑选出结束时间尽量早的活动，并且满足后一个活动的起始时间晚于前一个活动的结束时间，全部找出这些活动就是最大的相容活动子集合。事实上系统一次检查活动i是否与当前已选择的所有活动相容。若相容活动i加入已选择活动的集合中，否则，不选择活动i，而继续下一活动与集合A中活动的相容性。若活动i与之相容，则i成为最近加入集合A的活动，并取代活动j的位置。各活动的起始时间和结束时间存储于数组s和f中，且按结
35、束时间的非减序排列。如果所给的活动未按此序排列，可以用O(nlogn)的时间重排。4.4程序实现及程序截图4.4.1程序源码/ 活动安排问题 贪心算法#include using namespace std;templatevoid GreedySelector(int n, Type s, Type f, bool A);const int N = 11;int main() /下标从1开始,存储活动开始时间 int s = 0,1,3,0,5,3,5,6,8,8,2,12; /下标从1开始,存储活动结束时间 int f = 0,4,5,6,7,8,9,10,11,12,13,14; bool AN+1; cout各活动的开始时间,结束时间分别为：endl; for(int i=1;i=N;i+) couti:(si,fi)endl; GreedySelector(N,s,f,A); cout最大相容活动子集为：endl; for(int i=1;i=N;i+) if(Ai) couti:(si,fi)endl; return 0;templatevoid GreedySelector(int n, Type s, Type f, bool A) A1=true; int j=1;/记录最近一次加入A中的活动 for (int i=2;i=fj)
