宽度优先搜索

1、宽度优先搜索宽度优先搜索走迷宫（Maze）【问题描述】已知一NN的迷宫，允许往上、下、左、右四个方向行走，现请你找出一条从左上角到右下角的最短路径。【输入数据】输入数据有若干行，第一行有一个自然数N（N20），表示迷宫的大小，其后有N行数据，每行有N个0或1（数字之间没有空格，0表示可以通过，1表示不能通过），用以描述迷宫地图。入口在左上角（1，1）处，出口在右下角（N，N）处。所有迷宫保证存在从入口到出口的可行路径。【输出数据】输出数据仅一行，为从入口到出口的路径（有多条路径时输出任意一条即可请严格按照 下 上 左 右）。路径格式参见样例。【样例输入】40001010000100110 【样

2、例输出】(1,1)-(1,2)-(1,3)-(2,3)-(2,4)-(3,4)-(4,4)#includeusing namespace std;const int dx5=0,1,-1,0,0;const int dy5=0,0,0,1,-1;int a20,b20;int c2020;int n;int main()string s;int i,j;cinn;for (i=1;is;for (j=0;js.length();+j) if (sj=0) cij+1=0; else cij+1=1; dfs(1,1,1); void print(int dep)int i;for (i=1;i

3、dep;i+) cout(ai,bi;cout(ai,bi)endl;void dfs(int dep,int x,int y) int i,tx,ty; adep=x; bdep=y; cxy=1; if(x=n&y=n) print(dep); else for (i=1;i0&tx0&ty=n&ctxty=0) dfs(dep+1,tx,ty); 算法1：dfs 从左上角开始，找到下一个能走的路cij=0，然后dfs(i,j),（接着穷举i,j）下一个点继续dfs,直到找到出口位置。算法2：bfs(宽度优先搜索)_利用队列实现入队入队出队出队 A1 A2 A3 A4 A5 A6 A1A7

4、 队列的概念队列和栈一样，也是一种特殊的线性表；队列是一种运算受到限制的线性表，插入操作限定在表的一端进行，称为“入队”，删除操作则限定在表的另一端进行，称为“出队”；插入一端称为队尾（rear），删除一端称为队头（front）。队头队头队尾队尾队列的概念队列的特点：先进队列的元素先出队列；队列的特点：先进队列的元素先出队列；队列常说成队列常说成先进先出线性表先进先出线性表（FIFO，First In First Out）；）；类似于生活中排队购票：先来先买，后来后买。类似于生活中排队购票：先来先买，后来后买。队列的存储结构在计算机中实现（存储）队列的最简单方法是用一维数组；若每个节点需要存储

5、的不只一个数据，则可以把每个数组元素的基类型设置为记录；或者定义成多个一维数组，再或者定义成一个几行n列的二维数组；为了标识队头和队尾，还要设置两个下标（指针）变量front和rear，分别指向队列的头和尾。周末舞会 假设在周末舞会上，男士们和女士们进入舞厅时，各自排成一队。跳舞开始时，依次从男队和女队的队头上各出一人配成舞伴。规定每个舞曲只能有一对跳舞者。若两队初始人数不相同，则较长的那一队中未配对者等待下一轮舞曲。现要求写一个程序，模拟上述舞伴配对问题。输入： 3个整数m，n，k，分别表示男士人数、女士人数、几轮舞曲。输出： 各轮舞曲的配对方案。例、周末舞会 假设在周末舞会上，男士们和女士

6、们进入舞厅时，各自排成一队。跳舞开始时，依次从男队和女队的队头上各出一人配成舞伴。规定每个舞曲只能有一对跳舞者。若两队初始人数不相同，则较长的那一队中未配对者等待下一轮舞曲。现要求写一个程序，模拟上述舞伴配对问题。输入： 3个整数m，n，k，分别表示男士人数、女士人数、几轮舞曲。输出： 各轮舞曲的配对方案。输入样例：2 4 6输出样例：1 12 21 32 41 12 2算法：模拟舞会配对 设计两个队列分别存放男士和女士的编号，每次取出（出队）两个队列的队头元素进行配对（输出），每对跳舞的人一旦跳完后就回到队尾（入队）等待下次被选。宽度优先搜索（宽搜，bfs)宽度优先搜索算法又称为广度优先搜索

7、，是最简便的图的搜索算法之一，这个算法是很多重要的图论算法的模型；BFS（Breadth First Search）属于一种盲目搜寻法，目的是系统地展开并检查图中的所有节点，以找寻目标节点（目标状态）；换句话说，它并不考虑结果的可能位置，不关心搜索的快慢好坏，就是彻底地搜索整张图，直到找到目标节点为止（或者无解）；从算法的观点看，所有因为展开节点而得到的子节点都会被加入到一个先进先出的队列中，所以是队列的重要应用。通过搜索树，比较通过搜索树，比较bfsbfs与与dfsdfs的区别。白色表示未访问的区别。白色表示未访问的节点，黑色表示已经访问的节点，灰色表示：的节点，黑色表示已经访问的节点，灰色

