当前位置:首页 >> 学科竞赛 >>

BFS宽搜(广度)c++


广度优先搜索
?

基本原理及方法

在深度优先搜索算法中, 深度越大的结点越先得到扩展。 若把它改为深度越小的结点越 先得到扩展, 就是广度优先搜索法, 下面通过一个具体实例来讨论广度优先算法的一般规律。 【例题】八数码难题。在 3×3 的棋盘上,摆有八个棋子,每个棋子上标有 1 至 8 的某一数 字。棋盘中留有一个空格。空格周

围的棋子可以移到空格中。要求解的问题是:给出一种初 始布局(初始状态)和目标面局(目标状态) ,找到一种最少步骤的移动方法,实现从初始 布局到目标布局的转变。 【分析】由于题目要找到的解是达到目标最少步骤,因此解题的方法为:从初始状态出发, 先把移动一步后的布局全部找到,检查是否达到目标布局,如果没有,再从这些移动一步的 布局出发,找到移动两步后的所有布局,再判断是否有达到目标的,如此继续,一直达到目 标状态为止,输出结果。由于是按移动步数从少到多产生新布局的,所以找到的第一个目标 一定是移动步数最少的一个,也就是最优解。 建立产生式系统。其中:综合数据库。显然用 3*3 的二维数组来表示布局比较直观。用 ch (i,j)表示第 i 行第 j 列格子上放的棋子数字,空格则用 0 表示。为了方便编程,还需存 储该布局的空格位置: (si,sj) ; 初始布局到该布局的步数, 即深度 dep;该布局的上一布局, 即父结点的位置。这样数据库每一个元素应该是由上述几个数据组成的记录。 因为新产生的结点深度 (也即从初始布局到该结点的步数) 一般要比数据库原有结点大 (或相等) ,按步数大的后扩展的要求,应该放在数据库的后面。而当前扩展的结点从数据 库前面选取,即符合先产生的先扩展,后产生的后扩展规律。所以数据库的结构用队列的结 构形式较合适。用上述记录为元素的数组 data 来表示数据库,并设置两个指针:closed 为队 列的首指针,open 为队列的尾指针。 产生规则。原规则规定空格周围的棋子可以向空格移动。但如果换一种角度观察,也可看作 空格向四周移动。这样处理更便于编程。如果空格位置在(si,sj) ,则有四条规则: (1)空格向上移动。If si-1>=1 then ch(si,sj):=ch(si-1,sj); ch(si-1,sj):=0 (2)空格向下移动。If si+1<=3 then ch(si,sj):=ch(si+1,sj); ch(si+1,sj):=0 (3)空格向左移动。If sj-1>=1 then ch(si,sj):=ch(si,sj-1); ch(si,sj-1):=0 (4)空格向右移动。If sj+1<=3 then ch(si,sj):=ch(si-1,sj); ch(si,sj+1):=0 用数组 DI 和 HJ 来表示移动的行列增量,则有: R 1 2 3 4 方向 左 上 右 下 DI 0 -1 0 1 HJ -1 0 1 0 搜索策略。按照问题分析中提出的方法,算法设计如下: Program num8; 初始化;把初始布局存入数据库 data; 设首指针 closed:=0; 尾指针 open:=1; Repeat Closed 增 1,取出队列首记录为当前被扩展结点; For r:=1 to 4 do {r 是规则编号} Begin If 新空格位置合法 then Begin

Open 增 1,并把新布局存入队尾; If 新布局与队列中原有记录重复 then 删除新产生的布局 Else if 达到目标 then 输出并退出; End; End; Until closed>=open; {队列空} 源程序如下; {$A-,B-,D-,E-,F-,G-,I-,L-,N-,O-,P-,Q-,R-,S-,T-,V-,X-,Y-} {$M 65521,0,655360} const fn1 ='input.txt'; fn2 ='output.txt'; type xtype =array[1..3,1..3] of 0..8; ctype =array[1..10000] of ^xtype; dtype =array[1..10000] of integer; var a,b :xtype; c :ctype; dep,father :^dtype; x0 :array[1..10000,1..2] of byte; procedure init; var f :text; i,j :integer; begin new(dep); new(father); for i:=1 to 10000 do new(c[i]); assign(f,fn1); reset(f); for i:=1 to 3 do for j:=1 to 3 do read(f,a[i,j]); for i:=1 to 3 do for j:=1 to 3 do read(f,b[i,j]); close(f) end; procedure calc; var i,j,k,l,x :integer; open,closed :integer; d :xtype; procedure bool;{判断当前状态是否到达目标状态} var i,j,k,l :integer; f :text; e :dtype; begin l:=0; for j:=1 to 3 do for k:=1 to 3 do if b[j,k]<>c[closed]^[j,k] then l:=1; if l=0 then begin assign(f,fn2); rewrite(f); j:=0; repeat

inc(j); e[j]:=closed; closed:=father^[closed] until closed=0; for k:=j downto 1 do begin for i:=1 to 3 do begin for j:=1 to 3 do write(f,c[e[k]]^[i,j]:3); writeln(f) end; writeln(f) end; close(f); halt end{输出答案} end; procedure cheakup;{判断是否重复,如果是则删掉当前状态} var i,j,k,l :integer; begin for i:=1 to closed-1 do begin l:=0; for j:=1 to 3 do for k:=1 to 3 do if c[i]^[j,k]<>c[closed]^[j,k] then l:=1; if l=0 then begin dec(closed); exit end end; bool end; begin open:=0; closed:=1; c[closed]^:=a; dep^[closed]:=0; father^[closed]:=0; bool; for i:=1 to 3 do for j:=1 to 3 do if a[i,j]=0 then begin x0[1,1]:=i; x0[1,2]:=j end; repeat inc(open); d:=c[open]^; i:=x0[open,1]; j:=x0[open,2]; k:=dep^[open]; if i>1 then{空格向上移动} begin inc(closed); c[closed]^:=d; c[closed]^[i,j]:=c[closed]^[i-1,j]; c[closed]^[i-1,j]:=0; dep^[closed]:=k+1; father^[closed]:=open; x0[closed,1]:=i-1; x0[closed,2]:=j; cheakup end; if i<3 then{空格向下移动} begin

inc(closed); c[closed]^:=d; c[closed]^[i,j]:=c[closed]^[i+1,j]; c[closed]^[i+1,j]:=0; dep^[closed]:=k+1; father^[closed]:=open; x0[closed,1]:=i+1; x0[closed,2]:=j; cheakup end; if j>1 then{空格向左移动} begin inc(closed); c[closed]^:=d; c[closed]^[i,j]:=c[closed]^[i,j-1]; c[closed]^[i,j-1]:=0; dep^[closed]:=k+1; father^[closed]:=open; x0[closed,1]:=i; x0[closed,2]:=j-1; cheakup end; if j<3 then{空格向右移动} begin inc(closed); c[closed]^:=d; c[closed]^[i,j]:=c[closed]^[i,j+1]; c[closed]^[i,j+1]:=0; dep^[closed]:=k+1; father^[closed]:=open; x0[closed,1]:=i; x0[closed,2]:=j+1; cheakup end; until (open>=closed)or(closed>=10000); end; procedure print;{输出无解} var f :text; begin assign(f,fn2); rewrite(f); writeln(f,'No solution!'); close(f) end; begin init; calc; print end. 运行上面程序的结果为: 283 283 203 023 123 123 164 → 104 → 184 → 184 → 084 → 804 705 765 765 765 765 765 上述程序产生的搜索图如图 所示, 其中每个布局旁的数字是产生的顺序号。 从搜索图中可 以看出, 程序运行中, 先产生深度为 1 的所有结点, 然后再产生深度为 2 的所有结点, ??, 最后产生含有目标深度为 5 的结点结束。先往“横向”扩展,再往纵向深入,因此称为广度 优先搜索。

