pascal广度优先搜索

《pascal广度优先搜索》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、09年暑假集训（二）——广度优先搜索广度优先搜索概念广度优先是另一种控制结点扩展的策略，这种策略优先扩展深度小的结点，把问题的状态向横向发展。广度优先搜索法也叫BFS法(BreadthFirstSearch)，进行广度优先搜索时需要利用到队列这一数据结构。广度优先搜索算法适应范围如果问题的解是由若干部选择构成的一个选择序列，题目要求我们用最少的步骤解决最优化的问题，这个时候我们一般考虑是否使用广度优先搜索。广度优先搜索具有很明确的解题结构，很容易掌握。让我们来看个例子！重排九宫问题游戏在一个3乘3的九宫

2、中有1-8的8个数及一个空格随机摆放在其中的格子里。如下面左图所示。现在要求实现这样的问题：将该九宫调整为如下图右图所示的形式。调整规则是：每次只能将与空格（上，下或左，右）相临的一个数字平移到空格中。试编程实现。

3、2

4、8 

5、3

6、                

7、1

8、2

9、3

10、-

11、1

12、    

13、4

14、                

15、8

16、   

17、4

18、

19、7

20、 6 

21、5

22、                

23、7

24、6

25、5

26、在深度优先搜索算法中，是深度越大的结点越先得到扩展。如果在搜索中把算法改为按结点的层次进

27、行搜索，本层的结点没有搜索处理完时，不能对下层结点进行处理，即深度越小的结点越先得到扩展，也就是说先产生的结点先得以扩展处理，这种搜索算法称为广度优先搜索法。在深度优先搜索算法中，是深度越大的结点越先得到扩展。如果在搜索中把算法改为按结点的层次进行搜索，本层的结点没有搜索处理完时，不能对下层结点进行处理，即深度越小的结点越先得到扩展，也就是说先产生的结点先得以扩展处理，这种搜索算法称为广度优先搜索法。特别提示在有些情况下，比如求最优秀解的时候，有时广度搜索比深度搜索好;一般来说广度优先搜索可以利用队列实

28、现，主要用于求一种状态通过几种规定的操作以最小次的变换到另一种状态广度优先搜索基本算法1）从某个顶点出发开始访问，被访问的顶点作相应的标记，并输出访问顶点号；2）从被访问的顶点出发，依次搜索与该顶点有边的关联的所有未被访问的邻接点，并作相应的标记。3）再依次根据2）中所有被访问的邻接点，访问与这些邻接点相关的所有未被访问的邻接点，直到所有顶点被访问为止。【算法过程框架】procedureguangdu(i);beginwrite(i);v[i]:=true;insert(q,i);{q是队列，i进队}r

29、epeatk:=delete(q)；{出队}forj:=1tondoif(a[k,j]=1)and(notv[j])thenbeginwrite(j);v[j]:=true;insert(q,j);end;until队列q为空;变化的就是每个节点的表示形式和扩展的策略例一、分油问题假设有3个油瓶，容量分别为4，3，1(斤)。开始时4斤油瓶是满的，另外两个是空的，请用这三个油瓶将倒出2斤的油来分析：由于每一次倒油都是从一个油瓶向另外一个油瓶倒油，要么向外倒油的油瓶倒空，要不接受倒油的油瓶道满。我们将三个油

30、瓶编号，用三个油瓶的油表示当前状态，共有六种不同的倒油方法1->2;1->3;2->3;2->1;3->2;3->1;（相当于八种跳马的方案,回溯的条件是该状态在以前出现过，而我们现在不但要求出一种解，而且我们要的出最优化（操作次数最少的解），也就是我们要求我们搜索树的层最少)深度优先搜索:状态树4001300130313014003102111301—>21—>32—>11—>23—>13—>21—>21—>3状态树(广度优先搜索）4，0，01，3，03，0，14,0,01,2,11->21->30,

31、3,11->32->32->1在上面的状态树中，我们要注意下面几点1:对于每个当前的状态节点来说，可能有八种可能，但是有些可能我们可以预先处理处理。缩小该节点的度数（要求到出的酒杯非空），另外如果该节点已经被产生那么我们就不必在搜索下去了，我们利用队列来控制）；2：我们搜索的结束条件是搜索到有2着瓶油；3：因为我们要找到最优秀解，所以我们按照层来搜索广度优先搜索所用的数据结构DATA（状态）OP（由何种操作变换而来)PRE(由何种状态变换来，即父节点）初始状态初始状态A操作结果初始状态B操作结果初始状态

32、经过两次A的结果012B1AAFRONTREAR一:交通图问题表示的是从城市A到城市H的交通图。从图中可以看出，从城市A到城市H要经过若干个城市。现要找出一条经过城市最少的一条路线。分析该题分析：看到这图很容易想到用邻接距阵来表示，0表示能走，1表示不能走。如图5。利用队列广度搜索首先想到的是用队的思想。我们可以a记录搜索过程，a.city记录经过的城市,a.pre记录前趋元素，这样就可以倒推出最短线路。具体过程如下：　　（1）将城市A入