3.22在线视频

我们来看一个有趣的游戏

从这个游戏来思考上面提出的问题

同时

也可以看看人和机器是怎样

协同解决问题的

这个游戏就是人和动物渡河的问题

题面是这样的

人要把鸡猫米

这三种物品从河的左岸运到河的右岸

人呢一次只能带鸡猫米三者之一过河

或者人单独过河

我们知道猫要吃掉鸡

鸡要吃掉米

所以猫和鸡或者鸡和米

是不能同时在一个地方出现的

那么现在人要把鸡猫米

从河的左岸安全的送到右岸

请设计一个安全的渡河方案

要求人通过最少的渡河次数

来完成这个任务

我们来思考一下怎么解决这个问题

如果我们利用计算机

来帮助我们解决这个问题

那么又该怎么办呢

另外

这个过程当中哪些是计算机解决的

哪些是人解决的

首先

我们想到

人鸡猫米

根据规则的不同

会出现多种不同的组合状态

另外

在船上也有多种不同的组合状态

在直觉的引导下

我们会想到能不能用向量的方式

把所有的可能组合状态全部都列出来

是不是可以用图的方式

把这些状态之间的转换过程

描述出来呢

按照这个思路

我们先来设置状态向量

然后画出状态之间的转换图

当我们把所有的状态转换的可能性

都用一张图表示出来

理论上我们就一定能找到最佳的渡河方案

对吧

我们知道机器能解决的问题

一般是需要确定的状态输入的

也就是说

如果要用计算机来解决问题

首先要把问题用数值化的方式表示出来

在这里

我们需要把人

人猫鸡米的不同的组合状态

用数值化的向量来表示

那么这里

我们设置两个数值向量a向量和b向量

我们用a向量来表示

它们是在左岸还是右岸

我们用1来表示人或者某物品

在左岸的状态

用0来表示它们在右岸

人猫鸡米分别对应a1a2a3和a4

比如

某个a状态是

1010

按着刚才我们的约定

就表示人和鸡在左岸

猫和米在右岸

同样的道理如果a状态是1111

表示他们都在左岸

如果a状态是0000

那么表示他们都在右岸

同样呢用b状态来表示它们是否在船上

人猫鸡米分别对应b1b2b3和b4

我们用1表示某个物品在船上

0表示不在船上

比如

某个b状态是1100

表示人和猫都在船上

鸡和米不在船上

当然人是一定要在船上的

那么我们一共有多少状态呢

一共有16个a状态

16个b状态

因为都是4个2进制数组成的状态

那这32个状态是不是我们

题面允许的合理状态呢

我们知道猫是要吃掉鸡

鸡也是要吃米的

因此有些状态是不可能出现的

我们来分析一下

比如a状态里的1010

这个状态是不是合理的

这个状态描述的是人和鸡在左岸

猫和米在右岸

这个状态是没有违反我们约定的

它是合理的

但是如果a状态是0011呢

它表示的是人和猫是在左岸

而鸡和米在右岸

那这种状态下鸡会把米吃掉

这个状态显然是不合理的

通过分析我们知道a状态

有十个是合理的状态

也就是可取状态

那么六个是不合理的状态

或者是叫不可取状态

好我们再来分析一下b的状态

就是在船上的状态

船上也是有一共16种情况

但是船上一共可取状态的是多少呢

刚才我们讲了

人一次只能带鸡猫米的三者之一过河

或者人单独过河

所以说一共只有四种可取状态

其实

我们通过刚才的步骤

把不同的状态用0和1的

数值向量表示了出来

这个过程就是现实问题的抽象过程

通过对问题的抽象

我们把渡河的各种状态抽象成了

特征的数值向量

接下来

就是渡河的过程

在这里就是各个状态的转换过程

我们把这个过程用图形化的方式表示出来

左岸就是这五种状态

右岸是另外五个状态

他们是对应的

B是在船上的4种状态

这里呢

我们试图给这个问题建立一个数学模型

那么我们再来看一看原来的问题

变成了什么问题呢

我的题面的问题是所有的物品和人都在左岸

问人要经过多少次

最少的次数

来回搬运

才能把所有物品运到右岸

如果把这个问题用数学的语言来表述

就转化成了

如果我们要从a1111状态

也就是都在左岸的状态

至少经过多少次状态

转化才能变成a0000的状态

也就是都在右岸的状态

那么这样一来

这个问题实际上就变成了一个计算机

可以解决的问题了

第二个步骤

我们要把

整个的状态转移图

全部都画出来

也就是把状态转移的中间的过程

全部都用画的方式表达出来

我们先分析一下

每一次渡河都会改变原来的a状态

如果说是我们渡船一次

状态a1变成了另外一个

a的状态比如说我们用a10来表示

这个过程发生了什么

最开始

大家都在左岸

a的状态是a1

1111

如果先让人把鸡运过去的话

这个时候a状态会变成什么呢

因为人和鸡到了右岸

那么只有猫和米留在了左岸

也就是说这个时候a1状态变成了a10

0101的状态

那么

从1111到0101

改变他们是怎么发生的呢

我们结合规则思考一下

不难得到结果

我们注意到人和鸡在船上的状态

可以用b1010来表示

经过分析

我们发现

1111的a状态

通过与b状态1010的结合

会得到这次渡河后的a10状态0101

也就是说

从数学上讲

每次渡河的过程

可以用a和b向量的一次二进制

运算来表示

那么这个运算是什么运算呢

如果有一点布尔代数的知识

我们就知道这是一次二进制异或运算

这样

我们就得到了状态转换的计算公式

如果你不知道异或运算也没关系

只要知道一次渡河可以表示成

a向量和b向量的一次二进制运算

那么就可以了

这样

我们就可以把所有的渡河

都用a和b的异或运算表示出来

那么A1状态第一次渡河

有四种不同的渡河方式

可以转换为对应的

另外四种a状态

这实际上是对应了四个不同的异或运算

新生成的a状态

是我们要进行后续渡河使用的

这其中有一些是合理的状态

有一些是不合理的状态

我们只需要关注合理的新的a状态

然后再把这些状态向量分别与

四种渡河向量b做异或运算

这样

我们就会得到所有的后续状态转换的情况

这种方法我们称为穷举法

这样

我们就可以把整个

过程状态转换用图的方式表示出来

问题的答案就藏在这个状态转换图里

从这张图上

我们很容易找出满足条件的

最少渡河次数方案

分析以后

我们发现有两种渡河方案

是渡河次数最少的

都是经过了七次渡河

就完成了把所有物品

从左岸带到右岸的过程

其中一个方案是这样的

第一次人先把鸡从左岸运过河

然后人再单独回到左岸

接着人再把猫运到右岸

这样

只有米在左岸

鸡和猫是在右岸

这当然是符合规程的

然后人再把鸡运回左岸

同时在把米带到右岸

这样

就是鸡在左岸

猫和米在右岸

同样也是符合规则的

最后一次

人再单独回到左岸

最后把鸡带到右岸

完成整个渡河过程