广度宽度优先搜索.ppt

广度宽度优先搜索
现在学习的是第1页，共39页
深度搜索与广度搜索区分
[深度搜索与广度搜索]
深度搜索与广度搜索的区别：深度搜索下一次扩展的是本次扩展出来的子节点中的一个，而广度搜索扩展的则是本次扩展的节点的兄弟节点。
在具中留有一个空格，允许其周围的某一个将牌向空格中移动，如图1所示。这样通过移动将牌就可以不断改变的布局结构，给出一个初始布局（称初始状态）和一个目标布局（称目标状态），问如何移动将牌，才能实现从初始状态到目标状态的转换。
下面我们看看怎样用宽度优先搜索来解决八数码问题。
图2给出广度优先搜索应用于八数码难题时所生成的搜索树。搜索树上的所有结点都标记它们所对应的状态，每个结点旁边的数字表示结点扩展的顺序。粗线条路径表明求得的一个解。从图中可以看出，扩展第２６个结点，总共生成４６个结点之后，才求得这个解。此外，直接观察此图表明，不存在有更短走步序列的解。
现在学习的是第8页，共39页
八数码问题扩展搜索树
现在学习的是第9页，共39页
综合数据库（变量设置）
{Pxy}，其中1<=x,y<=3，Pxy∈{0,1,2,3,4,5,6,7,8}，且Pxy互不相等
用Pascal语言描述如下：
type
t8no = array[1..3,1..3]of longint; {棋盘状态 }
tList = record {描述一个节点}
Father : longint;　　　　　　　　 {父指针}
dep : longint;　　 {深度}
x , y : longint; {空格的位置}
state : t8no; 　　　　　　　　　　
end;
const
Max=10000;
var
s, t : t8no; {s为初始状态，t为目标状态}
List : array[0..max] of tList; {综合数据库 }
现在学习的是第10页，共39页
产生式规则（关系）
if　条件　then　规则；
设Pxy表示将牌第x行第y列的数码，m,n表示数码空格所在的行列值，记Pm,n=0,则可以得到如下四条规则：
① if n -1>=1 then begin Pm, n:=Pm,n -1­ ; Pm,n -1­ ­:=0 end;
② if m - 1>=1 then begin Pm, n:=Pm-1, n ; Pm-1, n :=0 end;
③ if n + 1<=3 then begin Pm, n:=Pm, n+1; Pm, n+1:=0 end;
④ if m + 1<=3 then begin Pm, n:=Pm+1­,n; Pm+1­, n:=0 end;
Const
Dir : array[1..4,1..2]of longint {对应四种产生式规则}
= ((1,0),(-1,0),(0,1),(0,-1));
现在学习的是第11页，共39页
控制策略
PROCEDURE Production-System；
DATA初始化数据库
Repeat
 在规则集中选择某一条可作用于DATA的规则R
  DATAR作用于DATA后得到的结果
     Until DATA满足结束条件
现在学习的是第12页，共39页
八数码问题宽度优先算法框架
List[1]=source;closed:=0;open:=1; {加入初始节点,List为扩展节点的表}
Repeat
closed:=closed+1; n:=List[closed]; {取出closed对应的节点}
For x:=1 to 4 do begin
new:=move(n,4); {对n节点使用第x条规则，得到new}
if not_appear(new,List) then begin {如果new没有在List中出现}
open:=open+1;List[open]:=new;{加入新节点到open}
List[open].Father:=closed; {修改指针}
if List[open]=Goal then GetOut;
end;
end
until clo