AI基础:美女和野人过河问题

AI时代,如何更快入行抢占红利得高薪?前阿里巴巴产品专家带你15天入门AI产品经理。了解一下>

AI是一个提升高级度的概念,真正的AI远远不是说说而已。笔者以AI算法的经典问题为例,阐释了问题的解决逻辑和办法,展示了算法的形成过程。

AI(Artificial Intelligence)人工智能,可以说是最近比较火热一个词。就像曾经的互联网概念一样,任何一个项目只要和AI搭上边,就似乎显得非常高大上。

AI是一个领域,是一门学科,里面涉及的知识非常多,仅我们大家能想到的AI应用,就能随口说出数几种,像NLP(NaturalLanguage Processing)自然语言处理,TTS(TextTo 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种【0,1,2,3】,表示左岸没有美女,有1个美女,有2个美女,有3个美女;同样,野人的状态也有4种【0,1,2,3】,船的状态有2种【0,1】。

排列组合一下,我们整理初以下状态;同时,我们标记出不符合条件的状态:

  1. 野人人数大于美女人数的状态,用绿色标出,不符合条件,因为按照题目要求,河的左岸和右岸上,野人人数大于美女人数,美女会被吃掉,任务失败;这里不仅要考虑左岸的情况,也要考虑右岸的,例如:【2,0,1】,这就很明显,船在左岸的时候,右岸有1个(3减2)美女和3个(3减0)野人,也是不满足题目要求的。
  2. 不可能存在的状态,用黄色标出;例如:船不可能停在没有人的岸边【0,0,1】,以及美女不可能在野人占多数的情况下,划船到对岸【3,0,1】。

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

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

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

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

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

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

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

三、算法实现

我们分析的思路有了,接下来就是如何通过算法,实现我们的思想。

其实这就用到了数据结构中,经典的图的搜索——图的遍历,一般有深度优先和广度优先遍历算法。如果从最小生成树的角度,可以使用普里姆算法和克鲁斯卡算法。

如果题目要求最优解,我们还会用到最短路径计算的概念。这里如果扩展的话,又可以写很多。因为同一个问题,解决问题的方法也肯定不止一种。

接下来,我们算法实现的基本思路就是:

找出船上的载人状态,比如:船上可以有1个美女,1个野人,也可以有2个美女,也可以有2个野人;也就是船上的承载人数,受到船的承载量限制,本文题目要求是船上最多为2个。

我们根据船上的运送人员的数量,根据船的运送满足题目要求的结果,来去寻找满足条件的运送方案,之后我们存在动态数组中。

同时,为了防止重复计算,我们还要判断生成的方法是不是已经存在历史结果中。

当然,历史结果的存储我们用的也是动态数组;如果历史中已经有了这条信息,我们就不再计算,再去寻找新的方法。直到找出所有的结果。

实现的算法如下图3-1所示,已经经过实验检验,并可以保证正确运行。

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

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

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

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

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

图3-1 算法实现

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

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

图3-2 算法执行结果

四、结论

本文中,我们从美女与野人过河这个经典的问题出发,展开分析,阐述了解决此类问题的基本逻辑与解决方法,并对美女与野人的算法进行了扩展。

美女人数和野人数量,以及船的承载人数进行参数修改后,此算法仍然可以根据要求进行计算,算法的灵活性较强。如下图4-1所示:

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

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

本文也有不足之处,就是程序的算法仍然有优化的空间。

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

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

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

从这个实验中,我们也可以发现,仅这么一个简单问题,用到的理论知识已经相当多了,数据结构与算法、数值计算。而且还并不是十分完美,离理想中的优美的算法,还有较大的差距。

仅从这一个小问题出发,要做到算法的极限,仍然需要付出很多努力。而这仅仅只是人工智能中,非常非常非常基础的,非常非常非常微小的一个知识点而已,真要做到极致,博士也不是那么容易。

所以,有时候就不明白,有时仅仅本科毕业一两年的人也敢叫什么算法工程师,真不知道哪里来的自信。

真正的科学研究是枯燥的,是要沉下心来踏踏实实做研究的,也是要耐得住寂寞的。不走心的走秀最多只能是昙花一现,唯有踏实与真诚才可以基业长青。

最后,希望本文能给大家带来帮助。

共勉!

 

作者:王佳亮,中国计算机学会(CCF)会员。微信公众号:佳佳原创

本文由 @佳佳原创 原创发布于人人都是产品经理,未经许可,禁止转载

题图来自Unspalsh, 基于CC0协议

给作者打赏,鼓励TA抓紧创作!
评论
欢迎留言讨论~!
  1. 想问一下,为何不可以每一趟,一个美女和一个野人同时过去

    回复
    1. :grin: 过去了船咋回来

      回复