程序运行产生结点过程图

?

基本方法

综上所述,广度优先的基本算法如下: Program BFS; 初始化;建立数据库 data;初始状态存入数据库 data; 设队列首指针 closed:=0; 队列尾指针 open:=1; Repeat Closed 增 1,取出 closed 所指结点进行扩展; For r:=1 to rmax do {r 为产生规则编号} Begin If 子结点符合条件 then Begin Open 增 1,并把新结点存入数据库队尾; If 新结点与原有结点重复 then 删去该结点(open 减 1) Else if 新结点即目标 then 输出并退出; End; End; Until closed>=open; {队列空} 从上例可以看出,广度优先搜索法可以求出步数最少的解,即深度最少的解。 与深度优先搜索类似,不同的问题,用广度优先搜索的基本算法是一样的,但在数据库 的表示方法、 产生的结点是否符合条件和重复的判断上可以有不同的编程技巧, 程序的运行 效率也有所不同。以八数码问题为例,上面的程序中用 3*3 的二维数组表示布局比较直观, 但在判断重复,判断是否达到目标方面,却给程序增加了复杂性,也影响了运行速度。可以 改 用 字 符 串 形 式 来 表 示 布 局 。 例 如 初 始 布 局 表 示 为 “ 283164705 ” ,目标布局表示为 “123804765” 。 产生规则也必须作相应改动。设空格当前位置是 SI,则有: (1)空格向上移动:空格的位置减 3,即交换 SI 和 SI-3 的字符; (2)空格向左移动:空格的位置减 1,即交换 SI 和 SI-1 的字符; (3)空格向右移动:空格的位置加 1,即交换 SI 和 SI+1 的字符; (4)空格向下移动:空格的位置加 3,即交换 SI 和 SI+3 的字符。 如设规则编号为 k,则上述四条规则可归纳为一条: 交换 SI 和 SI+(2*k-5)的字符 布局用字符串表示, 使得判断重复过程和判断目标的过程变得很简单, 只需判断两个字符串 是否相等就可以了。按照上述的改进,读者可自己编制的解八数码问题的程序。 【例题】翻币问题。有 N 个硬币(N≥6)正面朝上排成一排,每次将 5 个硬币翻过来放在 原位置, 直到最后全部硬币翻成反面朝上为止。 编程让计算机找出步数最少的翻法并把翻币 过程及次数打印出来(用 O 表示正面,*表示反面) 。 【分析】由于问题要求找出最少步骤,用广度优先搜索法来求解。表面看,翻币的过程与正 反面硬币的排列位置有关, 但只要经过仔细分析会发现: 实际上翻币过程仅与硬币正反面的 个数有关,与它们的位置是无关的。例如下面两种状态: O * O * O * O O 和* * * O O O O O 都只要把 5 个正面朝上的硬币翻过来就达到了目标。 因此在搜索过程中只需考虑当前状态正 面朝上的个数。又如,如果当前状态是:* * * O O * * * 翻第 1,2,4,6,8 个得到:O O * * O O * O 而翻第 3,5,6,7,8 个得到:* * O O * O O O

这两种翻法虽翻的硬币不同,但都是把原状态中 4 个反面朝上 1 个正面朝上的硬币翻过来。 结果状态不同,但都有 5 个硬币正面朝上,再翻一次就都可以达到目标。所以产生规则也只 需考虑翻正面朝上的硬币的个数不同就可以了。 建立产生式系统。其中:综合数据库。综合数据库中每个记录设计为三项:当前状态中硬币 正面朝上的个数,父结点位置,由父结点翻了几个正面朝上的硬币得到当前状态。数据库本 身用队列形式。 产生规则有六条,即翻 R 个正面朝上的硬币: if 当前结点正面朝上的硬币个数 M≥R 且反面朝上的个数≥5-R then 子结点 data=(M-R)+(5-R) {R=0,1,2,??,5} 搜索策略。采用广度优先搜索法求解。源程序如下: {$A-,B-,D-,E-,F-,G-,I-,L-,N-,O-,P-,Q-,R-,S-,T-,V-,X-} {$M 65521,0,655360} var n :integer; a :array[1..8000,1..3] of integer;{数据库} b :array[0..8000] of boolean;{标志数组——判重} {a[i,1]:父节点编号} {a[i,2]:M_zhengmiancaoshang} {a[i,3]:fanlejige} procedure calc; var r,m :integer; open,closed :integer;{open、closed 为队列的首位指针} procedure print; var i,j,k,l,h :integer; d :array[1..5000] of integer; st :array[1..5000] of char; begin write('step 0: '); for i:=1 to n do write('o'); writeln; for i:=1 to n do st[i]:='o'; j:=0; i:=closed; repeat j:=j+1; d[j]:=i; i:=a[i,1]; until i=0; for i:=j-1 downto 1 do begin k:=a[d[i],3]; l:=5-k; for h:=1 to n do if st[h]='o' then begin if k>0 then begin dec(k); st[h]:='*' end end else begin if l>0 then begin dec(l); st[h]:='o' end end; write('step',j-i:4,': '); for h:=1 to n do write(st[h]); writeln end; halt end; begin fillchar(b,sizeof(b),true); b[n]:=false;

open:=0; closed:=1; a[1,1]:=0; a[1,2]:=n; a[1,3]:=0; repeat inc(open); m:=a[open,2]; for r:=0 to 5 do if (m>=r)and(n-m>=5-r)and(b[m-r+5-r]) then begin inc(closed); b[m-r+5-r]:=false; a[closed,1]:=open; a[closed,2]:=m-r+5-r; a[closed,3]:=r; if a[closed,2]=0 then print end; until open>=closed; writeln('No answer!');{输出无解} end; begin writeln('Input n:'); readln(n); if n<6 then writeln('Input error!') else calc end. 【例题】有两个无刻度标志的水壶,分别可装 x 升和 y 升(x、y 为整数,x、y<=100)的水, 设另有一水缸,可用来向水壶灌水或倒出水,两水壶间,水也可以相互倾灌。已知 x 升壶为 满壶,y 升壶为空壶。问如何通过倒水或灌水操作,用最少步数能在 y 升壶中量出 z(<=100) 升的水来。 【分析】 本题要求最少步数, 显然应采用广度优 水缸 y升 先搜索。设 A 水壶内有 a 升水,B 水壶内有 b 升水, x 升 则最多会有六种产生规则: (1)当 a>0 且 b<y 时,可以从水壶 A 倒 MIN A 水壶 B 水壶 (a,y-b)升水给水壶 B。这时水壶 A 内有 a-MIN(a,y-b) 升水;水壶 B 内有 b+MIN(a,y-b)升水; a升 b升 a升 b升 (2)当 b>0 且 a<x 时,可以从水壶 B 倒 MIN(b,x-a) 升水给水壶 A。这时水壶 A 内有 a+MIN A 水壶
B 水壶 A 水壶 B 水壶