8、表示：DFSDFS中为中为正在访问的节点、正在访问的节点、BFSBFS中为已入队等待访问的节点。中为已入队等待访问的节点。六、宽度优先搜索（宽搜，bfs)结构一：求一个解、所有解、最优解while front=rear 由front状态去寻找新的目标状态 if 找到新的状态没有出现过 把新状态添加进队列（rear+) if 新的状态就是目标状态 做相应处理（退出循环输出解、输出当前解、比较解的优劣） front+front状态可能到达的状态穷举完毕，则出队，进入下一个状态去寻求新状态 宽度优先搜索（宽搜，bfs)例1：迷宫宽搜程序怎么实现bfs应用举例例2、数字变换（num.in/out/pa

9、s/cpp)给定一个数N (ON100000)，变成另一个数K(OK100000)，允许的操作是乘以2，或者加减1，问最少要几步才能完成？【输入格式】仅有两个整数 N 和 K 【输出格式】最少步数【样例输入】517【样例输出】4bfs应用举例 bfs应用举例541068379 912112016214181322191715部分状态空间树部分状态空间树BFS vs DFS程序实现例3、关系网络（relationship.?） 有n个人，他们的编号为1n，其中有一些人相互认识，现在x想要认识y，可以通过他所认识的人来认识更多的人（如果a认识b、b认识c，那么a可以通过b来认识c），求出x最少需要

10、通过多少人才能认识y。输入: 第一行三个整数n、x、y；接下来一个nn的邻接矩阵，ai,j=1表示i认识j，ai,j=0表示不认识。保证i=j时,ai,j=0,并且ai,j=aj,i。输出: x认识y最少需要通过的人数。数据保证x一定能认识y 。样例输入：5 1 50 1 0 0 01 0 1 1 00 1 0 1 00 1 1 0 10 0 0 1 0样例输出：2七、bfs应用举例算法分析： 宽搜。 先设答案ans=0。把x加入队列并设置为队头元素，从队头开始进行宽搜，穷举邻接矩阵的第x行，看x认识谁（判断ax,j=1），认识的人（j）全部依次入队，并且ans:=ans+1，如果出现了y，则

11、输出ans，结束搜索，否则，取出队头元素继续宽搜。七、bfs应用举例 程序实现bfs应用举例小结 本题是说明“宽搜”的另一个重要应用：求最优值问题。比如最少几次、最快几步等！思考：如果要输出x是通过什么关系（哪些人）认识y的呢？解决：再设一个数据域（或者数组），记录当前节点是从哪个节点扩展得到的。bfs应用举例例：例：奇怪的电梯（奇怪的电梯（lift.?） 呵呵，有一天我做了一个梦，梦见了一种很奇怪的电梯。大楼的每呵呵，有一天我做了一个梦，梦见了一种很奇怪的电梯。大楼的每一层楼都可以停电梯，而且第一层楼都可以停电梯，而且第i层楼层楼(1=i=N)上有一个数字上有一个数字Ki(0=Ki0) an

12、d (x70) and (x70) and (x30) and (x33) 操作是操作是x10:=x10+x3-3;x3:=3;x7x10:=x10+x3-3;x3:=3;x7不变不变7 7斤的瓶子往斤的瓶子往3 3斤的瓶子里倒：斤的瓶子里倒：? ?7 7斤的瓶子往斤的瓶子往1010斤的瓶子里倒：斤的瓶子里倒：? ?3 3斤的瓶子往斤的瓶子往7 7斤的瓶子里倒：斤的瓶子里倒：? ?3 3斤的瓶子往斤的瓶子往1010斤的瓶子里倒：斤的瓶子里倒：? ?七、bfs应用举例例例6 6、倒油问题（、倒油问题（oil.?oil.?）算法分析：算法分析： 第三、在没有找到解（没出现目标状态）之前，是不知道该

13、怎么倒油第三、在没有找到解（没出现目标状态）之前，是不知道该怎么倒油的，也就是说从当前状态到在一个状态是的，也就是说从当前状态到在一个状态是盲目盲目的，只能穷举。如何穷的，只能穷举。如何穷举、如何保存每一个状态呢？队列！举、如何保存每一个状态呢？队列！ 第四、由于是要输出最快的倒油方案，所以不应该做无谓的倒油操作，第四、由于是要输出最快的倒油方案，所以不应该做无谓的倒油操作，也就是说从一个状态采用一种倒油方法得到的状态不能出现过，否则也就是说从一个状态采用一种倒油方法得到的状态不能出现过，否则一定不是最快的倒油方案。所以，需要对一定不是最快的倒油方案。所以，需要对状态状态“判重判重”。如何实现？。如何实现？穷举！穷举！ 第五、因为要第五、因为要输出具体的倒油步骤输出具体的倒油步骤，所以要保存各个状态之间是怎么，所以要保存各个状态之间是怎么转移的，以便找到目标状态后倒过来，按照这个线索输出从初始状态转移的，以便找到目标状态后倒过来，按照这个线索输出从初始状态到目标状态。