Pascal广度优先搜索.ppt

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

握•让我们来看个例子！让我们来看个例子！让我们来看个例子！让我们来看个例子！3 3重排九宫问题游戏n n在一个在一个3 3乘乘3 3的九宫中有的九宫中有1-81-8的的8 8个数及一个空格随机摆放在其中的格个数及一个空格随机摆放在其中的格子里如下面左图所示现在要求实现这样的问题：将该九宫调整为子里如下面左图所示现在要求实现这样的问题：将该九宫调整为如下图右图所示的形式调整规则是：每次只能将与空格（上，下或如下图右图所示的形式调整规则是：每次只能将与空格（上，下或左，右）相临的一个数字平移到空格中试编程实现左，右）相临的一个数字平移到空格中试编程实现   | 2 | 8  | 3 |                 | 1 | 2 | 3 | | 2 | 8  | 3 |                 | 1 | 2 | 3 | - - | 1 |     | 4 |                 | 8 |    | 4 | | 1 |     | 4 |                 | 8 |    | 4 | | 7 | 6  | 5 |                 | 7 | 6 | 5 || 7 | 6  | 5 |                 | 7 | 6 | 5 |     在深度优先搜索算法中，是深度越大的结点越先得到扩展。

如果在搜索在深度优先搜索算法中，是深度越大的结点越先得到扩展如果在搜索中把算法改为按结点的层次进行搜索，中把算法改为按结点的层次进行搜索， 本层的结点没有搜索处理完时，不本层的结点没有搜索处理完时，不能对下层结点进行处理，即深度越小的结点越先得到扩展，也就是说先产能对下层结点进行处理，即深度越小的结点越先得到扩展，也就是说先产生生 的结点先得以扩展处理，这种搜索算法称为广度优先搜索法的结点先得以扩展处理，这种搜索算法称为广度优先搜索法 4 4     在深度优先搜索算法中，是深度越大的结在深度优先搜索算法中，是深度越大的结在深度优先搜索算法中，是深度越大的结在深度优先搜索算法中，是深度越大的结点越先得到扩展如果在搜索中把算法改点越先得到扩展如果在搜索中把算法改点越先得到扩展如果在搜索中把算法改点越先得到扩展如果在搜索中把算法改为按结点的层次进行搜索，为按结点的层次进行搜索，为按结点的层次进行搜索，为按结点的层次进行搜索，   本层的结点没本层的结点没本层的结点没本层的结点没有搜索处理完时，不能对下层结点进行处理有搜索处理完时，不能对下层结点进行处理有搜索处理完时，不能对下层结点进行处理有搜索处理完时，不能对下层结点进行处理，即深度越小的结点越先得到扩展，也就是，即深度越小的结点越先得到扩展，也就是，即深度越小的结点越先得到扩展，也就是，即深度越小的结点越先得到扩展，也就是说先产生说先产生说先产生说先产生   的结点先得以扩展处理，这种搜的结点先得以扩展处理，这种搜的结点先得以扩展处理，这种搜的结点先得以扩展处理，这种搜索算法称为广度优先搜索法。

索算法称为广度优先搜索法索算法称为广度优先搜索法索算法称为广度优先搜索法   5 5特别提示特别提示n n在有些情况下，比如求最优秀解的时候，有时广度搜索比深度搜索好;n n一般来说广度优先搜索可以利用队列实现，主要用于求一种状态通过 几种规定的操作以最小次的变换到另一种状态6 6广度优先搜索基本算法广度优先搜索基本算法      1）从某个顶点出发开始访问，被访问的顶点作相应的标记，并输出访问顶点号；    2）从被访问的顶点出发，依次搜索与该顶点有边的关联的所有未被访问的邻接点，并作相应的标记    3）再依次根据2）中所有被访问的邻接点，访问与这些邻接点相关的所有未被访问的邻接点，直到所有顶点被访问为止7 7 【算法过程框架】 procedure guangdu(i);procedure guangdu(i); begin begin   write(i);   write(i);   v[i]:=true;   v[i]:=true;   insert(q,i);{q   insert(q,i);{q是队列，是队列，i i进队进队} }   repeat   repeat     k:=delete(q)     k:=delete(q)；；{ {出队出队} }     for j:=1 to n do     for j:=1 to n do     if (a[k,j]=1) and (not v[j]) then     if (a[k,j]=1) and (not v[j]) then     begin     begin     write(j);     write(j);     v[j]:=true;     v[j]:=true;     insert(q,j);     insert(q,j);     end;     end;   until    until 队列队列q q为空为空; ;变化的就是每个节点的表示形式和扩展的策略变化的就是每个节点的表示形式和扩展的策略变化的就是每个节点的表示形式和扩展的策略变化的就是每个节点的表示形式和扩展的策略8 8例一、分油问题    假设有假设有3 3个油瓶，容量分别为个油瓶，容量分别为4 4，，3 3，，1(1(斤斤) )。