(b,x-a)升水;水壶 B 内有 b+MIN(b,x-a)升水;
a升

水缸

a升 A 水壶

水缸

A 水壶

(3)当 a>0 时,可以从水壶 A 倒 a 升水给水缸 4、当 a<x 时,可以从水缸倒 x-a 升水给水壶 A 这时水壶 A 内有 0 升水; 这时水壶 A 内有 x 升水, 水壶 B 内有 b 升水; 水壶 B 内有 b 升水;
B 水壶 a升 B 水壶

水缸

a升

水缸

(4)当 b>0 时,可以从水壶 B 倒 b 升水给水缸水壶 B 这时水壶 A 内有 a 升水;水壶 B 内有 0 升水; (5)当 b<y 时,可以从水缸倒 y-b 升水给这时水壶 A 内有 a 升水水壶 B 内有 y 升水。 初始时,水壶 A 内有 x 升水,水壶 B 内有 0 升水。 综合数据库: 可用一个记录类型描述一个状态: atype=record father,a,b:word;

end; father 记录当前节点的父亲节点的编号,a、b 表示当前状态中,水壶 A 和水壶 B 里各有多 少水。 整个数据库可用一个以为数组 DATA[1..10000] of atype;另外用一个标志数组 bool, 当 bool[I, j]为真,表示水壶 A 为 I 升,水壶 B 为 j 升的状态还没有产生过,反之则表示已产生过。源 程序如下: {$A-,B-,D-,E-,F-,G-,I-,L-,N-,O-,P-,Q-,R-,S-,T-,V-,X-} {$M 65521,0,655360} type atype =record father,a,b:word; end; btype =array[0..100,0..100] of boolean; var x,y,z :word; data :array[1..10000] of atype; bool :^btype; procedure calc;{广搜} var i,j,k,l :word; open,closed :integer; function min(a,b:word):word;{求较小值} begin if a<b then min:=a else min:=b end; procedure print;{输出} var i,j :integer; d :array[1..10000] of integer; begin j:=0; i:=closed; repeat j:=j+1; d[j]:=i; i:=data[i].father until i=0; for i:=j downto 1 do writeln('setp ',j-i:3,':',data[d[i]].a:5,data[d[i]].b:5); readln; halt{结束} end; procedure evaluate(i,j:word);{赋值} begin bool^[i,j]:=false; inc(closed); data[closed].a:=i; data[closed].b:=j; data[closed].father:=open; if j=z then print end; begin new(bool); fillchar(bool^,sizeof(bool^),true); open:=0; closed:=1; bool^[x,0]:=false; data[1].a:=x; data[1].b:=0; data[1].father:=0; if (z=x)or(z=0) then print; repeat inc(open); i:=data[open].a; j:=data[open].b; k:=min(i,y-j); l:=min(x-i,j); if (i>0)and(j<y)and(bool^[i-k,j+k]) then evaluate(i-k,j+k); if (j>0)and(i<x)and(bool^[i+l,j-l]) then evaluate(i+l,j-l); if (i>0)and(bool^[0,j]) then evaluate(0,j); if (j>0)and(bool^[i,0]) then evaluate(i,0);

if (i<x)and(bool^[x,j]) then evaluate(x,j); if (j<y)and(bool^[i,y]) then evaluate(i,y){六种产生规则} until open>=closed; writeln('No answer!'); readln{输出无解} end; begin writeln('Input x,y,z:'); readln(x,y,z); calc end. 【例题】房间问题。图 4-9 意示出了一张建筑平面图,编程计算:该建筑中有多少个房间; 最大的房间有多大,拆除建筑中的某一堵墙,以形成一个尽可能大的房间,指出该墙。该建 筑分成 m*n 割方块(m≤50,n≤50) ,每个方块可有 0~4 堵墙(0 表示无墙) 。 1 2 3 4 5 6 7 N 1 W 2 S
图 4-9 建筑平面图 3 输入数据:平面图以数字形式存储,用一个数字表示一个方块。 4 (1)文件开始是南北方向的方块数,其次是东西方向的方块数。 (2)后面的行中,每个方块中墙的特征由数字 p 来描述(0≤p≤15) 。数字 p 是下面的可能 取的数字之和:1(西墙 west)2(北墙 north)4(东墙 east)8(南墙 south) 。 (3)建筑中至少有两个房间。例: 输入: 2 3 15 3 14 11 12 15 输出: 3 {三个房间} 4 {有四个方块} (1,1) (1,2) {拆除方格(1,1) (1,2)之间的墙} 【分析】 该题要求根据建筑平面图中每个方块的墙的特征字得出: 房间分布情况和求最佳拆 墙方案。 其中问题 1 的解是问题 2 的解的基础。 因为只有计算出各房间拥有的方块数以及房 间之间的隔墙情况,才能明确拆除那堵墙后可形成尽可能大的房间。 (1)明确每个方块中的设墙情况。程序从文件中输入 m*n 个 0..15 的数,每个数字描述了 一个方块中墙的特征,即下面的可能取的数字之和: 1(西墙 west)2(北墙 north)3(东墙 east)4(南墙 south) 将方格中墙的特征字转换成一个四位二进制数,每一位对应一个方向的墙。 D3 D2 D1 D0

E

(2,1) 方向 :南墙 东墙 北墙 西墙 方向数: 3 2 1 0 若 DI 位为 1,表示该方格的 I 方向上有一堵墙; 若 DI 位为 0,表示该方格的 I 方向上无墙,该方块与 I 方向上的相邻块同属一个房间(0≤I ≤3) ,例如: (2,1)方块的墙的特征字为 13, (11)10=(1011)2。即: (2,1)方块的墙的南 面、北面、西面各有一堵墙。 (2)求房间的分布。虽然求出了每个方块中的设墙情况,但由于除周边外的中间方块中, 每堵墙被位于墙两面的方块各定义一次, 因此还不能得出有多少个房间, 每个房间拥有那些

