算法考试复习纲要_第1页
算法考试复习纲要_第2页
算法考试复习纲要_第3页
算法考试复习纲要_第4页
算法考试复习纲要_第5页
已阅读5页,还剩11页未读, 继续免费阅读

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

1、考试题型一,问答题(16%)二,算法填空题(24%)三,运算题(20%)四,证明题(10%)五,算法设计题(30%)考试样题一,问答题(每小题 8 分,共 16 分) 1. 什么是算法 算法有哪几个特性 2. 动态规划算法的基本思想是什么 它和分治法有什么区别和联系 3. 用动态规划算法求解问题的基本步骤有那些 考试样题二,算法填空题(每小题 12 分,共 24 分) 1.阅读下面的算法,在答题处填充所缺的语句: Void Knapsack(int n,float M,float v,float w,float x)Sort(n,v,w);int i;for(i=1;i<=n;i+) x

2、i=0;float c=M;for(i=1;i<=n;i+)if( (1) break;xi=1;(2) ; if(ic (2) c-=wi (3) xi=c/wi 考试样题三,运算题(每小题 10 分,共 20 分) 在矩阵连乘问题中,采用课本标准的动态规划算法,已知si,j的值如下图所示,写出调用Traceback(1,6,s)后输出的最优次序.答案:最优计算次序为: (A1(A2A3 )(A4 A5)A6 )考试样题四,证明题(每小题 10 分,共 10 分) 证明装载问题具有贪心选择性质.参考答案:证明:设集装箱已依其重量从小到大排序, (x1,x2, ,xn)是最优装载问题的一

3、个最优解.又设1.当k=1时, (x1,x2, ,xn)是一个满足贪心选择性质的最优解.2.当k>1时,取y1=1;yk=0;yi=xi,1<IN,IK因此,(y1,y2, ,yn)是所给最优装载问题的一个可行解另一方面,由(y1,y2, ,yn)是一个满足贪心选择性质的最优解所以,最优装载问题具有贪心选择性质考试样题五,算法设计题(每小题 15 分,共 30 分) 1. 给定已排好序的n个元素a0:n-1,现要在这n个元素中找出一特定的元素x,要求时间复杂度为O(logn).int BinarySearch(Type a,const Type & x,int n)int

4、BinarySearch(Type a,const Type & x,int n)int left=0; int right=n-1;while(leftamiddle) left=middle+1;else right=middle-1;return -1; 第一章 算法一.算法的概念与性质1)算法的特性和基本概念算法是在有限步骤内求解某一问题所使用的一组定义明确的规则。通俗点说,就是计算机解题的过程。简单的说就是解决问题的方法和过程。五个重要的特征:(一个算法应该具有)1.确切性: 算法的每一步骤必须有确切的定义; 2.输入: 一个算法有0个或多个输入,以刻画运算对象的初始情况;

5、3.输出: 一个算法有一个或多个输出,以反映对输入数据加工后的结果。没有输出的算法是毫无意义的; 4.可行性:算法原则上能够精确地运行,而且人们用笔和纸做有限次运算后即可完成。5.有穷性:一个算法必须保证执行有限步之后结束;2)算法的时间,空间复杂度:计算机的资源,最重要的是时间和空间(即存储器)资源。因而,算法的复杂性有时间复杂性和空间复杂性之分。a. 算法的时间复杂性:通常指算法中包含简单操作次数的多少。算法的复杂性是算法效率的度量,是评价算法优劣的重要依据。一个算法的复杂性的高低体现在运行该算法所需要的计算机资源的多少上面,所需的资源越多,我们就说该算法的复杂性越高;反之,所需的资源越低

6、,则该算法的复杂性越低。 b. 算法的空间复杂性:指算法在运行过程中临时占用的存储空间的大小。空间复杂度作为算法所需存储空间的量度,记作S(n)=O(f(n)采用时间的渐近表示,从计算时间上可以把算法分成两类。凡可以用多项式来对其计算时间限界的算法,称为多项式时间算法;而计算时间用指数函数限界的算法称为指数时间算法。其中有六种多项式时间算法最为常见,其关系为:O(1)<O(logn)<O(n)<O(nlogn)<O(n2)<O(n3);指数时间算法一般有:O(2n)<O(n!)<O(nn)。3)算法的分类:1.(数值算法 )  2. 非数值算

