《新《计算机算法设计与分析》课程设计.doc》由会员分享，可在线阅读，更多相关《新《计算机算法设计与分析》课程设计.doc（15页珍藏版）》请在金锄头文库上搜索。
1、用分治法解决快速排序问题及用回溯法解决0-1背包问题一、 课程设计目的：计算机算法设计与分析这门课程是一门实践性非常强的课程，要求我们能够将所学的算法应用到实际中，灵活解决实际问题。通过这次课程设计，能够培养我们独立思考、综合分析与动手的能力，并能加深对课堂所学理论和概念的理解，可以训练我们算法设计的思维和培养算法的分析能力。二、课程设计内容：1、分治法：（2）快速排序；2、回溯法：（2）图的着色。三、概要设计：l 分治法快速排序：分治法的基本思想是将一个规模为n的问题分解为k个规模较小的子问题，这些子问题互相独立且与原问题相同。递归地解这些子问题，然后将各个子问题的解合并得到原问题的解。分治
2、法的条件：（1) 该问题的规模缩小到一定的程度就可以容易地解决；（2) 该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质；（3) 利用该问题分解出的子问题的解可以合并为该问题的解；（4) 该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子子问题。 抽象的讲，分治法有两个重要步骤：（1）将问题拆开；（2）将答案合并；l 回溯法0-1背包问题回溯法的基本思想是确定了解空间的组织结构后，回溯法就是从开始节点（根结点）出发，以深度优先的方式搜索整个解空间。这个开始节点就成为一个活结点，同时也成为当前的扩展结点。在当前的扩展结点处，搜索向纵深方向移至一个新结点。这个新
3、结点就成为一个新的或节点，并成为当前扩展结点。如果在当前的扩展结点处不能再向纵深方向移动，则当前的扩展结点就成为死结点。换句话说，这个节点，这个结点不再是一个活结点。此时，应往回（回溯）移动至最近一个活结点处，并使这个活结点成为当前的扩展结点。回溯法即以这种工作方式递归的在解空间中搜索，直到找到所要求的解或解空间中以无活结点为止。四、详细设计与实现：l 分治法快速排序 快速排序是基于分治策略的另一个排序算法。其基本思想是，对于输入的子数组,按以下三个步骤进行排序： （1）、分解(divide) 以元素为基准元素将划分为三段，和，使得中任何一个元素都小于，而中任何一个元素大于等于，下标在划分过程
4、中确定。（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的元素交换到右边区域 whi
5、le(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(请输入要排列的数目
6、（=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 回溯法是一个既带有系统性又带有跳跃性的的搜索算法。它在包含问题的所有解的解空间树中，按照深度优先的策略，从根结点出发搜索解空间树。算法搜索至解空间树的任一结点时，总是先判断该结点是否肯定不包含问题的解。如果
7、肯定不包含，则跳过对以该结点为根的子树的系统搜索，逐层向其祖先结点回溯。否则，进入该子树，继续按深度优先的策略进行搜索。回溯法在用来求问题的所有解时，要回溯到根，且根结点的所有子树都已被搜索遍才结束。而回溯法在用来求问题的任一解时，只要搜索到问题的一个解就可以结束。这种以深度优先的方式系统地搜索问题的解的算法称为回溯法，它适用于解一些组合数较大的问题。二、算法框架：1、问题的解空间：应用回溯法解问题时，首先应明确定义问题的解空间。问题的解空间应到少包含问题的一个（最优）解。2、回溯法的基本思想：确定了解空间的组织结构后，回溯法就从开始结点（根结点）出发，以深度优先的方式搜索整个解空间。这个开始
8、结点就成为一个活结点，同时也成为当前的扩展结点。在当前的扩展结点处，搜索向纵深方向移至一个新结点。这个新结点就成为一个新的活结点，并成为当前扩展结点。如果在当前的扩展结点处不能再向纵深方向移动，则当前扩展结点就成为死结点。换句话说，这个结点不再是一个活结点。此时，应往回移动（回溯）至最近的一个活结点处，并使这个活结点成为当前的扩展结点。回溯法即以这种工作方式递归地在解空间中搜索，直至找到所要求的解或解空间中已没有活结点时为止。运用回溯法解题通常包含以下三个步骤：（1）针对所给问题，定义问题的解空间；（2）确定易于搜索的解空间结构；（3）以深度优先的方式搜索解空间，并且在搜索过程中用剪枝函数避免
9、无效搜索；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. 回溯法的基本思想是按深度优先策略，从根节点出发搜索解空
10、间树，算法搜索至解空间的任一点时，先判断该结点是否包含问题的解，如果肯定不包含，则跳过以该结点为根的子树的搜索，逐层向其祖先结点回溯，否则，进入该子树，继续按深度优先进行搜索。深入贯彻落实科学发展观和党的十七届五中全会，及全国、省、市纪委工作会议精神，坚持以人为本、执政为民理念，坚持标本兼治、综合治理、惩防并举、注重预防的方针，弘扬理论联系实际的马克思主义学风several group number, then with b a, =c,c is is methyl b two vertical box between of accurate size. Per-23 measurement,
11、 such as proceeds of c values are equal and equal to the design value, then the vertical installation accurate. For example a, b, and c valueswhile on horizontal vertical errors for measurement, General in iron angle code bit at measurement level points grid errors, specific method is from baseline
12、to methyl vertical box center line distance for a, to b vertical box distance for b, list can measured第15页 共10页2 问题分析利用回溯法的设计思想来解决背包问题。首先是将可供选择的物品的个数输入程序，将物品排成一列，计算总物品的体积s，然后输入背包的实际体积V，如果背包的体积小于0或者大于物品的总体积s，则判断输入的背包体积错误，否则开始顺序选取物品装入背包，假设已选取了前i 件物品之后背包还没有装满，则继续选取第i+1件物品，若该件物品太大不能装入，则弃之而继续选取下一件，直至背包装满
13、为止。但如果在剩余的物品中找不到合适的物品以填满背包，则说明刚刚装入背包的那件物品不合适，应将它取出弃之一边，继续再从它之后的物品中选取，如此重复，直至求得满足条件的解。因为回溯求解的规则是后进先出，所以要用到栈来存储符合条件的解，在存储过程中，利用数组来存储各个物品的体积，然后用深度优先的搜索方式求解，将符合条件的数组元素的下标存入栈里，最后得到符合条件的解并且实现输出。3 建立数学模型 0-l背包问题是子集选取问题。一般情况下，0-1背包问题是NP难题。0-1背包问题的解空间可用子集树表示。解0-1背包问题的回溯法与装载问题的回溯法十分类似。在搜索解空间树时，只要其左儿子结点是一个可行结点
14、，搜索就进入其左子树。当右子树有可能包含最优解时才进入右子树搜索。否则将右子树剪去。设r是当前剩余物品价值总和；cp是当前价值；bestp是当前最优价值。当cp+rbestp时，可剪去右子树。计算右子树中解的上界的更好方法是将剩余物品依其单位重量价值排序，然后依次装入物品，直至装不下时，再装入该物品的一部分而装满背包。由此得到的价值是右子树中解的上界。算法复杂性是算法运行所需要的计算机资源的量，需要时间资源的量称为时间复杂性，需要的空间资源的量称为空间复杂性。这个量应该只依赖于算法要解的问题的规模、算法的输入和算法本身的函数。如果分别用N、I和A表示算法要解问题的规模、算法的输入和算法本身，而且用C表示复杂性，那么，应该有C=F(N,I,A)。一般把时间复杂性和空间复杂性分开，并分别用T和S来表示，则有： T=T(N,I)和S=S(N,I) 。最坏情况下的时间复杂性：最好情况下的时间复杂性：平均情况下的时间
