广度优先搜索(3)

图1 程序：

program No8_DFS; {八数码的深度优先搜索算法}

Const

Dir : array[1..4,1..2]of integer = ((1,0),(-1,0),(0,1),(0,-1));

maxN = 15; ｛可以承受的最大深度｝ Type

T8No = array[1..3,1..3]of integer; tList = record state : T8No; x0,y0 : integer; end; Var

Source,Target : T8No;

List,Save : array[0..maxN]of tList; ｛综合数据库，最优解路径｝ Open,Best : integer;

procedure GetInfo; {见程序1} Function Same(A,B : T8No):Boolean; {见程序1} function Not_Appear(New : tList):boolean; {见程序1}

procedure Move(N : tList;d : integer;var ok : boolean;var New : tList);

{见程序1}

procedure GetOutInfo; {输出｝ var i,x,y : integer; begin

writeln('total = ',best); for i:=1 to best+1 do begin for x:=1 to 3 do begin

for y:=1 to 3 do write(Save[i].State[x,y],' '); writeln; end; writeln; end; end;

Procedure Recursive; ｛递归搜索过程｝ Var i : integer; New: tList; ok : boolean; Begin

If Open-1>=Best then exit;

If Same(List[Open].state,Target) then begin ｛如果找到解，保存当前最优解｝ Best:=Open-1; Save:=List; end;

For i:=1 to 4 do begin ｛依次选用规则｝ Move(List[Open],i,OK,New);

if ok and not_Appear(New) then begin ｛如果没有重复｝ inc(open); ｛插入综合数据库｝ List[Open]:=New;

Recursive; {继续搜索} dec(Open); {退栈} End; End; End;

procedure Main; {搜索主过程} var x,y : integer; begin

List[1].state:=Source; {初始化} for x:=1 to 3 do

for y:=1 to 3 do if Source[x,y]=0 then begin List[1].x0:=x; List[1].y0:=y; end;

Best:=MaxN;

搜索“diyifanwen.net”或“第一范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，第一范文网，提供最新人文社科广度优先搜索(3)全文阅读和word下载服务。