7、法 4)算法的描述:1.自然语言描述 2.(流程图描述) 3.程序语言描述 5)算法的分析标准:1.时空观念  2. (发展观念) 3. 设计观点 4. 交流的观点第二章 递归与分治策略一.递归的概念1递归的定义:一个过程(或函数)直接或间接调用自己本身,这种过程(或函数叫递归过程(或函数),有直接调用和间接调用两种。2.设计递归算法主要步骤:(1)确定递归公式;(2)确定边界(终了)条件;3.递归描述的算法的特征:为求解规模为N的问题,设法将它分解成规模较小的问题,从这些小问题的解方便地构造出大问题的解,并且这些规模较小的问题也能采用同样的分解和综合方法,分解成规模更小的问题,并从

8、这些更小问题的解构造出规模较大问题的解。特别地,当规模N=1时,能直接得解。4.递归定义:为了描述问题的某一状态,必须用到它的上一状态,而描述上一状态,又必须用到它的上一状态,这种用自已来定义自己的方法,称为递归定义。 例如:定义函数f(n)为:f(n)=n*f(n1) (n>0);f(n)= 1(n=0)则当0时,须用f(n-1)来定义f(n),用f(n-1-1)来定义f(n-1)当n=0时,f(n)=1。5.递归定义有两个要素:(1)递归边界条件。也就是所描述问题的最简单情况,它本身不再使用递归的定义。如上例,当n=0时,f(n)=1,不使用f(n-1)来定义。 (2)递归定义:使问

9、题向边界条件转化的规则。递归定义必须能使问题越来越简单。如上例f(n)由f(n-1)定义,越来越靠近f(0),即边界条件。最简单的情况是f(0)=1。递归算法效率往往很低, 费时和费内存空间. 但递归也有长处, 它能使一个蕴含递归关系且结构复杂的程序简化精炼, 增加可读性. 特别在难于找到从边界到解的全过程的情况下, 把问题推进一步简化而其结果仍维持原问题的关系。6.递归调用方式: 1. 直接递归, 递归过程P直接自己调用自己; 2. 间接递归, 即P包含另一过程D, 而D又调用P.7.递归算法适用的一般场合为:(1)数据的定义形式按递归定义.如裴波那契数列的定义: f(n)=f(n-1)+f

10、(n-2);f(0)=1;f(1)=2.对应递归程序:Int Function fib(int n)if n = 0 then fib = 1递归边界else if n = 1 then fib = 2 else fib= fib(n-2) + fib(n-1)递归这类递归问题可转化为递推算法,递归边界作为递推的边界条件.(2)数据之间的关系(即数据结构)按递归定义. 如树的遍历, 图的搜索等.(3)问题解法按递归算法实现. 例如回溯法等。二.排序算法:排序就是将杂乱无章的数据元素,通过一定的方法按关键字顺序排列的过程。这里的数据元素是指记录,即若干个数据项,关键字就是选中的数据元素。1排序问

11、题一般分为内排序( internal sorting )和外排序( external sorting )两类:a.内排序:待排序的表中记录个数较少,整个排序过程中所有的记录都可以保留在内存中;b.外排序:待排序的记录个数足够多,以至于他们必须存储在磁带、磁盘上组成外部文件,排序过程中需要多次访问外存。 2.排序问题的复杂性:对排序算法计算时间的分析可以遵循若干种不同的准则,通常以排序过程所需要的算法步数作为度量,有时也以排序过程中所作的键比较次数作为度量。特别是当作一次键比较需要较长时间。例如:当键是较长的字符串时,常以键比较次数作为排序算法计算时间复杂性的度量。当排序时需要移动记录,且记录都

12、很大时,还应该考虑记录的移动次数。究竟采用哪种度量方法比较合适要根据具体情况而定。在下面的讨论中我们主要考虑用比较的次数作为复杂性的度量。为了对有n个元素的线性表进行排序,至少必须扫描线性表一遍以获取这n个元素的信息,因此排序问题的计算复杂性下界为(n)。如果我们对输入的数据不做任何要求,我们所能获得的唯一信息就是各个元素的具体的值,我们仅能通过比较来确定输入序列<a1,a2,.,an>的元素间次序。即给定两个元素ai和aj,通过测试ai<aj ,aiaj ,ai=aj ,aiaj ,ai>aj 中的哪一个成立来确定ai和aj间的相对次序。这样的排序算法称为比较排序算法

13、。下面我们讨论一下比较排序算法在最坏情况下至少需要多少次比较,即比较排序算法的最坏情况复杂性下界。三、分而治之算法1算法思想:分而治之算法与软件设计的模块化方法非常相似。为了解决一个大问题,可以如下进行:1)、将大问题分成两个或多个更小的问题;2)、分别解决每个小问题;3)、把每个小问题的解答组合起来即可得到原问题的解答。小问题通常与原问题相似,可以递归的使用分而治之策略解决问题。二分搜索技术大整数乘法合并排序和快速排序排序算法归纳:一.插入排序(Insertion Sort)1)基本思想:每次将一个待排序的数据元素,插入到前面已经排好序的数列中的适当位置,使数列依然有序;直到待排序数据元素全

