回溯算法入门及应用.doc

回溯算法入门及应用 广东省东莞市东华高级中学 杨光文 难易指数:在求解一些问题（如马的遍历、选书、八皇后问题、自然数的拆分等问题）时，题目的要求可能是求出原问题的一种或所有可能的解决方案。这类问题的解往往是由一个一个的步骤或状态所构成的，每一步骤又有若干种可能的决策方案；由于没有固定、明确的数学解析方法，往往要采用搜索的做法，即从某一个初始状态出发，不断地向前（即下一个状态）搜索，以期最终达到目标状态，从而得到原问题的一个解或所有的解。在搜索的过程中，由于问题本身及所采取的搜索方法的特点（如在缺乏全局及足够的前瞻信息的情况下进行搜索等），会导致走到某一状态就走不下去的情况，这时，就必须回头（即回到上一步，而不是回到最初的状态），再尝试其他的可能性，换一个方向或方法再试试。这样，不断地向前探索、回溯，再向前、再回溯，直至最终得出问题的解，或者一路回溯到出发点（出现这种情况即表示原问题无解）。注意，这种搜索过程并不是尝试搜索问题解空间中所有的可能状态和路径，而是采用深度优先的方式，沿着一条路径，尽可能深入地向前探索，这就是回溯算法。一、回溯算法的定义：回溯算法也叫试探法，它是一种系统地搜索问题的解的方法。回溯算法的基本思想是：从一条路往前走，能进则进，不能进则退回来，换一条路再试。用回溯算法解决问题的一般步骤为： 1、定义一个解空间，它包含问题的解。 2、利用适于搜索的方法组织解空间。 3、利用深度优先法搜索解空间。 4、利用限界函数避免移动到不可能产生解的子空间。 问题的解空间通常是在搜索问题的解的过程中动态产生的，这是回溯算法的一个重要特性。下面通过一个具体实例加深大家对回溯算法的认识。 二、回溯算法的应用举例：例1：马的遍历中国象棋半张棋盘如图1(a)所示。马自左下角往向右上角跳。规定只许往右跳，不许往左跳，马只能走日字。比如图1(a)所示为一种跳行路线，并将所经路线打印出来，打印格式为：0,0-2,1-3,3-1,4-3,5-2,7-4,8。找出所有路径。【算法分析】如图1（b）,马最多有四个方向，若原来的横坐标为j、纵坐标为i,则四个方向的移动可表示为：1: （i,j）（i+2,j+1）； (i3,j8)2: （i,j）（i+1,j+2）； (i4,j0,j1,j); writeln(4,8,t:5); end;procedure try(i:integer); 搜索 var j:integer; begin a1,1:=0;a1,2:=0; for j:=1 to 4 do if (ai-1,1+xj,1=0) and (ai-1,1+xj,1=0) and (ai-1,2+xj,20) then begin flag:=flag+j;booki:=j; if i=5 then print else try(i+1); flag:=flag-j;booki:=0; end; end;begin flag:=; c:=0; try(1); readlnend.例3：八皇后问题【问题描述】在一个的棋盘里放置个皇后，要求每个皇后两两之间不相冲（在每一横列竖列斜列只有一个皇后）。【问题分析】这道题可以用回溯算法来做，分别一一测试每一种摆法，直到得出正确的答案。主要解决以下几个问题：1、冲突。包括行、列、两条对角线：（1）列：规定每一列放一个皇后，不会造成列上的冲突；（2）行：当第I行被某个皇后占领后，则同一行上的所有空格都不能再放皇后，要把以I为下标的标记置为被占领状态；（3）对角线：对角线有两个方向。在同一对角线上的所有点（设下标为(i,j)），要么(i+j)是常数，要么(i-j)是常数。因此，当第I个皇后占领了第J列后，要同时把以(i+j)、(i-j)为下标的标记置为被占领状态。2、数据结构。（1）解数组A。AI表示第I个皇后放置的列；范围：1.8（2）行冲突标记数组B。BI=0表示第I行空闲；BI=1表示第I行被占领；范围：1.8（3）对角线冲突标记数组C、D。CI-J=0表示第（I-J）条对角线空闲；CI-J=1表示第（I-J）条对角线被占领；范围：-7.7DI+J=0表示第（I+J）条对角线空闲；DI+J=1表示第（I+J）条对角线被占领；范围：2.16【算法流程】、数据初始化。、从n列开始摆放第n个皇后（因为这样便可以符合每一竖列一个皇后的要求），先测试当前位置(n,m)是否等于（未被占领），如果是，摆放第n个皇后，并宣布占领(记得要横列竖列斜列一起来哦)，接着进行递归；如果不是，测试下一个位置(n,m+1)，但是如果当n8时，便一一打印出结果。【参考程序】program exam3;var a:array 1.8 of integer; b,c,d:array -7.16 of integer; t,i,j,k:integer;procedure print;begin t:=t+1; write(t, ); for k:=1 to 8 do write(ak, ); writeln;end;procedure try(i:integer);var j:integer;begin for j:=1 to 8 do 每个皇后都有8种可能位置 if (bj=0) and (ci+j=0) and (di-j=0) then 判断位置是否冲突 begin ai:=j; 摆放皇后 bj:=1; 宣布占领第J行 ci+j:=1; 占领两个对角线 di-j:=1; if i8 then try(i+1) 8个皇后没有摆完，递归摆放下一皇后 else print; 完成任务，打印结果 bj:=0; 回溯 ci+j:=0; di-j:=0; end;end;begin for k:=-7 to 16 do 数据初始化 begin bk:=0; ck:=0; dk:=0; end; try(1);从第1个皇后开始放置end. 例4、自然数拆分【问题描述】输入自然数n，然后将其拆分成若干数相加的形式，参与加法运算的数可以重复。输入：待拆分的自然数n输出：若干数的加法式子【样例输入】5【样例输出】5=1+1+1+1+1 5=1+1+1+2 5=1+1+3 5=1+2+2 5=1+4 5=2+3【问题分析】算法分析：等式中后一个数必须大于等于前一个数，因为这个可以1、避免重复2提高效率我们用一个数组ai来记录拆分的数字，用bi记录剩下的数字。K记录第几个拆分的数字。每次拆分都可以把ai都打印出来。把剩下的数字bi在进行拆分，并且是从i开始拆分的。Find(bi,i,k+1)program cf;var a,b:array1.100 of integer; n,i:integer;procedure find(start,m,k:integer);从start开始，对m进行拆分，拆分是第k个数var i,j:integer;begin for i:=start to (m div 2) do 只要从start 到m的一个半，可以避免重复 begin write(n,=); ak:=i;bk:=m-i; for j:=1 to k do write(aj,+); writeln(bk); find(i,bk,k+1); end;end;beginassign(input,word.in);assign(output,word.out);reset(input);rewrite(output);readln(n);find(1,n,1);close(input);close(output);end. 解法二：针对所给问题，定义问题的解空间；如本题对5的拆分来说，1=拆分的数=5。确定易于搜索的解空间结构；如本题对5的拆分来说，用ki数组来存储解，每个数组元素的取值范围都是1=拆分的数=5，从1开始搜索直到5。搜索解空间，并在搜索过程中用剪枝函数避免无效搜索。如本题对5的拆分来说，为了避免重复，拆分出的加数要求满足k1k2kin 且k1k2ki。program exam4;var k:array1.100of longint; n:longint;procedure print(x:longint);/输出var i:longint;begin if x=1 then exit;/判断是否存在n=n的情况 write(n,=); for i:=1 to x-1 do write(ki,+); writeln(kx);end;procedure try(x,y,num:longint);/回溯搜索var i:longint;begin if y=0 then begin print(num-1);exit;end; for i:=x to y do/非递减搜索 begin if (y=i)or(i=y*2) then/如果y=3，x=2，那么后面是不可能 begin knum:=i; try(i,y-i,num+1); end; end;end;begin readln(n); try(1,n,1);end.例5、售货员的难题【问题描述】 某乡有n个村庄(1n40)，有一个售货员，他要到各个村庄去售货，各村庄之间的路程s(0s1000)是已知的，且A村到B村与B村到A村的路大多不同。为了提高效率，他从商店出发到每个村庄一次，然后返回商店所在的村，假设商店所在的村庄为1，他不知道选择什么样的路线才能使所走的路程最短。请你帮他选择一条最短的路。【输入】 村庄数n和各村之间的路程(均是整数)。【输出】 最短的路程。【样例】 salesman.in salesman.out 3 村庄数 3 0 2 1 村庄1到各村的路程 1 0 2 村庄2到各村的路程 2 1 0 村庄3到各村的路程【问题分析】题目给定的村庄数不多(40)，所以可以用回溯的方法，从起点(第一个村庄)出发找出所有经过其他所有村庄的回路，计算其中的最短路程。当村庄数n比较大时这种方法就不太适用了。用一个过程road(step，line：byte)来描述走的状况，其中step是当前已到村庄数、line是当前所在的村庄。如果stepn，下面只能回起点了，直接看第line个村庄到第一个村庄的路程加上已走的总路程，如果比最小值还小则替换最小值(要保存路径的话也可保存，这是回溯算法的优点，考虑到达最小值的路径可能不止一条，不便于测试，题目没要求输出路径)。如果step还小于n，那么将还没有到过的村庄一个一个地试过去，再调用下一步road(step+1，新到的村庄号)。Program exam5;var i,j,n,ans:longint; map:array1.41,1.41of longint; f:array1.41of boolean;procedure dfs(t,x,tot:longint);var i:longint;begin if t=n then begin if tot+mapx,1ans then ans:=tot+mapx,1; exit; end; for i:=2 to n do if fi then begin if tot+mapx,ians then begin fi:=false; dfs(t+1,i,tot+mapx,i); fi:=true; end; end; end;begin readln(n); fillchar(f,sizeof(f),true); for i:=1 to n do for j:=1 to n do read(mapi,j); ans:=maxlongint; dfs(1,1,0); writeln(ans); end.另一参考程序：var i,j,n,min:integer; a:array1.40,1.40of integer;/储存图 v:array1.40of boolean;/判断该点是否访问过procedure dfs(k,x,m:longint);/回溯var i:byte;beginif k=n then/到达终点 if m+ax,10)and vi then/当前点未访问 begin vi:=false; if m+ax,imin then/最优剪枝 dfs(k+1,i,m+ax,i);/回溯 vi:=true; end;IFend;dfsbeginmainassign(input,salesma.in);reset(input);assign(output,salesma.out);rewrite(output);fillchar(v,sizeof(v),true);readln(n);for i:=1 to n do for j:=1 to n do read(ai,j);min:=maxint;v1:=false;dfs(1,1,0);/回溯writeln(min);/输出最小值close(in