回溯算法的一些例题

回溯算法搜索与回溯是计算机解题中常用的算法，很多问题无法根据某种确定的计算法则来求解，可以利用搜索与回溯的技术求解。回溯是搜索算法中的一种控制策略。它的基本思想是：为了求得问题的解，先选择某一种可能情况向前探索，在探索过程中，一旦发现原来的选择是错误的，就退回一步重新选择，继续向前探索，如此反复进行，直至得到解或证明无解。如迷宫问题：进入迷宫后，先随意选择一个前进方向，一步步向前试探前进,如果碰到死胡同，说明前进方向已无路可走，这时，首先看其它方向是否还有路可走，如果有路可走，则沿该方向再向前试探；如果已无路可走，则返回一步，再看其它方向是否还有路可走；如果有路可走，则沿该方向再向前试探。按此原则不断搜索回溯再搜索，直到找到新的出路或从原路返回入口处无解为止。递归回溯法算法框架[一]procedureTry(k:integer);beginfori:=1to算符种数Doif满足条件thenbegin保存结果if到目的地then输出解elseTry(k+1);恢复：保存结果之前的状态{回溯一步}end;end;递归回溯法算法框架[二]procedureTry(k:integer);beginif到目的地then输出解elsefori:=1to算符种数Doif满足条件thenbegin保存结果Try(k+1);end;end;例1：素数环：把从1到20这20个数摆成一个环，要求相邻的两个数的和是一个素数。【算法分析】非常明显，这是一道回溯的题目。从1开始，每个空位有20（19）种可能，只要填进去的数合法：与前面的数不相同；与左边相邻的数的和是一个素数。第20个数还要判断和第1个数的和是否素数。〖算法流程〗1、数据初始化；2、递归填数：判断第J种可能是否合法；A、如果合法：填数；判断是否到达目标（20个已填完）：是，打印结果；不是，递归填下一个；B、如果不合法：选择下一种可能；【参考程序】programz74;框架[一]vara:array[0..20]ofbyte;b:array[0..20]ofboolean;total:integer;functionpd(x,y:byte):boolean;vark,i:byte;begink:=2;i:=x+y;pd:=false;while(k=trunc(sqrt(i)))and(imodk0)doinc(k);ifktrunc(sqrt(i))thenpd:=true;end;procedureprint;varj:byte;begininc(total);write('',total,':');forj:=1to20dowrite(a[j],'');writeln;end;proceduretry(t:byte);vari:byte;beginfori:=1to20doifpd(a[t-1],i)andb[i]thenbegina[t]:=i;b[i]:=false;ift=20thenbeginifpd(a[20],a[1])thenprint;endelsetry(t+1);b[i]:=true;end;end;BEGINfillchar(b,sizeof(b),#1);total:=0;try(1);write('total:',total);END.通过观察，我们可以发现实现回溯算法的特性：在解决过程中首先必须要先为问题定义一个解的空间．这个空间必须包含问题的一个解。在搜索路的同时也就产生了新的解空间。在搜索期间的任何时刻．仅保留从起始点到当前点的路径。例2：设有n个整数的集合｛1,2,…,n｝，从中取出任意r个数进行排列（rn），试列出所有的排列。解法一：programit15;框架[一]typese=setof1..100;VARs:se;n,r,num:integer;b:array[1..100]ofinteger;PROCEDUREprint;vari:integer;beginnum:=num+1;fori:=1tordowrite(b[i]:3);writeln;end;PROCEDUREtry(k:integer);VARi:integer;beginfori:=1tondoifiinsthenbeginb[k]:=i;s:=s-[i];ifk=rthenprintelsetry(k+1);s:=s+[i];end;end;BEGINwrite('Inputn,r:');readln(n,r);s:=[1..n];num:=0;try(1);writeln('number=',num);END.解法二：programit15;框架[二]typese=setof1..100;VARs:se;n,r,num,k:integer;b:array[1..100]ofinteger;PROCEDUREprint;vari:integer;beginnum:=num+1;fori:=1tordowrite(b[i]:3);writeln;end;PROCEDUREtry(s:se;k:integer);VARi:integer;beginifkrthenprintelsefori:=1tondoifiinsthenbeginb[k]:=i;try(s-[i],k+1);end;end;BEGINwrite('Inputn,r:');readln(n,r);s:=[1..n];num:=0;try(s,1);writeln('number=',num);readln;END.例3、任何一个大于1的自然数n,总可以拆分成若干个小于n的自然数之和.当n=7共14种拆分方法：7=1+1+1+1+1+1+17=1+1+1+1+1+27=1+1+1+1+37=1+1+1+2+27=1+1+1+47=1+1+2+37=1+1+57=1+2+2+27=1+2+47=1+3+37=1+67=2+2+37=2+57=3+4total=14{参考程序}programjjj;vara:array[0..100]ofinteger;n,t,total:integer;procedureprint(t:integer);vari:integer;beginwrite(n,'=');fori:=1tot-1dowrite(a[i],'+');writeln(a[t]);total:=total+1;end;proceduretry(s,t:integer);vari:integer;beginfori:=1tosdoif(a[t-1]=i)and(in)thenbegina[t]:=i;s:=s-a[t];ifs=0thenprint(t)elsetry(s,t+1);s:=s+a[t];end;end;beginreadln(n);try(n,1);writeln('total=',total);readln;end.例4、八皇后问题：要在国际象棋棋盘中放八个皇后，使任意两个皇后都不能互相吃。（提示：皇后能吃同一行、同一列、同一对角线的任意棋子。）放置第i个皇后的算法为：procedureTry(i)；beginfor第i个皇后的位置=1to8do；if安全thenbegin放置第i个皇后；对放置皇后的位置进行标记；ifi=8then输出elseTry(i+1)；{放置第i+1个皇后}对放置皇后的位置释放标记，尝试下一个位置是否可行；end；end；【算法分析】显然问题的键在于如何判定某个皇后所在的行、列、斜线上是否有别的皇后；可以从矩阵的特点上找到规律，如果在同一行，则行号相同；如果在同一列上，则列号相同；如果同在／斜线上的行列值之和相同；如果同在＼斜线上的行列值之差相同；如果斜线不分方向，则同一斜线上两皇后的行号之差的绝对值与列号之差的绝对值相同。从下图可验证：对于一组布局我们可以用一个一维数组来表示：A:ARRAY[1..8]OFINTEGER;A[I]的下标I表示第I个皇后在棋盘的第I行，A[I]的内容表示在第I行的第A[I]列，例如：A[3]=5就表示第3个皇后在第3行的第5列。在这种方式下，要表示两个皇后I和J不在同一列或斜线上的条件可以描述为：A[I]A[J]ANDABS(I-J)ABS(A[I]-A[J]){I和J分别表示两个皇后的行号}考虑每行有且仅有一个皇后，设一维数组A[1..8]表示皇后的放置：第i行皇后放在第j列，用A[i]＝j来表示，即下标是行数，内容是列数。判断皇后是否安全，即检查同一列、同一对角线是否已有皇后，建立标志数组b[1..8]控制同一列只能有一个皇后，若两皇后在同一对角线上，则其行列坐标之和或行列坐标之差相等，故亦可建立标志数组c[1..16]、d[-7..7]控制同一对角线上只能有一个皇后。从分析中，我们不难看出，搜索前进过程实际上是不断递归调用的过程，当递归返回时即为回溯的过程。programex1;vara:array[1..8]ofbyte;b:array[1..8]ofboolean;c:array[1..16]ofboolean;d:array[-7..7]ofboolean;sum:byte;procedurepr;vari:byte;beginfori:=1to8dowrite(a[i]:4);inc(sum);writeln('sum=',sum);end;proceduretry(t:byte);varj:byte;beginforj:=1to8do{每个皇后都有8种可能位置}ifb[j]andc[t+j]andd[t-j]then{寻找放置皇后的位置}begin{放置皇后,建立相应标志值}a[t]:=j;{摆放皇后}b[j]:=false;{宣布占领第j列}c[t+j]:=false;{占领两个对角线}d[t-j]:=false;ift=8thenpr{8个皇后都放置好,输出}elsetry(t+1);{继续递归放置下一个皇后}b[j]:=true;{递归返回即为回溯一步,当前皇后退出}c[t+j]:=true;d[t-j]:=true;end;end;BEGINfillchar(b,sizeof(b),#1);fillchar(c,sizeof(c),#1);fillchar(d,sizeof(d),#1);sum:=0;try(1);{从第1个皇后开始放置}END.例5：马的遍历中国象棋半张棋盘如图4（a）所示。马自左下角往右上角跳。今规定只许往右跳，不许往左跳。比如图4（a）中所示为一种跳行路线，并将所经路线打印出来。打印格式为：0，0-2,1-3,3-1,4-3,5-2,7-4,8…分析：如图4（b）,马最多有四个方向，若原来的横坐标为j、纵坐标为i,则四个方向的移动可表示为：1：（i,j）→（i+2,j+1）；(i3,j8)2:（i,j）→（i+1,j+2）；(i4,j7)3:（i,j）→（i-1,j+2）；(i0,j7)4:（i,j）→（i-2,j+1）；(i1,j8)搜索策略：S1:A[1]:=(0,0);S2:从A[1]出发，按移动规则依次选定某个方向，如果达到的是（4,8）则转向S3,否则继续搜索下一个到达的顶点；S3:打印路径。programexam2;constx:array[1..4,1..2]ofinteger=((2,1),(1,2),(-1,2),(-2,1));{四种移动规则}vart:integer;{路径总数}a:array[1..9,1..2]ofinteger;{路径}procedureprint(ii:integer);{打印}vari:integer;begininc(t);{路径总数}fori:=1toii-1dowrite(a[i,1],',',a[i,2],'--');writeln('4,8',t:5);readln;end;proceduretry(i:integer);{搜索}varj:integer;b