方块。 接下来的问题是将建筑平面划分为若干连通的闭区域, 这种区域亦称面。 面有墙围成, 两两面之间无公共方块。 对每一面着一种序号的颜色, 这个颜色序号对应该面内方块所在的 房间序号。 对建筑平面图的着色方案勾勒出建筑中房间的分布情况, 其颜色数即为房间总数。 从(1,1)方块出发,由上而下、从左至右搜索一个目前未着色的块 (x,y)。运用广度优先搜 索的方法求(x,y)所在的面,对该面着一种新颜色。运用一次宽度优先搜索,可以确定一 个面的所有方块,完成一个面着色。反复搜索,直到所有方块被着色时就求出了所有面。 (3)求最佳拆墙方案。有了房间的分布情况,求最佳拆墙方案便不难了,搜索最佳拆墙方 案的算法如下: 设 best:为目前最大房间的面积,搜索前初始化为 0;按由上而下,由左至右搜索每一方块 (i,j)的相邻格;若(I,j)与(I,j)k(0≤k≤1)方向的相邻块(x,y)分属两个房间 且两个房间的面积之和大于 best,则: best: (I,j)所属房间面积+(x,y)所属房间面积;记下两个方块(i,j)和(x,y) 。 源程序如下: const fn1 ='room.in'; fn2 ='room.out'; dig :array[0..3] of integer=(1,2,4,8); {dig[I]——第[I]位二进制数的权} way :array[0..3,1..2] of integer=((0,-1),(-1,0),(0,1),(1,0)); {way[I,1]——方向 I 的垂直增量;way[I,2]——方向 I 的水平增量} var n,m :integer; {n:平面图南北方向的长度,m:平面图东西方向的长度} total,max :integer; {total 为房间总数,max 为最大房间包含的方块数} x1,x2,x3,x4 :integer; {表示应拆除方格(x1,x2)与方格(x3,x4)之间的那堵墙} a :array[1..50,1..50,0..3] of boolean; {0:west 西墙} {1:north 北墙} {2:east 东墙} {3:south 南墙} {当 a[I,j,k]为真时:方块(I,j)的 k 方向无墙,否则有墙} b :array[1..50,1..50] of integer; {若 map[I,j]=0,则(I,j)方块未被检查过,否则为方块(I,j)所属的房间号} area :array[1..2500] of integer; {area[I]:第 I 个房间的面积} list :array[1..2500,1..2] of integer; {open 表,closed 表} procedure init;{输入} var f :text; i,j,k,p :integer; begin assign(f,fn1); reset(f); readln(f,n,m); fillchar(a,sizeof(a),true);{初始化,假设所有方格四面无墙} for i:=1 to n do for j:=1 to m do begin read(f,p);{读入特征字 p} for k:=3 downto 0 do if p>=dig[k] then begin a[i,j,k]:=false; dec(p,dig[k]) end {将特征字转换为四周设墙的情况} end; close(f) end;

procedure print;{打印} var f :text; begin assign(f,fn2); rewrite(f); writeln(f,total); writeln(f,max); writeln(f,'(',x1,',',x2,')','(',x3,',',x4,')'); close(f) end; procedure calc1;{计算房间数即每个方块所属的房间} var i,j,k,x,y :integer; open,closed :integer; begin fillchar(b,sizeof(b),0);{置所有方块未检查标志} fillchar(area,sizeof(area),0);{所有房间的面积初始化为 0} total:=0; i:=1; j:=0; repeat inc(total); repeat{搜索未确定房间的方块(I,j)} inc(j); if j>m then begin j:=1; inc(i) end until (i>n)or(b[i,j]=0); if i>n then exit;{若所有方块都已检查则退出} fillchar(list,sizeof(list),0); list[1,1]:=i; list[1,2]:=j; b[i,j]:=total; area[total]:=1; open:=0; closed:=1; repeat inc(open); x:=list[open,1]; y:=list[open,2]; for k:=0 to 3 do if a[x,y,k] and (b[x+way[k,1],y+way[k,2]]=0) then begin inc(closed); inc(area[total]); list[closed,1]:=x+way[k,1]; list[closed,2]:=y+way[k,2]; b[list[closed,1],list[closed,2]]:=total end until open>=closed until false end; procedure calc2;{计算最大房间所含的方块数,即拆除那一堵墙可得最大房间} var i,j :integer;

newmax :integer;{拆除一堵墙后最大房间所含的方块数} procedure evaluate(k,l:integer);{计算、比较、赋值} begin if (b[i,j]<>b[k,l])and(area[b[i,j]]+area[b[k,l]]>newmax) then begin newmax:=area[b[i,j]]+area[b[k,l]]; x1:=i; x2:=j; x3:=k; x4:=l {若(i,j)方块(k,l)属于两不同房间且两个房间 的面积和大于当前的最大面积,则记录下新的最大面积以及这两个方块的编号} end end; begin dec(total); max:=0; newmax:=0; for i:=1 to total do if area[i]>max then max:=area[i]; {计算最大房间的面积} for i:=1 to n-1 do for j:=1 to m do evaluate(i+1,j); {判断拆除东西方向之间的墙} for i:=1 to n do for j:=1 to m-1 do evaluate(i,j+1) {判断拆除南北方向之间的墙} end; procedure main; begin calc1; calc2 end; begin init; main; print end. 此题也可用深度优先搜索,但由于数据规模比较大,搜索的深度最多可达到 5000 左右,肯 定会造成堆栈溢出,所以不宜采用,这里不再阐述。感兴趣的读者可以思考深搜的算法。

?

优化方法

广度优先搜索是另一类常用的搜索方法, 从搜索方法自身的特点而言, 广度优先搜索的 效率是远高于深度优先搜索的,这是因为就一棵搜索树而言,解的分布情况是不知道的,深 度优先搜索在某些时候就会出现困死在某一个不存在解的树枝当中不断搜索的情况, 而广度 优先搜索则不会出现这样一种情况, 但是广度优先搜索存在着一个相当大的弊病, 就是扩展 的节点的个数是成几何级数膨胀的, 很快就导致内存溢出的情况。 为了避免这些情况的出现, 这里介绍几种优化广度优先搜索的算法。 根据算法的特点, 把主要的优化方法分为搜索策略 上的优化和状态存储中的优化两大类。 搜索策略上的优化 搜索策略上的优化,主要介绍 A*算法和双向搜索。 所谓 A*算法,又称之为启发式搜索,主要是在搜索的过程中,选择较好的方法来扩张 节点。在广度优先搜索当中,扩张出来的节点与目标节点的接近程度是不相同的,当然希望 拿那些与目标节点越接近的节点来进行扩张, 查找这些节点的方法是: 对每个节点设计一个 估价函数:f(n)=d(n)+w(n),d(n)表示该节点在搜索树中的深度,w(n)表示该节点与目标节点 接近程度,称这个函数为启发函数。为了更好的解释这个估价函数,来看一个例题。

【例题】八数码问题 【分析】采用估价函数:f(n)=d(n)+w(n)。其中 d(n)是搜索树中节点 n 的深度,w(n)适用以计 算当前节点 n 的状态表述中错放位的棋子数(与目标状态比较) 。每次选取 f(n)值最小的节 点进行扩展。运用这种方法在求解问题的过程当中扩展的节点明显减少了很多。 在 f(n)=d(n)+w(n)当中:若 w(n)=0,不体现任何启发信息,若 f(n)= d(n),它反映的就是 广度优先搜索的过程。下面是利用 A*算法解决八数码问题的源程序: program ex5-3; type Arr = array [1 .. 3, 1 .. 3] of Byte; const t1: arr=((2, 8, 3), (1, 6, 4), (7, 0, 5));{初始状态} t2: arr=((1, 2, 3), (8, 0, 4), (7, 6, 5));{目标状态} Mo: array [1 .. 4, 1 .. 2] of ShortInt = ((0, -1), (0, 1), (1, 0), (-1, 0)); Max = 4000; var a: array [1 .. Max] of Arr;{存储状态的队列} U: array [1 .. Max] of Boolean; Po: array [1 .. Max] of Integer; F, H, Space: array [1 .. Max] of Byte; Wei: array [1 .. 8, 1 .. 2] of Byte; W: array [1 .. 50] of Integer; dd: array [1 .. 8] of Byte; db: array [1 .. 8] of Byte; q, i, j, k, l, q2, min, x0, y0, x1, y1: Integer; c: Boolean; procedure Print(t : Integer);{输出} var m, ii, jj, kk: Integer; begin Writeln(t, ' ', h[t]); m := 0; kk := t; repeat Inc(m); w[m] := kk; kk := Po[kk]; until kk = 0; for ii := m downto 1 do begin Writeln('Step.', m - ii); for jj := 1 to 3 do begin for kk := 1 to 3 do Write(a[w[ii], jj, kk]); Writeln; end; Readln; end; c := True; end; function Compute(t: Integer): Integer;{计算估价函数} var ii, s, jj, kk: Integer; begin s := 0; for ii := 1 to 3 do for jj := 1 to 3 do if a[t, ii, jj] <> 0 then

