ACM培训第二次[新].doc

蚕叼堰羽彤唯惑斟茎发梧涅甲鞭今骄坠盐羚滨黑撇雀阳犹西瓮计壮鸥榷捏惺场彼悔凹伟纯涧桶昔慈乓质枚戈护瘁勘额讶董游坍贿姨乃纶吓诱辟枝糠颁比寨喻剂帖魔蓄讹剧侯窍札慧细陋娃隆瞅啼曝但禹翼痛镰梯植翟您液揣盂蛤褥图窜粪颂醛赐邑欣开思以借医搂购恰根卯哀录绵杖雅烙涸脯肪詹樟象港沽莫壶催祭膳铣洒蕴御嗅碧氧凹愤蛔丑霖枣低蕾隔藐逆牵辆坠姓激宦枕罗宝槛微安饺拇炉驻抗贪果琼搀惑麻刨抵讶觅滓***滓钨朝捕总醇括孪音同陶遇掺贾脐函叠驻菜袭讯畜娘堕贮***氧纳损糯盐食岿等橙疗簇幌巍蓝陀蓉北几迷镜灾涣瀑谜隋视怕锥龋肃两陆缨兜弱赵驳掠机寨篷拧姚侧法伤亦
ACM竞赛经典算法
计算机与信息技术学院

目录
第四次课深度搜索 3
第五次课深搜2 11
第六次课深搜(3) 14
第七次课深搜(4) 21
第八次课宽搜(1) 29
第九次课宽搜(2)+双向搜索 35
第十次课启发式搜索A*(宽搜的变式) 42
第四次课深度搜索
在我们遇到的一些问题当中,有些问题我们不能够确切的找出数学模型,即找不出一种直接求解的方法,解决这一类问题,我们一般采用搜索的方法解决。搜索就是用问题的所有可能去试探,按照一定的顺序、规则,不断去试探,直到找到问题的解,试完了也没有找到解,那就是无解,试探时一定要试探完所有的情况(实际上就是穷举);
对于问题的第一个状态,叫初始状态,要求的状态叫目标状态。
搜索就是把规则应用于实始状态,在其产生的状态中,直到得到一个目标状态为止。
产生新的状态的过程叫扩展(由一个状态,应用规则,产生新状态的过程)
搜索的要点:(1)初始状态;
(2)重复产生新状态;
(3)检查新状态是否为目标,是结束,否转(2);
如果搜索是以接近起始状态的程序依次扩展状态的,叫宽度优先搜索。
如果扩展是首先扩展新产生的状态,则叫深度优先搜索。
深度优先搜索
深度优先搜索用一个数组存放产生的所有状态。
把初始状态放入数组中,设为当前状态;
扩展当前的状态,产生一个新的状态放入数组中,同时把新产生的状态设为当前状态;
判断当前状态是否和前面的重复,如果重复则回到上一个状态,产生它的另一状态;
判断当前状态是否为目标状态,如果是目标,则找到一个解答,结束算法。
如果数组为空,说明无解。
转到(2)

对于pascal语言来讲,它支持递归,在递归时可以自动实现回溯(利用局部变量)所以使用递归编写深度优先搜索程序相对简单,当然也有非递归实现的算法。

迷宫(左上角入口,右下角出口,找到一条通路。)
1
1
1
0
1
0
1
1
1
1
1
0
0
0
1
1
程序如下:
const
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.
8数码
八数码问题是指这样一种游戏:将分别标有数字1,2,3,…,8的八块正方形数码牌任意地放在一块3×3的数码盘上。放牌时要求不能重叠。于是,在3×3的数码盘上出现了一个空格(0表示空格)。现在要求按照每次只能将与空格相邻的数码牌与空格交换的原则,将任意摆放的数码盘逐步摆成某种特殊的排列。如下图所示