N皇后问题 回溯法

回溯

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(t>n)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(t>0){

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；i<>j)不同对角线：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****出解后可以继续刚才的做法过程：进入新一行，该行上按顺序逐个格子尝试，直到能放为止（不冲突、不越界）算法描述：产生一种新放法冲突，继续找，直到找到不冲突----不超范围if不冲突thenk<nk+1 k=n一组解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←1

whilek>0dobegin

x[k]←x[k]+1

whilex[k]<=nand(notplace(k))dox[k]←x[k]+1

ifx[k]<=nthenifk=nthensum←sum+1

else

begink←k+1x[k]←0

end

elsek←k-1

end

end

非递归写法：

ifk=nthenprint;flag←false算法描述：产生一种新放法冲突，继续找，直到找到不冲突----不超范围if不冲突thenk<nk+1 k=n一组解if冲突then回溯Flag←trueWhileflagdoN皇后问题proceduretry(k:byte);

vari:byte;

begin

fori:=1tondo {每层均有n种放法}

ifplace(k)then {寻找放置皇后的位置}

begin

x[k]:=i; {放置皇后)

ifk=nthenprint {８个皇后都放置好,输出} {若只想找一组解，halt}

elsetry(k+1); {继续递归放置下一个皇后}

end;

end;递归写法：分析：状态恢复（回溯）在什么地方实现？N皇后问题在n×m棋盘上有一中国象棋中的马：马走日字；马只能往右走。请你找出一条可行路径，使得马可以从棋盘的左下角（1，1）走到右上角（n，m）。输入：95输出：(1,1)->(3,2)->(5,1)->(6,3)->(7,1)->(8,3)->(9,5)跳马问题分析：按题意，马每一步可以有4种走法！搜索过程：当马一开始位于左下角的时候，根据规则，它只有两条线路可以选择（另外两条超出棋盘的范围），我们无法预知该走哪条，故任意选择一条，到达A1。AA1A2当到达A1点后，又有三条线路可以选择，于是再任意选择一条，到达B1。从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①②③④④⑤⑤⑤⑤⑥⑥⑦⑦①②③④算法描述：产生一种新走法越界，继续用新走法，直到找到一种走法不越界----不超过4种走法if不越界thenk<nk+1 k=n一组解if越界then回溯跳马问题Horse()

beginpath[1]←0，k←1，x←1，y←1

while(x<>m)and(y<>n)dobegin

path[k]←path[k]+1

while(x+dx[i]<=n)and(y+dy[i]>0)and(y+dy[i]<=n)

and (path[k]<=4)dopath[k]←path[k]+1

ifpath[k]<=4then {在4种走法中找到不越界的走法}beginx←x+dx[i]，y←y+dy[i]if(x<>m)and(y<>n)thenprint

else

begink←k+1path[k]←0

end

end

elsepath[k]←0，k←k-1

end

end

跳马问题（非递归）跳马问题跳马问题（递归）跳马问题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);halt;//是目标点，输出结果并终止程序

endelsesearch(k+1);//不是目标点，继续尝试下一步

//扩展出的点是死点，回溯

x:=x-dx[i];y:=y-dy[i];//恢复扩展节点坐标，状态恢复

end;end;Beginread(n,m);x:=1;y:=1;search(1);End.思考:1.在本例中，我们只要求输出一条可行路径，如果我们需要输出所有的可行路径，怎样改动此程序呢？<递归><非递归>2.如果我们把问题改成“在n×m的棋盘上有一骑士，开始时，骑士在点(x,y)，现在请你找出一条可行的路径，使得骑士可以不重复的走遍棋盘上的每一个点。”的话，又要如何编写此程序呢？跳马问题

设有一个N*N方格的迷宫，入口和出口分别在左上角和右上角，迷宫格子中分别放有0和1，0表示可走，1表示不能走，迷宫走的规则如图。当迷宫给出之后，找出一条从入口到出口的通路。输入：NN*N的迷宫输出：具体路径输入样例：

8输出样例：(1,1)-(2,1)-(3,1)-(2,2)-(1,3)-(2,4)-(3,3)-(4,3)-(5,2)-(6,3)-(7,3)-(8,2)-(8,1)迷宫问题xy①②③④⑤⑥⑦⑧分析：增量和方向表示

dx=(1,1,-1,-1,1,-1,0,0)dy=(-1,0,1,0,1,-1,1,-1)path:array[1..maxn*maxn]ofinteger;其中，path[i]：表示第i个节点所走的方向解空间约束条件不越界且该点可走(x>=1)and(x<=N)and(y>=1)and(y<=N)andA[x,y]=1迷宫信息用二维数组表示