14、部插入完为止。2)排序过程:【示例】:初始关键字49 38 65 97 76 13 27 49 J=2(38) 38 49 65 97 76 13 27 49 J=3(65) 38 49 65 97 76 13 27 49 J=4(97) 38 49 65 97 76 13 27 49 J=5(76) 38 49 65 76 97 13 27 49 J=6(13) 13 38 49 65 76 97 27 49 J=7(27) 13 27 38 49 65 76 97 49 J=8(49) 13 27 38 49 49 65 76 97 3)直接插入排序算法:void si_sort(int

15、e,int n)int i,j,t;for(i=0;i< n;i+)for(t=ei,j=i-1; j>=0&&t<ej;j-) ej+1=ej; ej+1=t; 二、选择排序1)基本思想:每一趟从待排序的数据元素中选出最小(或最大)的一个元素,顺序放在已排好序的数列的最后,直到全部待排序的数据元素排完。2)排序过程:【示例】: 初始关键字 49 38 65 97 76 13 27 49第一趟排序后 13 38 65 97 76 49 27 49第二趟排序后 13 27 65 97 76 49 38 49第三趟排序后 13 27 38 97 76 49 65

16、49第四趟排序后 13 27 38 49 49 97 65 76第五趟排序后 13 27 38 49 49 97 97 76第六趟排序后 13 27 38 49 49 76 76 97第七趟排序后 13 27 38 49 49 76 76 97最后排序结果 13 27 38 49 49 76 76 97 选择排序主要是每一趟从待排序列中选取一个关键码最小记录,即第一趟从n个记录中选取关键码最小记录,第二趟从剩下的n-1个记录中选关键码最小记录,直到整个序列记录选完。这样,由选取记录的顺序,便得到按关键码有序的序列。3)操作方法:第一趟,从n个记录中找出关键码最小的记录与第一个记录交换;第二趟,

17、从第二个记录开始的n-1个记录中再选出关键码最小的记录与第二个记录交换;如此,第i趟,则从第i个记录开始的n-i+1个记录中选出关键码最小的记录与第i个记录交换,直到整个序列按关键码有序。4)【算法】void SelectSort(S_TBL *s) for(i=1;i<s->length;i+) /* 作length-1趟选取 */ for(j=i+1,t=i;j<=s->length;j+) /* 在i开始的length-n+1个记录中选关键码最小的记录*/ if(s->elemt.key>s->elemj.key) t=j; /* t中存放关键码

18、最小记录的下标 */s->elemt<->s->elemi; /*关键码最小的记录与第i个记录交换 */三、冒泡排序(BubbleSort)1)基本思想:两两比较待排序数据元素的大小,发现两个数据元素的次序相反时即进行交换,直到没有反序的数据元素为止。2)排序过程:设想被排序的数组R1.N垂直竖立,将每个数据元素看作有重量的气泡,根据轻气泡不能在重气泡之下的原则,从下往上扫描数组R,凡扫描到违反本原则的轻气泡,就使其向上"漂浮",如此反复进行,直至最后任何两个气泡都是轻者在上,重者在下为止。【示例】:49 13 13 13 13 13 13 1338

19、 49 27 27 27 27 27 2765 38 49 38 38 38 38 3897 65 38 49 49 49 49 4976 97 65 49 49 49 49 4913 76 97 65 65 65 65 6527 27 76 97 76 76 76 7649 49 49 76 97 97 97 97 3)冒泡排序算法实践:void sb_sort(int e, int n) int j, p, h, t; for(h=n-1; h>0; h=p)for(p=j=0; j<h; j+)if(ej>ej+1) t=ej;ej=ej+1; ej+1=t;p=j;

