人工智能（第3版高等学校计算机教育规划教材）

作者简介

\"贲可荣，海军工程大学教授、博士生导师，中国计算机学会理论计算机科学专委副主任、软件工程专委委员，担任军队人工智能专业组专家，获军队院校育才奖金奖。硕士、博士先后师从南京大学莫绍揆先生、国防科技大学陈火旺先生，打下了扎实的理论基础。 张彦铎，武汉工程大学党委常委、副校长、教授，湖北省有突出贡献的中青年专家，中国人工智能学会智能机器人专业委员会委员、机器人足球技术专业委员会委员，国际机器人足球联盟中国分会华中地区召集人。 \"

内容简介

第3章 搜 索 技 术搜索技术是一种通用的问题求解技术,一直是人工智能的核心研究领域。它通常是先将待解问题转化为某种可搜索的“问题空间”(problem spaces),然后在该空间中寻找解。问题空间通常由于规模巨大不适于采用显式的枚举表示,而采用隐式的形式化问题模型。不同类型的问题可表示为状态空间(state spaces)、方案空间(solution spaces)等不同类型的空间,因而需要不同的方法予以形式化。不同类型的问题空间因结点(nodes)和弧(arcs)的含义不同也需要相适应的搜索算法。 本章将主要介绍基于状态空间的搜索技术。此类技术的共同特点是: 使机器人(Agent、智能代理)在采取行动之前,以达成某目标状态为目的,在状态空间上搜索得出从初始状态可达到目标状态的“动作序列”。注意,搜索技术是机器人在思考阶段的一种技术。当然,这种思考在实际问题上的适用性也取决于两个方面: 问题模型的适用性、搜索算法的适用性。对于较复杂的实际问题,采用过于简单、抽象的问题模型或许导致搜索得出的方案不可用。对于新的问题模型,以往的搜索算法也很可能无法得出最优方案。 本章介绍3种重要的状态空间上的通用型搜索技术。第一种状态空间常用于建模单方面行动问题,第二种状态空间(ANDOR图)常用于建模复杂问题的分解,第三种状态空间常用于建模双方博弈问题。 3.1概述 搜索技术是人工智能的基本求解技术之一,在人工智能各领域中被广泛应用。早期的人工智能程序与搜索技术联系就相当紧密,几乎所有的早期的人工智能程序都以搜索为基础。例如,A.Newell和H.A.Simon等人编写的LT(Logic Theorist)程序,J.Slagle写的符号积分程序SAINT,A.Newell和H.A.Simon写的GPS(General Problem Solver)程序, H.Gelernter写的Geometry TheoremProving Machine程序, R.Fikes和N.Nilsson写的STRIPS(Stanford Research Institute Problem Solver)程序以及A.Samuel写的Chechers程序等,都使用了搜索技术。现在,搜索技术已渗透在人工智能各领域中,例如,专家系统、自然语言理解、自动程序设计、模式识别、机器人学、信息检索和博弈等领域都广泛使用搜索技术。搜索技术具有如此丰富应用领域的原因在于: 广义地讲,人工智能的大多数问题都可以转化为搜索问题。 人工智能需处理的问题大部分是结构不良或非结构化问题,对这样的问题一般不存在显而易见的求解算法。对于给定的问题,智能系统的行为首先应是找到能够达到所希望目标的动作序列,并使其付出的代价最小、性能最好。基于给定的问题,问题求解的第一步是问题的建模。搜索就是为智能系统找到动作序列的过程。搜索算法的输入是问题的实例,输出是表示为动作序列的方案。一旦有了方案,系统就可以执行该方案给出的动作了。通常,解决一类问题主要包括3个阶段: 问题建模、搜索和执行,而且多数实际问题都需要这3个阶段的多次迭代，才能予以解决。本章主要讨论搜索阶段,其他两个阶段会在其他章节予以讨论。能进行搜索的前提是问题具有良好的结构,为此,下面介绍形式化问题模型(formalized problem model)。 适于进行搜索的问题由以下4部分组成。 人工智能（第3版）第3章搜索技术(1) 初始状态(initial state): 描述了Agent在问题中的初始状态。 (2) 动作集合(actions): 每个动作把一个状态转换为另一状态。 (3) 目标检测(goal test)函数: 用于判断一个状态是否为目标。 (4) 路径费用(path cost)函数: 指明路径费用的函数。此函数用于支持搜索算法，寻找费用最优的路径。 其中,初始状态和动作集合(隐式)定义了问题空间。我们首先解释“定义”的含义,然后解释“隐式”的用意。问题空间是有向图,由结点和弧组成。根据(1)和(2),能判断给定的一个结点是否属于该问题空间,同样,能判断一条弧是否属于该空间。因此说,(1)和(2)定义了该问题空间。所谓“隐式”,是相对“显式”而言。显式地定义一个问题空间的方式是将其中所有的结点和所有的弧罗列出来并存储在内存中。然而,对于人工智能中的非平凡问题,其结点数目和弧的数目都是巨大的,若罗列出来,则计算机的存储空间或许不能完全存储(试想,若问题空间包含1020个结点,需要多大的内存空间)。当内存不能支持问题的完全存储时,搜索程序则无法开始。因此,“隐式”的问题模型是搜索技术成为可行的关键。下面分别以旅行售货商问题(Traveling Salesperson Problem,TSP)和九宫图问题(Eight Puzzle Problem)为例,说明建立形式化模型的基本方法。 TSP问题为: 已知一些城市和这些城市之间的距离,为售货商找到一条从初始城市出发经历其他城市仅一次且最终回到初始城市的最短路径。当然,其中的“城市”可以为任意距离的地点,或者是同城内的地点。TSP问题与我们当前熟悉的快递配送业务极其相关,也适用于其他类型的路径搜索业务。图31TSP问题实例图31是一个TSP问题实例,其中含4个城市: A、B、C、D,城市之间的距离在边上标出。TSP问题虽然在生活中常见,但在计算上却是困难的。理论上,TSP问题的计算复杂度是NP完全的,因而成为人工智能领域的典型问题。针对TSP问题,怎样用“初始状态”“动作集合”“目标检测函数”和“路径费用函数”这4个要素建模它呢？以图31为例,首先需要建模旅行商的状态。我们所关心的状态是“旅行商处于哪个城市”。可用谓词(at A)表示旅行商在A,用(at B)表示旅行商在B,类似地可表示旅行商在某个城市的状态。因此,假设旅行商初始城市为A,则其初始状态为(at A)。在某个状态上,旅行商可以做旅行的动作,旅行的始点是当前城市、终点是下一个相邻城市。可用move(A, B)表示旅行商从城市A旅行到城市B的动作。一般地,只要两个城市x和y存在边,且旅行商当前在城市x,则旅行商都可以做move(x, y)的动作,该动作的结果是将旅行商在城市x的状态变换为在城市y的状态,如对于动作move(A, B),它对应的状态映射见表31。其中，move(A, B)在某状态上不适用时,我们假定它对该状态不发生改变。注意,在表31中,动作move(A, B)只在一个状态上执行,但在其他类型的问题中，一个动作可在多个状态上执行。表31动作move(A, B)定义的状态映射当前状态下一状态当前状态下一状态(at A)(at B)(at C)(at C)(at B)(at B)(at D)(at D)在明确旅行商的状态和动作后,对于图31的问题,你能较轻松地找出一个费用最优的动作序列使他从初始位置A经历{B, C, D}仅一次并返回A吗？ \"1．教材第1版入选普通高等教育“十一五”国家级规划教材，第2版入选普通高等教育“十二五”国家级规划教材，被多所985、211高校采用。 2.作者硕士博士先后师从南京大学莫绍揆先生、国防科技大学陈火旺先生，打下了扎实的理论基础。目前，担任军队人工智能专业组专家。多年从事人工智能科研和教学工作，并借鉴了国内外优秀人工智能教材的习题及案例。 3．教材以基本理论与方法为主体，反映人工智能技术发展现状，以方便学生理解和培养学生具备继续学习能力为目标；教材定位力求扩大适应面。 4．用比较多的篇幅论述人工智能的应用，除包括问题状态与搜索、知识表示、知识库系统、机器学习、自然语言技术处理、机器人学等内容外，还增加了智能体、语音处理、神经网络、自然启发式优化算法、互联网智能等内容。 5．注重实践。附录I介绍了人工智能程序设计语言Prolog；附录II给出了28个人工智能课程大作业。 6.为使用本教材的老师提供了习题答案（通过清华大学出版社网站下载）。 \"