A:array[1..maxn,1..maxn]of0..1;入口（1,1）；出口（n,1）状态树迷宫问题给定无向连通图G和m种不同的颜色。用这些颜色为图G的各顶点着色，每个顶点着一种颜色。是否有一种着色法使G中每条边的2个顶点着不同颜色。这个问题是图的m可着色判定问题。若一个图最少需要m种颜色才能使图中每条边连接的2个顶点着不同颜色，则称这个数m为该图的色数。求一个图的色数m的问题称为图的m可着色优化问题。图的着色问题

有形如下列图形的地图，图中每一块区域代表一个省份，现请你用红（1）、兰（2）、黄（3）、绿（4）四种颜色给这些省份填上颜色，要求每一省份用一种颜色，且任意两个相邻省份的颜色不能相同，请给出一种符合条件的填色方案。1234567图的存储R:array[1..n,1..n]of0..1;其中，R[I,j]=0------省i和省j不相邻

=1------省i和省j相邻①②③④⑤⑥⑦将实际地图用无向图的形式给出，每个省份代表图上的一个顶点，边代表两个省份是相邻的。四色问题图的着色问题解向量：(x1,x2,…,xn)表示顶点i所着颜色x[i]

可行性约束函数：顶点i与已着色的相邻顶点颜色不重复。voidColor::Backtrack(intt){if(t>n){sum++;for(inti=1;i<=n;i++)cout<<x[i]<<'';cout<<endl;}elsefor(inti=1;i<=m;i++){x[t]=i;if(Ok(t))Backtrack(t+1);}}boolColor::Ok(intk){//检查颜色可用性

for(intj=1;j<=n;j++)if((a[k][j]==1)&&(x[j]==x[k]))returnfalse;returntrue;}图的着色问题1234567算法思想：从编号1的省开始，按4种颜色的排列顺序，首先选择第一种颜色，然后检查是否矛盾，即相邻的区域中是否已有该颜色，若不矛盾，则涂色，若矛盾，则选择下一个颜色，再判断，当4种颜色都不可能时，则需回溯。当第一个省的颜色确定之后，依次对第二个省、第三个省……进行处理，当所有省都涂上颜色之后，得到一种解法。color:array[1..maxn]ofinteger;其中，color[k]：表示第k个省所填的颜色解空间Color(1,2,1,3,1,3,4)迷宫问题Functionpd(k:integer):boolean;Varm:integer;Beginm:=1;{从第一个省份开始检查是否冲突}pd:=true;{不冲突}

