搜索算法-算法.ppt
文本预览下载声明
搜索算法——BFS;;
搜索顺序: A,(B,C,D),(E,F,G,H),(I,J,K,L);BFS;BFS;._.;迷宫问题：求从起点到终点的最短路径，并输出相应的点的坐标。;bfs算法流程如下：;const da:array[1..4]of integer=(0,1,0,-1);
db:array[1..4]of integer=(1,0,-1,0);
var t,m,n,i1,i2,j1,j2,i,j,closed,open:longint;
a:array[1..50,1..50]of longint;
h:array[1..1000]of record
a1,b1:longint;
end;
father:array[1..50]of longint;
f1,f2:text;
procedure printf;
var i:integer;
begin
t:=1;i:=open;
while father[i]1 do
begin
i:=father[i];
writeln(f2,h[i].a1,,,h[i].b1);
inc(t);
end;
writeln(f2,i1,,,j1);
writeln(f2,t);
close(f2);
halt;
end;;双向广度优先搜索;例题：;分析：
从初始状态和目标状态均按照深度优先搜索扩展结点，当达到以下状态时，出现相交点，如图1(a)，结点序号表示结点生成顺序。 双???扩展结点：
顺序 逆序
1 1
___AABBAA___ BAAAAB
2 / \ 3 2 / \ 3
__ABABAA__ AABABA ABAAAB BAAABA
4 / |5 \ 6 7 / \ 8 4 /
ABBAAA BAABAA ABAABA AAABBA AABAAB AABAAB
(a) 图1 (b)
顺序扩展的第8个子结点与逆序扩展得到的第4个子结点就是相交点，问题的最佳路径是：
[AABBAA]—[AABABA]—[AABAAB]—[ABAAAB]—[BAAAAB]
显示全部