数据结构-算法设计方法讲义

第十一章算法设计方法11.1

分治法11.2

动态规划11.3

贪心法11.4

回溯法11.5

分枝限界法11.1分治法对于一个输入规模为n的问题，用某种方法把输入分割成k个子集（1<k≤n），从而产生a个子问题，a个子问题解决后，再用某种方法组合成原来问题的解。分治法：分而治之一、排序算法中的分治法选择排序

将n个元素放在一个数组中，

先通过n-1次比较选出其中的最小元素，与第1个元素交换

再在剩下的n-1个元素中选出最小的元素，与第2个元素交换........规模为n的问题规模为1的问题规模为n-1的问题归并排序voidMSort(RcdTypeSR[],RcdType&TR1[],ints,intt){//将SR[s..t]归并排序为TR1[s..t]

if(s==t)TR1[s]=SR[s];else{m=(s+t)/2;

//将SR[s..t]平分为SR[s..m]和SR[m+1..t]

Msort(SR,TR2,s,m,);

//递归地将SR[s..m]归并为有序的TR2[s..m]

Msort(SR,TR2,m+1,t);

//递归地将SR[m+1..t]归并为有序的TR2[m+1..t]

Merge(TR2,TR1,s,m,t);

//将TR2[s..m]和TR2[m+1..t]归并到TR1[s..t]

}}//Msort快速排序从输入序列中随机的抽取一个元素a，

以a为界，把全体元素分成：S1S2S3{小于a}{等于a}{大于a}

若S1、S3排好序了，则全体元素就有序了，

