留言 | 关于 | 联系
神经网络 专家系统 自然语言其它知识
返回首页
当前位置: 首页 > 人工智能 > 其它知识 > 博奕5:广度搜索

博奕5:广度搜索

时间:2010-04-06 21:12来源:网络 作者:hitman 点击:
博奕棋类游戏设计教程的第五章,广度搜索及相关内容。

上一章介绍了深度搜索,现在我们来介绍广度搜索。为了使你对这两种搜索方式有一个较深刻的了解,再次我把它们做个比较。

我用下面的树来说明这两种搜索方式。节点a是搜索的起点,而节点i是我们搜索的目标。

先来看看深度搜索。深度搜索的搜索路径如下:

a-b
a-b-e
a-c
a-c-f
a-c-g
a-d-i

最后找到了节点i。它先找出与a相连的某个节点b,发现b下面还有节点e,由于是深度搜索,所以它就会访问节点e,此时发现e下面没有其它的节点了,于是就返回到节点b,同样b下面也没有其它的节点,于是就返回到节点a,节点a还有子节点c,所以就开始访问节点c,如此下去,直到找到节点i。

而广度搜索的路径如下:

a-b
a-c
a-d
a-b-e
a-c-f
a-c-g
a-d-i

这种搜索方式先考察a的所有子节点b、c和d,当它没有发现目标时就再考虑这些子节点的子节点,直到找到目标。这也是它取名为广度搜索的原因。

广度搜索的Prolog程序与深度搜索一样简单:

%append(L1,L2,L3).当列表L3是L1与L2连接而成时,append/3谓词成功。
append([],X,X).
append([A|X],Y,[A|Z]):-append(X,Y,Z).

sub(a,b).
sub(a,c).
sub(a,d).
sub(b,e).
sub(c,f).
sub(c,g).
sub(d,i).
sub(d,h).

route([],X,X).
route(Links,Current,Des):-
route(PreLinks,Current,Next),
sub(Next,Des),
append(PreLinks,[Next],Links).

?-route(L,a,f).
L=[c,f]
append/3谓词的作用是把两个表合成为一个表。上面的route/3使用广度搜索来找出答案。我们不难看出广度搜索与深度搜索的区别就是:广度搜索是递归在前,而深度搜索是递归在后。其实从逻辑上理解上面的route/3的编写方法是不难的,不过许多人都不会满足于这种逻辑上的理解,而希望能够了解程序的运行流程。广度搜索的运行流程比较复杂,我们来仔细研究一下。下面是单步跟踪的结果:

?-route(L,a,f)%与route(2)匹配
CALL:(2)route/3
L=H23,Current=a,Des=f
CALL:(1)route/3%route谓词的第一个目标就是递归调用route/3,
它与第一条route子句匹配。
PreLinks='[]'Current=aNext=a%匹配后的结果

EXIT:route/3
FAIL:sub/2%第二个目标就成了sub(a,f),因为Des与Next分别绑定为a和f。
结果找遍了所有的sub/2子句也没发现能与sub(a,f)的子句。
注意:Prolog寻找了所有的子句,这就是广度搜索的意义。
FAIL:route/3由于sub/2目标失败,所以就回溯到了route/3目标。

REDO:(2)route/3%于是route/3目标与route的第二条子句匹配。
CALL:(1)route/3%而第二条子句中立刻递归调用route/3,
所以再次满足route的第一条子句。
'[]'
a
a
EXIT:route/3%与第一条子句匹配的结果。
'[]'
a
a
CALL:(1)sub/2%再次运行sub/2。这次的sub/2中的第二个参数为变量
所以它首先绑定为b。sub目标成功。
a
b
EXIT:sub/2
a
b
CALL:(1)append/3%调用第三个目标append,加入路径。
'[]'
[a]
[a]
EXIT:append/3
'[]'
[a]
[a]
EXIT:route/3当这三个目标都满足后,route/3目标就满足了。
[a]
a
b
FAIL:sub/2但是从b到f没有路径,所以上一层的sub目标失败。
b
f
FAIL:append/3
'[]'
[a]
[a]
FAIL:append/3
'[]'
[a]
H72
FAIL:sub/2
a
b
REDO:(2)sub/2于是通过回溯,找到a的第二个子节点c。
a
c
EXIT:sub/2
a
c
CALL:(1)append/3
'[]'
[a]
[a]
EXIT:append/3
'[]'
[a]
[a]
EXIT:route/3
[a]
a
c
CALL:(5)sub/2%从c到f存在一条路径,所以成功。
c
f
EXIT:sub/2
c
f
CALL:(2)append/3
[a]
[c]
[a|H457]
CALL:(1)append/3
'[]'
[c]
[c]
EXIT:append/3
'[]'
[c]
[c]
EXIT:append/3
[a]
[c]
[a,c]
EXIT:route/3
[a,c]
a
f

你要是不耐烦来研究上面的当步跟踪结果,那么我再来用语言解释一遍。

首先,我们调用的目标与第二个route子句匹配,而此子句的头一个子目标就是它本身,所以又与route的第一个子句匹配。于是我们的程序就变成了如下的样子。

route(Links,Current,Des):-
route([],Current,Current),
sub(Current,Des),
append(PreLinks,[Next],Links).

很清楚这段程序判断从Current到Des有没有直接的通路。当找不到时,它就回溯到route目标,这次它与第二条route子句匹配,而第二条子句有马上递归调用它本身,所以再次与第一条子句匹配。这是程序变成了如下的样子:

route(Links,Current,Des):-
route([],Current,Current),(1)
sub(Current,Next),(2)
append,(3)
sub(Next,Des),
append.

前面的1、2、3个子句是把第一个route目标展开的结果。很容易看出来,此程序考虑了深度为2的节点。如果还没有发现目标,它又会递归调用来寻找深度为3的节点。每次展开后的程序大致如下:

sub(Current,X1),
sub(X1,X2),
...
sub(Xn-1,Xn),
sub(Xn,Des).

于是此程序能够完成广度搜索。当然这种搜索的工作量是巨大的,并且程序的运行流程也很复杂,幸好这些工作都由Prolog完成了,我们所要做的就是使用这些搜索方法来解决一些实际的问题。

广度搜索应用于图时,也会像深度搜索那样出现死循环的情况,但是不会像深度搜索那样严重。因为只要目标不太远它总能够通过一层层的搜索工作找到目标,而深度搜索可能会陷入图中的某个环路永远出不来。不过为了加快运算,我们还是采取和深度搜索一样的措施来防止这种情况出现。这也容易办到,只需加入和深度搜索相同的判断语句。

route(Links,Current,Des):-
route(PreLinks,Current,Next),
not(member(Next,PreLinks)),
sub(Next,Des),
append(PreLinks,[Next],Links).

顶一下
(6)
75%
踩一下
(2)
25%
发表评论
评价:
验证码:点击我更换图片
推荐内容
  • 机器学习讲义

    机器学习的PPT讲义,包括基于符号和逻辑表示的概念学习,决策...

  • 遗传算法介绍

    遗传算法(Genetic Algorithm, GA)是近几年发展起来的一种崭新的全局...