深优先搜索算法学习教案.pptx

会计学
1
深优先(yōuxiān)搜索算法
第一页，共32页。
深度优先搜索法有两大基本特点:
1． 对已产生的结点按深度排序，深度大的先得到扩展(kuòzhǎn)，即先产生它的子结点；2． 深度大的结点是后产生的，但先得到扩展(kuòzhǎn)，即“后产生先扩展(kuòzhǎn)”。因此用堆栈作为该算法的主要数据结构，存储产生的结点，先把产生的数入栈，产生站顶（即深度最大的元素）子结点，子结点产生以后，出栈，再产生栈顶子结点。
第1页/共32页
第二页，共32页。
一． 递归算法：递归过程为：procedure TRY(i);For r:=1 to maxr do (maxr是产生式规则数)begin If 子结点(jié diǎn)MR 符合条件 THEN begin
产生的子结点(jié diǎn)MR压入栈； IF 子结点(jié diǎn) MR是目标结点(jié diǎn) THEN 输出 ELSE TRY（I+1）; 栈顶元素出栈（删去MR）；
end;end;{**********main**********}program DFS;初始栈；TRY（1）；
第2页/共32页
第三页，共32页。
For r:=1 to maxr do
子结点mr符合条件
Y
产生的子结点mr入栈
输出
Try(I+1)
栈顶元素出栈（删去mr）
N
子结点(jié diǎn)mr是目标结点(jié diǎn)
N
Y
Try(I)
第3页/共32页
第四页，共32页。
二． 非递归算法program DFS(dep);dep:=0;repeat dep:=dep+1;j:=0;p:=false;
repeat
j:=j+1; if 子结点mr符合条件 then
产生子结点mr并将其记录 if 子结点是目标 then 输出并出栈(更新(gēngxīn)j) else p:=true; else if j>maxj then 回溯 else p:=false; until p=true;until dep=0;
第4页/共32页
第五页，共32页。
其中回溯过程如下：procedure backtracking;dep:=dep-1;if dep>0 then 取回(qǔ huí)栈顶元素else p:=true;
第5页/共32页
第六页，共32页。
Dep:=0
Dep:=dep+1
j:=0;p:=false;
j:=j+1;
产生子节点MR并记录
回溯
P:=false
输出并出栈
P:=true
Until p=false
Until dep=0
Y
N
Mr符合条件
子节点(jié diǎn)是目标
Y
N
Y
N
J>=maxj
第6页/共32页
第七页，共32页。
如图：A点有一个过河卒，需要走到目标B点。卒行走的规则：可以向下、或者向右。同时在棋盘上的任一点有一个对方的马（如图的C点），该马所在的点和所有串跳跃一步可达的点称为对方马的控制点。例如图中C点上的马可以控制9个点（图中的P1，P2，…，P8和C）。卒不能通过对方马的控制点。
棋盘用坐标表示，A点（0，0）、B点（n,m）（n,m为不超过20的整数，并由键盘输入），同样马的位置坐标是需要给出的（约定：C<>A,同时C<>B）。现在要求你计算出卒从A点能够(nénggòu)到达B点的路径的条数。
第7页/共32页
第八页，共32页。
A
1
2
3
4
5
6
7
8
Y
1
P5
P4
2
P6
P3
3
马
4
P7
P2
X
P8
P1
B(4,8)
第8页/共32页