ACM竞赛经典算法
计算机与信息技术学院
目 录
第四次课 深度搜索 ....................................................................................................... 3 第五次课深搜2 .............................................................................................................. 11 第六次课深搜（３） ..................................................................................................... 14 第七次课 深搜（４） ................................................................................................... 21 第八次课 宽搜（1） ..................................................................................................... 29 第九次课宽搜（2）+双向搜索 ..................................................................................... 35 第十次课启发式搜索A*（宽搜的变式） ................................................................... 42
第四次课 深度搜索
在我们遇到的一些问题当中，有些问题我们不能够确切的找出数学模型，即找不出一种直接求解的方法，解决这一类问题，我们一般采用搜索的方法解决。搜索就是用问题的所有可能去试探，按照一定的顺序、规则，不断去试探，直到找到问题的解，试完了也没有找到解，那就是无解，试探时一定要试探完所有的情况（实际上就是穷举）；
对于问题的第一个状态，叫初始状态，要求的状态叫目标状态。
搜索就是把规则应用于实始状态，在其产生的状态中，直到得到一个目标状态为止。 产生新的状态的过程叫扩展（由一个状态，应用规则，产生新状态的过程） 搜索的要点：（1）初始状态；
（2）重复产生新状态；
（3）检查新状态是否为目标，是结束，否转（2）；
如果搜索是以接近起始状态的程序依次扩展状态的，叫宽度优先搜索。 如果扩展是首先扩展新产生的状态，则叫深度优先搜索。
深度优先搜索
深度优先搜索用一个数组存放产生的所有状态。 （1） 把初始状态放入数组中，设为当前状态；
（2） 扩展当前的状态，产生一个新的状态放入数组中，同时把新产生的状态设为当
前状态；
（3） 判断当前状态是否和前面的重复，如果重复则回到上一个状态，产生它的另一
状态；
（4） 判断当前状态是否为目标状态，如果是目标，则找到一个解答，结束算法。 （5） 如果数组为空，说明无解。 （6） 转到（２）
对于pascal语言来讲，它支持递归，在递归时可以自动实现回溯（利用局部变量）所以使用递归编写深度优先搜索程序相对简单，当然也有非递归实现的算法。
1、
迷宫（左上角入口，右下角出口，找到一条通路。）
1 0 1 0
1 1 1 1
0 1 0
0 1 11
程序如下： const
1
d:array[1..4,1..4]of integer=((1,1,0,0),(0,1,1,1),(1,1,0,1),(0,1,1,1)); c:array[1..4,1..2]of -1..1=((0,1),(0,-1),(1,0),(-1,0)); var
a:array[1..16,1..2]of integer; i,j:integer;
procedure play(k:integer); var
i:integer; begin
if (a[k,1]=4)and(a[k,2]=4) then begin
for i:=1 to k do
write('(',a[i,1],',',a[i,2],')'); writeln; readln; exit; end;
for i:=1 to 4 do
if (a[k,1]+c[i,1]>0)and(a[k,1]+c[i,1]<5) and(a[k,2]+c[i,2]>0)and(a[k,2]+c[i,2]<5) then if d[a[k,1],a[k,2]]=1 then begin d[a[k,1],a[k,2]]:=2;
a[k+1,1]:=a[k,1]+c[i,1]; a[k+1,2]:=a[k,2]+c[i,2]; play(k+1);
d[a[k,1],a[k,2]]:=1; end; end; begin
fillchar(a,sizeof(a),0); a[1,1]:=1;a[1,2]:=1; play(1); end.
2、 8数码
八数码问题是指这样一种游戏：将分别标有数字1，2，3，…，8的八块正方形数码牌任意地放在一块3×3的数码盘上。放牌时要求不能重叠。于是，在3×3的数码盘上出现了一个空格（0表示空格）。现在要求按照每次只能将与空格相邻的数码牌与空格交换的原则，将任意摆放的数码盘逐步摆成某种特殊的排列。如下图所示：
2 8 3 1 2 3
1 6 4 8 0 4
7 0 5 7 6 5
程序如下： type
node=array[1..3,1..3]of 0..8; const
st:node=((2,8,3),(1,6,4),(7,0,5)); gl:node=((1,2,3),(8,0,4),(7,6,5));
rl:array[1..4,1..2]of-1..1=((0,1),(0,-1),(1,0),(-1,0)); var
a:array[1..20]of node;
function result(k:integer):boolean; var
i,x,y:integer; begin
result:=false; for x:=1 to 3 do for y:=1 to 3 do
if a[k,x,y]<>gl[x,y] then exit; result:=true; end;
procedure look(k:integer;var x,y:integer); var
i,j:integer; begin
for i:=1 to 3 do for j:=1 to 3 do
if a[k,i,j]=0 then begin x:=i;y:=j;end; end;
procedure print(k:integer); var
i,x,y:integer; begin
for i:=1 to k do begin
writeln('step:',i); for x:=1 to 3 do begin
for y:=1 to 3 do write(a[i,x,y]:3); writeln; end;
writeln('------------'); end;