还剩16页未读,继续阅读
本资源只提供10页预览,全部文档请下载后查看!喜欢就下载吧,查找使用更方便
文本内容:
(1)用计算机求解问题的步骤
1、问题分析
2、数学模型建立
3、算法设计与选择
4、算法指标
5、算法分析
6、算法实现
7、程序调试
8、结果整理文档编制
(2)算法定义算法是指在解决问题时,按照某种机械步骤一定可以得到问题结果的处理过程
(3)算法的三要素
1、操作
2、控制结构
3、数据结构算法具有以下5个属性 有穷性一个算法必须总是在执行有穷步之后结束,且每一步都在有穷时间内完成 确定性算法中每一条指令必须有确切的含义不存在二义性只有一个入口和一个出口 可行性一个算法是可行的就是算法描述的操作是可以通过已经实现的基本运算执行有限次来实现的 输入一个算法有零个或多个输入,这些输入取自于某个特定对象的集合 输出一个算法有一个或多个输出,这些输出同输入有着某些特定关系的量算法设计的质量指标 正确性算法应满足具体问题的需求; 可读性算法应该好读,以有利于读者对程序的理解; 健壮性算法应具有容错处理,当输入为非法数据时,算法应对其作出反应,而不是产生莫名其妙的输出结果 效率与存储量需求效率指的是算法执行的时间;存储量需求指算法执行过程中所需要的最大存储空间一般这两者与问题的规模有关经常采用的算法主要有迭代法、分而治之法、贪婪法、动态规划法、回溯法、分支限界法迭代法也称“辗转法”,是一种不断用变量的旧值递推出新值的解决问题的方法利用迭代算法解决问题,需要做好以下三个方面的工作
一、确定迭代模型在可以用迭代算法解决的问题中,至少存在一个直接或间接地不断由旧值递推出新值的变量,这个变量就是迭代变量
二、建立迭代关系式所谓迭代关系式,指如何从变量的前一个值推出其下一个值的公式(或关系)迭代关系式的建立是解决迭代问题的关键,通常可以使用递推或倒推的方法来完成
三、对迭代过程进行控制在什么时候结束迭代过程?这是编写迭代程序必须考虑的问题不能让迭代过程无休止地重复执行下去迭代过程的控制通常可分为两种情况一种是所需的迭代次数是个确定的值,可以计算出来;另一种是所需的迭代次数无法确定对于前一种情况,可以构建一个固定次数的循环来实现对迭代过程的控制;对于后一种情况,需要进一步分析出用来结束迭代过程的条件编写计算斐波那契(Fibonacci)数列的第n项函数fib(n) 斐波那契数列为
0、
1、
1、
2、
3、……,即 fib0=0; fib1=1; fibn=fibn-1+fibn-2(当n1时) 写成递归函数有 intfibintn {ifn==0return0; ifn==1return1; ifn1returnfibn-1+fibn-2; }一个饲养场引进一只刚出生的新品种兔子,这种兔子从出生的下一个月开始,每月新生一只兔子,新生的兔子也如此繁殖如果所有的兔子都不死去,问到第12个月时,该饲养场共有兔子多少只? 分析这是一个典型的递推问题我们不妨假设第1个月时兔子的只数为u1,第2个月时兔子的只数为u2,第3个月时兔子的只数为u3,……根据题意,“这种兔子从出生的下一个月开始,每月新生一只兔子”,则有 u1=1,u2=u1+u1×1=2,u3=u2+u2×1=4,…… 根据这个规律,可以归纳出下面的递推公式 un=un-1×2n≥2 对应un和un-1,定义两个迭代变量y和x,可将上面的递推公式转换成如下迭代关系 y=x*2 x=y 让计算机对这个迭代关系重复执行11次,就可以算出第12个月时的兔子数参考程序如下 cls x=1 fori=2to12 y=x*2 x=y nexti printy end分而治之法
1、分治法的基本思想任何一个可以用计算机求解的问题所需的计算时间都与其规模N有关问题的规模越小,越容易直接求解,解题所需的计算时间也越少例如,对于n个元素的排序问题,当n=1时,不需任何计算;n=2时,只要作一次比较即可排好序;n=3时只要作3次比较即可,…而当n较大时,问题就不那么容易处理了要想直接解决一个规模较大的问题,有时是相当困难的分治法的设计思想是,将一个难以直接解决的大问题,分割成一些规模较小的相同问题,以便各个击破,分而治之分治法所能解决的问题一般具有以下几个特征
(1)该问题的规模缩小到一定的程度就可以容易地解决;
(2)该问题可以分解为若干个规模较小的相同问题,即该问题具有最优子结构性质;
(3)利用该问题分解出的子问题的解可以合并为该问题的解;
(4)该问题所分解出的各个子问题是相互独立的,即子问题之间不包含公共的子子问题
3、分治法的基本步骤分治法在每一层递归上都有三个步骤
(1)分解将原问题分解为若干个规模较小,相互独立,与原问题形式相同的子问题;
(2)解决若子问题规模较小而容易被解决则直接解,否则递归地解各个子问题;
(3)合并将各个子问题的解合并为原问题的解快速排序在这种方法中,n个元素被分成三段(组)左段left,右段right和中段middle中段仅包含一个元素左段中各元素都小于等于中段元素,右段中各元素都大于等于中段元素因此left和right中的元素可以独立排序,并且不必对left和right的排序结果进行合并middle中的元素被称为支点pivot图14-9中给出了快速排序的伪代码 //使用快速排序方法对a[0:n-1]排序 从a[0:n-1]中选择一个元素作为middle,该元素为支点 把余下的元素分割为两段left和right,使得left中的元素都小于等于支点,而right中的元素都大于等于支点 递归地使用快速排序方法对left进行排序 递归地使用快速排序方法对right进行排序 所得结果为left+middle+right 考察元素序列
[48371562]假设选择元素6作为支点,则6位于middle;4,3,1,5,2位于left;8,7位于right当left排好序后,所得结果为1,2,3,4,5;当right排好序后,所得结果为7,8把right中的元素放在支点元素之后,left中的元素放在支点元素之前,即可得到最终的结果
[12345678] 把元素序列划分为left、middle和right可以就地进行(见程序14-6)在程序14-6中,支点总是取位置1中的元素也可以采用其他选择方式来提高排序性能,本章稍后部分将给出这样一种选择 程序14-6快速排序 templateclassT voidQuickSortT*aintn {//对a[0:n-1]进行快速排序 {//要求a[n]必需有最大关键值 quickSorta0n-1; templateclassT voidquickSortTa[]intlintr {//排序a[l:r],a[r+1]有大值 ifl=rreturn; inti=l//从左至右的游标 j=r+1;//从右到左的游标 Tpivot=a[l]; //把左侧=pivot的元素与右侧=pivot的元素进行交换 whiletrue{ do{//在左侧寻找=pivot的元素 i=i+1; }whileapivot; do{//在右侧寻找=pivot的元素 j=j-1; }whilea[j]pivot; ifi=jbreak;//未发现交换对象 Swapaa[j]; } //设置pivot a[l]=a[j]; a[j]=pivot; quickSortalj-1;//对左段排序 quickSortaj+1r;//对右段排序 }贪婪法它采用逐步构造最优解的思想,在问题求解的每一个阶段,都作出一个在一定标准下看上去最优的决策;决策一旦作出,就不可再更改制定决策的依据称为贪婪准则贪婪法是一种不追求最优解,只希望得到较为满意解的方法贪婪法一般可以快速得到满意的解,因为它省去了为找最优解要穷尽所有可能而必须耗费的大量时间贪婪法常以当前情况为基础作最优选择,而不考虑各种可能的整体情况,所以贪婪法不要回溯【问题】背包问题问题描述有不同价值、不同重量的物品n件,求从这n件物品中选取一部分物品的选择方案,使选中物品的总重量不超过指定的限制重量,但选中物品的价值之和最大#includestdio.hvoidmain{intmnijw
[50]p
[50]pl
[50]b
[50]s=0max;printf输入背包容量m物品种类n:;scanf%d%dmn;fori=1;i=n;i=i+1{printf输入物品的重量W和价值P:;scanf%d%dw[i]p[i];pl[i]=p[i];s=s+w[i];}ifs=m{printfwholechoose\n;//return;}fori=1;i=n;i=i+1{max=1;forj=2;j=n;j=j+1ifpl[j]/w[j]pl[max]/w[max]max=j;pl[max]=0;b[i]=max;}fori=1s=0;smi=n;i=i+1s=s+w[b[i]];ifs!=mw[b[i-1]]=m-w[b[i-1]];forj=1;j=i-1;j=j+1printfchooseweight%d\nw[b[j]];}动态规划的基本思想前文主要介绍了动态规划的一些理论依据,我们将前文所说的具有明显的阶段划分和状态转移方程的动态规划称为标准动态规划,这种标准动态规划是在研究多阶段决策问题时推导出来的,具有严格的数学形式,适合用于理论上的分析在实际应用中,许多问题的阶段划分并不明显,这时如果刻意地划分阶段法反而麻烦一般来说,只要该问题可以划分成规模更小的子问题,并且原问题的最优解中包含了子问题的最优解(即满足最优子化原理),则可以考虑用动态规划解决动态规划的实质是分治思想和解决冗余,因此,动态规划是一种将问题实例分解为更小的、相似的子问题,并存储子问题的解而避免计算重复的子问题,以解决最优化问题的算法策略由此可知,动态规划法与分治法和贪心法类似,它们都是将问题实例归纳为更小的、相似的子问题,并通过求解子问题产生一个全局最优解贪心法的当前选择可能要依赖已经作出的所有选择,但不依赖于有待于做出的选择和子问题因此贪心法自顶向下,一步一步地作出贪心选择;而分治法中的各个子问题是独立的(即不包含公共的子问题),因此一旦递归地求出各子问题的解后,便可自下而上地将子问题的解合并成问题的解不足之处如果当前选择可能要依赖子问题的解时,则难以通过局部的贪心策略达到全局最优解;如果各子问题是不独立的,则分治法要做许多不必要的工作,重复地解公共的子问题解决上述问题的办法是利用动态规划该方法主要应用于最优化问题,这类问题会有多种可能的解,每个解都有一个值,而动态规划找出其中最优(最大或最小)值的解若存在若干个取最优值的解的话,它只取其中的一个在求解过程中,该方法也是通过求解局部子问题的解达到全局最优解,但与分治法和贪心法不同的是,动态规划允许这些子问题不独立,(亦即各子问题可包含公共的子问题)也允许其通过自身子问题的解作出选择,该方法对每一个子问题只解一次,并将结果保存起来,避免每次碰到时都要重复计算因此,动态规划法所针对的问题有一个显著的特征,即它所对应的子问题树中的子问题呈现大量的重复动态规划法的关键就在于,对于重复出现的子问题,只在第一次遇到时加以求解,并把答案保存起来,让以后再遇到时直接引用,不必重新求解
3、动态规划算法的基本步骤设计一个标准的动态规划算法,通常可按以下几个步骤进行
(1)划分阶段按照问题的时间或空间特征,把问题分为若干个阶段注意这若干个阶段一定要是有序的或者是可排序的(即无后向性),否则问题就无法用动态规划求解
(2)选择状态将问题发展到各个阶段时所处于的各种客观情况用不同的状态表示出来当然,状态的选择要满足无后效性
(3)确定决策并写出状态转移方程之所以把这两步放在一起,是因为决策和状态转移有着天然的联系,状态转移就是根据上一阶段的状态和决策来导出本阶段的状态所以,如果我们确定了决策,状态转移方程也就写出来了但事实上,我们常常是反过来做,根据相邻两段的各状态之间的关系来确定决策
(4)写出规划方程(包括边界条件)动态规划的基本方程是规划方程的通用形式化表达式一般说来,只要阶段、状态、决策和状态转移确定了,这一步还是比较简单的动态规划的主要难点在于理论上的设计,一旦设计完成,实现部分就会非常简单根据动态规划的基本方程可以直接递归计算最优值,但是一般将其改为递推计算,实现的大体上的框架如下标准动态规划的基本框架
1. 对fn+1xn+1初始化; {边界条件}fork:=ndownto1dofor每一个xk∈Xkdofor每一个uk∈Ukxkdobeginfkxk:=一个极值; {∞或-∞}xk+1:=Tkxkuk; {状态转移方程}t:=φfk+1xk+1vkxkuk; {基本方程9式}if t比fkxk更优thenfkxk:=t;{计算fkxk的最优值}end;t:=一个极值; {∞或-∞}for每一个x1∈X1doiff1x1比t更优thent:=f1x1; {按照10式求出最优指标}输出t;但是,实际应用当中经常不显式地按照上面步骤设计动态规划,而是按以下几个步骤进行
(1)分析最优解的性质,并刻划其结构特征
(2)递归地定义最优值
(3)以自底向上的方式或自顶向下的记忆化方法(备忘录法)计算出最优值
(4)根据计算最优值时得到的信息,构造一个最优解步骤
(1)~
(3)是动态规划算法的基本步骤在只需要求出最优值的情形,步骤
(4)可以省略,若需要求出问题的一个最优解,则必须执行步骤
(4)此时,在步骤
(3)中计算最优值时,通常需记录更多的信息,以便在步骤
(4)中,根据所记录的信息,快速地构造出一个最优解总结动态规划实际上就是最优化的问题,是指将原问题的大实例等价于同一最优化问题的较小实例,自底向上的求解最小实例,并将所求解存放起来,存放的结果就是为了准备数据与递归相比,递归是不断的调用子程序求解,是自顶向下的调用和求解回溯法 回溯法也称为试探法,该方法首先暂时放弃关于问题规模大小的限制,并将问题的候选解按某种顺序逐一枚举和检验当发现当前候选解不可能是解时,就选择下一个候选解;倘若当前候选解除了还不满足问题规模要求外,满足所有其他要求时,继续扩大当前候选解的规模,并继续试探如果当前候选解满足包括问题规模在内的所有要求时,该候选解就是问题的一个解在回溯法中,放弃当前候选解,寻找下一个候选解的过程称为回溯扩大当前候选解的规模,以继续试探的过程称为向前试探
1、回溯法的一般描述可用回溯法求解的问题P,通常要能表达为对于已知的由n元组(x1,x2,…,xn)组成的一个状态空间E={(x1,x2,…,xn)∣xi∈Si,i=1,2,…,n},给定关于n元组中的一个分量的一个约束集D,要求E中满足D的全部约束条件的所有n元组其中Si是分量xi的定义域,且|Si|有限,i=1,2,…,n我们称E中满足D的全部约束条件的任一n元组为问题P的一个解解问题P的最朴素的方法就是枚举法,即对E中的所有n元组逐一地检测其是否满足D的全部约束,若满足,则为问题P的一个解但显然,其计算量是相当大的我们发现,对于许多问题,所给定的约束集D具有完备性,即i元组(x1,x2,…,xi)满足D中仅涉及到x1,x2,…,xi的所有约束意味着j(ji)元组(x1,x2,…,xj)一定也满足D中仅涉及到x1,x2,…,xj的所有约束,i=1,2,…,n换句话说,只要存在0≤j≤n-1,使得(x1,x2,…,xj)违反D中仅涉及到x1,x2,…,xj的约束之一,则以(x1,x2,…,xj)为前缀的任何n元组(x1,x2,…,xj,xj+1,…,xn)一定也违反D中仅涉及到x1,x2,…,xi的一个约束,n≥ij因此,对于约束集D具有完备性的问题P,一旦检测断定某个j元组(x1,x2,…,xj)违反D中仅涉及x1,x2,…,xj的一个约束,就可以肯定,以(x1,x2,…,xj)为前缀的任何n元组(x1,x2,…,xj,xj+1,…,xn)都不会是问题P的解,因而就不必去搜索它们、检测它们回溯法正是针对这类问题,利用这类问题的上述性质而提出来的比枚举法效率更高的算法回溯法首先将问题P的n元组的状态空间E表示成一棵高为n的带权有序树T,把在E中求问题P的所有解转化为在T中搜索问题P的所有解树T类似于检索树,它可以这样构造 设Si中的元素可排成xi1,xi2,…,ximi-1,|Si|=mi,i=1,2,…,n从根开始,让T的第I层的每一个结点都有mi个儿子这mi个儿子到它们的双亲的边,按从左到右的次序,分别带权xi+11,xi+12,…,xi+1mi,i=0,1,2,…,n-1照这种构造方式,E中的一个n元组(x1,x2,…,xn)对应于T中的一个叶子结点,T的根到这个叶子结点的路径上依次的n条边的权分别为x1,x2,…,xn,反之亦然另外,对于任意的0≤i≤n-1,E中n元组(x1,x2,…,xn)的一个前缀I元组(x1,x2,…,xi)对应于T中的一个非叶子结点,T的根到这个非叶子结点的路径上依次的I条边的权分别为x1,x2,…,xi,反之亦然特别,E中的任意一个n元组的空前缀(),对应于T的根 因而,在E中寻找问题P的一个解等价于在T中搜索一个叶子结点,要求从T的根到该叶子结点的路径上依次的n条边相应带的n个权x1,x2,…,xn满足约束集D的全部约束在T中搜索所要求的叶子结点,很自然的一种方式是从根出发,按深度优先的策略逐步深入,即依次搜索满足约束条件的前缀1元组(x1i)、前缀2元组(x1,x2)、…,前缀I元组(x1,x2,…,xi),…,直到i=n为止 在回溯法中,上述引入的树被称为问题P的状态空间树;树T上任意一个结点被称为问题P的状态结点;树T上的任意一个叶子结点被称为问题P的一个解状态结点;树T上满足约束集D的全部约束的任意一个叶子结点被称为问题P的一个回答状态结点,它对应于问题P的一个解分支定界法分支限界法这是一种用于求解组合优化问题的排除非解的搜索算法类似于回溯法,分枝定界法在搜索解空间时,也经常使用树形结构来组织解空间然而与回溯法不同的是,回溯算法使用深度优先方法搜索树结构,而分枝定界一般用宽度优先或最小耗费方法来搜索这些树因此,可以很容易比较回溯法与分枝定界法的异同相对而言,分枝定界算法的解空间比回溯法大得多,因此当内存容量有限时,回溯法成功的可能性更大算法思想分枝定界(branchandbound)是另一种系统地搜索解空间的方法,它与回溯法的主要区别在于对E-节点的扩充方式每个活节点有且仅有一次机会变成E-节点当一个节点变为E-节点时,则生成从该节点移动一步即可到达的所有新节点在生成的节点中,抛弃那些不可能导出(最优)可行解的节点,其余节点加入活节点表,然后从表中选择一个节点作为下一个E-节点从活节点表中取出所选择的节点并进行扩充,直到找到解或活动表为空,扩充过程才结束有两种常用的方法可用来选择下一个E-节点(虽然也可能存在其他的方法)1先进先出(FIFO)即从活节点表中取出节点的顺序与加入节点的顺序相同,因此活节点表的性质与队列相同2最小耗费或最大收益法在这种模式中,每个节点都有一个对应的耗费或收益如果查找一个具有最小耗费的解,则活节点表可用最小堆来建立,下一个E-节点就是具有最小耗费的活节点;如果希望搜索一个具有最大收益的解,则可用最大堆来构造活节点表,下一个E-节点是具有最大收益的活节点。