赫尔辛基大学AI基础教程:搜索和解决问题(2.1节)

2018年05月24日 由 yuxiangyu 发表 140304 0


许多问题可以被视为搜索问题。这就要求我们从制定替代选择及其结果开始。






在实践中搜索:从A到B




想象一下你在一个外国的城市,在某个地方(比如一家酒店),想用公共交通工具去另一个地方(比如一家不错的餐馆)。你是做什么?如果你会像许多人一样,掏出智能手机,输入目的地并开始按照说明操作。




赫尔辛基大学AI基础教程


这个问题属于搜索和规划问题。自驾驶汽车需要解决类似的问题,还有用于玩游戏的AI(可能不太明显)AI。例如,在国际象棋比赛中,难度不是从A到B,以保证你棋子不被对手吃掉。


赫尔辛基大学AI基础教程


通常会有许多不同的方法来解决这个问题,其中有一些在时间,努力,成本或其他标准方面更为可取。不同的搜索技术带来不同的解决方案,而开发高级搜索算法是一个既定的研究领域。


赫尔辛基大学AI基础教程




在这里,我们不会去关注实际的搜索算法。相反,我们强调问题解决过程的第一阶段:定义选择及其结果,这往往远非小事,需要仔细思考。我们还需要确定我们的目标是什么,换句话说,我们何时可以解决问题。完成这些后,我们可以查找从初始状态到目标的操作序列。





在本章中,我们将讨论两种问题:






  • 在静态环境中搜索和规划只有一个“代理”。

  • 俩个玩家(“代理”)相互竞争




这两类并不涵盖所有可能的现实场景,但它们是通用的,足以演示主要的概念和技术。





在处理像导航或下棋这样的复杂搜索任务之前,让我们从一个简化的模型开始,以增强我们对如何通过AI解决问题的理解。




赫尔辛基大学AI基础教程




鸡过河问题




我们将从一个简单的问题开始,以阐明这种思路。一艘划艇上的机器人需要将三件货物运过河:一只狐狸,一只鸡和一袋鸡饲料。如果有机会,狐狸就会吃这只鸡,如果有机会,鸡也会吃饲料,两者都不是我们想要的结果。机器人在动物附近时,可以保证它们不吃,但也只有机器人可以操作划艇,并且皮艇最多只允许两件货物与机器人一起过河。机器人如何将其所有货物安全的移至河对岸?




注:

划艇谜题的简易版本

如果你之前听说过这个谜题,你可能会知道,即使船上空间更小,也可以解决。在我们一起解决这个简单的版本之后,你可以练习稍难的版本。

我们通过标出五个可移动的物体来模拟这个难题:机器人、划艇、狐狸、鸡和鸡饲料。原则上,这五个中的每一个都可以出现在河的任一侧,但是由于只有机器人可以操纵划艇,所以两者将始终在同一侧。因此有四种物体,每种物体有两种可能的位置,即16种组合,我们称之为状态:





鸡过河谜题的状态



赫尔辛基大学AI基础教程




我们给各状态写了简短的标识,否则确定属于哪个状态时会很麻烦。现在我们可以说,起始状态是NNNN,目标状态是FFFF,而不是说“在起始状态中,机器人在近侧,狐狸在近侧,鸡在近侧,并且鸡饲料在近侧,而在目标状态下,机器人在远侧“,等等。





这些状态中某一些是谜题条件禁止出现的。例如,在NFFN状态(意思是机器人和鸡饲料在近侧,但狐狸和鸡在远侧),狐狸会吃掉鸡。因此,我们可以排除NFFN,NFFF,FNNF,FNNN,NNFF和FFNN(如果你有所怀疑,可以自行检查)。我们留下以下十个状态:




赫尔辛基大学AI基础教程


接下来我们将弄清哪些状态转换是可能的,也就是说,当机器人将一些货物带到对岸时,会产生怎样的状态。最好绘制转换图,并且由于在任何转换中,第一个字母在N和F之间交替,因此在一行中绘制以N开头的状态(因此机器人在旁边),在另一行中绘制以F开头的状态是很方便的:


赫尔辛基大学AI基础教程


现在让我们画出转换。一般来说我们可以使用方向箭头,表示它们从一个节点指向另一个节点,但是在这个谜题中,转换具有可逆性:如果机器人可以从状态NNNN行进到状态FNFF,那么它同样可以从FNFF转换到NNNN。因此,简单地使用用没有方向箭头的线条简单地绘制转换即可。从NNNN开始,我们可以转换成FNFN,FNFF,FNFN,FFNF和FFFN:


赫尔辛基大学AI基础教程


然后我们填上其他的连线:


赫尔辛基大学AI基础教程




我们现在已经为这个谜题上做了很多的工作,没有看到更接近解决方案的情况,毫无疑问,通过自己动脑,你已经可以解决这个谜题。但是对于更复杂的问题,可能的解决方案数量成千上万倍的增长,我们的系统或机械方法将会起到效果,因为困难的部分适合于简单的计算机。现在我们已经制定了它们之间的状态更替和转换,剩余的部分成为了一个机械任务:找到一条从初始状态NNNN最终状态FFFF的路径。





在下面的图片中染色的路径。首先从NNNN到FFFN(机器人将狐狸和鸡带到另一边),然后再到NFNN(机器人将鸡带回起始侧),最后到FFFF(机器人将鸡和饲料带到另一边)。




赫尔辛基大学AI基础教程




状态空间,转换和成本




为了规则化规划问题,我们使用诸如状态空间(State space),转换(transitions)和成本(costs,也译为代价)等概念。




关键术语




状态空间


意思为一组可能的情况。在这个鸡过河谜题中,状态空间由从NNNN到FFFF的10个允许的状态组成(不包括如NFFF这样游戏规则不允许的状态)。如果任务要从地点A导航到地点B,状态空间可以定义为从A点出发可以到达的(x,y)坐标的集合。或者,我们可以使用的位置集合是有限的,例如,不同的街道地址,所以可能的状态数量也是有限的。




转换


转换是一个状态和另一个状态之间可能的移动,例如NNNN到FNFN。需要注意的是,我们只计算相邻状态之间的直接转换。例如,从A到C,从C到D,从D到B(目标)这一系列多重转换是一种路径,而不是一次单纯的转换。

成本


成本指的是,这样的事实,即不同的转换往往不尽相同。他们有不同的方式使某些转换变得更优选或更廉价(并不特指钱),而让其他的最贵。我们可以通过将每个转换与一定的成本相关联来表达这一点。如果目标是最小化旅行总距离,那么成本就是各状态之间的地理距离。又或者,目标是最小化时间而不是距离,在这种情况下,成本显然是时间。如果所有的转换都是平等的,那么我们可以忽略它。




练习5:更小的划艇





在这个难题的传统版本中,机器人只能在船上装一件东西。状态空间仍然相同,但转换可能更少。使用下面的状态转换图来查找从初始状态到最终状态的路径(我们建议你画着试试)。现在你的任务是计算从NNNN到FFFF的最短路径的长度。

最短路径中的转换次数是多少?



赫尔辛基大学AI基础教程



练习6:汉诺塔





让我们来做另一个谜题:汉诺塔(Towers of Hanoi,也称为河内塔)。在我们的版本中,这个难题涉及三个柱子和两个圆盘:一个大,一个小。(实际上,可以有任意数量的光盘,但对于这个练习,两个就足以证明这个原则了 。)

在初始状态下,两个碟片都堆放在第一个(最左边的)柱子中。目标是将圆盘移动到第三个柱子。你每次可以移动一个圆盘,但要求它上面没有其他圆盘。不允许在较小的圆盘上放较大的圆盘。

下图显示了初始状态和目标状态。还有其他七个状态,所以可能状态的总数是九:三种方式放置大圆盘,而它们中的每一种都有三种方式放置小圆盘。



赫尔辛基大学AI基础教程


你的任务:绘制状态图。该图应包含游戏中所有可能的九种状态,把可能的转换用线连接起来。下图显示了状态图的总体结构和前三个状态圆盘的位置。它表明,从开始状态(顶部),你可以移动小圆盘移动到另外两个状态。将剩下的状态放在正确的位置来完成状态图。请注意,转换是可逆的,你可以向侧面(左侧或右侧)或向上移动。

使用笔和纸来解决任务后,通过选择哪个状态属于图中的哪个节点来输入你的解决方案。(注意:每个状态只属于一个节点。)

赫尔辛基大学AI基础教程


为上图中的每个节点(1-6),从下图中选择正确的状态(A-F)。


赫尔辛基大学AI基础教程


方框1-6分别是什么状态?


 教程合集传送门:赫尔辛基大学AI基础教程

欢迎关注ATYUN官方公众号
商务合作及内容投稿请联系邮箱:bd@atyun.com
评论 登录
热门职位
Maluuba
20000~40000/月
Cisco
25000~30000/月 深圳市
PilotAILabs
30000~60000/年 深圳市
写评论取消
回复取消