while(m<k)and(color[k]*g[m,k]<>color[m])doinc(m);ifk>=mthenpd:=false;{冲突}End;约束条件该点k涂的颜色(color[k)与和k相邻的点m(1<=m<=k-1)的颜色(color[m])相同

color[k]*g[m,k]=color[m]状态树迷宫问题proceduresearch(k:integer);{递归搜索第m个省份}beginifk>nthen {是否所有省份都已经填色}beginwrite(color[1]);{已全部填色，输出结果，终止程序}forj:=2tondowrite('',color[j]);writeln;haltendelse {还未全部填色}forj:=1to4dobegin{依次用四种颜色对当前省份填色}if(k<=n)andpd(k)then {没有冲突}begincolor[k]:=j; {记录当前省份颜色}search(k+1); {递归检查下一个省份}end;end;end;四色问题（递归）迷宫问题输入：第一行一个整数，为背包的容量M；第二行一个整数，为物品的种数Ｎ；第三行Ｎ个整数为各物品的重量；第四行Ｎ个整数分别为Ｎ个物品的价值输出：第一行为最大总价值；第二行为装入的各物品的重量（未装的物品用０）；第三行为装入的各物品的价值（未装的物品用０）

已知一个容量大小为M重量的背包和N种物品，每种物品的重量为Wi。若将物品放入背包将得到Pi的效益，求怎样选取物品将得到效益最大输入样例：

50

3

102030

60100120

输出样例：

220

02030

0100120测试数据：

输入：

10

5

22654

63546

输出：

?0-1背包问题bag:array[1..maxn]of0..1;其中，bag[k]=1表示第k个物品要取

0表示第k个物品不取解空间约束条件第k个物品确定放置方法后，背包所剩重量足够放第K个物品wei-bag[k]*w[k]>=0 {wei：背包还能装的重量}Best:=0;表示最大价值当一组解产生后，得到当前总价值count，

ifcount>bestthenbest:=count利用这种方法记录最优解！如果还要记录最优时的物品取法应：ifcount>bestthenbegin best:=count; fori:=1tondoy[i]:=bag[i];状态树求最优值0-1背包问题本题可以用递归求解：本题可用方法很多！非递归写法与前几题相似，请自己写出！算法分析：

设当前有N个物品，容量为M；这些物品要么选，要么不选，我们假设选的第一个物品编号为i（1~i-1号物品不选），问题又可以转化为有N-I个物品（即第I+1~N号物品），容量为M-Wi的子问题……如此反复下去，然后在所有可行解中选一个效益最大的便可。回溯（状态恢复）后，需恢复的状态有：Bag[k]背包可装的物品重量：wei:=wei+w[k]*i已装物品的价值总和：count:=count:-c[k]*i0-1背包问题procedurework(k,wei:integer);vari,j:integer;beginfori:=1downto0doif(wei-w[k]*i>=0)thenbeginbag[k]:=i;count:=count+c[k]*i;if(k=n)and(count>best)thenbeginbest:=count;forj:=1tondoy[j]:=bag[j];end;ifk<nthenwork(k+1,wei-w[k]*i);count:=count-c[k]*i;{状态恢复}end;end;(k)(k,wei,count)work(k+1)wei:=wei+w[k]*iwork(k+1,wei-w[k])*i,count)0-1背包（递归）wei:=wei-w[k]*i0-1背包问题有一批共n个集装箱要装上2艘载重量分别为c1和c2的轮船，其中集装箱i的重量为wi，且装载问题要求确定是否有一个合理的装载方案可将这个集装箱装上这2艘轮船。如果有，找出一种装载方案。容易证明，如果一个给定装载问题有解，则采用下面的策略可得到最优装载方案。(1)首先将第一艘轮船尽可能装满；(2)将剩余的集装箱装上第二艘轮船。将第一艘轮船尽可能装满等价于选取全体集装箱的一个子集，使该子集中集装箱重量之和最接近。由此可知，装载问题等价于以下特殊的0-1背包问题。用回溯法设计解装载问题的O(2n)计算时间算法。在某些情况下该算法优于动态规划算法。装载问题解空间：子集树可行性约束函数(选择当前元素)：上界函数(不选择当前元素)：当前载重量cw+剩余集装箱的重量r当前最优载重量bestwvoidbacktrack(inti){//搜索第i层结点

if(i>n)//到达叶结点更新最优解bestx,bestw;return;r-=w[i];

if(cw+w[i]<=c){//搜索左子树

x[i]=1;cw+=w[i];

backtrack(i+1);cw-=w[i];}

if(cw+r>bestw){x[i]=0;//搜索右子树

backtrack(i+1);}r+=w[i];}装载问题给定n个作业的集合{J1,J2,…,Jn}。每个作业必须先由机器1处理，然后由机器2处理。作业Ji需要机器j的处理时间为tji。对于一个确定的作业调度，设Fji是作业i在机器j上完成处理的时间。所有作业在机器2上完成处理的时间和称为该作业调度的完成时间和。批处理作业调度问题要求对于给定的n个作业，制定最佳作业调度方案，使其完成时间和达到最小。这3个作业的6种可能的调度方案是1,2,3；1,3,2；2,1,3；2,3,1；3,1,2；3,2,1；它们所相应的完成时间和分别是19，18，20，21，19，19。易见，最佳调度方案是1,3,2，其完成时间和为18。批处理作业问题解空间：排列树voidFlowshop::Backtrack(inti){if(i>n){for(intj=1;j<=n;j++)bestx[j]=x[j];bestf=f;}elsefor(intj=i;j<=n;j++){f1+=M[x[j]][1];f2[i]=((f2[i-1]>f1)?f2[i-1]:f1)+M[x[j]][2];f+=f2[i];if(f<bestf){Swap(x[i],x[j]);Backtrack(i+1);Swap(x[i],x[j]);}f1-=M[x[j]][1];f-=f2[i];}}classFlowshop{friendFlow(int**,int,int[]);private:voidBacktrack(inti);int**M,//各作业所需的处理时间*x,//当前作业调度*bestx,//当前最优作业调度*f2,//机器2完成处理时间

f1,//机器1完成处理时间

f,//完成时间和

bestf,//当前最优值

n;//作业数};批处理作业问题【问题描述】

从整数1到10中任取9个不同的数，填入下面的9个格子中，使所有相邻（左、右、上、下）两个格子中的数的和是素数。【输出】

一行3个数，共3行。【样例】

125 438 7109【说明】

输出所有本质不同的解。（通过某个解的旋转、上下翻转、左右翻转得到的是本质相同的）填数问题【问题描述】

排列与组合是常用的数学方法，其中组合