📄 回溯算法.htm
字号:
<TABLE cellSpacing=0 cellPadding=0 width=618>
<TBODY>
<TR>
<TD width=616 colSpan=2>
<P align=right> </P></TD></TR>
<TR>
<TD width=181>
<P><IMG height=20 src="回溯算法.files/s2.gif" width=20
align=absMiddle border=0> <B>回溯算法</B></P></TD>
<TD width=433>
<P align=right><A
href="http://www.muduhs.com/~yanxm/index1.htm">Index</A> >
<A href="http://www.muduhs.com/~yanxm/pds.htm">Alogri+Data
str</A> > <A
href="http://www.muduhs.com/~yanxm/pds00.htm">常用算法</A> >
回溯</P></TD></TR>
<TR>
<TD width=616 background=回溯算法.files/bg.gif colSpan=2
height=1></TD></TR>
<TR>
<TD width=616 colSpan=2>
<P><BR>一、回溯法：<BR>回溯法是一个既带有系统性又带有跳跃性的的搜索算法。它在包含问题的所有解的解空间树中，按照深度优先的策略，从根结点出发搜索解空间树。算法搜索至解空间树的任一结点时，总是先判断该结点是否肯定不包含问题的解。如果肯定不包含，则跳过对以该结点为根的子树的系统搜索，逐层向其祖先结点回溯。否则，进入该子树，继续按深度优先的策略进行搜索。回溯法在用来求问题的所有解时，要回溯到根，且根结点的所有子树都已被搜索遍才结束。而回溯法在用来求问题的任一解时，只要搜索到问题的一个解就可以结束。这种以深度优先的方式系统地搜索问题的解的算法称为回溯法，它适用于解一些组合数较大的问题。<BR><BR>二、算法框架：<BR>1、问题的解空间：应用回溯法解问题时，首先应明确定义问题的解空间。问题的解空间应到少包含问题的一个（最优）解。<BR><BR>2、回溯法的基本思想：确定了解空间的组织结构后，回溯法就从开始结点（根结点）出发，以深度优先的方式搜索整个解空间。这个开始结点就成为一个活结点，同时也成为当前的扩展结点。在当前的扩展结点处，搜索向纵深方向移至一个新结点。这个新结点就成为一个新的活结点，并成为当前扩展结点。如果在当前的扩展结点处不能再向纵深方向移动，则当前扩展结点就成为死结点。换句话说，这个结点不再是一个活结点。此时，应往回移动（回溯）至最近的一个活结点处，并使这个活结点成为当前的扩展结点。回溯法即以这种工作方式递归地在解空间中搜索，直至找到所要求的解或解空间中已没有活结点时为止。<BR>运用回溯法解题通常包含以下三个步骤：<BR>（1）针对所给问题，定义问题的解空间；<BR>（2）确定易于搜索的解空间结构；<BR>（3）以深度优先的方式搜索解空间，并且在搜索过程中用剪枝函数避免无效搜索；<BR><BR>3、递归回溯：由于回溯法是对解空间的深度优先搜索，因此在一般情况下可用递归函数来实现回溯法如下：<BR>procedure
try(i:integer);<BR>var<BR>begin<BR>if i>n then 输出结果<BR>else
for j:=下界 to 上界 do<BR>begin<BR>x[i]:=h[j];<BR>if
可行{满足限界函数和约束条件} then begin 置值；try(i+1);
end;<BR>end;<BR>end; <BR><BR>说明：<BR>i是递归深度； <BR>n是深度控制，即解空间树的的高度；<BR>可行性判断有两方面的内容：不满约束条件则剪去相应子树；若限界函数越界，也剪去相应子树；两者均满足则进入下一层；<BR><BR> 搜索：全面访问所有可能的情况，分为两种：不考虑给定问题的特有性质，按事先顶好的顺序，依次运用规则，即盲目搜索的方法；另一种则考虑问题给定的特有性质，选用合适的规则，提高搜索的效率，即启发式的搜索。<BR>回溯即是较简单、较常用的搜索策略。<BR>基本思路：若已有满足约束条件的部分解，不妨设为（x1,x2,x3,……xi），I<n,则添加x(i+1)属于s(i+2)，检查(x1,x2,……,xi,x(i+1))是否满足条件，满足了就继续添加x(i+2)、s(i+2)，若所有的x(i+1)属于s(i+1)都不能得到部分解，就去掉xi，回溯到(xi,x2,……x(i-1))，添加那些未考察过的x1属于s1，看其是否满足约束条件，为此反复进行，直至得到解或证明无解。 <BR><BR>例子:<BR><BR> 例1、八皇后问题：要在国际象棋棋盘中放八个皇后，使任意两个皇后都不能互相吃。<BR>
（提示：皇后能吃同一行、同一列、同一对角线的任意棋子。）<BR><BR>program tt;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(a[k],' '); writeln;end;procedure
try(i:integer);var j:integer;begin for j:=1 to 8 do
{每个皇后都有8种可能位置} if (b[j]=0) and (c[i+j]=0) and (d[i-j]=0) then
{判断位置是否冲突} begin a[i]:=j; {摆放皇后} b[j]:=1; {宣布占领第J行} c[i+j]:=1;
{占领两个对角线} d[i-j]:=1; if i<8 then try(i+1)
{8个皇后没有摆完，递归摆放下一皇后} else print; {完成任务，打印结果} b[j]:=0; {回溯}
c[i+j]:=0; d[i-j]:=0; end;end;begin for k:=-7 to 16 do {数据初始化}
begin b[k]:=0; c[k]:=0; d[k]:=0; end;
try(1);{从第1个皇后开始放置}end. 例2、跳马问题。在5*5格的棋盘上，有一个国家象棋的马，它可以朝8个方向跳，但不允许出界或跳到已跳过的格子上，要求在跳遍整个棋盘后再条回出发点。<BR><BR>program
jump;<BR> var<BR> h:array[-1..7,-1..7] of integer;<BR>
a,b:array[1..8] of integer;<BR> i,j,num:integer;<BR>
procedure print;<BR> var i,j:integer;<BR> begin<BR>
num:=num+1;<BR> if num<=5 then<BR> begin<BR> for
i:=1 to 5 do<BR> begin<BR> for j:=1 to 5 do
write(h[i,j]:4);<BR> writeln;<BR> end;<BR>
writeln;<BR> end;<BR> end;<BR> procedure
try(x,y,i:integer);<BR> var j,u,v:integer;<BR>
begin<BR> for j:=1 to 8 do<BR> begin<BR>
u:=x+a[j];<BR> v:=y+b[j];<BR> if h[u,v]=0
then<BR> begin h[u,v]:=i;<BR> if i<25 then
try(u,v,i+1)<BR> else print;<BR>
h[u,v]:=0<BR> end;<BR> end;<BR> end;<BR>
begin<BR> for i:=-1 to 7 do<BR> for j:=-1 to 7 do<BR>
if (i>=1)and(i<=5)and(j>=1)and(j<=5)<BR> then
h[i,j]:=0<BR> else h[i,j]:=1;<BR> a[1]:=2;b[1]:=1;<BR>
a[2]:=1;b[2]:=2;<BR> a[3]:=-1;b[3]:=2;<BR>
a[4]:=-2;b[4]:=1;<BR> a[5]:=-2;b[5]:=-1;<BR>
a[6]:=-1;b[6]:=-2;<BR> a[7]:=1;b[7]:=-2;<BR>
a[8]:=2;b[8]:=-1;<BR> num:=0;<BR> h[1,1]:=1;<BR>
try(1,1,2);<BR> writeln('num=',num);<BR>
end.<BR><BR> 例３：素数环：
把从1到20这20个数摆成一个环，要求相邻的两个数的和是一个素数。<BR>〖问题分析〗
非常明显，这是一道回溯的题目。从1开始，每个空位有20（19）种可能，只要填进去的数合法：<BR>与前面的数不相同；与左边相邻的数的和是一个素数。第20个数还要判断和第1个数的和是否素数。<BR><BR>〖算法流程〗<BR>1、数据初始化；<BR>2、递归填数：<BR>判断第J种可能是否合法；<BR>A、如果合法：填数；判断是否到达目标（20个已填完）：是，打印结果；不是，递归填下一个；<BR>B、如果不合法：选择下一种可能；<BR><BR>参考程序：<BR><BR>program
tt;<BR>var a:array [1..20] of
integer;<BR> k:integer;<BR>function
pd1(j,i:integer):boolean;<BR>begin<BR> pd1:=true;<BR> for
k:=1 to i-1 do<BR> if a[k]=j<BR> then
begin<BR> pd1:=false;<BR>exit;<BR>end;<BR>end;<BR>function
pd2(x:integer):boolean;<BR>begin<BR> pd2:=true;<BR> for
k:=2 to trunc(sqrt(x)) do<BR> if x mod k=0<BR> then
begin<BR> pd2:=false;<BR> exit;<BR>end;<BR>end;<BR>function
pd3(j,i:integer):boolean;<BR>begin<BR> if
i<20<BR> then pd3:=pd2(j+a[i-1])<BR> else
pd3:=pd2(j+a[i-1]) and pd2(j+1);<BR>end;<BR>procedure
print;<BR>begin<BR> for k:=1 to 20
do<BR> write(a[k]:4);<BR> writeln;<BR>end;<BR>procedure
try(i:integer);<BR>var j:integer;<BR>begin<BR> for j:=2
to 20 do<BR> begin<BR> if pd1(j,i) and
pd3(j,i)<BR> then begin<BR> a[i]:=j;<BR> if
i=20<BR> then
begin<BR> print;<BR> halt;<BR>end<BR> else
try(i+1);<BR> a[i]:=0;<BR> end;<BR> end;<BR>end;<BR>begin<BR> for
k:=1 to 20
do<BR> a[k]:=0;<BR> a[1]:=1;<BR> try(2);<BR>end. <BR><BR>练习：<BR>
1、对于任意一个m*n的矩阵,
求L形骨牌覆盖后所剩方格数最少的一个方案.<BR> 2、任何一个正整数都可以用2的幂次方表示.<BR> 例如:137=2^7+2^3+2^0<BR> 同时约定次方用括号来表示,即a^b可表示为a(b)<BR> 由此可知,137可表示为:2(7)+2(3)+2(0)<BR> 进一步:7=2^2+2+2^0
(2^1用2表示)<BR> 3=2+2^0<BR> 所以最后137可表示为:2(2(2)+2+2(0))+2(2+2(0))+2(0)<BR> 又如:1315=2^10+2^8+2^5+2+1<BR> 所以1315最后可表示为:2(2(2+2(0))+2)+2(2(2+2(0)))+2(2(2)+2(0))+2+2(0)<BR> 输入:正整数(n<=20000)<BR> 输出:符合约定的n的0,2表示(在表示中不能有空格) <BR><BR>习题：<BR>1、0-1背包：n=3,w=[16,15,15],p=[45,25,25],c=30<BR><BR>2、旅行售货员问题：某售货员要到若干城市去推销商品，已知各城市之间的路程（或旅费）。他要选定一条从驻地出发，经过每个城市一遍，最后回到驻地的路线，使总的路程（或总旅费）最小。<BR><BR>3、括号检验<BR>题目描述：输入一个代数表达式(只含有+,-,*,/,(,),1,2,3,4,5,6,7,8,9,0等字符,每个数字均小于10),设表达式除括号匹配有误外无其他错误.编程对输入的表达式检验,判断括号匹配是否正确.<BR><BR>正确的:<BR>1+2+4<BR>(1+2)+4<BR>(1+2)
错误的:<BR>(1+)2<BR>(1+2(4+3))<BR>(1+2+3*(4+5()))<BR>1+2+3*(4+5)) <BR><BR>4、四色问题：<BR>〖问题描述〗<BR>设有如下图所示的地图，每个区域代表一个省，区域中的数字代表省的编号，将每个省涂上红（R），蓝（B），白（W），黄（Y）四种颜色之一，使相邻的省份有不同的颜色。<BR><BR>1
2 3 4 <BR>5
6 <BR><BR>输入：用邻接矩阵表示地图。从文件中读入，文件格式如下：<BR>N
（有N个省）<BR>N行用空格隔开的0/1串
（1表示相邻，0表示不相邻）<BR><BR>输出：RBWY串</P></TD></TR></TBODY></TABLE></TD>
<TD width=152> </TD></TR></TBODY></TABLE></TD></TR>
<TR>
<TD vAlign=bottom height=81>
<TABLE cellSpacing=0 cellPadding=0 width="100%" border=0>
<TBODY>
<TR bgColor=#cccccc>
<TD width=800 height=1><IMG height=1 width=800></TD>
<TD width=459 height=1></TD></TR>
<TR vAlign=top>
<TD width=800>
<TABLE cellSpacing=0 cellPadding=0 width=800>
<TBODY>
<TR>
<TD width=210 height=10></TD>
<TD width=590 colSpan=2 height=10></TD></TR>
<TR>
<TD width=210 height=14>
<P align=center><A onfocus=this.blur()
href="http://www.muduhs.com/" target=_blank><FONT face=Verdana
color=#999999 size=1>GO Muduhs WebSite!</FONT></A> </P></TD>
<TD width=536 height=14>
<P><FONT face=Verdana size=1>Copyright ⓒ MuDu - Internet
HighSchool. Some right reserved.</FONT></P></TD>
<TD width=54 height=14>
<P align=right><A onfocus=this.blur()
href="http://www.muduhs.com/~yanxm/pds05.htm#"><FONT
face=Verdana size=1><B>-TOP</B></FONT></A> </P></TD></TR>
<TR>
<TD width=210 height=10></TD>
<TD width=590 colSpan=2 height=10></TD></TR></TBODY></TABLE></TD>
<TD width=459></TD></TR></TBODY></TABLE></TD></TR></TBODY></TABLE><MAP
name=ImageMap1><AREA shape=RECT coords=81,1,161,33
href="http://www.muduhs.com/~yanxm/pds.htm"><AREA shape=RECT
coords=161,1,240,33 href="http://www.muduhs.com/~yanxm/contest.htm"><AREA
shape=RECT coords=240,1,320,34
href="http://www.muduhs.com/~yanxm/circle.htm"><AREA shape=RECT
coords=319,1,401,35 href="http://www.muduhs.com/~yanxm/gellery.htm"><AREA
shape=RECT coords=401,2,479,35
href="http://www.muduhs.com/~yanxm/board.htm"><AREA shape=RECT
coords=1,1,82,33
href="http://www.muduhs.com/~yanxm/about.htm"></MAP></BODY></HTML>
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -