人工智能基础之美女和野人过河问题

王佳亮

一、引言

AIArtificial Intelligence)人工智能,可以说是最近比较火热一个词。就像曾经的互联网概念一样,任何一个项目只要和AI搭上边,就似乎显得非常高大上。AI是一个领域,是一门学科,里面涉及的知识非常多,仅我们大家能想到的AI应用,就能随口说出数几种,像NLPNatural Language Processing)自然语言处理,TTSText To Speech)文本到语音,涉及的人机对话,语音合成。以及我们现在所用到的人脸识别,正在推广的刷脸支付,家里用的智能扫地机器人。情景感知智能家具、智能金融。无处不在的AI技术,同我们的生活息息相关,也在不断影响着我们的生活。AI概念本身不错,如区块链一样,本身是一个很好的理念,但由于部分人过度投机,使得这个领域也存在着参差不齐,鱼龙混杂的情况。现实中存在这种情况,是个人,会写个逻辑语句,就敢叫什么人工智能工程师,什么算法工程师,是个项目加一点点逻辑判断,也敢叫人工智能项目。比较浮躁,缺乏对科学基本的敬畏。我们目前所见到的所谓的人工智能的项目,大多是把市面上已经有的人工智能服务,自己整合一下,包装一下,用用而已,但如果真要形成核心产品,要有相当长的路要走,要投入巨大的人力物力财力。试想,你做的所有的服务,都是其他厂家所提供的,自己没有核心的技术,很容易受到其他厂商的控制,除非你将来做的产品可以被这些大厂收购,但话说回来,做的产品没有核心竞争力,只是整合别人的功能,是没有什么技术壁垒的,就更不要说形成自己的护城河了,很容易被模仿,超越。所以,个人认为,人工智能,最为基础的还是算法,要最最基础的研究,涉及大量的计算机、心理学、运筹学等各学科领域的知识。以文字转语音为例,单纯的一个字转成语音,不是很难,但一长段话转成很流畅的语音,并可以跟据不同人的音色来采样和播放,这一个看似很小的功能,背后有着大量的研发人员。人工智能的核心,就是算法,不同的算法结合起来,像一个个DNA一样,组成了人工智能的应用。所以,今天我们就从一个最简单的例子入手,从而开启人工智能最最基础的算法入门之旅。

二、问题场景

这个问题的确比较基础,网上搜索一下,会一有大堆这样的文章。我自己也在网上看了一些,但发现网上探索出来的内容还是不是很好,有些代码还存在一些问题。不是很严谨。这个世界上,指责别人最容易,认清自己最难。与其去吐槽别人,不如自己写一个更好一点文章,分享给大家。

现在我们进入主题。

有3个美女和3个野人要过河,只有1条船,没有船夫,这6个人都会划船。但这条船1次只能载两个人,任何情况下,只要野人的数量大于美女的数量,美女就会被野人吃掉。也就是说,在河的两岸,即河的左岸上和右岸上,野人的数量任何时候都不能大于美女的数量。

如何6个人能全部过河,并且美女安全(即不被野人吃掉)?

如果我们从逻辑上理解,其实就是各种方案的探索,最终试出一条可行的方案。

现状,我们可以认为他们都在河的左岸,要到河的右岸:

 

美女1 美女2 美女3   ||||

野人1 野人2 野人3   ||||

 第一步,两个野人先一起到河的右岸,然后一个野人回来:

 美女1 美女2 美女3   ||河||

       野人2 野人3   ||||   野人1


 第二步,两个野人一起到河的右岸,然后一个野人回来:

 美女1 美女2 美女3   ||河||  

             野人3   ||||   野人1 野人2


 第三步,两个美女去,然后一个美女和一个野人回:

美女2 美女3  ||||  美女1

        野人2 野人3  ||||  野人1

 

第四步,两个美女去,一个野人回。

 ||||  美女1 美女2 美女3

野人1 野人2 野人3  |||| 


第五步,两个野人去,一个野人回。

        ||||  美女1 美女2 美女3

野人2 野人3  ||||  野人1

 

第六步,两个野人回。

  ||||  美女1 美女2 美女3

  ||||  野人1 野人2 野人3

 

以上问题,可以理解为决策问题,其实也是人工智能学科中的一个非常基础的经典问题。

我们分析的思路以及答案,虽然似乎是解决了问题。但问题来了,除了我们上述使用的方法,这个题目还有没有其他方法?哪种最快?以上问题只涉及6个人,我们通过人工分析的方法,还可以将结果罗列出来,那如果是60个人,600个人,难道我们还是靠这种方法来分析?这样单凭人力手工计算是非常复杂耗时的。那如何实现呢?这就需要我们编制一套搜索算法,通过计算机来帮助我们计算。

三、问题分析

我们从初态和终态来分析,可以知道初态是河的左岸有3个美女和3个野人,而终态是河的右岸有3个美女和3个野人。就是初始状态是【3,3】,表示左岸最开始,有3个美女和3个野人。而终态是【0,0】,表示左岸最终美女和野人的数量均为0。而美女和野人,从左岸到右岸,右岸回左岸,是要靠船来运送的,所以,船的状态有两种(航行中就不考虑了),要么在左岸,要么在右岸。我们用1表示船在左岸,用0表示船在右岸。那么结合美女和野人的状态,最初始状态就是【3,3,1】,表示最初船停靠在左岸,左岸有3个美女,3个野人。那么终态我们知道,是船在右岸,左岸美女和野人数量都为0,那么怎么用数学来表示呢?就是【0,0,0】。

现在问大家一个问题,如果从状态的视角来分析,会有几种状态?

很显显然,会有32种状态,怎么来的?这就用到了数学基础中的排列组合。美女的状态有4种【0123】,表示左岸没有美女,有1个美女,有2个美女,有3个美女。同样,野人的状态也有4种【0123】,船的状态有2种【01】。排列组合一下。我们整理出

同时,我们标记出不符合条件的状态:

1、野人人数大于美女人数的状态,用绿色标出。不符合条件。因为按照题目要求,河的左岸和右岸上,野人人数大于美女人数,美女会被吃掉,任务失败。这里不仅要考虑左岸的情况,也要考虑右岸的,例如:【201】,这就很明显,船在左岸的时候,右岸有1个(32)美女和3个(30)野人,也是不满足题目要求的。

2、不可能存在的状态,用黄色标出。例如:船不可能停在没有人的岸边【001】,以及美女不可能在野人占多数的情况下,划船到对岸【301】。

整理后的状态表,如下表所示。

 表3-1 左岸美女与野人的状态表

 

我们根据以上的状态,画出状态空间图,如下图所示。


3-1 美女与野人过河的状态空间图

 

很显然,所有从初态可以到达终态的路径,都是美女可以安全过河的方案。

 

四、算法实现

 

我们分析的思路有了,接下来就是如何通过算法,实现我们的思想。其实这就用到了数据结构中,经典的图的搜索。图的遍历,一般有深度优先和广度优先遍历算法,如果从最小生成树的角度,可以使用普里姆算法和克鲁斯卡算法。如果题目要求最优解,我们还会用到最短路径计算的概念。这里如果扩展的话,又可以写很多。因为同一个问题,解决问题的方法也肯定不止一种。接下来,我们算法实现的基本思路就是:找出船上的载人状态,比如:船上可以有1个美女,1个野人,也可以有2个美女,也可以有2个野人。也就是船上的承载人数,受到船的承载量限制。本文题目要求是船上最多为2个。我们根据船上的运送人员的数量,根据船的运送满足题目要求的结果,来去寻找满足条件的运送方案,之后我们存在动态数组中。同时,为了防止重复计算,我们还要判断生成的方法是不是已经存在历史结果中,当然,历史结果的存储我们用的也是动态数组。如果历史中已经有了这条信息,我们就不再计算,再去寻找新的方法。直到找出所有的结果。实现的算法如下图4-1所示,已经经过实验检验,并可以保证正确运行。


 




图4-1 算法实现

代码执行结果,我们可以看到,安全过河的方法有好几种。如下图4-2 算法执行结果所示。

4-2 算法执行结果

 

五、结论

本文中,我们从美女与野人过河这个经典的问题出发,展开分析。阐述了解决此类问题的基本逻辑与解决方法。并对美女与野人的算法进行了扩展。美女人数和野人数量,以及船的承载人数进行参数修改后,此算法仍然可以根据要求进行计算,算法的灵活性较强。如下图5-1 人数与船承载量参数修改后执行的结果,所示。

5-1 人数与船承载量参数修改后执行的结果

 

本文也有不足之处,就是程序的算法仍然有优化的空间。根据测算,当船最大承载量为2,美女和野人数量各为8人的情况下,找到第一种方案程序需要执行约40万次。如下图5-2所示,算法的时间复杂度和空间复杂度较高,仍然有进一步的优化空间。

5-2  美女和野人数量各为8人的情况

 从这个实验中,我们也可以发现,仅这么一个简单问题,用到的理论知识已经相当多了,数据结构与算法、数值计算。而且还并不是十分完美,离理想中的优美的算法,还有较大的差距。仅从这一个小问题出发,要做到算法的极限,仍然需要付出很多努力,而这仅仅只是人工智能中,非常非常非常基础的,非常非常非常微小的一个知识点而已。而真要做到极致,博士也不是那么容易。所以,有时候就不明白,有时仅仅本科毕业一两年的人也敢叫什么算法工程师,真不知道哪里来的自信。真正的科学研究是枯燥的,是要沉下心来踏踏实实做研究的,也是要耐的住寂寞的。不走心的走秀最多只能是昙花一现,唯有踏实与真诚才可以基业长青。最后,希望本文能给大家带来帮助。

共勉!