赫尔辛基大学AI基础教程:使用AI解决问题(2.2节)

2018年05月25日 由 yuxiangyu 发表 112605 0

人工智能历史的历史:从搜索开始




人工智能可以说和计算机科学一样古老。早在我们拥有电脑之前,人们就会想到自动推理和智能的可能性。而思考这个问题的伟大思想家之一就是艾伦·图灵。除了图灵测试之外,他对人工智能的贡献,或者说对计算机科学的贡献还包括对任何可以计算(=用数字或其他符号计算)的东西都可以实现自动化的见解。




注:


帮助赢得二战


图灵设计了一个非常简单的设备,可以计算任何可以计算的东西。他的设备被称为图灵机。虽然这是一个实际上并不实用的理论模型,但它将图灵引向了可编程计算机的发明:根据不同编程方式可以执行不同人物的计算机。


这样,我们不必为每项任务构建不同的设备,而是使用同一台计算机完成许多任务。这就是编程的概念。时至今日,这个发明听起来微不足道,但在图灵的时代,远非如此。在第二次世界大战期间,一些早期的可编程计算机被用来破解德国的密码,这是图灵也亲自参与的一个项目。

术语人工智能通常归因于约翰·麦卡锡(John McCarthy,1927-2011) - 他通常也被称为人工智能之父 - 但事实上他否认提出这个术语。尽管如此,他在新兴领域的采用方面仍然具有影响力。这一术语被确定为夏季研讨会—达特茅斯会议(Dartmouth conference)的主题,会议由麦卡锡组织,1956年在新罕布什尔州达特茅斯学院(Dartmouth College)举行。在组织研讨会的提案中,麦卡锡继续阐述了图灵关于自动计算的论点。


注:

约翰麦卡锡关于人工智能的主要声明:

“这项研究是基于一种猜想,即学习的每一个方面或智力的任何其他特征在原则上都能被精确地描述为能够模拟它的机器。”

换句话说,智能的任何元素都可以分解成更小的步骤,以便每个步骤都如此简单和“机械”,以至于它可以作为计算机程序记录下来。这个说法,至今仍是一个猜想,也就是说我们不能证明它是真的。尽管如此,这也是实现人工智能的绝对基础的。当我们谈到AI的哲学时,我们就会回到这个观点。





为什么搜索和游戏会成为人工智能研究的核心




20世纪50年代,随着计算机逐渐发展到可以用人工智能算法进行实验的水平,最突出的AI问题(除了破解纳粹代码之外)就是游戏。游戏提供了一个方便的可以很容易地形式化的限制域。棋盘游戏,如跳棋,国际象棋,最近还有围棋,极大的鼓舞了无数的研究人员。





与游戏密切相关的是,搜索和规划技术是AI在20世纪60年代取得巨大进步的一个领域:当时开发的算法如Minimax或Alpha-Beta剪枝等仍然是AI的基础,当然,这么多年来已经提出了更高级的变体。在本章中,我们将从概念层面研究游戏和规划问题。





练习5:更小的划艇





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

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



赫尔辛基大学AI基础教程


7次。从NNNN开始到目标FFFF有两条最短路径。其中一个是NNNN→FNFN→NNFN→FFFN→NFNN→FFNF→NFNF→FFFF,另一个是NNNN→FNFN→NNFN→FNFF→ NNNF→FFNF→NFNF→FFFF。也就是说,策略是首先将鸡移到远侧,然后返回将狐狸或饲料带到远侧。然后再将鸡带回到近侧以免它被吃掉或者吃掉饲料,并将剩下的其他物品(狐狸或饲料)从近侧带到远侧。最后,机器人去取鸡,并把它带到远侧,达到目标​​。



练习6:汉诺塔





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

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

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



赫尔辛基大学AI基础教程


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

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

赫尔辛基大学AI基础教程


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


赫尔辛基大学AI基础教程


答案:EBFDCA



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

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