算法及数据结构讲义三(搜索算法).doc

第十三课搜索算法
搜索树
搜索算法的基本原理
广度优先搜索
深度优先搜索
练习
搜索树
引例:在一个4*4的棋盘上的左下角有一个马,按照国际象棋的规则,将这个马跳到右
*
上角。
分析:首先建立棋盘的坐标,我们以左下角为(1,1),以右上角、
为(4,4)。按照马的移动规则,假定当前马的位置坐标为
(x,y),则移动方法有:
(1)x’=x+1; y’=y+2
(2)x’=x+1; y’=y-2;
(3)x’=x+2; y’=y+1;
(4)x’=x+2; y’=y-1;
(5)x’=x-1; y’=y+2;
(6)x’=x-1; y’=y-2;
(7)x’=x-2; y’=y+1;
(8)x’=x-2; y’=y-1
1
1
3
2
2
3
1
2
2
1
1
3
3
1
4
4
2
4
1
1
4
2
4
4
1
1
2
3
3
2
2
3
2
3
4
3
2
3
3
2
3
4
1
2
3
2
4
3
2
1
3
2
4
4
可以建立搜索树如下:
图中表示:由(1,1)可以跳到(2,3)和(3,2)两个点(其它移动规则由于边
界限制无法到达);(2,3)又可以跳到(1,1)、(4,4)、(4,2)、(3,1)四个点,(3,2)
可以跳达(1,1)、(1,3)、(2,4)、(4,4)四个点,……。
搜索树:按照数据元素的产生式规则建立起来的数据元素逻辑关系。
特点:(1)数据之间的逻辑关系为一对多。
(2)每个结点数据的下一级子结点是由该结点的产生式规则生成。
(3)目标结点(答案数据)一定在搜索树中能够出现。
(4)对于数据规模较大的问题,搜索树的结点将是海量的。
(5)搜索树可能是无穷无尽的(因为很多结点回重复出现)。
搜索算法的基本原理:
从搜索树中可以看出,一个问题从起始状态,通过穷举的方式建立起搜索树后,目标状态一定能在搜索树中出现。因此,只要建立起搜索树,就可以在其中搜索到目标状态(数据、路径、位置等)。
搜索算法要解决的问题:
产生式规则:由当前状态按照问题的需求和限制,生成新的状态的方法集合。
搜索树的生成和存储:一般采用一边生成,一边搜索;存储方法有:集合、栈。
搜索的方法:按行搜索:即从上到下,逐层搜索
双向按行搜索:一边从上往下(起始状态到中间状态),一边从下往上逐
层搜索(从目标状态到中间状态),找到相同的中间状态
即可。
回朔法搜索:优先向更深层结点查找,走不通则换一条路,无法换则退回
到上一层。
搜索状态的减少:在生成搜索树时,对于已搜过的中间状态的再次出现,是否需要
再次加入到树中重新搜索。
广度优先搜索(bfs)
又称宽度优先搜索,是一种从搜索树的根结点开始,沿着树的宽度遍历树的结点。如果所有节点均被访问,则算法中止。一般用于求从起始状态到目标状态所需的最少步骤数。
算法过程:
1、首先将根结点放入队列中。
2、从队首取出一个结点,按照产生式规则逐个生成新的结点数据,对新数据:
如果如果是目标结点,则结束算法并返回结果。
如果不是目标结点,则检查它是否已在搜索树中出现过,未出现就将它作为尚未检查过的子结点加入到队列的队尾(特殊情况下,也有已出现过的结点重新入队的)。
3、重复步骤2。
4、若队列为空,表示整张图都检查过了,即目标无法达到,结束算法并返回“找
不到目标”的信息。
算法细化:
用哈希数组判断新生成的结点数据是否已出现过。
队列经常要多开一行,记录新结点的父亲(即该结点由上一层的哪个结点扩展而来),用于最后输出过程。
如数据规模过大,需要使用循环队列(后果是无法记录父亲)。
算法框架:
function creat(i)
begin
case i of
1:creat:=按照第一产生式规则生成新状态数据;
2:creat:=按照第二产生式规则生成新状态数据;
.
.
.
end;
end;
////////////////////////////////////////////////////////////////
procedure bfs;
begin
join(起始状态);
while not(队空) do
begin
当前处理状态:=deq;
for i:=第一产生式规则 to 最大产生式规则 do
begin
新状态:=creat(i);
if 新状态=目标状态