20、4)冒泡排序(Bubble Sort)算法分析:先来看看待排序列一趟冒泡的过程:设1<jn,r1,r2,···,rj为待排序列,通过两两比较、交换,重新安排存放顺序,使得rj是序列中关键码最大的记录。一趟冒泡方法为: i=1; /设置从第一个记录开始进行两两比较 若ij,一趟冒泡结束。 比较ri.key与ri+1.key,若ri.keyri+1.key,不交换,转 当ri.key>ri+1.key时, r0=ri;ri=ri+1;ri+1=r0;将ri与ri+1交换; i=i+1; 调整对下两个记录进行两两比较,转5)冒泡排序方法:对n个记录的表,第一

21、趟冒泡得到一个关键码最大的记录rn,第二趟冒泡对n-1个记录的表,再得到一个关键码最大的记录rn-1,如此重复,直到n个记录按关键码有序的表。四、快速排序(Quick Sort)1)基本思想:在当前无序区R1.H中任取一个数据元素作为比较的"基准"(记为X),用此基准将当前无序区划分为左右两个较小无序区:R1.I-1和RI+1.H,且左边的无序子区中数据元素均小于等于基准元素,右边的无序子区中数据元素均大于等于基准元素,而基准X则位于最终排序的位置上,即R1.I-1X.KeyRI+1.H(1IH),当R1.I-1和RI+1.H均非空时,分别对它们进行上述的划分过程,至所有无

22、序子区中数据元素均已排序为止。2)排序过程:【示例】:A初始关键字 49 38 65 97 76 13 27 49第一次交换后27 38 65 97 76 13 49 49第二次交换后27 38 49 97 76 13 65 49J向左扫描,位置不变,第三次交换后 27 38 13 97 76 49 65 49I向右扫描,位置不变,第四次交换后 27 38 13 49 76 97 65 49J向左扫描 27 38 13 49 76 97 65 49(一次划分过程) B 初始关键字 49 38 65 97 76 13 27 49一趟排序之后27 38 13 49 76 97 65 49二趟排序之

23、后13 27 38 49 49 6576 97三趟排序之后 13 27 38 49 49 6576 97最后的排序结果 13 27 38 49 49 65 76 973)分析:快速排序是通过比较关键码、交换记录,以某个记录为界(该记录称为支点),将待排序列分成两部分。其中,一部分所有记录的关键码大于等于支点记录的关键码,另一部分所有记录的关键码小于支点记录的关键码。我们将待排序列按关键码以支点记录分成两部分的过程,称为一次划分。对各部分不断划分,直到整个序列按关键码有序。4)【算法】void QSort(S_TBL *tbl,int low,int high) /*递归形式的快排序*/ /*对

24、顺序表tbl中的子序列tbl->lowhigh作快排序*/ if(low<high) pivotloc=partition(tbl,low,high); /*将表一分为二*/ QSort(tbl,low,pivotloc-1); /*对低子表递归排序*/ QSort(tbl,pivotloc+1,high); /*对高子表递归排序*/5)【效率分析】空间效率:快速排序是递归的,每层递归调用时的指针和参数均要用栈来存放,递归调用层次数与上述二叉树的深度一致。因而,存储开销在理想情况下为O(log2n),即树的高度;在最坏情况下,即二叉树是一个单链,为O(n)。时间效率:在n个记录的待

25、排序列中,一次划分需要约n次关键码比较,时效为O(n),若设T(n)为对n个记录的待排序列进行快速排序所需时间。理想情况下:每次划分,正好将分成两个等长的子序列,则T(n)cn+2T(n/2) c是一个常数cn+2(cn/2+2T(n/4)=2cn+4T(n/4)2cn+4(cn/4+T(n/8)=3cn+8T(n/8) ······cnlog2n+nT(1)=O(nlog2n)最坏情况下:即每次划分,只得到一个子序列,时效为O(n2)。6)总结:快速排序是通常被认为在同数量级(O(nlog2n))的排序方法中平均性能最好的。但若初始

26、序列按关键码有序或基本有序时,快排序反而蜕化为冒泡排序。为改进之,通常以“三者取中法”来选取支点记录,即将排序区间的两个端点与中点三个记录关键码居中的调整为支点记录。快速排序是一个不稳定的排序方法。五、堆排序(Heap Sort)1)基本思想:堆排序是一树形选择排序,在排序过程中,将R1.N看成是一颗完全二叉树的顺序存储结构,利用完全二叉树中双亲结点和孩子结点之间的内在关系来选择最小的元素。2)堆的定义: N个元素序列K1,K2,K3,.,Kn.称为堆,当且仅当该序列满足特性: KiK2i Ki K2i+1(1 I N/2)堆实质上是:满足如下性质的完全二叉树:树中任一非叶子结点的关键字均大于