而S1、S3的排序又可以用这种方法voidQsort(SqList&L,intlow,inthigh){//对依次表L中的子表L.r[low..high]作快速排序if(low<high)//长度大于1{pivotloc=Partition(L,low,high); //将L.r[low..high]一分为二Qsort(L,low,pivotloc-1);//对低子表递归排序，pivotloc是枢轴位置Qsort(L,pivotloc+1,high); //对高子表递归排序}}//Qsort想一想，在数据结构中还有哪些算法接受了分治法？二、分治法应用其他实例：折半(二分)查找线性时间选择(依次统计)给定线性序集中n个元素和一个整数k（1≤k≤n），请找出这n个元素中第k小的元素把这n个元素放在集合S中，从S中随机地选出一个元素a，以a为界，把全体元素分成：S1S2S3{小于a}{等于a}{大于a}再依据S1、S2、S3中元素个数在某个子集中找寻intselect1(intk,int*S){if(length(S)<=10){将S中的元素干脆排序；return(S中第k个最小元素);}else{从集合S中随机地抽取一个元素a；把s中的元素分成小于a、等于a、大于a的三个集合S1、S2、S3；if(length(S1)>=k)return(select1(k,S1));elseif(length(S1)+length(S2)>=k)return(a);elsereturn(select1(k-length(S1)-length(S2),S3));}}该问题的规模缩小到确定的程度就可以简洁地解决该问题可以分解为若干个规模较小的相同问题利用该问题分解出的子问题的解可以合并为该问题的解该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题分治法选用11.2动态规划动态规划方法涉及多级决策过程中的最优化问题。求解的问题分成很多级或很多个子问题（子问题往往不是相互独立的），然后按依次求解各子问题。前一子问题的解为后一子问题的求解供应了有用的信息。在求解任一子问题时，保留那些有可能达到最优的局部解，丢弃其它局部解。依次解决各子问题，最终一个子问题的解就是初始问题的解。最佳原则：不论前面的状态和策略如何，后面的最优策略只取决于前一次策略所产生的状态。定义n阶方阵序列：v0v1v2641132Floyd算法最长公共子序列给定序列X={x1,x2,…,xm}，Z={z1,z2,…,zk}，Z是X的子序列是指存在一个递增的下标序列{i1,i2,…,ik}，使得对于全部j=1,2,…,k有：zj=xij。X={A，B，C，B，D，A，B},Z={B，C，D，B},Z是序列X的子序列,递增下标序列为{2，3，5，7}问题：给定2个序列X和Y，当序列Z既是X的子序列又是Y的子序列时，称Z是序列X和Y的公共子序列。请找出X和Y的最长公共子序列。最长公共子序列的最佳原则设序列X={x1,x2,…,xm}和Y={y1,y2,…,yn}的最长公共子序列为Z={z1,z2,…,zk}，则：(1)若xm=yn，则zk=xm=yn，且Zk-1是Xm-1和Yn-1的最长公共子序列。(2)若xm≠yn且zk≠xm，则Z是Xm-1和Y的最长公共子序列。(3)若xm≠yn且zk≠yn，则Z是X和Yn-1的最长公共子序列。Xm-1={x1,x2,…,xm-1},Yn-1={y1,y2,…,yn-1}X={A，B，C，B，D，A，B}Y={B，D，C，A，B，A}Z={?}B，D，A，BB，C，A，BB，C，B，A动态规划方法的选用找出最佳原则，并刻划其结构特征递归地定义最佳解值以自底向上的方式计算出最佳解依据计算最佳解时得到的信息，构造最佳解11.3贪心法某些问题，有多个输入，一些约束条件满足约束条件的一个解称为一个可能的解最佳解是使目标函数最大/小的一个可能解贪心法也是一个多步决策法，每一步是当前看来最好的选择，构成问题的一个可能解的一部分（局部最优）并使目标函数的值变更最大其决策过程是以某些最优化量为依据的。背包问题问题：给定n种不同的物体和一个背包，物体i的总重量为wi，总价值为pi，背包的容量为M，如何装入物体，使背包的总重量不超过M而价值最大。（假设每种物体可以随意分割）形式化描述：

M>0,wi>0,pi>0,1in找一个n元向量(x1,x2,………,xn),约束条件

目标函数贪心策略1：

每次选择价值最大的物体全部装进背包

这样目标函数增加最快

当一种物体不能全部放进背包时，

选择一个适当的0<xi<1,使物体装满背包，

剩下的xi置0。

最优化量度为pi贪心策略2：

让背包尽可能的多装物体

每次选择重量最轻的物体全部装进背包

当一种物体不能全部放进背包时，

选择一个适当的0<xi<1,使物体装满背包，

剩下的xi置0。

最优化量度为wi贪心策略3：每次选择单位重量价值最大的物体全部装进背包

当一种物体不能全部放进背包时，

选择一个适当的0<xi<1,使物体装满背包，

剩下的xi置0。

最优化量度为pi/wi

贪心法不确定能产生最佳解，须要证明其能够找到最佳解赫夫曼树构造算法(1)依据给定的n个权值{W1,W2,….,Wn}构成n棵二叉树的集合F={T1,T2,….,Tn};其中每棵二叉树Ti只有一个权为Wi的根结点,左右子树均空(2)在F中选取两棵根结点权值最小的树作为左右子树，设为Ti，Tj,构造一棵新的二叉树Tk，且Ti、Tj根结点的权值之和为新的二叉树Tk的根结点的权值(3)把Ti,Tj从F中删去，把Tk插入到F中(4)重复(2),(3)直到F中只含有一棵树为止,此树即为赫夫曼树n=2,Huffman树确定是带权路径长度最短的二叉树（最优树）假设有n-1个叶结点的Huffman树是最优树设一棵Huffman树T有n个叶结点(n>=2)，并假设w0≤w1≤…≤wn-1记V是频率为w0和w1的两个字符的父结点那么w0、w1是树T中最深的结点T中结点V换为一个叶结点V′(权等于w0+w1)，得到另一棵树T′依据归纳假设，T′具有最小的外部路径长度把V′绽开为V（w0+w1），T′还原为T，则T也应当是带权路径长度最小的定理成立普里姆算法Prim设N=（V，E）为连通网用TE表示N上最小生成树边的集合(1)从V中选一顶点u0加入U，TE=(2)对全部uU，vV-U，（u，v）E,找一条代价最小的边（u0，v0）加入TE,并把v0加入U(3)重复(2)，直到U=V为止,则（V，TE）为N的最小生成树11.4回溯法回溯法是一种避开不必要搜寻的穷举式搜寻方法，适用于解一些组合数相当大的问题。解能用一个n元式(x1,x2,….,xn)来表示（解向量）其中xiSi，要求解向量满足判定函数B(x1,x2,….,xn)或使判定函数B(x1,x2,….,xn)的值极大或微小回溯法在问题的解空间树中，按深度优先策略，从根结点动身搜寻解空间树。算法搜寻至解空间树的随意一点时，先推断该结点是否包含问题的解。假如确定不包含，则跳过对子树的搜寻，逐层向其祖先结点回溯；否则，进入该子树，接着按深度优先策略搜寻。每个n元组的子组（对应部分解）(x1,x2,….,xi)应满足确定的约束条件。若已有满足约束条件的部分解，添加xi+1Si+1，检查(x1,x2,….,xi,xi+1)是否满足约束条件，若满足接着添加xi+2Si+2，若全部xi+1Si+1都不满足约束条件，就去掉xi，回溯到(x1,x2,….,xi-1)，再添加尚未考虑过的xi，如此反复，直到找到一个解或全部解为止。4243444546474849505152535455565758596061626364656181920212223242526272829303132333435363738394041789101112131415161723451x1=1x1=2x1=3x1=4x2=234444444443333333x3=3x4=422222222211111111133333344444111111222224皇后问题的解空间扩展结点:一个正在产生儿子的结点称为扩展结点活结点:一个自身已生成但其儿子还没有全部生成的节点称做活结点死结点:一个全部儿子已经产生的结点称做死结点深度优先的问题状态生成法：假如对一个扩展结点R，一旦产生了它的一个儿子C，就把C当做新的扩展结点。在完成对子树C（以C为根的子树）的穷尽搜寻之后，将R重新变成扩展结点，接着生成R的下一个儿子（假如存在）宽度优先的问题状态生成法：在一个扩展结点变成死结点之前，它始终是扩展结点回溯法：为了避开生成那些不行能产生最佳解的问题状态，要不断地利用限界函数(boundingfunction)来处死那些事实上不行能产生所需解的活结点，以削减问题的计算量。具有限界函数