算法分析_回溯法(很不错)

回溯Backtracking回溯N皇后问题跳马问题迷宫问题图的着色问题0-1背包问题装载问题批处理作业调度填数问题组合输出问题算24点问题ACM应用学习要点掌握回溯的概念掌握经典问题的回溯解决方法掌握回溯与其它方法的异同►。有许多问题，当需要找出它的解集或者要求回答什么解是满足某些约束条件的最佳解时，往往要使用回溯法►回溯法的基本做法是搜索，或是一种组织得井井有条的，能避免不必要搜索的穷举式搜索法。这种方法适用于解一些组合数相当大的问题。►回溯法在问题的解空间树中，按深度优先策略，从根结点出发搜索解空间树。算法搜索至解空间树的任意一点时，先判断该结点是否包含(而不是找到解）问题的解。如果肯定不包含，则跳过对该结点为根的子树的搜索（剪枝），逐层向其祖先结点回溯；否则，进入该子树，继续按深度优先策略搜索。回溯法回溯算法是所有搜索算法中最为基本的一种算法,是一种能避免不必要搜索的穷举式的搜索算法，其基本思想就是穷举搜索。算法思想：采用了一种“走不通就掉头”的思想。搜索时往往有多分支，按某一分支为新的出发点，继续向下探索，当所有可能情况都探索过且都无法到达目标的时候，再回退到上一个出发点，继续探索另一个可能情况，这种不断回头寻找目标的方法称为“回溯法”。回溯法回溯算法是所有搜索算法中最为基本的一种算法,是一种能避免不必要搜索的穷举式的搜索算法，其基本思想就是穷举搜索。回溯法搜索的方式主要采用深度优先搜索的方式回溯三要素：1)解空间：该空包含问题的解2)约束条件3)状态树问题的解空间•问题的解向量：回溯法希望一个问题的解能够表示成一个n元式(x1,x2,…,xn)的形式。•显约束：对分量xi的取值限定。•隐约束：为满足问题的解而对不同分量之间施加的约束。•解空间：对于问题的一个实例，解向量满足显式约束条件的所有多元组，构成了该实例的一个解空间。注意：同一个问题可以有多种表示，有些表示方法更简单，所需表示的状态空间更小（存储量少，搜索方法简单）。n=3时的0-1背包问题用完全二叉树表示的解空间生成问题状态的基本方法►扩展结点:一个正在产生儿子的结点称为扩展结点►活结点:一个自身已生成但其儿子还没有全部生成的节点称做活结点►死结点:一个所有儿子已经产生的结点称做死结点►深度优先的问题状态生成法：如果对一个扩展结点R，一旦产生了它的一个儿子C，就把C当做新的扩展结点。在完成对子树C（以C为根的子树）的穷尽搜索之后，将R重新变成扩展结点，继续生成R的下一个儿子（如果存在）►宽度优先的问题状态生成法：在一个扩展结点变成死结点之前，它一直是扩展结点►回溯法：为了避免生成那些不可能产生最佳解的问题状态，要不断地利用限界函数(boundingfunction)来处死那些实际上不可能产生所需解的活结点，以减少问题的计算量。具有限界函数的深度优先生成法称为回溯法回溯法的基本思想(1)针对所给问题，定义问题的解空间；(2)确定易于搜索的解空间结构；(3)以深度优先方式搜索解空间，并在搜索过程中用剪枝函数避免无效搜索。常用剪枝函数：用约束函数在扩展结点处剪去不满足约束的子树；用限界函数剪去得不到最优解的子树。用回溯法解题的一个显著特征是在搜索过程中动态产生问题的解空间。在任何时刻，算法只保存从根结点到当前扩展结点的路径。如果解空间树中从根结点到叶结点的最长路径的长度为h(n)，则回溯法所需的计算空间通常为O(h(n))。而显式地存储整个解空间则需要O(2h(n))或O(h(n)!)内存空间。递归回溯回溯法对解空间作深度优先搜索，因此，在一般情况下用递归方法实现回溯法。voidbacktrack(intt){if(tn)output(x);elsefor(inti=f(n,t);i=g(n,t);i++){x[t]=h(i);if(constraint(t)&&bound(t))backtrack(t+1);}}迭代回溯采用树的非递归深度优先遍历算法，可将回溯法表示为一个非递归迭代过程。voiditerativeBacktrack(){intt=1;while(t0){if(f(n,t)=g(n,t))for(inti=f(n,t);i=g(n,t);i++){x[t]=h(i);if(constraint(t)&&bound(t)){if(solution(t))output(x);elset++;}}elset--;}}在一个n*n的国际象棋棋盘上放置n个皇后，使得它们中任意2个之间都不互相“攻击”，即任意2个皇后不可在同行、同列、同斜线上。输出N，⑴求N皇后问题的一种放法；⑵求N皇后问题的所有放法分析：N=4时，右图是一组解要素一：解空间一般想法：利用二维数组，用[i,j]确定一个皇后位置！优化：利用约束条件，只需一维数组即可！x:array[1..n]ofinteger;x[i]：i表示第i行皇后x[i]表示第i行上皇后放第几列x[3,1,4,2]N皇后问题要素二：约束条件不同行：数组x的下标保证不重复不同列：x[i]x[j](i=I,j=n；ij)不同对角线：abs(x[i]-x[j])abs(i-j)要素三：状态树将搜索过程中的每个状态用树的形式表示出来！画出状态树对书写程序有很大帮助！填到第K行时，就与前1~(K-1)行都进行比较FunctionPlace(k:integer):boolean;place:=true;forj←1tok-1doif|k-j|=|x[j]-x[k]|orx[j]=x[k]thenplace:=falseN皇后问题K=0K=1**************回溯**********回溯***********K=3K=2K=4****出解后可以继续刚才的做法过程：进入新一行，该行上按顺序逐个格子尝试，直到能放为止（不冲突、不越界）算法描述：1.产生一种新放法2.冲突，继续找，直到找到不冲突----不超范围3.if不冲突thenknk+1k=n一组解4.if冲突then回溯N皇后问题回溯部份：即状态恢复，使其恢复到进入该分支前的状态，继续新的分支x[k]:=0;Dec(k);程序结束条件：一组解：设标志，找到一解后更改标志，以标志做为结束循环的条件所有解：k=0程序实现：回溯算法可用非递归和递归两种方法实现！判断约束函数FunctionPlace(k:integer):boolean;place:=true;forj←1tok-1doif|k-j|=|x[j]-x[k]|orx[j]=x[k]thenplace:=falseN皇后问题Nqueens()beginx[1]←0k←1whilek0dobeginx[k]←x[k]+1whilex[k]=nand(notplace(k))dox[k]←x[k]+1ifx[k]=nthenifk=nthensum←sum+1elsebegink←k+1x[k]←0endelsek←k-1endend非递归写法：ifk=nthenprint;flag←false算法描述：1.产生一种新放法2.冲突，继续找，直到找到不冲突----不超范围3.if不冲突thenknk+1k=n一组解4.if冲突then回溯Flag←trueWhileflagdoN皇后问题proceduretry(k:byte);vari:byte;beginfori:=1tondo{每层均有n种放法}ifplace(k)then{寻找放置皇后的位置}beginx[k]:=i;{放置皇后)ifk=nthenprint{８个皇后都放置好,输出}{若只想找一组解，halt}elsetry(k+1);{继续递归放置下一个皇后}end;end;递归写法：分析：状态恢复（回溯）在什么地方实现？N皇后问题在n×m棋盘上有一中国象棋中的马：1.马走日字；2.马只能往右走。请你找出一条可行路径，使得马可以从棋盘的左下角（1，1）走到右上角（n，m）。输入：95输出：(1,1)-(3,2)-(5,1)-(6,3)-(7,1)-(8,3)-(9,5)跳马问题分析：按题意，马每一步可以有4种走法！搜索过程：1.当马一开始位于左下角的时候，根据规则，它只有两条线路可以选择（另外两条超出棋盘的范围），我们无法预知该走哪条，故任意选择一条，到达A1。AA1A22.当到达A1点后，又有三条线路可以选择，于是再任意选择一条，到达B1。3.从B1再出发，又有两条线路可以选择，先选一条，到达C1。AA1A2B1B2B3C1C2跳马问题AA1A2B1B2B3C1C2D1D2D3E14.从C1出发，可以有三条路径，选择D1。但到了D1以后，我们无路可走且D1也不是最终目标点，因此，选择D1是错误的，我们退回C1重新选择D2。同样D2也是错误的。再回到C1选择D3。D3只可以到E1，但E1也是错误的。返回D3后，没有其他选择，说明D3也是错误的，再回到C1。此时C1不再有其他选择，故C1也是错误的，退回B1，选择C2进行尝试。AA1A2B1B2B3C2E2BD4E1F15.从C2出发，有四条路径可以选择，选择D4，从D4出发又有两条路径，选择E1错误，返回D4选择E2，从E2出发有两条路径，先选择F1错误，返回E2选择B，而B恰好是我们要到达的目标点，至此，一条路径查找成功。跳马问题①②③④从上面的分析我们可以得知：在无法确定走哪条线路的时候，任选一条线路进行尝试；为方便路径表示，对马可以走到的四个点（方向）都编上号；当从某点出发，所有可能到达的点都不能到达终点时，说明此点是一个死节点，必须回溯到上一个点，并重新选择一条新的线路进行尝试。解空间:为了描述路径，我们最直接的方法就是记录路径上所有点的坐标。优化：每一个方向上两个坐标和原位置对应关系若马所处的位置为(x,y)，则其下一步可以到达的四个位置分别是(x+1,y-2)，(x+2,y-1)，(x+2,y+1)，(x+1,y+2)。增量数组：dx=(1,2,2,1)dy=(-2,-1,1,2)方向t，下一步的位置就是(x+dx[t],y+dy[t])。xypath:array[1..m]ofinteger;其中，path[i]：表示第i个节点所走的方向跳马问题约束条件：不越界：(x+dx[i]=n)and(y+dy[i]0)and(y+dy[i]=n)状态树：0①②③④⑤⑤⑤⑥④Path[1]:=3Path[2]:=2Path[3]:=3Path[4]:=234Path[5]:=14①②③④④⑤⑤⑤⑤⑥⑥⑦⑦①②③④算法描述：1.产生一种新走法2.越界，继续用新走法，直到找到一种走法不越界----不超过4种走法3.if不越界thenknk+1k=n一组解4.if越界then回溯跳马问题Horse()beginpath[1]←0，k←1，x←1，y←1while(xm)and(yn)dobeginpath[k]←path[k]+1while(x+dx[i]=n)and(y+dy[i]0)and(y+dy[i]=n)and(path[k]=4)dopath[k]←path[k]+1ifpath[k]=4then{在4种走法中找到不越界的走法}beginx←x+dx[i]，y←y+dy[i]if(xm)and(yn)thenprintelsebegink←k+1path[k]←0endendelsepath[k]←0，k←k-1endend跳马问题（非递归）跳马问题跳马问题（递归）跳马问题proceduresearch(k:integer);//递归查找beginfori:=1to4do//依次尝试四个方向if(x+dx[i]=n)and(y+dy[i]0)and(y+dy[i]=n)then//在棋盘上beginpath[k]:=i;//记录下当前方向x:=x+dx[i];y:=y+dy[i];//修改扩展节点坐标if(x=n)and(y=m)then//是否是目标点beginoutput(k);