begin kk := a[t, ii, jj]; s := s + abs(ii - wei[kk, 1]) * dd[kk] + abs(jj - Wei[kk, 2]) * dd[kk]; end; if s = 0 then Print(t); if a[t, 2, 2] <> 0 then s := s + 5; compute := s + h[t]; end; function Fang: Boolean; var ii, jj, kk: Integer; ff: Boolean; begin for ii := 1 to q2 do if Space[ii] = 1 then begin jj := 0; ff := False; repeat Inc(jj); k := 0; repeat Inc(kk); if a[ii, jj, kk] <> a[q2 + 1, jj, kk] then ff := true; until (kk = 3) or ff; until (jj = 3) or ff; if not (ff) then begin if h[ii] > h[q] + 1 then begin f[ii] := f[ii] - h[ii] + h[q] + 1; h[ii] := h[q] + 1; u[ii] := true; po[ii] := q end; fang := False; exit; end; end; Fang := True; end; begin {主程序} for i := 1 to 3 do for j := 1 to 3 do if t2[i, j] <> 0 then begin Wei[t2[i, j], 1] := i; Wei[t2[i, j], 2] := j; end; for i := 1 to 8 do dd[i] := 1; for i := 1 to 3 do for j := 1 to 3 do if t1[i, j] <> t2[i, j] then dd[t1[i, j]] := 2; a[1] := t1; f[1] := 0; po[1] := 0; h[1] := 1; Space[1] := 32; u[1] := True; q2 := 1; c := False; Repeat{广度优先搜索过程} Min := 1000; for i := 1 to q2 do if U[i] and (Min > f[i]) then begin

Min := f[i]; q := i end; u[q] := False; Writeln(q); x0 := space[q] div 10; y0 := space[q] mod 10; for i := 1 to 4 do begin x1 := x0 + mo[i, 1]; y1 := y0 + mo[i, 2]; if (x1 > 0) and (x1 < 4) and (y1 > 0) and (y1 < 4) then begin a[q2 + 1] := a[q]; a[q2 + 1, x0, y0] := a[q2 + 1, x1, y1]; a[q2 + 1, x1, y1] := 0; l := x1 * 10 + y1; if Fang then begin Inc(q2); po[q2] := q; space[q2] := l; h[q2] := h[q] + 1; f[q2] := compute(q2); u[q2] := True; end; end; end; until c; end. 某些问题,其规则既可以正向使用,也可以逆向使用,两个方向(目标节点到初始节点 和初始节点到目标节点)同时搜索,就称为双向搜索。当两个方向的搜索边域以某个方式会 合时,就终止搜索过程。应用双向搜索应注意下列几点: (1)问题应有明确的目标状态; (2)判定双向搜索域的会合是关键,要建立可行、准确的识别法则; (3)双向搜索的费用可能会比单项搜索费用大。应注意内存溢出的处理。如果判定边 域会合错误,节点的扩展可能是单向搜索扩展节点的两倍。 【例题】由 8 个方格构成图,间隔为虚线的表示可以通过,五枚棋子编号如图 5-1 所示,或 由键盘输入。走棋子规则如下: (1)相邻的空格时序间隔时,棋子可以向此相邻空格前进。每次移动一格; (2)不允许跳过某一棋子或方格; (3)每移动一格,记为一步。 编程实现: (1)把棋子从左到右倒序排列在最下一层五个方格内,即为 54321; (2)移 动棋子的步数最少的不同走法的所有解。一枚棋子的走法不同,就可认为走法不同; (3)输 出格式应直观,易于对比查错。
初始状态 目标状态












棋子图









【分析】采用双向广度搜索解这道题。这道题双方向的状态变化虽然复杂,但很确定,且描 述表示不难。 根据状态变化的边域会合的识别法则: 双向每一方扩展一层后继子节点的状态 描述相同就结束搜索,给出问题的解答。

注意:第一判定搜索的会合边域,求出问题的所有解;第二防止数据溢出及识别双边搜 索步会合的可能情形,防止死机。源程序如下: const b: array [1 .. 8, 1 .. 8] of Byte = ((0, 1, 0, 0, 0, 0, 0, 0), (1, 0, 1, 0, 0, 1, 0, 0), (0, 1, 0, 0, 0, 0, 0, 0), (0, 0, 0, 0, 1, 0, 0, 0), (0, 0, 0, 1, 0, 1, 0, 0), (0, 1, 0, 0, 1, 0, 1, 0), (0, 0, 0, 0, 0, 1, 0, 1), (0, 0, 0, 0, 0, 0, 1, 0)); type Arr = array [1 .. 8] of Byte; var a: array [1 .. 2, 1 .. 3000] of Arr;{两个队列} Po: array [1 .. 2, 1 .. 3000] of Word; c: array [1 .. 5] of ShortInt; Q1, Q2, Q3, pp: array [1 .. 2] of Word; i, j, k, l, num, t, code: Integer; procedure Print;{输出} var m, p, r, s: Word; w: array [1 .. 50] of Word; begin m := 0; p := pp[1]; repeat Inc(m); w[m] := p; p := po[l, p]; until p=0; Inc(num); Writeln('No.',num); for r := m downto 1 do begin Writeln('Step.',m - r); Writeln(' ', a[1, w[r], 1], a[1, w[r], 2], a[1, w[r], 3]); for s := 4 to 8 do Write(a[1, w[r], s]); Writeln; Readln; end; p := po[2, pp[2]]; r := m - 1; repeat Inc(r); Writeln('Step.', r); Write(' '); for s := 1 to 3 do Write(a[2, p, s]); Writeln; for s := 4 to 8 do Write(a[2, p, s]); Writeln; Readln; p := po[2, p]; until p = 0; end; procedure Check; var ii, jj: Integer; begin for ii := q3[3 - i] to q2[3 - i] - 1 do begin jj := 0; repeat Inc(jj);

