《ACM培训第二次》由会员分享，可在线阅读，更多相关《ACM培训第二次（46页珍藏版）》请在金锄头文库上搜索。
1、 ACM竞赛经典算法计算机与信息技术学院 目 录第四次课 深度搜索3第五次课深搜211第六次课深搜（）14第七次课 深搜（）21第八次课 宽搜（1）29第九次课宽搜（2）+双向搜索35第十次课启发式搜索A*（宽搜的变式）42第四次课 深度搜索 在我们遇到的一些问题当中，有些问题我们不能够确切的找出数学模型，即找不出一种直接求解的方法，解决这一类问题，我们一般采用搜索的方法解决。搜索就是用问题的所有可能去试探，按照一定的顺序、规则，不断去试探，直到找到问题的解，试完了也没有找到解，那就是无解，试探时一定要试探完所有的情况（实际上就是穷举）；对于问题的第一个状态，叫初始状态，要求的状态叫目标状态。
2、搜索就是把规则应用于实始状态，在其产生的状态中，直到得到一个目标状态为止。产生新的状态的过程叫扩展（由一个状态，应用规则，产生新状态的过程）搜索的要点：（1）初始状态； （2）重复产生新状态； （3）检查新状态是否为目标，是结束，否转（2）；如果搜索是以接近起始状态的程序依次扩展状态的，叫宽度优先搜索。如果扩展是首先扩展新产生的状态，则叫深度优先搜索。深度优先搜索深度优先搜索用一个数组存放产生的所有状态。（1） 把初始状态放入数组中，设为当前状态；（2） 扩展当前的状态，产生一个新的状态放入数组中，同时把新产生的状态设为当前状态；（3） 判断当前状态是否和前面的重复，如果重复则回到上一个状态，
3、产生它的另一状态；（4） 判断当前状态是否为目标状态，如果是目标，则找到一个解答，结束算法。（5） 如果数组为空，说明无解。（6） 转到（） 对于pascal语言来讲，它支持递归，在递归时可以自动实现回溯（利用局部变量）所以使用递归编写深度优先搜索程序相对简单，当然也有非递归实现的算法。 1、 迷宫（左上角入口，右下角出口，找到一条通路。）1110101111100011程序如下：const d:array1.4,1.4of integer=(1,1,0,0),(0,1,1,1),(1,1,0,1),(0,1,1,1); c:array1.4,1.2of -1.1=(0,1),(0,-1),(
4、1,0),(-1,0);var a:array1.16,1.2of integer; i,j:integer;procedure play(k:integer); var i:integer; begin if (ak,1=4)and(ak,2=4) then begin for i:=1 to k do write(,ai,1,ai,2,); writeln; readln; exit; end; for i:=1 to 4 do if (ak,1+ci,10)and(ak,1+ci,10)and(ak,2+ci,25) then if dak,1,ak,2=1 then begin dak
5、,1,ak,2:=2; ak+1,1:=ak,1+ci,1; ak+1,2:=ak,2+ci,2; play(k+1); dak,1,ak,2:=1; end;end;begin fillchar(a,sizeof(a),0); a1,1:=1;a1,2:=1; play(1);end.2、 8数码八数码问题是指这样一种游戏：将分别标有数字1，2，3，8的八块正方形数码牌任意地放在一块33的数码盘上。放牌时要求不能重叠。于是，在33的数码盘上出现了一个空格（0表示空格）。现在要求按照每次只能将与空格相邻的数码牌与空格交换的原则，将任意摆放的数码盘逐步摆成某种特殊的排列。如下图所示：567408
6、321507461382程序如下：type node=array1.3,1.3of 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:array1.4,1.2of-1.1=(0,1),(0,-1),(1,0),(-1,0);var a:array1.20of 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
7、 ak,x,yglx,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 ak,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 f
8、or y:=1 to 3 do write(ai,x,y:3); writeln; end; writeln(-); end; end;function nrep(k:integer):boolean; var i,x,y:integer; f:boolean; begin nrep:=false; for i:=1 to k-1 do begin f:=true; for x:=1 to 3 do for y:=1 to 3 do if ai,x,yak,x,y then begin f:=false;break;break;end; if f then exit; end; nrep:=t
9、rue; end;procedure step(k:integer); var i,x,y:integer; begin if k=20 then exit; if result(k) then begin print(k);exit;end; look(k,x,y); for i:=1 to 4 do begin if (x+rli,1=1)and(x+rli,1=3)and(y+rli,2=1)then begin ak+1:=ak; ak+1,x+rli,1,y+rli,2:=ak,x,y; ak+1,x,y:=ak,x+rli,1,y+rli,2; if nrep(k+1) then
10、step(k+1); end; end; end; begin a1:=st; step(1);end.3、 跳马（5*5）国际象棋8*8棋盘上某个位置的一只马，按马的行走规则，每个方格进入一次.，它是否可能只走63步，正好走过除起点外的其他63个位置各一次？如果有一种这样的走法，则称所走的这条路线为一条马的周游路线。试设计一个算法找出这样一条马的周游路线并输出。本题采用5*5的棋盘。程序如下：const d:array1.8,1.2of -2.2=(-2,1),(-2,-1),(1,2),(1,-2),(2,-1),(2,1),(-1,-2),(-1,2);var a:array1.5,1.
11、5of 0.1;procedure print; var i,j:integer; begin for i:=1 to 5 do begin for j:=1 to 5 do write(ai,j:3); writeln; end; readln; end;procedure play(x,y:integer); var i:integer; begin if (x=5)and(y=5) then begin print;exit;end; for i:=1 to 8 do if (x+di,10)and(x+di,10)and(y+di,2目标(40,40.0)程序如下：const v:array1.3of integer=(80,50,30);var a:array1.30,1.3of integer;procedure print(k:integer); var i:integer; begin for i:=1 to k do writeln(step:,i,ai,1:3,ai,2:3,ai,3:3); re
