资源描述
单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,*,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第五章 回溯法,(backtracking),5.1,回溯法的基本思想,5.2,回溯法的算法框架,5.3,回溯法的应用,n,后问题,5.4,回溯法的应用,装载问题,第五章 回溯法,(Backtracking),回溯法,和,分支限界法,都是通过系统地搜索解空间树而求得问题解的搜索算法。,在系统地检查解空间的过程中，抛弃那些不可能导致合法解的候选解，从而使求解时间大大缩短。（与蛮干算法相区别）,回溯法,以深度优先的方式搜索解空间，而,分支限界法,以广度优先或最小耗费（最大收益）的方式搜索解空间。,5.1,回溯法的基本思想,回溯法（,backtracking,）是一种系统地搜索问题解的方法。为实现回溯，首先需要定义一个解空间（,solution space,），然后以易于搜索的方式组织解空间，最后用深度优先的方法搜索解空间，获得问题的解。,5.1,回溯法的基本思想,回溯法求解的三个步骤：,（,1,）定义一个解空间，它包含问题的解,（,2,）用易于搜索的方式组织解空间,（,3,）深度优先搜索解空间，获得问题的解。,5.1,回溯法的基本思想,（,1,）解空间,设问题的解向量为,X=(x,1,x,2,x,n,),，,x,i,的取值范围为有穷集,S,i,。把,x,i,的所有可能取值组合，称为问题的解空间。每一个组合是问题的一个可能解。,5.1,回溯法的基本思想,（,1,）解空间,例：,0/1,背包问题，,S=0,1,，当,n=3,时，,0/1,背包问题的解空间是：,(0,0,0),(0,0,1),(0,1,0),(0,1,1),(1,0,0),(1,0,1),(1,1,0),(1,1,1),当输入规模为,n,时，有,2,n,种可能的解。,5.1,回溯法的基本思想,（,1,）解空间,例：货郎担,(,旅行商,),问题，,S=1,2,n,，当,n=3,时，,S=1,2,3,，货郎担问题的解空间是：,(1,1,1),(1,1,2),(1,1,3),(1,2,1),(1,2,2),(1,2,3),(3,3,1),(3,3,2),(3,3,3),当输入规模为,n,时，它有,n,n,种可能的解。,考虑到约束方程,x,i,x,j,。因此，货郎担问题的解空间压缩为：,(1,2,3),(1,3,2),(2,1,3),(2,3,1),(3,1,2),(3,2,1),当输入规模为,n,时，它有,n!,种可能的解。,5.1,回溯法的基本思想,（,2,）状态空间树：问题解空间的树形式表示,例：,n=3, 0/1,背包问题的状态空间树。,A,B,C,D,E,F,G,N,O,L,M,J,K,H,I,1,1,1,1,1,1,1,0,0,0,0,0,0,-,子集树,解空间大小,: 2,n,5.1,回溯法的基本思想,（,2,）状态空间树：问题解空间的树形式表示,例：,n=4,旅行商问题的状态空间树。,A,B,C,D,E,F,G,N,O,L,M,J,K,H,I,1,2,P,Q,4,3,3,3,4,4,4,3,2,2,4,2,2,3,-,排列树,解空间大小,: n!,5.1,回溯法的基本思想,（,3,）状态空间树的动态搜索,可行解和最优解,:,可行解：满足约束条件的解，解空间中的一个子集,最优解：使目标函数取极值（极大或极小）的可行解，一个或少数几个,例：货郎担问题，有,n,n,种可能解。,n!,种可行解，只有一个或几个解是最优解。,例：背包问题，有,2,n,种可能解，有些是可行解，只有一个或几个是最优解。,有些问题，只要可行解，不需要最优解，例如八后问题。,5.1,回溯法的基本思想,（,3,）状态空间树的动态搜索,状态空间树的动态搜索,l_,结点（活结点）：所搜索到的结点不是叶结点，且满足约束条件和目标函数的界，其儿子结点还未全部搜索完毕，,e_,结点（扩展结点）：正在搜索其儿子结点的结点，它也是一个,l_,结点；,d_,结点（死结点）：不满足约束条件、目标函数、或其儿子结点已全部搜索完毕的结点、或者叶结点。以,d_,结点作为根的子树，可以在搜索过程中删除。,5.1,回溯法的基本思想,（,3,）状态空间树的动态搜索,例：,0/1,背包问题，,n=3,w=16,15,15,p=45,25,25,c=30,例：旅行商问题，,1,3,2,4,6,30,5,4,20,10,5.1,回溯法的基本思想,（,3,）状态空间树的动态搜索,例：回溯法搜索解空间树时，通常采用两种策略避免无效搜索。,其一，用约束函数在扩展结点出剪去不满足约束的子树；,其二，用限界函数剪去得不到最优解的子树。,这两类函数通称为剪枝函数。,5.2,回溯法的算法框架,递归回溯的一般解法：,Void,traceback(int,t),If(t,n),output(x,);,Else,for(i,=,f(n,t);i,0),if(f(n,t,)=,g(n,t,),for(i,=,f(n,t);i,n),output(x,);,Else,for(i,=0;in),output(x,);,Else,for(i,=,t;i,=,n;i,+),swap(xt,xi,);,if(constraint(t)&bound(t,) backtrack(t+1);,swap(xi,xt,);,5.3,回溯法的应用,n,后问题,例,1,（,8-,皇问题）,例,1,（,8-,皇问题）,在,88,的棋盘上放置,8,个皇后，使得这,8,个皇后不在同一行、同一列及同一斜角线上。如下图,6.1,：,Q,Q,Q,Q,Q,Q,Q,Q,1,2,3,4,5,6,7,8,1 2 3 4 5 6 7 8,（,8-,皇问题）,8,皇后问题可以表示成,8-,元组,(x,1,x,8,),其中,x,i,是放在第,i,行的皇后所在的列号。于是，解空间由,8,8,个,8-,元组组成。,约束条件：,x,i,x,j,for all i, j,|x,i,-,x,j,|,| j-i |,约束条件之一为没有两个,x,i,相同,(,即任意两个皇后不在同一列上,),。将其加入到元组的定义中，这时解空间的大小由,8,8,个元组减少到,8,！个元组。,6.3,回溯法的应用,n,后问题,n,后问题算法的实现,函数,place,用来判断皇后所处位置的正确性，,1. BOOL,place(int,x,int,k),2. ,3.,int,i;,4. for (i=1;i0) ,6.,xk, =,xk, + 1;/*,在当前列加,1,的位置开始搜索 *,/,7. while (,xk,=,n)&(!place(x,k,) /*,当前列位置是否满足条件 *,/,8.,xk, =,xk, + 1; /*,不满足条件,继续搜索下一列位置 *,/,9. if (,xk,n)sum+;output(x,),else,for(i,=1;in),if(cw,bestw,),bestw,=,cw,;,return;,if(cw+wi,n)bestp,=cp; return;,if(cw+wi,bestp,),backtrack(i+1);,int,bound(,int,i),int,cleft=,c-cw,;,int,bound=cp;,while(i,=,n&wi,=cleft),cleft-=,wi,;,bound+=,pi,;,i+;,if(i,=n),bound+=pi/,wi,*cleft;,return bound;,
展开阅读全文