27、等于其孩子结点的关键字。例序列10,15,56,25,30,70就是一个堆,它对应的完全二叉树如上图。这种堆中根结点(称为堆顶)的关键字最小,我们把它称为小根堆。反之,若完全二叉树中任一非叶子结点的关键字均大于等于其孩子的关键字,则称之为大根堆。3)排序过程:堆排序正是利用小根堆(或大根堆)来选取当前无序区中关键字小(或最大)的记录实现排序的。我们不妨利用大根堆来排序。每一趟排序的基本操作是:将当前无序区调整为一个大根堆,选取关键字最大的堆顶记录,将它和无序区中的最后一个记录交换。这样,正好和直接选择排序相反,有序区是在原记录区的尾部形成并逐步向前扩大到整个记录区。4)堆排序【示例】:对关键字

28、序列42,13,91,23,24,16,05,88建堆 void sift(e, n, s) int e;int n; int s; int t, k, j; t=es; k=s; j=2*k+1;while(j<n) if (j<n-1&&ej<ej+1) j+; if(t<ej) ek=ej; k=j; j=2*k+1; else break; ek=t; void heapsorp (int e, int n)int i, k, t; for(i=n/2-1; i>=0; i-) sift(e, n, i); for(k=n-1; k>

29、=1; k-) t=e0; e0=ek; ek=t; sift(e, k, 0); 六、几种排序算法的比较和选择1)选取排序方法需要考虑的因素:(1) 待排序的元素数目n;(2) 元素本身信息量的大小;(3) 关键字的结构及其分布情况;(4) 语言工具的条件,辅助空间的大小等。2) 小结:(1) 若n较小(n <= 50),则可以采用直接插入排序或直接选择排序。由于直接插入排序所需的记录移动操作较直接选择排序多,因而当记录本身信息量较大时,用直接选择排序较好。(2) 若文件的初始状态已按关键字基本有序,则选用直接插入或冒泡排序为宜。(3) 若n较大,则应采用时间复杂度为O(nlog2n)

30、的排序方法:快速排序、堆排序或归并排序。 快速排序是目前基于比较的内部排序法中被认为是最好的方法。(4) 在基于比较排序方法中,每次比较两个关键字的大小之后,仅仅出现两种可能的转移,因此可以用一棵二叉树来描述比较判定过程,由此可以证明:当文件的n个关键字随机分布时,任何借助于"比较"的排序算法,至少需要O(nlog2n)的时间。(5) 当记录本身信息量较大时,为避免耗费大量时间移动记录,可以用链表作为存储结构。七.比较以上各种内部排序方法: 1)首先,从时间性能上说:按平均的时间性能来分,有三类排序方法: a.时间复杂度为O(nlogn)的方法有:快速排序、堆排序和归并排序

31、,其中以快速排序为最好; b.时间复杂度为O(n2)的有:直接插入排序、起泡排序和简单选择排序,其中以直接插入为最好,特别是对那些对关键字近似有序的记录序列尤为如此; c.时间复杂度为O(n):的排序方法只有基数排序。 2)当待排记录序列按关键字顺序有序时:直接插入排序和起泡排序能达到O(n)的时间复杂度;而对于快速排序而言,这是最不好的情况,此时的时间性能蜕化为O(n2),因此是应该尽量避免的情况。 3) 简单选择排序、堆排序和归并排序的时间性能不随记录序列中关键字的分布而改变。第三章 动态规划动态规划算法的基本要素一. 动态规划法概念:将问题分解成多级或许多子问题,然后顺序求解子问题,前一

