回溯算法原理和几个常用的算法实例.doc

回溯算法思想： 回溯（backtracking）是一种系统地搜索问题解答的方法。为了实现回溯，首先需要为问题定义一个解空间（solution space），这个空间必须至少包含问题的一个解（可能是最优的）。 下一步是组织解空间以便它能被容易地搜索。典型的组织方法是图(迷宫问题)或树(N皇后问题)。 一旦定义了解空间的组织方法，这个空间即可按深度优先的方法从开始节点进行搜索。回溯方法的步骤如下： 1) 定义一个解空间，它包含问题的解。2) 用适于搜索的方式组织该空间。 3) 用深度优先法搜索该空间，利用限界函数避免移动到不可能产生解的子空间。回溯算法的一个有趣的特性是在搜索执行的同时产生解空间。在搜索期间的任何时刻，仅保留从开始节点到当前节点的路径。因此，回溯算法的空间需求为O（从开始节点起最长路径的长度）。这个特性非常重要，因为解空间的大小通常是最长路径长度的指数或阶乘。所以如果要存储全部解空间的话，再多的空间也不够用。算法应用：回溯算法的求解过程实质上是一个先序遍历一棵状态树的过程,只是这棵树不是遍历前预先建立的,而是隐含在遍历过程中。(1) 幂集问题(组合问题) (参见数据结构（严蔚敏）) 求含N个元素的集合的幂集。 如对于集合A=1,2,3,则A的幂集为 p(A)=1,2,3,1,2,1,3,1,2,3,2,3,幂集的每个元素是一个集合，它或是空集，或含集合A中的一个元素，或含A中的两个元素，或者等于集合A。反之，集合A中的每一个元素，它只有两种状态：属于幂集的元素集，或不属于幂集元素集。则求幂集P（A）的元素的过程可看成是依次对集合A中元素进行“取”或“舍”的过程，并且可以用一棵状态树来表示。求幂集元素的过程即为先序遍历这棵状态树的过程。程序：#include#include#defineERROR0#defineOK1typedefintElemType;typedefstructLNodeElemTypedata;structLNode*next;LNode,*LinkList;/初始化LinkListListInit()LNode*base=(LinkList)malloc(sizeof(LNode);base-data=0;base-next=NULL;returnbase;/插入一个元素intListInsert(LinkListL,inti,ElemTypee)LNode*p,*s;intj=0;p=(LNode*)L;while(p&jnext;+j;if(!p|ji-1)returnERROR;s=(LNode*)malloc(sizeof(LNode);s-data=e;s-next=p-next;p-next=s;returnOK;/删除一个结点intListDelete(LinkList&L,inti,ElemType&e)LinkListp=L,q;intj=0;while(p-next&jnext;+j;if(!(p-next)|ji-1)returnERROR;q=p-next;p-next=q-next;e=q-data;free(q);/长度intListLength(LinkListL)LinkListp=L;intj=0;if(!L)returnERROR;while(p-next)p=p-next;+j;returnj;/查找一个元素intGetElem(LinkListL,inti,ElemType&e)LNode*p=L;intj=0;while(p-next&jnext;+j;if(!p|ji)returnERROR;e=p-data;returnOK;/输出链表元素voidDisplay(LinkListL)LNode*p=L;if(!(p-next)printf(NULL,);return;elsep=p-next;while(p)printf(%d,p-data);p=p-next;/求幂集voidPowerSet(inti,LinkListA,LinkList&B)intk=0;ElemTypee=0;if(iListLength(A)Display(B);printf(n);elseGetElem(A,i,e);k=ListLength(B);ListInsert(B,k+1,e);PowerSet(i+1,A,B);ListDelete(B,k+1,e);PowerSet(i+1,A,B);intmain()LinkListlist=ListInit();/初始化LinkListlist2=ListInit();/初始化ListInsert(list,1,1);/插入元素ListInsert(list,2,2);ListInsert(list,3,3);Display(list);/输出元素printf(npowersetis:n);PowerSet(1,list,list2);/求幂集(2)迷宫问题(参见数据结构（严蔚敏）)计算机解迷宫时，通常用的是试探和回溯的方法，即从入口出发，顺某一方向向前探索，若能走通，则继续往前走；否则沿原路退回，换一个方向再继续探索，直至所有可能的通路都探索到为止,如果所有可能的通路都试探过，还是不能走到终点，那就说明该迷宫不存在从起点到终点的通道。1从入口进入迷宫之后，不管在迷宫的哪一个位置上，都是先往东走，如果走得通就继续往东走，如果在某个位置上往东走不通的话，就依次试探往南、往西和往北方向，从一个走得通的方向继续往前直到出口为止；2如果在某个位置上四个方向都走不通的话，就退回到前一个位置，换一个方向再试，如果这个位置已经没有方向可试了就再退一步，如果所有已经走过的位置的四个方向都试探过了，一直退到起始点都没有走通，那就说明这个迷宫根本不通； 3所谓走不通不单是指遇到墙挡路，还有已经走过的路不能重复走第二次，它包括曾经走过而没有走通的路。显然为了保证在任何位置上都能沿原路退回，需要用一个后进先出的结构即栈来保存从入口到当前位置的路径。并且在走出出口之后，栈中保存的正是一条从入口到出口的路径。由此，求迷宫中一条路径的算法的基本思想是： 若当前位置可通，则纳入当前路径，并继续朝下一位置探索；若当前位置不可通，则应顺着来的方向退回到前一通道块，然后朝着除来向之外的其他方向继续探索；若该通道块的四周四个方块均不可通，则应从当前路径上删除该通道块。 设定当前位置的初值为入口位置； do 若当前位置可通， 则将当前位置插入栈顶； / 纳入路径 若该位置是出口位置，则算法结束； / 此时栈中存放的是一条从入口位置到出口位置的路径否则切换当前位置的东邻方块为新的当前位置； 否则 若栈不空且栈顶位置尚有其他方向未被探索， 则设定新的当前位置为: 沿顺时针方向旋转找到的栈顶位置的下一相邻块；若栈不空但栈顶位置的四周均不可通， 则 删去栈顶位置； / 从路径中删去该通道块若栈不空，则重新测试新的栈顶位置， 直至找到一个可通的相邻块或出栈至栈空； while (栈不空)；程序如下:#include#defineWALL0/墙#defineCORRIDOR1/通道#definePATH9/为路径上的一块#defineTRIED2/#defineROW_NUM7/迷宫数组行数#defineCOL_NUM13/列数#defineTRUE1#defineFALSE0#defineMAXSIZE50typedefstructintrow;intcol;PosType;typedefstructintord;/通道块在路径上的序号PosTypeseat;/通道块在迷宫中的坐标intdi;/当前通道块的方向SElemType;typedefstructSElemTypeSMAXSIZE;inttop;MazeType;/迷宫intgridROW_NUMCOL_NUM=1,1,1,0,1,1,1,0,0,1,1,1,1,1,0,1,1,1,0,1,1,1,1,1,0,1,1,0,0,0,0,0,1,0,1,0,1,0,1,1,0,0,0,1,1,1,0,1,0,1,1,1,1,1,1,1,1,0,0,0,0,1,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1;/当前位置是否可以通过boolValid(PosTypepos)if(pos.row=0&pos.row=0&pos.col-1)/棧不空e=path.Spath.top-;while(e.di=3&path.top-1)Undo(e.seat);e=path.Spath.top-;if(e.di-1);returnFALSE;/输出路径voidPrintPath(MazeTypepath)inti=0;while(i=path.top)printf(第%d步:(%d,%d)n,path.Si.ord,path.Si.seat.row,path.Si.seat.col);i+;/输出路径voidPrintPath2()for(inti=0;iROW_NUM;i+)for(intj=0;jCOL_NUM;j+)if(gridij=PATH)printf(%d,%d)n,i,j);intmain()MazeTypepath;PosTypestart=0,0,end=6,12;if(MazePath(path,start,end)PrintPath(path);elseprintf(notreachable!n);PrintPath2();(3)N皇后问题:在一个N*N的棋盘上放置N个皇后，且使得每两个之间不能互相攻击，也就是使得每两个不在同一行，同一列和同一斜角线上。对于N1，问题的解很简单，而且我们很容易看出对于N2和N3来说，这个问题是无解的。所让我们考虑4皇后问题并用回溯法对它求解。因为每个皇后都必须分别占据行，我们需要做的不过是为图1棋盘上的每个皇后分配一列。 我们从空棋盘开始，然后把皇后1放到它所在行的第一个可能位置上，也就是第一行第列。对于皇后2，在经过第一列和第二列的失败尝试之后，我们把它放在第一个可能的位置，就是格子2，3),位于第二行第二列的格子。这被证明是一个死胡同,因为皇后：将没有位置可放。所以，该算法进行回溯，把皇后2放在下一个可能位置(2，4)上。然后皇后3就可以放在(3，2)，这被证明是另一个死胡同。该算法然后就回溯到底，把皇后1移到(1，2)。接着皇后2到(2，4)，皇后3到(3，1)，而皇后4到(4，3)，这就是该问题的一个解。图2给出了这个查找的状态空间树。程序如下：#include#include#defineN4intcolN+1;/输出结果voidOutput()for(inti=1;in)Output();elsefor(intj=1;j=n;+j)intk=1;coli=j;while(ki)if(colk-coli)*(fabs(colk-coli)-fabs(k-i)!=0)k+;if(k=i)Queen(i+1,n);elsebreak;intmain()printf(theansweris:n);for(inti=1;i=N;i+)col1=i;/设置第一行Queen(2,N);结果如下:(四)骑士周游问题/跳马问题跳马问题也称为骑士周游问题，是算法设计中的经典问题。其一般的问题描述是： 考虑国际象棋棋盘上某个位置的一只马，它是否可能只走63步，正好走过除起点外的其他63个位置各一次？如果有一种这样的走法，则称所走的这条路线为一条马的周游路线。试设计一个算法找出这样一条马的周游路线。 此题实际上是一个Hamilton回路问题,和迷宫问题很相似,可以用回溯算法来解决.考虑到马在每一个位置,最多有8种跳法,如下图所示: K7K0K6K1KK5K2K4K3可以使用N皇后问题的算法模板。算法如下：#include#include/*/*/棋盘行数constintN=8;intstepN*N=-1;/保存每一步做出的选择intchessNN=0;/棋盘/下一个方向intJump82=-2,1,-1,2,1,2,2,1,2,-1,1,-2,-1,-2,-2,-1;intp=0;/对解的个数计数/判断是否合法intcanJump(intx,inty)if(x=0&x=0&yN&chessxy=0)return1;return0;/输出结果voidOutPutChess()inti;for(i=1;i=N*N-1;+i)printf(%d,stepi);printf(n);for(i=0;iN;i+)for(intj=0;j=N*N)/if(t=37)p+;OutPutChess();/输出结果exit(1);/求得一个解时,退出程序/return;/求得所有解elsefor(inti=0;i8;+i)if(canJump(x+Jumpi0,y+Jumpi1)/求下一个结点x+=Jumpi0;y+=Jumpi1;printf(%2d,%2d),x,y);/打印当结点chessxy=t+1;stept=i;BackTrace(t+1,x,y);/递归调用/回溯chessxy=0;x-=Jumpi0;y-=Jumpi1;/*/*/intmain()intx=0;inty=0;chessxy=1;BackTrace(1,x,y);printf(AllResultsNumber=%d,p);该算法最坏的时间复杂度为O（8N*N）。这是一个相当大的数字，不能接受，但实际情况好得多。并且在37步的时候，开始发生回溯,可通过改BackTrace中的第一个if中的参数发现。据说,总的回溯次数达300多百万次.我的机子运行20分钟也没运行出结果.我们可以考虑,当N=8时,为2192,即使对于2100=1.3*1030,对于一台每秒1万亿(1012)次操作的计算机,也需要4*1010才能完成,超过了45亿年-地球的估计年龄.但是,该算法可以适当改进,考虑到:即向前看两步，当每准备跳一步时，设准备跳到(x, y)点，计算(x, y)这一点可能往几个方向跳（即向前看两步），将这个数目设为(x, y)点的权值，将所 有可能的(x, y)按权值排序，从最小的开始，循环遍历所有可能的(x, y)，回溯求出结果。算法可以求出所有可能的马跳棋盘路径，算出一个可行 的结果很快，但在要算出所有可能结果时，仍然很慢，因为最坏时间复杂度本质上并没有改变，仍为O(8(N * N),但实际情况很好,在瞬间即可得到一个解,当然,要求得所有解,也需要很长的时间.下面是实现这一思想的代码：#include#include/*/*/棋盘行数constintN=8;intstepN*N=-1;/保存每一步做出的选择intchessNN=0;/棋盘intJump82=-2,1,-1,2,1,2,2,1,2,-1,1,-2,-1,-2,-2,-1;intp=0;/对解的个数计数/判断是否合法intcanJump(intx,inty)if(x=0&x=0&yN&chessxy=0)return1;return0;/求权值intweightStep(intx,inty)intcount=0;for(inti=0;i8;+i)if(canJump(x+Jumpi0,y+Jumpi1)count+;re