if a[i, q2[i], jj] <> a[3 -i, ii, jj] then jj := 9; until jj >= 8; if jj = 8 then begin pp[i] := q2[i]; pp[3 - i] := ii; print end; end; end; function Kill : Boolean;{状态是否已经扩展} var ii, jj: Integer; f: Boolean; begin ii := 0; repeat Inc(ii); jj := 0; f := True; repeat Inc(jj); if a[i, q2[i], jj] <> a[i, ii, jj] then f := False; until (jj = 8) or not f; until f or (ii = q2[i] - 1); Kill := f; end; begin FillChar(c, SizeOf(c), 0); Writeln('Please input Number ...'); for j := 4 to 8 do begin repeat Write('Number ', j - 3, '='); Readln(a[1, 1, j]); code := ioresult; if (code <> 0) or (c[a[1, 1, j]] <> 0) or not (a[1, 1, j] in [1 .. 5]) then Writeln('Input Error!'); until (code = 0) and (c[a[1,1,j]] = 0) and (a[1, 1, j] in [1 .. 5]); c[a[1, 1, k]] := 1; end; po[1,1] := 0; po[2, 1] := 0; a[1, 1, 1] := 0; a[1, 1, 2] := 0; a[1, 1, 3] := 0; a[2, 1, 1] := 0; a[2, 1, 2] := 0; a[2, 1, 3] := 0; for i := 4 to 8 do a[2, 1, i] := i - 3; q2[1] := 1; q3[1] := 1; q2[2] :=1; q3[2] := 1; num := 0; repeat{广度优先搜索} for i := 1 to 2 do begin q1[i] := q3[i]; q3[i] := q2[i] + 1; Writeln(q1[i]:3, ' ', q2[i]:3); for j := q1[i] to q2[i] do begin for k := 1 to 7 do for l := k + 1 to 8 do if (b[k, l] = 1) and (a[i, j, k] + a[i, j, l] <> 0) and (a[i, j, k] * a[i, j, l] = 0) then begin Inc(q2[i]); a[i, q2[i]] := a[i, j]; t := a[i, q2[i], k]; a[i, q2[i], k] := a[i, q2[i], l]; a[i, q2[i], l] := t; if Kill then q2[i] := q2[i] - 1

else begin po[i, q2[i]] := j; check; end end; end; end; until num <> 0; end. 状态存储中的优化 在广度搜索当中, 扩张出来的新的节点总是有很大的重复, 必须对这些节点进行判重操 作,最简单判重方法是相当耗时的,它需要将新的节点与已经生成的节点分别进行比较,在 搜索的初期阶段,这一步的耗时是不明显的,但随着节点数目增大,判重的耗时相对就大大 增加,从而降低了算法的时间效率。为了省去这一个判重工作,往往是利用数据结构当中的 哈希表,下面结合例题来介绍这种利用哈希表的判重方法。 【例题】有一个 2*4 的矩形,在 8 个格子里放有 1-8 这 8 个数字,标准状态如下: 1 2 3 4 8 7 6 5 并提供了三条规则: (1)上下两行互相交换 (2)全体向右平移一格 (3)中间四个顺时针旋转 8 1 7 2 6 3 5 4 4 5 1 8 2 7 3 6 1 8 7 6 2 3 4 5

现在的问题是,如何使用这三条规则,使任意一种给定的状态转变为标准状态。 【分析】 看到这一问题, 首先想到的自然是广度优先搜索。 但是搜索中必然会出现许多重复, 大大的增加了时空复杂度,比如连用两次规则 A 显然是浪费的,因此需要判重。如果是用 传统的比较方法来排除重复的话,无疑将花去很多的时间,事实上也的确如此。而上面介绍 的双向搜索虽然可以缩小时空规模,但作用有限,本题又不适用上面提到的 A*算法,因此 需要研究新的方法。 受多维数组元素地址的计算方法的启发, 可以将魔板的每一种状态按以下规则对应于一 个双字节的整数 K: (1)用一维数组 S[1..8]表示一种状态。例如初始状态 S[i]=i; (2)令 T[i]表示 S[1..i-1]这 i-1 个数中,比 S[i]小的数的个数; (3) K ? ? T [i ] * (i ? 1)!
i ?1 8

可以证明 0—40319 之间的每一个整数都唯一的对应了一个 T 数列,也就是说,魔板的 每一个状态都与每一个整数一一对应。 ∵n!=(n-1)*(n-1)!+(n-1)! ∴n!=(n-1)*(n-1)!+(n-2)*(n-2)!+(n-3)*(n-3)!+……+2*2!+1*1!+1 n!-1=(n-1)*(n-1)!+(n-2)*(n-2)!+(n-3)*(n-3)!+……+2*2!+1*1! 这一式子类似于 10k-1=9*10k-1+9*10k-2+……+9*100,对于上面的结论就很容易证明了。 因此可以用一个 0—40319 的布尔型映射数组,初始状态为假。如果一种状态已经搜索 到,则将其对应的数组元素标记为真。判断一种状态是否与以前的状态重复的时候,只需要 检查该状态所对应的数组元素, 若为真则该状态一定已经搜索到了。 这样省略了查找工作的 时间量,虽然多花了 40k 的空间,却大大提高了时间效率。源程序如下: const

Fact: array [0 .. 7] of Word = (1, 1, 2, 6, 24, 120, 720, 5040);{数 0..7 的阶乘} Rule: array [1 .. 3, 1 .. 8] of Byte ={三种转换规则} ((8, 7, 6, 5, 4, 3, 2, 1), (4, 1, 2, 3, 6, 7, 8 ,5), (1, 7, 2, 4, 5, 3, 6, 8)); Obj = 40319;{目标状态编码} type TTable = array [1 .. 8] of Byte;{描述一个状态} TList = ^TNode;{搜索中的链表} TNode = object{搜索的一个结点} Now: Word;{当前状态} Next: TList; end; var t, t1: TTable; Head, Tail: TList;{搜索队列的头和尾} i, j: Byte; STate: array [0 .. 40319] of Byte;{描述状态是否一搜索到的映射数组} function Change1 : Word;{将状态转化为数} var i, j, s: Word; k: TTable; begin for i := 8 downto 1 do begin k[i] := 0; for j := 1 to i - 1 do if t[j] < t[i] then Inc(k[i]) end; s := 0; for i := 1 to 8 do Inc(s, k[i] * Fact[i - 1]); Change1 := s; end; procedure Change2(s : Word);{将数转化为状态} var i, j: Byte; b: array [1 .. 8] of Boolean; begin for i := 8 downto 1 do begin t1[i] := s div Fact[i - 1]; s := s mod Fact[i - 1]; end; FillChar(b, SizeOf(b), False); for i := 8 downto 1 do begin s := 1; for j := 1 to t1[i] do begin while b[s] do Inc(s); Inc(s) end; while b[s] do Inc(s);

t1[i] := s; b[s] := True end; end; procedure ReadIn; var i: Byte; begin Writeln('Input the init State'); for i := 1 to 8 do Read(t[i]); New(Head); Head^.Now := Change1; Head^.Next := nil; Tail := Head; if Head^.Now = Obj then Halt; FillChar(State, SizeOf(State), 0); State[Head^.Now] := 4; end; procedure Add(k : Word);{加入一个结点,如达到目标,则打印} begin New(Tail^.Next); Tail := Tail^.Next; Tail^.Now := k; Tail^.Next := nil; STate[k] := i; if k <> Obj then Exit; i := 0; repeat Write(Chr(State[k] + 64)); Change2(k); for j := 1 to 8 do t[j] := t1[Rule[State[k], j]]; k := Change1; Inc(i); until State[k] = 4; Writeln(' (', i, ')'); Halt; end; procedure Work;{搜索主过程} var q: TList; k: Word; begin repeat Change2(Head^.Now); for i := 1 to 3 do begin for j := 1 to 8 do t[Rule[i, j]] := t1[j]; k := Change1; if State[k] = 0 then Add(k) end; q := Head; Head := Head^.Next; Dispose(q); until Head = nil; Writeln('No answer'); end;

