20世纪90年代,英国有一部流行的电视剧叫做《水晶迷宫传奇》(
The Crystal Maze),其中有一个谜题可以用来解释人工智能遇到的一个难题。这个谜题出现在未来世纪区(
Futuristic Zone),这是四个区之一,参赛者会在其中搜寻「时间水晶」以赢得时间来赢取最后水晶宫中的大奖。
[caption id="attachment_7111" align="aligncenter" width="668"]
![Rocky Horrow Show creator, Richard O'Brien during a photocall at Channel Four television for a new series of his show " The Crystal Maze".](/wp-content/uploads/2015/11/image-20151026-18431-xdf4iy.jpg)
Rocky Horrow Show creator, Richard O'Brien during a photocall at Channel Four television for a new series of his show " The Crystal Maze".[/caption]
在电视剧中,这个谜题从没有在2分钟的时间限制内完成过。它由若干红色圆圈以及连接它们的网络组成,墙上写着要求:「相邻圆圈内不能有连续字母。」旁边放着一堆红色圆盘,印着A~H的字母,可以放入圆圈内。
那么,正确的方法是什么呢?一开始,我们可以先确定,哪些圆圈是最困难的部分。只需要观察一下,你就会选择中间的两个圆圈,因为它们连接的圆圈最多。那么,A和H就是最适合这两个圆圈的选项,因为它们都只有一个邻居(A只和B相连,H只和G相连)。我们可以把它们放入下面这个图中。
![1](/wp-content/uploads/2015/11/12.png)
现在,我们可以做一些推理,来排除掉其他圆圈中不能填的选项。比如说,左上角的圆圈和A和H都相连,由于字母不能连续,所以排除掉B和G。右上角、左下角、右下角的圆圈也可以用同样的方法,排除掉B和G。
![2](/wp-content/uploads/2015/11/24.png)
最左边和最右边的圆圈需要分别对待,因为它们分别与A和B相连。左边的,我们可以排除B,右边排除G。
![3](/wp-content/uploads/2015/11/33.png)
在仔细看看剩下的选项,只有最左边的圆圈可以选择G,只有最右边的圆圈可以选择B。只要把G和B放进去,其他四个圆圈中也可以排除掉一些选项了。
![4](/wp-content/uploads/2015/11/43.png)
现在,我们再猜一猜。左上角圆圈还剩3个可能性C、D和E,那就先选第一个C吧。这样,右上角圆圈就排除了D。左下角就只能是D,而右下角就只能是F。这样,我们就解出了这个问题。如下图所示。
决策,还是决策
这个谜题属于一个很大的决策问题类型,在生活中很常见,例如医院或工厂的名字登记策略,调度公交车或火车,或者设计医疗实验。为了帮助我们得出最好的解决方案,人工智能的一大挑战就是开发出一种通用的方法,对这些问题进行表征和推理。
其中一个方法是所谓的约束满足问题( constraint satisfaction problem)。就像水晶迷宫里的谜题一样,满足这个模型的问题都涉及到如下这些方面:一组需要进行的决策(比如,把红色盘子放入所有圆圈中);一组可能性(用所提供的A~H圆盘);一组约束条件,只允许某些可能性的组合出现(如,相邻圆圈内不能有连续字母)。如果你把这些问题的要求放入一个约束求解软件中,它就会尝试解决这个问题。它解题的方法与我们很相似:将猜测(我们称之为「搜索」)和推导结合起来,并基于目前的决策排除掉那些无法作为解的可能性。
在这个领域,程序员最大的挑战就是,当输入的问题变得越来越多时,会变得越来越难找到解。这与软件「猜测」答案的方式直接相关。尽管在简单的谜题中,我们的猜测被证明是正确的,但人工智能(AI)却常常将我们领向死路。庞大的问题中,可能存在大量的可能性,同样也存在大量的死路。
其中一个关键问题是,有没有一种不需要钻进死胡同的答案搜索方法?目前我们并不知道。这与计算机科学中两个最重要的开放式问题有关:P问题和NP问题。为此,美国克雷数学研究所悬赏1百万美元征集答案。从本质上说,它就是在询问,如果一个问题的答案能被计算机迅速检查,那这个问题是否也能被计算机迅速解决。
目前流行的答案是否定的。如果真是这样,我们的软件不得不搜索所有可能的猜测,那我们必须让它的效率尽可能的高。这里有一个重要的因素是:搜索策略——我们想让计算机下一步聚焦在什么决策,以及我们赋予它的权重是多少。还有一件非常重要的事情是,特定问题的要求是什么。可以选择把谜题直接套入约束满足的模板,但是在真实生活中,还有很多其他选项。只有选择了正确的策略和模型,才能在实际可行的时间内迅速找到解决办法。
现在,我们的水平已经比10年前高很多,目前的约束求解软件可以解决比10年前复杂很多的实际问题。它被用在科学项目中,例如去年的菲莱彗星着陆器。它还能为灾害事件编制更好的疏散计划。
![epa04487728 A handout picture released by the European Space Agency (ESA) on 13 November 2014 shows the panoramic view created from the first two CIVA images, confirming that Rosetta's lander Philae is safely on the surface of Comet 67P/Churyumov-Gerasimenko. One of the lander's three feet can be seen in the foreground. The 100-kilogram probe touched down on Comet 67P/Churyumov-Gerasimenko, seven hours after separating from its mothership Rosetta half a billion kilometres from Earth. Philae's task is to collect images and samples from the dusty iceball, which will give clues about the origins of the solar system. EPA/ESA HANDOUT HANDOUT EDITORIAL USE ONLY](/wp-content/uploads/2015/11/image-20151026-18411-1o8yk6g.jpg)
约束求解在调度问题中非常成功,但是,还有许多其他的AI工具可以解决更多类型的问题。例如,命题满足、进化算法、数学规划技术等,它们可以组合使用来解决问题。一旦计算机能够完成这样的分析,我们就能往前迈进一大步。
来自theconversation,作者Ian Miguel,Patrick Prosser。机器之心编译出品,编译:汪汪