当前课程知识点:智能时代下的创新创业实践 > 第三章智能时代的创新技术 > 3.2机器有“智慧”吗? > 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做异或运算
这样
我们就会得到所有的后续状态转换的情况
这种方法我们称为穷举法
这样
我们就可以把整个
过程状态转换用图的方式表示出来
问题的答案就藏在这个状态转换图里
从这张图上
我们很容易找出满足条件的
最少渡河次数方案
分析以后
我们发现有两种渡河方案
是渡河次数最少的
都是经过了七次渡河
就完成了把所有物品
从左岸带到右岸的过程
其中一个方案是这样的
第一次人先把鸡从左岸运过河
然后人再单独回到左岸
接着人再把猫运到右岸
这样
只有米在左岸
鸡和猫是在右岸
这当然是符合规程的
然后人再把鸡运回左岸
同时在把米带到右岸
这样
就是鸡在左岸
猫和米在右岸
同样也是符合规则的
最后一次
人再单独回到左岸
最后把鸡带到右岸
完成整个渡河过程
-0.1我们为什么设计这门课
--0.1
-0.2我们聊什么
--0.2
-0.3你们能学到什么
--0.3
-短片:AlphaGo
--Alphago
-1.1本章概述
--1.1
-1.2人与机器的本质区别
--1.21
--1.22
--1.23
-1.3我们会被智能机器抢了饭碗吗
--1.31
--1.32
--1.33
-1.4人和智能机器的和谐之道-增强智能
--1.41
--1.42
--1.43
--1.44
--1.45
--1.46
--1.47
-1.5项目指南一:如何找到好的项目
--1.51
--1.52
--1.53
--1.54
--1.55
-第一章测试
-2.1本章概述
--2.1
-2.2创业能力模型
--2.21
--2.22
--2.23
--2.34
--2.25
--2.26
--2.27
--2.28
--2.29
-2.3创新是人类的本能
--2.31
--2.32
--2.33
-2.4创新能力培养——创新心智模式
--2.41
--2.42
--2.43
--2.44
--2.45
--2.46
-2.5创新能力要素培养-思维方式
--2.51
--2.52
--2.53
--2.54
--2.55
-2.6项目指南二:创新项目的开发
--2.61
--2.62
--2.63
-2.7互联网心理学
--2.7
-第二章测试
-3.1本章概述
--3.1
-3.2机器有“智慧”吗?
--3.21
--3.22
--3.23
--3.24
--3.25
--3.26
--3.27
-3.3机器是如何学习的?
--3.31
--3.32
--3.33
--3.34
--3.35
--3.36
--3.37
--3.38
--3.39
--3.310
-3.4智能技术带来的认知升级
--3.41
--3.42
--3.43
--3.44
--3.45
-3.5项目指南三:投资者和创始人的心得经验
--3.51
--3.52
--3.53
--3.54
--3.55
-第三章测试