算法代表着用系统的方法描述解决问题的策略机制，北京大学《算法基础》课程将带你一一探索枚举、二分、贪心、递归、深度优先搜索、广度优先搜索、动态规划等经典算法，体会他们巧妙的构思，感受他们利用计算解决问题的独特魅力。顺利完成本课程，你将不但能够掌握这些算法的原理，还能够对这些算法进行灵活应用以及准确实现。本课程的中的编程任务，将充分训练你的思维能力和动手能力，促成全面、缜密思考问题的习惯。达到本门课程的要求，即意味者你具备了初步的算法基础和较强的编程实现能力。
八数码问题进一步讨论-双向广搜
Loading...
Из курса от партнера Peking University
算法基础
282 оценки
Из урока
广度优先搜索
与深度优先搜索算法类似，广度优先搜索(广搜)也是常用的搜索图的算法。它的思想是从一个顶点开始，辐射状地优先遍历其周围较广的区域。一般可以用它做什么呢？一个最直观经典的例子就是走迷宫，从起点开始，找出到终点的最短路程，很多最短路径算法都是基于广搜的思想。广索的基本方法是使用队列存放已经扩展过的节点。本模块先以简单例题引入广搜的基本实现方法，然后再通过经典的"八数码"问题，进一步介绍状态表示、判重的节省时间和空间的技巧。
Познакомьтесь с преподавателями
Jiaying Liu 刘家瑛, Ph.D.Associate Professor
Institute of Computer Science & Technology
郭 炜讲师
北京大学信息科学技术学院教学所
接下来我们再进一步讨论一下这个八数码问题，先总结一下这个广搜和深搜的比较，啊，
呃，广搜它需要很大的存储空间，所以说一般用于状态表示比较简单，就是用不大的空间就能表示一个状态这种情况，
然后求最优策略最优解我们用广搜比较合适，因为它找到一个解就是最优解，啊，
然后它的缺点当然就是，它也是比较盲目的，其实深搜也盲目啊，
广搜最大的缺点实际上就是它可能会拓展出来很多没有用的节点，
需要很大的空间来保存这些节点， 深搜呢，它可以解决任何问题，深搜也挺盲目的，
有时候它搜出来解未必是最优解，所以你要求最优解呢，
就是说深搜就会麻烦一些，但是它只需要保存从起始状态，
到当前状态路径上的一些节点，所以它所需要的空间是比较少的，
那，我们进一步讨论一下这个八数码问题，
啊，就是在 POJ 1077 这个题目下面，它实际上就一组数据， 所以我们刚才写的那个，
广搜程序能过，但是在 ii 的 HDU 这个1043 这个题目，也是，
也是八数码，它那个数据是有很多组的，那我刚才写的这个程序交上去就会
超时，啊，也即是我 的广搜在 POJ 上能过，在 HDU 上会超时，
那你想要做出一些什么改进，使得它在这个
HDU 上面能过呢？ 有三种办法，啊，一种办法是双向广搜，呃，这我们等会儿会，
提到双向广搜到底怎么回事，基本的思想呢，就是从两个方向，
都进行广度优先顺序，呃，广度优先的扩展，
呃，就是从起始节点，
扩展，同时也从目标节点扩展，两个方向同时，
同时扩展，把两个方向的扩展混在一块儿了，问题才解决了，等会儿会细说，
当然解决这个问题的第二种方法是预处理一下，啊，
怎么预处理呢，因为我们现在这个问题，因为总的状态数不多，只有36万
多种，一共只有40万种，因此我们就可以从这个目标节点开始，
做一步彻底的广搜，所谓彻底的广搜就是我从目标节点出发，
做一遍广搜，把所有从目标节点，有可能到达的节点，全部都给它找出来，
这数量是有限的，一共怎么也不到40万种，对吧，所以我们彻底做一遍广搜，也不需要多长时间，
我们彻底做一遍广搜以后，就找出了所有从目标节点，
能够抵达的这些节点， 那当然从那些节点也就都能够抵达目标节点，对吧这个东西肯定是
可逆的，啊，任何一个节点它能到目标节点，那从目标节点也能到
那个节点，是吧，它是可逆的。那比方说，我从目标节点
S 出发，啊，我做了一大堆的这个广搜的扩展，扩展到了一个节点 A, 那当然从
A 也就能到 S ，对吧，我从 S 扩展到 A 的过程中，实际上我就把从
S 到 A 的路径记下来了， 那反过来，那条路径反过来就是 A 到 S
的路径，对吧，所以这时候我就可以把 A 到 S 的路径给它存起来， 那我从 S
出去扩展了 A1 ,扩展了 A2 ，扩展了 A3 ，啊，所有能够抵达 S
的节点我们都会扩展出来， 而且在扩展出来的同时，我就把它们到 S 的路径全部都存下来了，那也就是说，
所有能够抵达 S 的那些状态，它们的路径，我都可以事先给它存下来，
这个只需要在一遍彻底的广搜过程中就能够完成，
那这一边彻底的广搜只需要牵涉到不到40万种状态，实际上它不慢，
那做好这个预处理以后，然后，你在
程序运行的时候，每读到一个状态，它不是要问你这个状态到，
到目标节点需要怎么走，对吧，那你读到这个状态，你不需要再去从头搜啦，就直接把存下来的那个解法，
给它输出就完了，对吧，这时候，那个 HDU 上面它是有多组数据，啊，
一大堆的数据，每一组数据我们都要求出来，从这个初始状态到，
终，终止状态的路径，如果，针对每，每一组数据你都去搜一遍，那当然就很慢，
现在我来一个预处理，我已经把所有能够到达目标节点那些状态的，
到达目标节点的路径全部都存下来了，那我读到一组数据，我直接把存下来的数据给它输出，就完了，就是说我们，
对读到的任何一组数据都不需要再去重新做搜索，那当然速度就会快很多，
等于我在这里只需要彻底搜一遍，如果你不这么做的话呢，每读入一个初始状态你都要去搜一遍，那它的数据比如说好几十组，
那你就要搜好几十遍，那你速度当然就很慢了，对吧，这就是第二种办法，就是预处理。
那第三种办法就是所谓的 A* 算法，我也写过一个在 HDU 下面能过，这个就超出现在
咱们课程范围，就不讲了，A*算法呢，你可以认为是对广搜的一个改进，
那下面我们要重点讲一下这个双向广搜啊，什么叫双向广搜，
双向，双向广搜也称为这个 DBFS ，啊，
它是对这个广搜，BFS 算法的一种扩展，啊， 呃，这个 BFS
算法，我们知道，它是从起始节点，以这个广度优先的这种顺序一层层扩展，
一直扩，扩展到目标节点，我们任务就算完成，但这个
DBFS 算法呢， DBFS 算法，它是从两个方向，
实际上就有两个起点，一个起点就是起始节点，另外一个起点就是目标节点，它从两个
节点开始，都进行扩展，而且扩展的方式都是用广度
优先的这个方式进行扩展，呃，
那从两个方向扩展以后，在这个扩展的过程中，两
个方向可能就碰，就可能会碰在一起，也就是说，有可能发生，
一个扩展队列中出现了从队头拿出来的一个节点，这个节点呢，在另外一个扩展队列中，它已经出现过，
啊，那么在这种情况下，我们就认为两个扩展的方向出现了交叉点，那出现交叉点，实际上就形成了一条，
从，呃，这个开始节点DOA交叉点的路径，然后交叉节点到这个， 这个目标节点也有一条路，那这两条路连起来，不就是一条从，
起始节点到目标节点的这个路径，对吧，也就是说我们找到了问题的解。
那这个双向广搜它对于单向广搜，
算法来说，它采取的双向扩展的方式，让这个搜索树的这个，
宽度就会明显减少，搜索树的宽度减少了，这个时间复杂度和空间复杂度肯定都减少了，对吧，
啊，那我们举，看一个图的例子，啊， 就是说，如果我们做单向广搜，假设这个是呃，这个开始节点，这个是目标节点，
那我们做单向广搜一层层扩展，它可能扩展出来是，到这样的一个三角形，扩展到这一层的时候，碰到了这个
目标节点，唉，那我们这个，呃，搜索就结束了，对吧，这就是扩展出来的这个节点数目，
这个大概说一下，是这样的一个三角形，对吧，
那如果我们做双向广搜的话，我们从，同时从节，开始节点，
开始节点在这儿，和这个目标节点同时向外扩展，呃，目标是这样扩展出去，其实节点是这样扩展过来，
然后，它在中间某个地方可能碰到了，就是开始节点它，从开始节点方向扩展出一个节点，
然后我们发现这个节点当初从目标节点扩展过去的时候都已经碰到它了，
也就是两头都碰上了，两头都碰上了，就等于找到了一条从开始节点到，
目标节点的路径，这时候我们一共扩展出来的节点数目呢就是在这个方块儿里面，
那这个方块儿里面呢数目，当然比这个大三角形的数目要少，对吧，
呃，这是一个呃，这个很粗略的，呃意思表达，粗略地画了一个图，
让你从直观上能够感受，唉，这个双向广搜，啊，它所扩展的节点数目是比单向广搜要少的，
那具体怎么个少法，我们还要严格一点来说，对吧，
那我们假设在这个一个问题里面，一个节点它能够扩展出 n 个节点，比如在八数码的问题里面，一个节点能扩展出几个啊，
最多就是呃，四个，对吧，因为那个空格，最多可以有四个移动方向，那好了我们假设一个节点它能够扩展出
n 个节点， 那，假设我们单向搜索，要搜到 m 层的时候才能找到答案，
那这个时候我们扩展出来的节点数目是多少呢，当然就是等比数列求和，对吧，那第一层只有一个节点，第二层就有，
呃 n 个节点，第三层就有 n*n 个节点，呃，等比数列求和，我们根据等比，
根据公式算出来，最后我们扩展出来的节点数目就是，这个数，啊，
那好了，呃这就是大三角形的数目，对吧，那如果对于这个双向广搜来说，
那我们假设同样一定，单向广搜，扩展了 m 层到这儿，
找到目标节点，对吧，那我们双向广搜，我们的扩展出来的这个层数，两边的层数加起来是一样的，因为我们是，
是在中间某个地方碰上了，那这个扩展的层数，两头加起来，它跟
单向广搜所扩展的这个层数一样，假设也是 m 层，对吧，是相同的，
那也就是说，同样，一，一共是扩展 m层， 那我们就是两边扩展出来的层数之和是 m
，那我可以采取某种平衡的 方式，你不要老是从一个方向扩展，你让两个方向轮流扩展，然后两边扩展出来的层数基本上差不多，
假设我们做到了让两边各扩展 m/2 层， 那这时候我们就有两个，呃，等比数列求和，求出来的节点
数目就是，2*（1-n
m/2)/(1-n)，这样一个东西， 那这个数值，跟这个数值相比，我们可以看出来，
在这个 m 大的时候，就会有很大的这个差别了，对吧， 指数级别的，节点数是指数级别的呃，
m 大的时候就有很大的差别， 啊，因此我们说双向广搜是能够有效地减少，呃，
扩展出来的状态数，那当然不管时间复杂度，还是空间复杂度都得到了降低，
那也就是说，我们在做这个节点扩展的时候，啊，
我们不要总是朝，在一头扩展，对吧，
或者我们也不要很机械地就轮流来，呃，起点那边扩展一次，然后终点这边扩展一次，我们不要这样机械地来，
我们应该总是选择节点数目比较少的那一边扩展，
那两头扩展就有两个队列，对吧，这两个队列里面的元素，也就是数量
可能会不一样，节点数量会不一样，我们选择节点数量比较少的那边进行扩展， 那我们的目标就是使得两边队列里面的元素个数总体来说差不多，这样
所能，所达到的最终目的就是说，从两边扩展出来的这个层次数是差不多，使得各是 m/2
层，对吧， 这样扩展出来的总的节点数目就会少，接下来，接下来我们看看这个双向广搜具体应该怎么写啊，
然后它有一个主要的函数叫作 dbfs ，双向广搜，那这个 函数一开始当然要把起始节点放入一个队列
q 里，啊，双向广搜， 双向广搜就有两个队列了，我们讲，把目标节点放入一个队列，q
1， 如果两个队列都没有空的话，
那我们要，呃，每一步我们取一个队列里面的队首节点进行扩展，到底取哪一个队列的队首节点进行扩展呢，
那如果 q0 里面的节点比 q1 中的少，我们就去扩展这个，呃，队列 q0
， 那如果 q0 里面的节点多呢，我们就去扩展队列里的
q1，啊， 那如果我们发现，
有一个队列空了，那假设是 q1 空了， q0 没空，那我们就不断地扩展，
不断地扩展 q0 ，直到把 q0 扩展空了，那这个问题就解决了，或者说无解，或者找不到答案，
那如果 q1 没空，而q0 空了，那我们就扩展 q1 ，这个是， dbfs
的过程。那具体每一，那具体每一步的扩展该怎么做呢， 比方说我现在写，写了一个函数叫expand（i），i
就是队列的编号，它是0或者1，那我要， expand（i）就是要从队列
qi 里面取一个头结点 H ，进行扩展，
啊，那我们取了头结点以后，我就要考查 H 的每一个相邻节点，所谓 相邻节点就是说，从
H 走一步就能够达到的那个节点，啊， 那这相邻节点，每一个都要考查，如果
相邻节点 od，adj ，它已经在队列 qi 中出现过，
那就是重复了的呗，那我就直接把这个，adj 给它扔掉不要了， 如果 adj 呢，没在
qi 中出现过，但是它在， 但，这，没在 qi中出现过，我们就要把这个
adj 放到队列 qi 里面， 然后我们还要看一下，adj ，是不是曾经在队列 q
i-1中出现过，要减去另外一个队列， 啊，是不是在另外一个队列中出现过，如果在
另外一个队列中出现过，就说明唉，就是说我们双向的这个广搜，它碰在一起啦，
两个方向有交叉啦，那问题就应该解决啦，这时候我们就可以输出找到的路径，这个找到的路径就是从
起点到这个 adj 的，这一条路，以及从， 呃以及从终点到
adj 的那条路的反过来，对吧， 把两条路连在一块儿，就是问题的解，
那当然这么，在这种做法里面我们会需要两个标志序列，分别记录，
呃，这个一个节点，它是不是出现在两个队列里面，那么
然后我们这个具体到这个八数码问题，呃，
刚才看到前面那个单向广搜， 的程序，在 POJ 上虽然能过，但是它花的时间是 891 毫秒，那
我写了一个双向广搜的呢，在 POJ 上就花63 毫秒就够了，我写了一个双向广搜，在HDU
上面是， 能够过的，好，这个八数码问题
我们讲到这儿，那双向广搜的程序呢，也提供给大家看，但是，
这个时间所限，没有办法再具体讲，那个程序呢，让大家自学一下吧，好。
Ознакомьтесь с нашим каталогом
Присоединяйтесь бесплатно и получайте персонализированные рекомендации, обновления и предложения.
Coursera делает лучшее в мире образование доступным каждому, предлагая онлайн-курсы от ведущих университетов и организаций.
© Coursera Inc., 2018 Все права защищены.