32、个子问题的解为后一个子问题的求解提供有用的信息。掌握设计动态规划算法的步骤矩阵连乘问题最长公共子序列最大子段和流水作业调度背包问题第四章 贪心算法一. 贪心算法的概念:从问题某一初始或推测值出发,一步步的攀登给定目标,尽可能快的去逼近更好的解,当达到某一步不能继续时终止。*贪心法是一种对某些求最优解问题的更简单、更迅速的设计方法。*(1)算法思想:从问题的某一个初始解出发逐步逼近给定的目标,以尽可能快的地求得更好的解。当达到某算法中的某一步不能再继续前进时,算法停止,得到问题的一个解。二、贪婪算法的思想:采用逐步构造最优解的方法。在每个阶段都作出一个看上去最优的决策(在一定的标准下)。决策一旦

33、作出,就不可以再修改。作出贪婪决策的依据-贪婪准则。依据不同的贪婪准则,往往会得到不同的问题解决方案。例:货船装箱问题:有n个集装箱需要装船,集装箱的重量W=w1 ,w2, wn,价值P=p1,p2,pn。船的限重C。试用贪婪方法装船,要求装船的集装箱价值最大。贪婪准则1):从剩下的货箱中选择最轻的先装船;贪婪准则2):从剩下的货箱中选择价值最大的先装船;贪婪准则3):从剩下的货箱中选择价值密度最大的先装船。问题:这些算法能否得到最优解?说明理由。例:对n=5,W=15,30,20,25,P=10,25,18,20,C1=60。按照贪婪准则1):X=1,0,1,1;按照贪婪准则2):X=0,1

34、,0,1;按照贪婪准则3):X=0,1,1,0。例:二分图覆盖问题则a,c,b,c都是B的覆盖。三.实现该算法的过程:贪心法是一种改进了的分级处理方法。它首先根据题意,选取一种量度标淮。然后将这n个输入排成这种量度标准所要求的顺序,按这种顺序一次输入一个量。如果这个输入和当前已构成在这种量度意义下的部分最优解加在一起不能产生一个可行解,则不把此输入加到这部分解中。要注意的是,对于一个给定的问题。往往可能有好几种量度标准。初看起来,这些量度标准似乎都是可取的。但实际上,用其中的大多数量度标准作贪心处理所得到该量度意义下的最优解并不是问题的最优解,而是次优解。尤其值得指出的是,把目标函数作为量度标

35、准所得到的解也不一定是问题的最优解。因此,选择能产生问题最优解的最优量度标准是使用贪心法的核心问题。在一般情况下,要选出最优量度标准并不是一件容易的事,不过,一旦对某问题能选择出最优量度标准。用贪心法求解则特别有四.贪心法可以用下面的抽象过程来描述。Procedure Greedy (A,n);A1n包含n个输入 begin solutionß 将解向量solution 初始化为空 for iß1 to n doxßselect (A);if feasible (solutioin ,x) then solutionß union (solution,x

36、); return (solution ) end;Greedy函数select的功能是按某种量度标准从A中选择一个输入,把它的值赋给x并从A中消去它。feasible是一个布尔函数,它判定x是否可以包含在解向量中,union将x与解向量结合并修改目标函数。过程Greedy描述了用贪心法设计算法的主要工作和基本控制路线。一旦给出一个特定的问题,就可将select、feasible和union具体化并付诸实现。对于最小化问题来说,总是先消耗最小的元素加入集合;而对于最大化问题,则反之。优点:简单、快捷;求解速度快,时间复杂性具有较低的阶。缺点:一般找不到最优解,它有一个致命的弱点:后进入解向量的

37、元素一般都有较大的消费。五.存在问题:1)不能保证求得的最后解是最佳的;在有些例子中,解是最优的。在有些例子中,解不是最优的。这一点也是我们强调的。即贪心法并不保证求得全局最优解。可看出,具体到每一步,贪心法做出的选择只是某种意义上的“局部最优选择”、最终结果一般不一定是最优的。由于我们总是从局部的最优出发,没有看到全局的情况,致使目光短浅,欲速不达。也正是由于它不再去看全局,使得这一方法成为简单、快捷的方法。对于某些问题,我们并不知道是否能用贪心法得出最优解。但一般使用贪心法会很快得到问题的“满意”解(即次优解)。如果一个问题的最优解只能用穷举法得到,那用贪心法(或其它启发式方法)去寻找问题

