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

AiTechYun

编辑:yxy

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

在实践中搜索:从A到B

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

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

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

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

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

  • 在静态环境中搜索和规划只有一个“代理”。
  • 俩个玩家(“代理”)相互竞争

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

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

鸡过河问题

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

注:

划艇谜题的简易版本

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

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

鸡过河谜题的状态

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

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

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

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

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

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

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

状态空间,转换和成本

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

关键术语

状态空间

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

转换

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

成本

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

练习5:更小的划艇

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

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

练习6:汉诺塔

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

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

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

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

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

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

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

本文分享自微信公众号 - ATYUN订阅号(atyun_com)

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2018-05-24

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏CDA数据分析师

3个步骤彻底学透Excel

本文为简书作者数据充电宝原创,CDA数据分析师已获得授权 目录 Excel函数学习常见的误区和问题及解决办法 ● 苦恼 ● 原因 ● 解决办法 学习3步法 (重...

22780
来自专栏CDA数据分析师

案例 | R语言数据挖掘实战:电商评论情感分析

随着网上购物的流行,各大电商竞争激烈,为了提高客户服务质量,除了打价格战外,了解客户的需求点,倾听客户的心声也越来越重要,其中重要的方式 就是对消费者的文本评论...

918100
来自专栏后台全栈之路

《ArcGIS 地理信息系统教程》概念笔记

之前研究了 GIS,接触到了很多 GIS 的概念。因此找了《 ArcGIS 地理信息系统教程(第 4 版)》来看。书的版本比较老了,不过一些基本概念还是想通的,...

36060
来自专栏灯塔大数据

探秘 | Python 求职 Top10 城市,来看看是否有你所在的城市

导读:从智联招聘爬取相关信息后,我们关心的是如何对内容进行分析,获取用用的信息。本次以上篇文章“5分钟掌握智联招聘网站爬取并保存到MongoDB数据库”中爬取的...

35030
来自专栏用户画像

相似人群画像算法

由于TESLA集群无法直接操作MongoDB,需要将TDW里面的用户画像数据,通过洛子系统导出至HDFS,再与MongoDB中原有群画像进行合并。

77150
来自专栏AI科技评论

开发 | MIT Taco项目:自动生成张量计算的优化代码,深度学习加速效果提高100倍

AI科技评论消息:我们生活在大数据的时代,但在实际应用中,大多数数据是“稀疏的”。例如,如果用一个庞大的表格表示亚马逊所有客户与其所有产品的对应映射关系,购买某...

399110

Python NLTK 自然语言处理入门与例程

那么 NLP 到底是什么?学习 NLP 能带来什么好处?

2.1K70
来自专栏非著名程序员

厉害了,我的同性交友网站

作为世界上最大的同性交友网站,真的是越来越好了。弱弱的,欠抽样的问一句:你们看到标题《厉害了,我的同性交友网站》,是不是以为我开发了一个同性交友的网站呢?哈哈…...

67120
来自专栏程序你好

程序员算法基础——贪心算法

23220
来自专栏数据小魔方

R语言可视化——ggplot图表配色技巧

今天跟大家分享ggplot图表的配色原理与基本技巧。 图表配色是一个很深奥的话题,多亏了R语言平台的众多开发者贡献的配色包,让图表的配色不再深不可测。 这里我暂...

80140

扫码关注云+社区

领取腾讯云代金券