回溯算法(含代码).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#d