38、的次优解就是唯一可行的方法了。2)只能求满足某些约束条件的可行解的范围。六.具体实例:例1:五个城市的售货员问题。费用矩阵和无向网络如下: 1 2 3 4 512751443241274135323 我们可以把路线费用最小这个目标落实在每前进一步的子目标上,这个子目标就是有一个城市通向所有其他未到过的城市通路中具有最小费用的弧。这条弧就是可行解的一个元素。现在我们用以下几张图来解释这个算法: 我们假设从基地城市N=1出发的路线结构。图中:用过的节点用小方块表示,尚未到达的节点用圆圈表示。 11 1 5 3 2 1 5 3 24 4 4 3 2 3 4 3 1 1 5 3 2 1 3 2 2 4

39、 1 3 1 7 1 3 2 1 从图中不难发现,最后返回基地城市1时,费用为7,这个费用时最昂贵的。这条路线的总费用为14,路线为1 2 5 3 4 1 很明显这条路线不是最佳路线。最佳路线时: 1 2 5 4 3 1总费用为10。所以登山法没有求得最佳解。我们可以看出虽然每步它都去最佳值,但没考虑后面几个点得费用,有可能后面得费用较高。根据这种情况我们对此做一些改进:从选择p(n)个不同得城市出发,分别调用函数,得到p个结果。比较这些结果,从中找出最小花费路线。例2:登山法求解背包问题背包问题,给定一个装载量为M得背包及分别重量为wi得n个物体得序列I。Xi 表示物体I的一部分,0Xi1。

40、Xi =1表示第i 个物体整个放进背包。Pi为第i个物体的价值/问应怎样选择物品的种类及数量,使背包装满且价值达到最大值。即给定M>0,Pi>0, 0in,求n元向量(X1 ,X2 ,, Xn ),使maxPiXi ( 0in );而且Xi满足:wi Xi =M ( 0in )可以采用登山法来选取物体的序列:每次从剩下的物体序列中选取Pi 为最大的物体放进背包。这样作,虽然上式增长最快,但是背包的装载量下降的很快,加入背包的Pi 的个数少了,不一定能使这个目标函数达到最大值。因此考虑目标函数的增量之外,还应考虑背包装载量的消耗的速度。根据这个想法可根据每次选取的Pi / wi 最大

41、的物体放进背包。从这个例子中不难发现在用登山法求解问题时选取什么作为最优化量度来求解显的非常的重用。如果有多个约束条件的话一定要在最优化量度当中有所体现。贪心算法的基本要素活动安排问题最优装载问题哈夫曼编码单源最短路径最小生成树 第五章 回溯法 一回溯法:从问题的某一种可能出发, 搜索从这种情况出发所能达到的所有可能,当这一条路走到"尽头"的时候,再倒回出发点,从另一个可能出发,继续搜索.这种不断"回溯 "寻找解的方法,称作"回溯法“.回溯法有"通用的解题法"之称。应用回溯法解问题时,首先应该明确问题的解空间。一个复杂问题的

42、解决往往由多部分构成,即,一个大的解决方案可以看作是由若干个小的决策组成。很多时候它们构成一个决策序列。解决一个问题的所有可能的决策序列构成该问题的解空间。解空间中满足约束条件的决策序列称为可行解。一般说来,解任何问题都有一个目标,在约束条件下使目标达优的可行解称为该问题的最优解。在解空间中,前 k项决策已经确定的所有决策序列之集称为 k定子解空间。0定子解空间即是该问题的解空间。回溯法的深度优先搜索策略用回溯法解题的算法框架装载问题批处理作业调度0-1背包问题图的m着色问题旅行售货员问题第六章 分支限界法一.分支定界法的概念:(分支与限界)对有约束条件的最优化问题所有可行解定向、适当地进行搜索。将可行解空间不断地划分为越来越小的子集(分支),并为每一个子集的解计算一个上界和下界(定界)。(1)算法的基本思想:分支定界法是对有约束条件的最优化问题的所有可行解(数目有限)空间进行搜索。该算法在具体执行时,把全部可行的解空间不断分割为越来越小的子集(称为分支),并为每个子集内的解的植计算一个下界或上界(称为定界)。再每次分支后,对凡是界限超出已知可行解值那些子集不再做进一步分支。这样,解的许多子集(即搜索树上的许多结点)就可以不予考虑了,从而缩小了搜索的范围。这一过程一直进行到找出可行解的值不大于任何子集的界限。因此这种算法一般可以求得最优解。(2)算法分析优点:可以求得最优解

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论