大家好
数据结构与算法这一讲
我们继续第三章栈与队列的学习
我们今天介绍队列的一个应用
在问题求解的时候
我们给过一个农夫过河的例子
农夫带着狼羊菜
从一个岸到另外一个岸
他划着小船过河的时候
只能够坐一个乘客
而且他不在的时候呢
狼和羊 羊和菜
不能够单独共处
从起始岸的角度来看这个问题
我把起始岸的合理的十个状态
列出来
然后呢
农夫带着一个物品
或者是说他什么也不带
他从一个岸到另外一个岸呢
就形成了这些状态之间的
一些联系
这个求解的过程呢
就是我们从起始的人羊狼菜
这样的一个结点
到最后的他们都到了彼岸
也就是在起始岸
是一个空结点
这样的可达路径的过程
在第七章图里面
我们会介绍一个最短路的
Dijkstra 算法
就可以解决这个问题
我们换一个角度来思考这个问题呢
我可以用一个位向量
来表达人狼菜羊这四个物品
它们是在起始岸还是在目标岸
在起始岸是0
而在目标岸是1
这样的话
我们就从初始的0000
这样的一个状态呢
经过某一些状态的迁移
要达到1111
这样的一个目标岸
那对刚才这样的
一个状态转移的空间
我们怎么来求解
一般来说我们有两类方法
第一类就是深搜的方法
就像我们皇后问题那样
我在第一行放了一个皇后以后
那我再看第二行的某一个位置
是不是能放
如果这个位置能放呢
那我就放下去继续放第三行
如果它不能放
我就换一个位置再放
如果在某一行
整个都没有位置可放了
那我就要退回到上一层再看
是不是上一层可以换一个状态
如果不行
那我们一层一层回退
一直可能要到第一行
去换这个位置
这个过程呢
就是一个深度优先的过程
如果我们看它的状态空间呢
就会是在一个结点出发
我沿着它的一个分支
尽量的往下面走
走到不能再走
我再在同层去换一个
然后如果这层也都不能够换了
那我就再回到上一层
再去试上一层的另外一个状态
这是深搜的一个求解的方法
我们可以用栈来辅助实现
也可以用递归来实现
我们这里呢
介绍一个宽搜的方法
宽搜的方法呢
它就是把顶层的所有的这些状态
都先存到这样的一个队列里面
然后呢
我们从队列头取出第一个结点
对这个结点下面的
可能的迁移状态
我又把它们都给设置好
然后呢再放到队列的尾部
我就相当于是从上到下
一层层这样的去扩展求解
我们再回到农夫过河这个问题
对它进行了这么一个问题的描述
也就是我们建立了状态的描述
然后我们知道
我们的问题是从0000到1111
这样的一个求解的要求
我们的数据的描述呢
那就很直接了
我就是用这么一个位向量
来表示各种可能的状态
这个位向量里面的0和1呢
分别代表的是起始岸和目标岸
然后我们这四个物品呢
它是有相应的固定的位置
这个位向量的话
我们有4位
它的可能的取值
其实总共有16种
但是其中有一些是不合法的
那我们去掉这些不合法的呢
它总共只有10种合法的状态
把这个位向量呢
其实就可以存在整数里面
因为我们整数是可以进行位运算的
例如对于农夫他在目标岸
其他的都在起始岸
这样的一个状态
那就是1000
当然这是一个非法的状态
因为没有他
狼和羊还有羊和菜
它是冲突的
目标岸表示为1111
这样表示了以后呢
我就可以描述整个这个求解过程
状态的一些迁移
还有一个重要的问题呢
就是对于这么一个状态的位向量
我怎么判断具体的哪一个物品
它是在此岸还是在彼岸
我们要对它进行相应的位运算
例如对于农夫
因为他对应的是最高的这一位
我们就用1000
来跟状态的位向量
进行一个按位与的运算
如果是农夫在目标岸的话
他这个相应的位
就会是1
与出来的结果
它一定是非0的
那就返回真
如果农夫他在这一位是0
也就是他在起始岸
那我们跟1000
按位与的结果呢
因为这个1000
它相应的第一的3位都是0
这边与出来的结果肯定是0
而如果农夫这一位是0的话
整个与出来的结果就是0
那我们就可以判断说
农夫他是在起始岸
对其他的几个物品也是
我们用它相应位的这么一个特征
来跟当前的这个状态
进行一个按位与的操作
另外我们还要判断一下
这个状态它是不是安全的
如果羊和菜
它是在一个岸
而农夫呢不在这个岸
就是不安全的 返回假
如果羊和狼它在一个岸
而且农夫他不在这个岸
也返回假
其他的状态才返回真
我们把这个算法的要求呢
再来捋一下
也就是说我们从起始的
一个0000的状态
要变成终止的1111这个状态
而且在这个解的序列当中
不能够有重复的状态
因为重复是没有意义的
重复了以后
下面这个片断
你可以再来一轮
只是做的无用的操作
而且如果你没有很好的
控制重复的话
很可能这个算法
会陷入一个死循环
这个状态的迁移过程
都是由农夫带着一个物品
要从这个岸到另外一个岸
或者他自己单独过去
我们还要用一些辅助的数据结构
来帮助农夫实现这样的搬运过程
其中最重要的就是队列
队列要保存当前的搜索的
空间的状态
还要定义一个
我们已经访问过的这个路径
要定义这个路径呢
我们最主要的就是要记录
这个状态呢
它是不是被访问过
如果它没被访问过呢
可以进入这个状态
同时我们把这个状态它的前驱
设为我刚才前面的那个状态
记录状态的路径
这个变量呢
它是一个数组
这个数组呢
它就对应的是我们16种
可能的状态
把它的初始值设为-1
而它的一个取值
就是在我们搜索的过程当中
从前面那个状态迁移到
它当前这个状态
它的前驱是谁
我们记录一下这个值
算法的实现
我们首先定义一些变量
然后呢把这个路径的数组
设置为-1
也就是所有的这些状态呢
都没有被访问过
然后我们把这个起始的状态
0000
给它存入到队列
同时把起始状态
对应的那个0位
设为它的前驱是0
这主要是区别于它没有被访问过的
那个-1的状态
我们来看这个算法的主框架
现在队列头呢
是整个这个状态空间的起始结点
也就是0000
然后我们进入循环
当队列不空
而且目标状态还没有出现的时候
我们从队列头
给弹出一个结点
然后尝试着带这几个物品之一
或者是什么也不带
我们让变量mover呢
从1开始发生变化
我们就是去试探下面几种选择
它的选择呢
其实就是1 2 4 8
对应的就是我们起始量0001
然后左移一位
变成0010
再左移一位
变成0100
最后左移一位
变成1000
相应的就是羊 菜和狼 人
这几个物品的特征位
前面三种就是农夫带着几种物品
最后1000呢
就是农夫什么也不带
他自己划着空船
从一岸走到另一岸
在循环的每一次呢
我们都是首先判断
这个农夫他跟待移动的这个物品
是不是在岸的同一侧
例如我们如果是开始的这个状态
0000
农夫呢要带着羊过去
可以看到这个农夫的特征位
和羊的特征位
它是相等的
因此它是在同样可以带过去
接着呢
我们要迁徙到下一个状态
我们是把这个农夫他的特征位
和我们待迁移的物品的特征位
进行一个或运算
得到一个新的特征的向量
然后这个特征向量呢
就跟我们前面那个status
来进行一个按位的异或运算
我们刚才的status是0000
那我们进行一个按位的
一个异或运算呢
就是农夫和他所携带的那个物品
就会发生改变
原来是0
现在就变成了1
而原来如果是1呢
它会变成0
另外两个物品
是不发生变化的
也就是说
我们从一个旧的状态 status
获得了一个新的状态
new status
接着我们要考虑这个新状态
它是不是安全的
而且呢要看这个新状态
它的路径呢
是不是已经被访问过
那也就是说这个状态
有没有在我们的一个解路径上头
出现过
如果没有
那我就可以把这个新状态呢
接受下来
我们把它记录在
我们的这个路径的
临时数组里头
而且它的前驱呢
就设为刚才这个status
接着把这个新的状态呢
插入到队列里面
等待着以后
继续进行宽搜的时候扩展
整个主框架呢
我们一直不断地进行
逐步的把这个队列里面的结点
给它弹出来
进行相应的操作
一直到队列为空
或者是我们的目标状态
已经出现了为止
如果是这个问题能够获得解
那我们把这个route[15]
它所存的这样一个前驱
然后逐个的逐个往前找它的前驱
一直找到route0为止
我们就得到了一个解的逆序序列
我们把这个序列给它倒转过来
就是正确的解
如果一直到完成了
刚才的主算法框架
我还没有遇到route[15]的合理解
这个时候呢
我们就不能够求解这个问题了
那就返回失败
那我们再来观察一下
这个算法它的一个求解的过程
其实我们从起始状态开始
我进行扩展的时候呢
可以发现它其实只有一个选择
来进行扩展
其他的两个呢
都是冲突的
从起始状态变到
下面这个状态的过程呢
我们是选的羊
也就是这里面只有两个位
是发生了改变
剩下的两个是不能变的
我们接着再变到下一个状态
只有人发生改变
别的是没有发生改变的
不断地从顶往下
然后一层层地把这种合理的状态
存到我们的队列里头
然后等待下一层的扩展
最后呢
遇到这样的一个解状态
我们的问题求解就完成了
最后给大家一个小游戏
在一个漆黑的夜晚
有一家五口提着一盏灯
要过独木桥
这五个人呢
他们过桥的速度不一样
而且在过桥的时候呢
只允许两个人同时过
过到对岸
还必须把那盏灯再拿回来
接这边需要过桥的人
这个灯呢它的延续时间
还特别的短
我们怎么设计一个方案
安排这一家五口合理的过桥
谢谢大家