begin Readin; Work; end. 但是哈希表的运用并不是万能的, 因为哈希表本身也存在着一个很大的缺点, 就是其所 占用的空间很大, 在很多搜索问题当中哈希表都是无法定义的, 但是有的时候表面上看来哈 希表示无法定义的,但是可以采用压缩存储的方法进行定义。看下面这一个例题。 【例题】补丁与错误。 (CTSC99) 错误就是人们所说的 Bug。用户在使用软件时总是希望其错误越少越好,最好是没有错 误的。 但是推出一个没有错误的软件几乎不可能。 所有很多软件公司都在疯狂地发放补丁 (有 时这种补丁甚至是收费的) 。T 公司就是其中之一。 上个月,T 公司推出了一个新的字处理软件,随后发放了一批补丁。最近 T 公司发现其 发放的补丁有致命的问题, 那就是一个补丁在排除某些错误的同时, 往往会加入另一些错误。 此字处理软件只可能出现 n 个特定的错误,这 n 个错误是由软件公司本身决定的。T 公司目 前公发放了 m 个补丁,对于每一个补丁,都有特定的适用环境,某个补丁只有在当前软件 中包含某些错误而同时又不包含另一些错误时才可以使用, 如果它被使用, 它将修复某些错 误而同时加入某些错误。另外,使用每个补丁都要耗一定的时间(即补丁程序运行的时间) 。 更准确地说明如下: 此字处理软件中可能出现的 n 个错误为集合 B={b1,b2,??,bn}中的元素,T 公司目前 共发放了 m 个补丁:p1,p2,??,pm。对于每一个补丁 pi,都有特定的适用环境,某个补丁 只有在软件中包含某些错误而同时又不包含另一些错误时才可以使用, 为了说明清楚, 设错 误集合:Bi-、Bi+,当软件包含了 Bi+中的所有错误,而没有包含 Bi-中的任何错误时,补 丁 Pi 才可以被使用,否则不能被使用,显然 Bi+、Bi-交集为空。补丁 Pi 将修复某些错误而 同时加入某些错误,设错误集合为 Fi-、Fi+,使用过补丁 Pi 之后,Fi-中的任何错误都不会 在软件中出现,而软件将包含 Fi+中的所有错误。同样 Fi-,Fi+交集为空。另外,使用每个 补丁都要耗一定的时间(即补丁程序的运行时间) 。 现在 T 公司的问题很简单,其字处理软件的初始版本不幸包含了集合 B 中的全部 n 个 错误,有没有可能通过使用这些补丁(任意顺序地使用,一个补丁可以使用多次) ,使此字 处理软件成为一个没有错误的软件。如果可能,希望找到耗时最少的方案。 输入:输入文件第一行有两个正整数 n 和 m,n 表示错误总数,m 表示补丁总数,1≤n ≤20,1≤m≤100。接下来 m 行给出了 m 个补丁的信息。每行包括一个正整数(表示此补 丁程序 Pi 的运行耗时)和两个长度为 n 的字符串,中间用一个空格符隔开。 第一个字符串,如果第 K 个字符为‘+’ ,则表示 bk 属于 Bi+,若为‘-’ ,则表示 bk 属 于 Bi-,若为‘0’ ,则 bk 既不属于 Bi+又不属于 Bi-,即软件中是否包含 bk 不影响补丁 Pi 是否可用。 第二个字符串,如果第 K 个字符为‘+’ ,则表示 bk 属于 Fi+,若为‘-’ ,则表示 bk 属 于 Fi-,若为‘0’ ,则 bk 既不属于 Fi+又不属于 Fi-,即软件中是否包含 bk 不会因使用补丁 Pi 而改变。 输出:输出一个整数,如果问题有解,输出总耗时。否则输出 0。 示例输入 示例输出 33 8 1 000 001 000 0-+ 2 0-- -++ 【分析】这显然是一道求最优解的题目,以各类错误的出现情况为状态,可以计算出所有状 态的总数为 220 ? 1048576 。如果采用深度优先搜索的话,由于递归的层数过多,是不可行

的。 自然想到了广度优先搜索。 但是状态判重编程是棘手的问题, 是否还能够采用哈希表呢? 表面上看来,哈希表需要的空间为 2 20 byte ? 1024 Kb ? 1Mb 。但是一个 Byte 型的整数,是 由 8 个二进制为构成的,因此对于 8 个布尔类型的数,可以把它压缩成占一个字节的 Byte 型整数,这样一来哈希表所占用的空间就只需要 128Kb 了,程序是完全可以承受的。 在具体的实现过程当中,为了满足最优性,每次对权值最小的节点进行扩展,然后对新 生成的节点进行处理,如果某一个节点已经被扩展了,就不对其进行处理。如果这一个节点 处在队列之中还未被扩展, 则调整队列当中的这个节点的权值。 如果这个节点既不在队列之 中,又未被扩展则加入队列当中。 对于一个状态可以把其描述成为一个 01 串,串的长度为错误的总个数,0 表示没有这 个错误,1 表示有这个错误。然后把这个 01 串看作成一个二进制数,把它化成对应的十进 制数,这个十进制数就是一个对应的状态了。在搜索的过程当中,主要是利用哈希表来判断 状态是否已经进行过扩展。下面是对哈希表的定义: type TList=array[1..128]of Byte; var Hash: array[1..1024]of ^Tlist; 将状态 K(0≤K<1048576)是进行了扩展,那么把 Hash[k div 1024]^[k div 8 mod 128] ←Hash[k div 1024]^[k div 8 mod 128]+2 k mod 8。在判断如果某一个状态 k 已经被扩展了,那 么 Hash[k div 1024]^[k div 8 mod 128] div 2 k mod 8 mod 2 = 1。 状态存储的多少,是广度优先搜索的关键,为了提高算法解决问题的规模,必须使每一 个状态尽可能的简化, 存储状态也可以运用类似于上面提到的哈希表的压缩存储方法。 因此 说在记录每一个状态的时候也可以采用二进制的方法进行存储, 这样一来可以大大的减少存 储的空间。以下是源程序: const MaxN = 20; MaxM = 100; type TList = array[1 .. MaxN] of Shortint;{描述状态} THax = array[0 .. 127] of Byte; THaxAll = array[0 .. 1023] of ^THax;{哈希表} TPatch = object{记录一个补丁} CostTime: Integer; Condition, Result: TList; function ReadChar(const Ch : Char) : Shortint; constructor ReadLine; end; TLink = ^TNode;{记录队列} TNode = object State, Time: Longint; Next: TLink; procedure WorkOut(var Status : TList);{将数转化成为状态} end; TWork = object Appear: THaxAll;{哈希表} Open, Closed: TLink;{队列的头和尾} constructor Prepare; constructor CreateTList(const x : Integer; Lt : TList; var Ls : TList); function WorkIn(const Status : TList) : Longint;{将状态转化成为数} function CanUse(const x : Integer; Lt : TList) : Boolean;{判断某一个补丁是否可用}