开始时开始时4 4斤油瓶是满的，另外两个是空的，请用这三个油瓶斤油瓶是满的，另外两个是空的，请用这三个油瓶将倒出将倒出2 2斤的油来斤的油来分析：由于每一次倒油都是从一个油瓶向另外一个油瓶分析：由于每一次倒油都是从一个油瓶向另外一个油瓶分析：由于每一次倒油都是从一个油瓶向另外一个油瓶分析：由于每一次倒油都是从一个油瓶向另外一个油瓶倒油，要么向外倒油的油瓶倒空，要不接受倒油的油倒油，要么向外倒油的油瓶倒空，要不接受倒油的油倒油，要么向外倒油的油瓶倒空，要不接受倒油的油倒油，要么向外倒油的油瓶倒空，要不接受倒油的油瓶道满我们将三个油瓶编号，用三个油瓶的油表示瓶道满我们将三个油瓶编号，用三个油瓶的油表示瓶道满我们将三个油瓶编号，用三个油瓶的油表示瓶道满我们将三个油瓶编号，用三个油瓶的油表示当前状态，共有六种不同的倒油方法当前状态，共有六种不同的倒油方法当前状态，共有六种不同的倒油方法当前状态，共有六种不同的倒油方法1->2;1-1->2;1->3;2->3;2->1;3->2;3->1;>3;2->3;2->1;3->2;3->1;（相当于八种跳马（相当于八种跳马（相当于八种跳马（相当于八种跳马的方案的方案的方案的方案, ,回溯的条件是该状态在以前出现过，而我们回溯的条件是该状态在以前出现过，而我们回溯的条件是该状态在以前出现过，而我们回溯的条件是该状态在以前出现过，而我们现在不但要求出一种解，而且我们要的出最优化（操现在不但要求出一种解，而且我们要的出最优化（操现在不但要求出一种解，而且我们要的出最优化（操现在不但要求出一种解，而且我们要的出最优化（操作次数最少的解），也就是我们要求我们搜索树的层作次数最少的解），也就是我们要求我们搜索树的层作次数最少的解），也就是我们要求我们搜索树的层作次数最少的解），也就是我们要求我们搜索树的层最少最少最少最少) )9 9深度优先搜索:状态树4 0 01 3  00  1 30  3   13  0  14  0  03  1  02 1  11 3  01—>21—>32—>11—>23—>13—>21—>21—>31010状态树(广度优先搜索）4，0，01，3，03，0，14,0,01,2,11->21->30,3,11->32->32->1在上面的状态树中，我们要注意下面几点1:对于每个当前的状态节点来说，可能有八种可能，但是有些可能我们可以预先处理处理。

缩小该节点的度数（要求到出的酒杯非空），另外如果该节点已经被产生那么我们就不必在搜索下去了，我们利用队列来控制）；2：我们搜索的结束条件是搜索到有2着瓶油；3：因为我们要找到最优秀解，所以我们按照层来搜索1111广度优先搜索所用的数据结构DATA DATA （状态）（状态）（状态）（状态）OPOP（由何种操作（由何种操作（由何种操作（由何种操作变换而来变换而来变换而来变换而来) )PRE (PRE (由何种状态由何种状态由何种状态由何种状态变换来，即父节点）变换来，即父节点）变换来，即父节点）变换来，即父节点）初始初始初始初始状态状态状态状态初始状态初始状态初始状态初始状态AA操作结果操作结果操作结果操作结果初始状态初始状态初始状态初始状态BB操作结果操作结果操作结果操作结果初始状态经过初始状态经过初始状态经过初始状态经过两次两次两次两次AA的结果的结果的结果的结果0 01 12 2BB1 1AAAAFRONTFRONTREARREAR1212一:交通图问题n n表示的是从城市表示的是从城市A A到城市到城市H H的交通图从图中可以的交通图从图中可以看出，从城市看出，从城市A A到城市到城市H H要经过若干个城市。

现要要经过若干个城市现要找出一条经过城市最少的一条路线找出一条经过城市最少的一条路线1313分析该题n n分析分析分析分析：看到这图很容易想到用邻接距阵来表示，：看到这图很容易想到用邻接距阵来表示，0 0表示能表示能走，走，1 1表示不能走如图表示不能走如图5 51414利用队列广度搜索n n首先想到的是用队的思想我们可以首先想到的是用队的思想我们可以a a记录搜索过记录搜索过程，程，a.citya.city记录经过的城市记录经过的城市,a.pre,a.pre记录前趋元素，记录前趋元素，这样就可以倒推出最短线路具体过程如下：这样就可以倒推出最短线路具体过程如下：　　（　　（1 1））   将城市将城市A A入队，队首、队尾都为入队，队首、队尾都为1 1　　（　　（2 2））   将队首所指的城市所有可直通的城市将队首所指的城市所有可直通的城市入队（如果这个城市在队中出现过就不入队，可入队（如果这个城市在队中出现过就不入队，可用一个集合来判断），将入队城市的用一个集合来判断），将入队城市的prepre指向队首指向队首的位置然后将队首加的位置然后将队首加1 1，得到新的队首城市重，得到新的队首城市。

重复以上步骤，直到城市复以上步骤，直到城市H H入队为止入队为止当搜到城市当搜到城市H H时，搜索结束时，搜索结束利用prepre可倒推出最少城市线路可倒推出最少城市线路1515n n参考程序参考程序n nconst ju:array[1..8,1..8] of 0..1=((1,0,0,0,1,0,1,1),const ju:array[1..8,1..8] of 0..1=((1,0,0,0,1,0,1,1),　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　(0,1,1,1,1,0,1,1),(0,1,1,1,1,0,1,1),　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　(0,1,1,0,0,1,1,1),(0,1,1,0,0,1,1,1),　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　(0,1,0,1,1,1,0,1),(0,1,0,1,1,1,0,1),　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　(1,1,0,1,1,1,0,0),(1,1,0,1,1,1,0,0),　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　(0,0,1,1,1,1,1,0),(0,0,1,1,1,1,1,0),　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　(1,1,1,0,0,1,1,0),(1,1,1,0,0,1,1,0),　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　(1,1,1,1,0,0,0,1));(1,1,1,1,0,0,0,1));　　　　type r=record {type r=record {记录定义记录定义} }　　　　　　　　　　　　city:array[1..100] of char;city:array[1..100] of char;　　　　　　　　　　　　pre:array[1..100] of integer;pre:array[1..100] of integer;　　　　　　　　　　end;end;　　　　var h,d,i:integer;var h,d,i:integer;　　　　　　　　a:r;a:r;　　　　　　　　s:set of 'A'..'H';s:set of 'A'..'H';　　　　procedure out; {procedure out; {输出过程输出过程} }　　　　beginbegin　　　　　　write(a.city[d]);write(a.city[d]);　　　　　　　　repeatrepeat　　　　　　　　　　d:=a.pre[d];d:=a.pre[d];　　　　　　　　　　write('--',a.city[d]);write('--',a.city[d]);　　　　　　　　until a.pre[d]=0;until a.pre[d]=0;　　　　　　writeln;writeln;　　　　　　halt;halt;　　　　end;end;　　　　　　　　用数组合表示8个城市的相互关系1616n nprocedure doit;procedure doit;beginbegin　　　　　　　　　　　　h:=0; d:=1;h:=0; d:=1;　　　　　　　　　　　　a.city[1]:='A';a.city[1]:='A';　　　　　　　　　　　　a.pre[1]:=0;a.pre[1]:=0;　　　　　　　　　　　　s:=['A'];s:=['A'];　　　　　　　　　　　　repeat {repeat {步骤步骤步骤步骤2}2}　　　　　　　　　　　　　　　　inc(h); {inc(h); {队首加一，出队队首加一，出队队首加一，出队队首加一，出队} }　　　　　　　　　　　　　　　　for i:=1 to 8 do {for i:=1 to 8 do {搜索可直通的城市搜索可直通的城市搜索可直通的城市搜索可直通的城市} }　　　　　　　　　　　　　　　　　　　　if if （（（（ju[ord(a.city[h])-64,i]=0ju[ord(a.city[h])-64,i]=0））））and and 　　　　　　（　　　　　　（　　　　　　（　　　　　　（notnot（（（（chrchr（（（（i+64i+64）））） in s in s））））））））then {then {判断城市是否走判断城市是否走判断城市是否走判断城市是否走过过过过} }　　　　　　　　　　　　　　　　　　　　　　　　　　　　beginbegin　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　inc(d); {inc(d); {队尾加一，入队队尾加一，入队队尾加一，入队队尾加一，入队} }　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　a.city[d]:=chr(64+i);a.city[d]:=chr(64+i);　　　　　　　　　　　　　　　　　　　　　　　　　　　　a.pre[d]:=h;a.pre[d]:=h;　　　　　　　　　　　　　　　　　　　　　　　　　　　　s:=s+[a.city[d]];s:=s+[a.city[d]];　　　　　　　　　　　　　　　　　　　　　　　　　　　　if a.city[d]='H' then out;if a.city[d]='H' then out;　　　　　　　　　　　　　　　　　　　　　　　　end;end;　　　　　　　　　　　　until h=d;until h=d;　　　　　　　　end;end;　　　　　　　　begin {begin {主程序主程序主程序主程序} }　　　　　　　　　　　　doit;doit;　　　　　　　　end.end.　　输出：　　输出：　　输出：　　输出：　　　　　　　　　　　　H-F--AH-F--A1717题二题二 字串变换字串变换 （（NOIPG2.pas) n n[ [问题描述问题描述问题描述问题描述]:]:　　已知有两个字串　　已知有两个字串 A$, B$  A$, B$ 及一组字串变换的规则（至多及一组字串变换的规则（至多6 6个规则）个规则）: :　　　　　　　　　　A1$ -> B1$A1$ -> B1$　　　　　　　　　　A2$ -> B2$A2$ -> B2$　　规则的含义为：在　　规则的含义为：在 A$ A$中的子串中的子串 A1$  A1$ 可以变换为可以变换为 B1$ B1$、、A2$ A2$ 可以变换为可以变换为 B2$ … B2$ …。

　　　　例如：　　　　例如：A$A$＝＝'abcd''abcd'　　B$B$＝＝'xyz''xyz'　　变换规则为：　　变换规则为：　　　　　　　　'abc'->'xu''abc'->'xu'　　'ud'->'y''ud'->'y'　　'y'->'yz''y'->'yz'　　则此时，　　则此时，A$ A$ 可以经过一系列的变换变为可以经过一系列的变换变为 B$ B$，其变换的过程为：，其变换的过程为：　　　　　　'abcd'->'xud'->'xy'->'xyz''abcd'->'xud'->'xy'->'xyz'　　共进行了三次变换，使得　　共进行了三次变换，使得 A$  A$ 变换为变换为B$B$[ [输入输入输入输入]:]:　　键盘输人文件名文件格式如下：　　键盘输人文件名文件格式如下：　　　　　　A$ B$A$ B$　　　　　　A1$ B1$ \A1$ B1$ \　　　　　　A2$ B2$ |-> A2$ B2$ |-> 变换规则变换规则　　　　　　... ... / ... ... / 　　所有字符串长度的上限为　　所有字符串长度的上限为 20 20[ [输出输出输出输出]:]:　　输出至屏幕。

格式如下：　　输出至屏幕格式如下：　　若在　　若在 10  10 步（包含步（包含 10 10步）以内能将步）以内能将 A$  A$ 变换为变换为 B$  B$ ，则输出最少的变换步数；否则输，则输出最少的变换步数；否则输出出"NO ANSWER!" "NO ANSWER!" 1818三、骑士精神（三、骑士精神（Knight））n n在一个在一个5×55×5的棋盘上有的棋盘上有1212个白色的骑士和个白色的骑士和1212个黑色的骑士，个黑色的骑士，   且有一且有一个空位在任何时候一个骑士都能按照骑士的走法（它可以走到和它个空位在任何时候一个骑士都能按照骑士的走法（它可以走到和它横坐标相差为横坐标相差为1 1，纵坐标相差为，纵坐标相差为2 2或者横坐标相差为或者横坐标相差为2 2，纵坐标相差为，纵坐标相差为1 1的格子）移动到空位上的格子）移动到空位上n n   给定一个初始的棋盘，怎样才能经过移动变成如下目标棋盘：给定一个初始的棋盘，怎样才能经过移动变成如下目标棋盘：n n              为了体现出骑士精神，他们必须以最少的步数完成任务为了体现出骑士精神，他们必须以最少的步数完成任务。

1919n n输入文件：输入文件：输入文件：输入文件：n n第一行有一个正整数第一行有一个正整数T(T<=10)T(T<=10)，表示一共有，表示一共有N N组数据接下来有组数据接下来有T T个个5×55×5的的矩阵，矩阵，0 0表示白色骑士，表示白色骑士，1 1表示黑色骑士，表示黑色骑士，* *表示空位两组数据之间没有空表示空位两组数据之间没有空行n n输出文件：输出文件：输出文件：输出文件：n n对于每组数据都输出一行如果能在对于每组数据都输出一行如果能在1515步以内（包括步以内（包括1515步）到达目标状态，步）到达目标状态，则输出步数，否则输出－则输出步数，否则输出－1 1n nSample InputSample Inputn n2 2n n1011010110n n01*1101*11n n1011110111n n0100101001n n0000000000n n0101101011n n110*1110*1n n0111001110n n0101001010n n00100 00100 2020题目四:移棋子n nMFGMFG投资公司发明了一种游戏棋盘，这个棋盘有投资公司发明了一种游戏棋盘，这个棋盘有1515个孔，除了一个孔个孔，除了一个孔外，其它孔中都有一粒棋子。

一粒棋子能沿着棋盘中的直线跳过一个外，其它孔中都有一粒棋子一粒棋子能沿着棋盘中的直线跳过一个或多个相邻的棋子到最近的一个空孔中，被跳过的棋子就被移出棋盘或多个相邻的棋子到最近的一个空孔中，被跳过的棋子就被移出棋盘在下面的图形中，位于在下面的图形中，位于1212孔或者位于孔或者位于1414号孔的棋子能跳入号孔的棋子能跳入5 5号孔如果位于果位于1212号孔的棋子跳过来，则位于号孔的棋子跳过来，则位于8 8号孔的棋子就被移出棋盘，同号孔的棋子就被移出棋盘，同样如果是位于样如果是位于1414号孔的棋子跳过来，则位于号孔的棋子跳过来，则位于9 9号孔的棋子就被移走了号孔的棋子就被移走了   　　　　　　　　　　　　　　　　　　　　　　   　　　　请你编写一个程序，找出用最请你编写一个程序，找出用最少跳动序列移走其它棋子，除少跳动序列移走其它棋子，除了最后一粒棋子留在初始的空了最后一粒棋子留在初始的空孔中如果这样的序列不存在，孔中如果这样的序列不存在，则程序要输出一行信息则程序要输出一行信息"IMPOSSIBLE"2121n n　　　　输入输入输入输入　　输入包含　　输入包含T T个测试数据。

输入文件的第一行给出了个测试数据输入文件的第一行给出了T T每一个测试每一个测试数据是单一的整数，表示一个空孔的编号数据是单一的整数，表示一个空孔的编号   　　　　输出输出输出输出　　对于每一个数据，输出的第一行包含一个整数，表示这最短的移　　对于每一个数据，输出的第一行包含一个整数，表示这最短的移棋子序列中的跳动次数在第二行中输出一个棋子移动的序列，一个棋子序列中的跳动次数在第二行中输出一个棋子移动的序列，一个棋子移动包含一对整数（之间用一个空格隔开），第一个整数是跳动棋子移动包含一对整数（之间用一个空格隔开），第一个整数是跳动的起始点编号，第二个整数是跳动的目的点编号的起始点编号，第二个整数是跳动的目的点编号n n　　　　Sample Input Sample Input 　　　　1 1 　　　　5 5 　　　　Output for the Sample InputOutput for the Sample Input　　　　10 10 　　　　12 5 3 8 15 12 6 13 7 9 1 7 10 8 7 9 11 14 14 5 12 5 3 8 15 12 6 13 7 9 1 7 10 8 7 9 11 14 14 5 2222。