新计算机算法设计及分析课程设计.docVIP

用分治法解决快速排序问题及用回溯法解决0-1背包问题一、 课程设计目的：计算机算法设计与分析这门课程是一门实践性非常强的课程，要求我们能够将所学的算法应用到实际中，灵活解决实际问题。通过这次课程设计，能够培养我们独立思考、综合分析与动手的能力，并能加深对课堂所学理论和概念的理解，可以训练我们算法设计的思维和培养算法的分析能力。二、课程设计内容：1、分治法：（2）快速排序；2、回溯法：（2）图的着色。三、概要设计：l 分治法快速排序：分治法的基本思想是将一个规模为n的问题分解为k个规模较小的子问题，这些子问题互相独立且与原问题相同。递归地解这些子问题，然后将各个子问题的解合并得到原问题的解。分治法的条件：（1) 该问题的规模缩小到一定的程度就可以容易地解决；（2) 该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质；（3) 利用该问题分解出的子问题的解可以合并为该问题的解；（4) 该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子子问题。 抽象的讲，分治法有两个重要步骤：（1）将问题拆开；（2）将答案合并；l 回溯法0-1背包问题回溯法的基本思想是确定了解空间的组织结构后，回溯法就是从开始节点（根结点）出发，以深度优先的方式搜索整个解空间。这个开始节点就成为一个活结点，同时也成为当前的扩展结点。在当前的扩展结点处，搜索向纵深方向移至一个新结点。这个新结点就成为一个新的或节点，并成为当前扩展结点。如果在当前的扩展结点处不能再向纵深方向移动，则当前的扩展结点就成为死结点。换句话说，这个节点，这个结点不再是一个活结点。此时，应往回（回溯）移动至最近一个活结点处，并使这个活结点成为当前的扩展结点。回溯法即以这种工作方式递归的在解空间中搜索，直到找到所要求的解或解空间中以无活结点为止。四、详细设计与实现：l 分治法快速排序 快速排序是基于分治策略的另一个排序算法。其基本思想是，对于输入的子数组,按以下三个步骤进行排序： （1）、分解(divide) 以元素为基准元素将划分为三段，和，使得中任何一个元素都小于，而中任何一个元素大于等于，下标在划分过程中确定。（2）、递归求解(conquer) 通过递归调用快速排序算法分别对和进行排序。（3）、合并(merge) 由于和的排序都是在原位置进行的，所以不必进行任何合并操作就已经排好序了。 算法实现题: 现将数列12 21 31 45 36 76 66 46 30 7 89 20 2 5 99 47 23 54 51 73进行快速排序。源程序如下：#include using namespace std;#define size 20 int partition(int data,int p,int r) int n=datap,i=p+1,j=r,temp; /将n的元素交换到右边区域 while(true) while(datain) -j; if(i=j) break; temp=datai; datai=dataj; dataj=temp; datap=dataj; dataj=n; return j; void quick_sort(int data,int p,int r) if(p=r) return; int q=partition(data,p,r); quick_sort(data,p,q-1); /对左半段排序 quick_sort(data,q+1,r); /对右半段排序 int main() int i,n,datasize;printf(请输入要排列的数目（=20）：);scanf(%d,&n);printf(请输入要排列的数列：n); for(i=0;in;+i) scanf(%d,&datai); quick_sort(data,0,n-1);printf(排列后的数列为：n); for(i=0;in;+i) printf( %d ,datai); printf(n);return 0; 运行结果如下：图1图5l 回溯法0-1背包问题l 回溯法是一个既带有系统性又带有跳跃性的的搜索算法。它在包含问题的所有解的解空间树中，按照深度优先的策略，从根结点出发搜索解空间树。算法搜索至解空间树的任一结点时，总是先判断该结点是否肯定不包含问题的解。如果肯定不包含，则跳过对以该结点为根的子树的系统搜索，逐层向其祖先结点回溯。否则，进入该子树，继续按深度优先的策略进行搜索。回溯法在用来求问题的所有解时，要回溯到根，且根结点的所有子树都已被搜索遍才结束。而回溯法在用来求问题的任一解时，只要搜索到问题的一个解就可以结束。这种以深度优先的方式系统地搜索问题的解的算法称为回溯法，它适用于解一些组合数较大的问题。二、算法框架：1、问题的解空间：应用回溯法解问题时，首先应明确定义问题的解空间。问题的解空间应到少包含问题的一个（最优）解。2、回溯法的基本思想：确定了解空间的组织结构后，回溯法就从开始结点（根结点）出发，以深度优先的方式搜索整个解空间。这个开始结点就成为一个活结点，同时也成为当前的扩展结点。在当前的扩展结点处，搜索向纵深方向移至一个新结点。这个新结点就成为一个新的活结点，并成为当前扩展结点。如果在当前的扩展结点处不能再向纵深方向移动，则当前扩展结点就成为死结点。换句话说，这个结点不再是一个活结点。此时，应往回移动（回溯）至最近的一个活结点处，并使这个活结点成为当前的扩展结点。回溯法即以这种工作方式递归地在解空间中搜索，直至找到所要求的解或解空间中已没有活结点时为止。运用回溯法解题通常包含以下三个步骤：（1）针对所给问题，定义问题的解空间；（2）确定易于搜索的解空间结构；（3）以深度优先的方式搜索解空间，并且在搜索过程中用剪枝函数避免无效搜索；3、递归回溯：由于回溯法是对解空间的深度优先搜索，因此在一般情况下可用递归函数来实现回溯法。l1 问题描述对于0-1背包问题回溯法的一个实例，n=4，c=7，p=9,10,7,4,w=3,5,2,1.这4个物品的单位重量价值分别为3,2,3,5,4.以物品为单位价值的递减序装入物品。先装入物品4，然后装入物品3和1.装入这3个物品后，剩余的背包容量为1，只能装入0.2的物品2.由此可得到一个解为x=1,0,2,1,1,其相应的价值为22.尽管这不是一个可行解，但可以证明其价值是最有大的上界。因此，对于这个实例，最优值不超过22. 回溯法的基本思想是按深度优先策略，从根节点出发搜索解空间树，算法搜索至解空间的任一点时，先判断该结点是否包含问题的解，如果肯定不包含，则跳过以该结点为根的子树的搜索，逐层向其祖先结点回溯，否则，进入该子树，继续按深度优先进行搜索。第15页 共10页2 问题分析利用回溯法的设计思想来解决背包问题。首先是将可供选择的物品的个数输入程序，将物品排成一列，计算总物品的体积s，然后输入背包的实际体积V，如果背包的体积小于0或者大于物品的总体积s，则判断输入的背包体积错误，否则开始顺序选取物品装入背包，假设已选取了前i 件物品之后背包还没有装满，则继续选取第i+1件物品，若该件物品太大不能装入，则弃之而继续选取下一件，直至背包装满为止。但如果在剩余的物品中找不到合适的物品以填满背包，则说明刚刚装入背包的那件物品不合适，应将它取出弃之一边，继续再从它之后的物品中选取，如此重复，直至求得满足条件的解。因为回溯求解的规则是后进先出，所以要用到栈来存储符合条件的解，在存储过程中，利用数组来存储各个物品的体积，然后用深度优先的搜索方式求解，将符合条件的数组元素的下标存入栈里，最后得到符合条件的解并且实现输出。3 建立数学模型 0-l背包问题是子集选取问题。一般情况下，0-1背包问题是NP难题。0-1背包问题的解空间可用子集树表示。解0-1背包问题的回溯法与装载问题的回溯法十分类似。在搜索解空间树时，只要其左儿子结点是一个可行结点，搜索就进入其左子树。当右子树有可能包含最优解时才进入右子树搜索。否则将右子树剪去。设r是当前剩余物品价值总和；cp是当前价值；bestp是当前最优价值。当cp+rbestp时，可剪去右子树。计算右子树中解的上界的更好方法是将剩余物品依其单位重量价值排序，然后依次装入物品，直至装不下时，再装入该物品的一部分而装满背包。由此得到的价值是右子树中解的上界。算法复杂性是算法运行所需要的计算机资源的量，需要时间资源的量称为时间复杂性，需要的空间资源的量称为空间复杂性。这个量应该只依赖于算法要解的问题的规模、算法的输入和算法本身的函数。如果分别用N、I和A表示算法要解问题的规模、算法的输入和算法本身，而且用C表示复杂性，那么，应该有C=F(N,I,A)。一般把时间复杂性和空间复杂性分开，并分别用T和S来表示，则有： T=T(N,I)和S=S(N,I) 。最坏情况下的时间复杂性：最好情况下的时间复杂性：平均情况下的时间复杂性：其中DN是规模为N的合法输入的集合；I*是DN中使T(N, I*)达到Tmax(N)的合法输入； 是中使T(N, )达到Tmin(N)的合法输入；而P(I)是在算法的应用中出现输入I的概率。4 算法设计使用栈作为该程序的数据结构，利用栈进行语法检查，以深度优先的搜索方式解空间，实现递归过程和函数的调用，在设计时还使用C语言的数组及其循环语言来实现程序。运用回溯法解题，在搜索解空间树时，只要其左儿子节点是一个可行结点，搜索就进入左子树，在右子树中有可能包含最优解是才进入右子树搜索。否则将右子树剪去。具体步骤如下：1.针对所给问题，定义问 题的解空间；2.确定易于搜索的解空间结3.以深度优先的方式搜索解空间，并且在搜索过程中用剪枝函数避免无效搜索；5 算法实现运用Pc机，C/C+程序学习系统软件 编程C语言程序源代码核心源代码#include struct bagdouble w;double cw,cp,bestp;struct goodsdouble wc,pc;int v; void paixu(goods g,int n)int i,j;double temp;for(i=0;ii;j-)if(gj.pc/gj.wc)(gj-1.pc/gj-1.wc)temp=gj.pc;gj.pc=gj-1.pc;gj-1.pc=temp;temp=gj.wc;gj.wc=gj-1.wc;gj-1.wc=temp;void backtruck(int i,int n,goods g,bag *b)if(i=n&b-cww)if(b-bestpcp)b-bestp=b-cp;if(icww)b-cw=b-cw+gi.wc;b-cp=b-cp+gi.pc;backtruck(i+1,n,g,b);b-cw=b-cw-gi.wc;b-cp=b-cp-gi.pc;backtruck(i+1,n,g,b);void main()goods g100;bag b;int n,i;coutb.w;coutn;cout输入物品的质量:;for(i=0;igi.wc;cout输入物品价值:;for(i=0;igi.pc;paixu(g,n); b.bestp=0;b.cw=0;b.cp=0; backtruck(0,n,g,&b);cout最优价值：;coutb.bestpendl;6 测试分析1.当输入的背包体积V小于物品的总体积s 时：2.当输入的背包体积V大于物品的总体积s 时：当输入的背包体积小于等于可供选择的物品的总体积时，可以正确进行选择装入的物品，并且统计符合条件的解的方法；当输入的背包体积小于0或者大于可供选择的物品的总体积时，程序会自动提醒输入背包体积错误，这样就方便了程序的正确运行与解决实际问题的重要作用。实验结果五、总结：通过本次课程设计，使我对快速排序以及0-1背包设计的基本过程的设计方法、步骤、思路、有了一定的了解与认识。在这次课程设计过程中，我认识到只是知道课本上的理论知识是远远不够的，我们还必须要深切的理解每个算法的思想，并且能够利用c+语言去编写相关的代码，经过不断的修改、调试，使之能解决相应的问题，最终能运用到实际案例中去。 本程序利用回溯法的设计思想来解决问题，在用来求问题的所有解时，针对所给问题，定义问题的解空间，确定易于搜索的解空间结构，要回溯到根，且根结点的所有子树都已被搜索遍才结束，回溯法的求解规则是后进先出，所以在程序设计中自然要使用到了栈。在程序设计过程中，更加巩固了我的C语言程序设计基础知识，使我对C语言的循环操作和指针、数组操作更加熟悉，区别了栈与链表，学会用栈来解决实际问题，并且联系了树的重要内容，重点训练了对算法与数据结构的难点内容，算法与数据结构的统一，使编程语言更加简洁，清晰易懂，强调了好的程序设计风格,运行结果更加美观，在调试和运行时，我遇到了一些很基础的问题，通过请教老师和同学，这些问题都逐一解决了，这使得我在运行正确通过时，内心产生了一种