function DonotHave(const x : Longint) : Boolean;{判断某一状态是否已经进行了扩展} procedure RecordState(const x : Longint);{记录一个以被扩展的节点} procedure Answer(const x : Integer); procedure Init; procedure Bfs; end; {Type definitions} var Patch: array[1 .. MaxM]of TPatch; n,m: Integer;{错误和补丁的个数} TestFile: Text; {Var for all program} function TPatch.ReadChar; begin ReadChar := 0; case ch of '-': ReadChar := -1; '+': ReadChar := 1; end; end; constructor TPatch.ReadLine; var ch: char; i: Integer; begin Read(TestFile, CostTime); Read(TestFile, Ch); for i := 1 to n do begin Read(TestFile, Ch); Condition[i] := ReadChar(Ch); end; Read(TestFile, Ch); for i := 1 to n do begin Read(TestFile, Ch); Result[i] := ReadChar(Ch); end; Readln(TestFile); end; {TPatch} constructor TWork.Prepare; var i: Integer; Lt: TList; begin for i := 0 to 1023 do begin New(Appear[i]); FillChar(Appear[i]^, SizeOf(Appear[i]^), 0) end; for i := 1 to n do Lt[i] := 1; New(Open);{初始化队列} Open^.State := WorkIn(Lt); Open^.Time := 0; Open^.Next := nil;

New(Closed); Closed^.Next := Open; end; constructor TWork.CreateTList; var i: Integer; begin FillChar(Ls, SizeOf(Ls), 0); for i := 1 to n do case Patch[x].Result[i] of 0: Ls[i] := Lt[i]; 1: Ls[i] := 1; -1: Ls[i] := 0; end; end; const Calc: array[0 .. MaxN - 1] of Longint = (1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 131072, 262144, 524288); function TWork.WorkIn; var Number: Longint; i: Shortint; begin Number := 0; for i := 1 to n do Inc(Number, Status[i] * Calc[i - 1]); WorkIn := Number; end; function TWork.DonotHave; var w1, w2, w3: Longint; begin w1 := x DIV 1024; w2 := x DIV 8 MOD 128; w3 := x MOD 8; if Appear[w1]^[w2] DIV Calc[w3] MOD 2 = 0 then DonotHave := True else DonotHave := False; end; const InputFileName = 'Bugs.In'; OutputFileName = 'Bugs.Out';{Const for input and output} procedure TWork.Answer;{输出} begin Assign(TestFile, OutputFileName); Rewrite(TestFile); Writeln(TestFile, x); Close(TestFile); Halt; end; procedure TWork.Init;{输入} var i : Integer; begin Assign(TestFile, InputFileName);

Reset(TestFile); Readln(TestFile, n, m); for i := 1 to m do Patch[i].ReadLine; Close(TestFile) end; procedure TWork.RecordState; var w1, w2, w3: Longint; begin w1 := x DIV 1024; w2 := x DIV 8 MOD 128; w3 := x MOD 8; Inc(Appear[w1]^[w2], Calc[w3]) end; function TWork.CanUse; var i: Integer; begin CanUse := False; for i := 1 to n do begin if (Lt[i] = 1) and (Patch[x].Condition[i] = -1) then Exit; if (Lt[i] = 0) and (Patch[x].Condition[i] = 1) then Exit; end; CanUse := True; end; procedure TWork.Bfs;{搜索主过程} var Lt, Ls: TList; i: Integer; NewState: Longint; Heap,p: TLink; procedure InsertNode; var q: TLink; begin q := Closed; while q^.Next <> nil do begin q := q^.Next; if q^.State = p^.State then{判断这个节点是否在队列当中} begin if q^.Time > p^.Time then q^.Time := p^.Time; Exit end; end; q := Closed; while q^.next <> nil do begin if p^.Time < q^.next^.Time then{将节点插入到队列当中} begin p^.Next := q^.next; q^.Next := p; Exit; end; q := q^.next;

end; p^.next := nil; q^.next := p; end; begin repeat Heap := Closed; Closed := Closed^.Next; Closed^.WorkOut(Lt); RecordState(Closed^.State); Dispose(Heap); if Closed^.State=0 then Answer(Closed^.Time); for i := 1 to m do{扩展节点} if CanUse(i, Lt) then begin CreateTList(i, Lt, Ls); NewState := WorkIn(Ls); if Donothave(NewState) then begin New(p); p^.State := NewState; p^.Time := Closed^.Time + Patch[i].CostTime; InsertNode; end; end; until Closed^.Next = nil; Answer(0); end; {TWork} procedure TNode.WorkOut; var i: Shortint; begin FillChar(Status, SizeOf(Status), 0); for i := 1 to n do Status[i] := State DIV Calc[i - 1] MOD 2; end; {TNode} var w: TWork; {var for main procedure} begin w.Init; w.Prepare; w.Bfs; end. 【例题】八数码问题(原题略) 。 【分析】 解决八数码问题的算法就不再介绍了, 这里再谈一谈状态存储当中的一些优化方法。 就第 4 章提到的状态描述的方法来看, 对于一个扩展出来的节点, 需要用 9 个字节来存储状 态,2 个字节来存储它的父亲节点,因此对于每一个节点,需要用 11 个字节来存储。然而 就一个简单的状态而言,如“012345678” ,如果用一个数来描述它的话,是小于 1000000000 的, 因此可以考虑用一个长整型数来进行存储, 这样一来存储一个状态所需要的字节数就降 到了 4 个字节。 采用这种方法存储节点可以比原来的方法存储的节点数多上将近一倍。 这样, 用长整型数存储状态,已经是非常好了,但是还可以进一步的优化存储方法。我们知道八数

码问题状态的总数为 9!种,因此 0 到 9!-1 这 9!个整数,每一个整数都可以相应的表示 一种八数码问题的状态, 并且可以保证每一个整数所对应的状态都是唯一的, 每个整数也唯 一的对应一种状态, 这个证明过程与上面的魔板问题的证明是一样的。 这样存储每一种状态 就只需要 3 个字节了。另外,由于状态的总数只有 9!种,因此可以采用压缩存储哈希表的 方法,来对状态进行判重。 在前面提到 A*算法的时候,那个估价函数的启发效率并不是很高,可以对 w(n)进行重新定 义。令 w(n)表示每一个数字目前的位置到它的目标位置的距离的总和。运用这种方法能够 扩展的节点数目达到了 30000 多个,能够出较多的解。(程序略)


相关文章:
C++基础复习
C++基础复习_计算机软件及应用_IT/计算机_专业资料。C++算法基础复习 NOIP2014 1...两个叫剩下的几个)——宽搜:spfa 的基础 inline void bfs() //深搜 //...
更多相关标签:
bfs广度优先搜索算法 | bfs广度优先搜索 | bfs c | c语言bfs 迷宫 | c语言 dfs bfs | c语言bfs | bfs c代码 | 广度优先搜索c语言 |