新書推薦：
《
慢慢来，好戏都在烟火里
》
售價：HK$
59.8
《
一间自己的房间
》
售價：HK$
47.8
《
波段交易的高级技术：股票和期权交易者的资金管理、规则、策略和程序指南
》
售價：HK$
94.8
《
人，为什么需要存在感：罗洛·梅谈死亡焦虑
》
售價：HK$
81.6
《
锁国：日本的悲剧
》
售價：HK$
93.6
《
AI智能写作： 巧用AI大模型 让新媒体变现插上翅膀
》
售價：HK$
70.8
《
家庭养育七步法5：理解是青春期的通关密码
》
售價：HK$
59.8
《
三体（全三册）
》
售價：HK$
113.5
|
| 編輯推薦： |
|
随着2016年3月AlphaGo（阿法狗）战胜围棋世界冠军、职业九段选手李世石，并以4：1的总分获胜以来，人工智能成为人们舌尖上的话题，本书旨在揭开人工智能的神秘面纱，为大家展示其精髓。本书作者在多年讲授人工智能课程的基础上，对相关理论与技术进行了提炼与总结，使全书结构严谨、逻辑性及前后章节的衔接增强，兼有普及与提高的双重功能。传统人工智能部分深入浅出，通俗易懂，容易学习；现代人工智能部分则体现其创新、精髓和尖端。每章后面附有习题，以供读者练习；提供配套课件，读者可在清华大学出版社网站本书页面下载。
|
| 內容簡介： |
本书系统介绍了人工智能的基本原理、基本技术、基本方法和应用领域等内容，比较全面地反映了60年来人工智能领域的进展，并根据人工智能的发展动向对一些传统内容做了取舍。全书共9章。第1章介绍人工智能的基本概念、发展历史、应用领域等。其后8章的内容分为两大部分： *部分（第2~5章）主要讲述传统人工智能的基本概念、原理、方法和技术，涵盖知识表示、搜索策略、确定性推理和不确定推理的相关技术与方法； 第二部分（第6~9章）主要讲述现代人工智能的新的技术和方法，涵盖机器学习、数据挖掘、大数据、深度学习的*技术与方法。每章后面附有习题，以供读者练习。
本书主要作为计算机专业本科生和其他相关学科本科生相关课程教材，也可供研究生和有关科技人员参考。
|
| 目錄：
|
目录
第1章绪论
1.1人工智能的定义
1.2人工智能的发展历史
1.2.1孕育阶段
1.2.2形成阶段
1.2.3发展阶段
1.3人工智能的三大学派
1.3.1符号主义
1.3.2连接主义
1.3.3行为主义
1.4人工智能研究内容与应用领域
1.4.1问题求解
1.4.2专家系统
1.4.3机器学习
1.4.4神经网络
1.4.5模式识别
1.4.6数据挖掘和知识发现
1.4.7计算机视觉
1.4.8智能控制
1.4.9计算智能
1.4.10其他
1.5人工智能的发展趋势
1.5.1多学科交叉研究
1.5.2智能应用和智能产业
1.6习题
第2章知识表示
2.1概述
2.1.1知识及知识的分类
2.1.2知识表示
2.2谓词逻辑表示法
2.2.1基本概念
2.2.2谓词逻辑表示法
2.2.3谓词逻辑表示法的经典应用
2.2.4谓词逻辑表示法的特点
2.3产生式表示法
2.3.1概述
2.3.2产生式系统
2.3.3产生式表示法应用举例
2.3.4产生式系统的推理方式
2.3.5产生式系统的特点
2.4语义网络表示法
2.4.1语义网络基本概念
2.4.2语义网络中常用的语义联系
2.4.3语义网络表示知识的方法
2.4.4语义网络的推理过程
2.4.5语义网络表示的特点
2.5框架表示法
2.5.1框架基本结构
2.5.2基于框架的推理
2.5.3框架表示法的特点
2.6习题
第3章搜索策略
3.1搜索的基本概念
3.1.1搜索的含义
3.1.2状态空间法
3.1.3问题归约法
3.2状态空间搜索
3.2.1盲目搜索
3.2.2状态空间的启发式搜索
3.3博弈树的启发式搜索
3.3.1概述
3.3.2极大极小过程
3.3.3剪枝
3.4习题
第4章确定性推理
4.1推理的基本概念
4.1.1什么是推理
4.1.2推理方法及其分类
4.1.3推理的控制策略及其分类
4.1.4正向推理
4.1.5逆向推理
4.1.6混合推理
4.2推理的逻辑基础
4.2.1谓词公式的解释
4.2.2谓词公式的永真性与可满足性
4.2.3谓词公式的等价性与永真蕴含性
4.2.4谓词公式的范式
4.2.5置换与合一
4.3自然演绎推理
4.4归结演绎推理
4.4.1子句集及其简化
4.4.2鲁滨逊归结原理
4.4.3归结演绎推理的归结策略
4.4.4用归结反演求取问题的解
4.5基于规则的演绎推理
4.5.1规则正向演绎推理
4.5.2规则逆向演绎推理
4.6习题
第5章不确定性推理
5.1概述
5.1.1为什么要采用不确定性推理
5.1.2不确定性推理要解决的问题
5.1.3不确定性推理类型
5.2概率基础
5.3主观贝叶斯方法
5.3.1不确定性的表示
5.3.2组合证据不确定性的计算
5.3.3不确定性的传递算法
5.3.4结论不确定性的合成
5.4可信度方法
5.4.1不确定性的表示
5.4.2组合证据不确定性的计算
5.4.3不确定性的传递算法
5.4.4结论不确定性的合成
5.5证据理论
5.5.1理论基础
5.5.2不确定性表示
5.5.3组合证据不确定性的计算
5.5.4不确定性的更新
5.6模糊推理
5.6.1模糊知识的表示
5.6.2模糊概念的匹配
5.6.3模糊推理
5.7习题
第6章机器学习
6.1概述
6.1.1机器学习的基本概念
6.1.2机器学习的发展历史
6.1.3学习系统的基本模型
6.1.4学习策略
6.2记忆学习
6.3归纳学习
6.3.1 示例学习
6.3.2观察与发现学习
6.4决策树学习
6.5类比学习
6.5.1类比学习的基本过程
6.5.2属性类比学习
6.5.3转换类比学习
6.5.4派生类比学习
6.5.5联想类比学习
6.6解释学习
6.7神经学习
6.7.1感知器学习
6.7.2反向传播网络学习
6.7.3Hopfield网络学习
6.8贝叶斯学习
6.8.1贝叶斯定理
6.8.2朴素贝叶斯分类算法
6.9在线机器学习
6.9.1截断梯度法
6.9.2前向后向切分算法
6.9.3正则对偶平均算法
6.9.4FTRL
6.10习题
第7章数据挖掘
7.1数据挖掘概述
7.1.1数据挖掘概念与发展
7.1.2数据挖掘的任务
7.1.3数据挖掘的应用
7.1.4数据挖掘过程与方法
7.2分类
7.2.1决策树分类法
7.2.2基于规则的分类器
7.2.3朴素贝叶斯分类器
7.2.4基于距离的分类算法
7.3聚类
7.3.1概念
7.3.2聚类分析的基本方法
7.4关联规则
7.4.1基本概念
7.4.2关联规则挖掘算法
7.4.3关联规则生成
7.5习题
第8章大数据
8.1大数据概述
8.1.1大数据概念
8.1.2特征
8.1.3发展历程
8.1.4应用
8.2数据获取
8.2.1网络爬虫
8.2.2RSS
8.3数据挖掘
8.3.1概述
8.3.2数据挖掘工具
8.3.3现状与未来
8.4数据分析
8.4.1概述
8.4.2数据分析流程
8.4.3数据分析方法
8.4.4数据分析工具
8.5Hadoop
8.5.1简介
8.5.2分布式离线计算框架MapReduce
8.5.3Hadoop分布式文件系统
8.5.4HBase大数据库
8.6数据可视化
8.7习题
第9章深度学习
9.1深度学习应用背景与概述
9.1.1应用背景
9.1.2概述
9.1.3人脑视觉机理
9.2特征的概念
9.2.1特征表示的粒度
9.2.2初级（浅层）特征表示
9.2.3结构性特征表示
9.2.4特征数量
9.3深度学习基本思想
9.4浅层学习和深度学习
9.4.1浅层学习
9.4.2深度学习
9.5深度学习常用模型和方法
9.5.1自动编码器
9.5.2稀疏编码
9.5.3深度信念网络
9.5.4卷积神经网络
9.6深度学习展望
9.7习题
参考文献
|
| 內容試閱：
|
前言
人工智能是研究人类智能活动的规律，构造具有一定智能的人工系统，研究如何让计算机去完成以往需要人的智力才能胜任的工作，也就是研究如何应用计算机的软硬件来模拟人类某些智能行为的基本理论、方法和技术。人工智能是计算机科学的一个分支，被称为20世纪世界三大尖端科技（空间技术、能源技术、人工智能）之一，也被称为21世纪三大尖端技术（基因工程、纳米科学、人工智能）之一。人工智能作为一门学科从正式提出到现在，已经走过了一甲子的岁月，经历了风风雨雨、起起落落。随着2016年3月AlphaGo战胜世界围棋冠军、职业九段选手李世石，人工智能又一次受到了世人极大的关注。2014年人工智能领域全球投资总额超过19亿美元，同比增长超50%，预计2020年全球市场规模将达到183亿美元。谷歌、微软、苹果等国外科技巨头纷纷发力，国内企业也纷纷和顶尖技术团队合作，积极布局，如百度的大脑计划、科大讯飞的超脑计划、京东的智能聊天机器人等。2015年7月1日，国务院印发了《关于积极推进互联网 行动的指导意见》，将互联网 人工智能列为11项重点行动之一； 2016年9月国家发改委、科技部、工信部、中央网信办制定的《互联网 人工智能三年行动实施方案》正式印发，计划到2018年基本建立人工智能的产业、服务和标准化体系，实现核心技术突破。基于此，本书在传统人工智能的基础之上增加了新的人工智能的技术与方法。本书的第6章介绍了机器学习中的一些基本问题、基本方法和关键技术。第7章介绍了数据挖掘的常用技术与方法。第8章介绍了大数据的最新研究进展、最新技术与方法。第9章介绍了深度学习的常用方法与最新技术。本书是集体智慧的结晶，全书由尚文倩主编，陈秀霞、封树超、颜梦菡、李振忠、王宇奇、娄延伟、程宇芬、张春洁等同学为本书做出了重要贡献，在此表示衷心的感谢！本书还参考了《20162020年中国人工智能行业深度调研及投资前景预测报告》，借鉴了有关教材及互联网上的一些资料，也向这些文献的作者表达诚挚的谢意！由于编者水平有限，书中的疏漏在所难免，敬请广大读者批评指正。作者2017年4月于中国传媒大学
第3章搜索策略
3.1搜索的基本概念3.1.1搜索的含义
如何在大量的知识甚至结构不良或非结构化的问题中获取对自己有用的信息，是人工智能中非常重要的一部分。对于这些问题，一般很难获得其全部信息，更没有现成的算法可供使用。因此，根据问题的实际情况，不断寻找可利用知识，从而构造一条代价最小的推理路线，就显得尤为重要。搜索就是要寻找一个操作序列，使问题从初始状态转换到目标状态。这个操作序列就是目标的解。因此，所谓搜索，就是根据问题的实际情况，按照一定的策略或规则，从知识库中寻找可利用的知识，从而构造一条使问题获得解决的推理路线的过程。搜索包含两层含义： 一是要找到从初始事实到问题最终答案的一条推理路线，二是找到的这条路线是时间和空间复杂度最小的求解路线。通常搜索策略的主要任务是确定选取规则的方式。可根据是否使用启发式信息分为盲目搜索和启发式搜索，也可以根据问题的表示方法分为状态空间搜索和与或树搜索。盲目搜索是不考虑给定问题所具有的特定知识，系统根据事先确定好的某种固定排序，依次调用规则或随机调用规则，一般统称为无信息引导的搜索策略。由于搜索总是按照预定的控制策略进行搜索，因此这种搜索策略具有盲目性，效率不高，不便于复杂问题的求解。启发式搜索考虑问题领域可应用的知识，动态地确定规则的排序，优先调用较合适的规则，加速问题的求解过程，使搜索朝着最有希望的方向前进，找到最优解。状态空间搜索是指用状态空间法来求解问题所进行的搜索。与或树搜索是指用问题归约法来求解问题时进行的搜索。下面分别介绍状态空间法与问题归约法。3.1.2状态空间法在分析了人工智能研究的求解方法之后，就会发现许多问题求解方法采用了试探搜索方法。也就是说，这些方法是通过在某个可能的解空间内寻找一个解来求解问题。这种基于解空间的问题表示和求解方法就是状态空间法。状态空间搜索的研究焦点在于设计高效的搜索算法，以降低搜索代价并解决组合爆炸问题。1. 状态空间及其搜索的表示在状态空间表示法中，问题是用状态和操作来表示的，问题求解的过程使用状态空间来表示。1 状态状态state是表示问题求解过程中每一步问题状况的数据结构，可以用如下形式表示：
Sk={Sk0,Sk1,}
在这种表示方式中，当对每一个分量都给予确定的值时，就得到了一个具体的状态。其中，每一个分量称为状态变量。实际上，任何一种类型的数据结构都可以用来描述状态，只要它有利于问题求解，就可以选用。2 操作操作operation也称为算符，它是把问题从一种状态变换为另一种状态的手段。当对一个问题状态使用某种操作时，它将引起该状态中某些分量值的变化，从而使问题从一个具体状态变为另一个具体状态。操作符可以是过程、规划、数学算子、运算符号或逻辑符号等。操作可理解为状态集合上的一个函数，它描述状态之间的关系。3 状态空间状态空间state space用来描述一个问题的全部状态及这些状态之间的相互关系。状态空间常用一个三元组S,F,G来表示。其中：S为问题的所有初始状态的集合，其中的每个元素表示一种状态。F为操作的集合，用于把一个状态转换为另一个状态。G是S的一个非空子集，为目标状态的集合。它可以是若干具体的状态，也可以是对某些状态性质的描述。状态空间也可以用一个赋值的有向图来表示，该有向图称为状态空间图。在状态空间图中，节点表示问题的状态，有向边弧表示操作。2. 状态空间问题的例子下面通过具体例子来说明状态空间法。例3.1二阶梵塔问题。设有3根柱子，它们的编号分别为1号、2号、3号。在初始情况下，1号柱子上穿有A和B两个圆盘，A比B小，A位于B的上面。要求把这两个圆盘全部移到另一根柱子上，而且规定每次只能移动一个圆盘，任何时刻都不能使大圆盘位于小圆盘的上面。解： 设用Sk={Sk0,Sk1}表示问题的状态，其中Sk0表示圆盘A所在的柱子号，Sk1表示圆盘B所在的柱子号。全部可能的问题状态共有以下9种：S0={1，1}S1={1，2}S2={1，3}S3={2，1}S4={2，2}S5={2，3}S6={3，1}S7={3，2}S8={3，3}其中，初始状态S0和目标状态S4、S8如图3.1所示。
图3.1二阶梵塔问题的部分状态
问题的初始状态集合为Sk={S0},目标状态集合为G={S4,S8}。操作分别用Ai,j和Bi,j表示。其中Ai,j表示把圆盘A从第i号柱子移到第j号柱子上，Bi,j表示把圆盘B从第i号柱子移到第j号柱子上。共有12种操作，分别是A1，2A1，3A2，1A2，3A3，1A3，2B1，2B1，3B2，1B2，3B3，1B3，2根据上述9种可能的状态和12种操作，可构成二阶梵塔问题的状态空间图，如图3.2所示。
图3.2二阶梵塔的状态空间图
在图3.2中，从初始节点1,1到目标节点2,2及3,3的任何一条路径都是问题的一个解。其中，最短的路径长度是3，它由3个操作组成。例如，从初始状态1,1开始，通过使用操作A1,3、B1,3及A3,2，可到达目标状态2,2。例3.2作为状态空间的经典例子，我们来观察传教士与野人问题。设N个传教士带领N个野人划船渡河，且为安全起见，渡河需要遵循两个约束： ①船上人数不得超过载重限量，设为K个人； ②为预防野人攻击，任何时刻包括两岸、船上野人数目不得超过传教士数目。为便于理解状态空间表示方法，可以将该问题简化为一个特例： N=3，K=2； 并以变量m和c分别表示传教士和野人在左岸或者在船上的实际人数，变量b表示船是否在左岸值1表示船在左岸，否则为0。从而上述约束条件转变成为m c2,mc。考虑到在这个渡河问题中，左岸的状态描述m，c，b可以决定右岸的状态，所以整个问题的状态就可以用左岸的状态来描述，以简化问题的表示。设初始状态下传教士、野人和船都在左岸，目标状态下这三者均在右岸，问题状态以三元组m,c,b表示，则问题求解任务可以描述为
3,3,10,0,0
在此问题中，状态空间可能的状态总数为442=32，但由于要遵守安全约束，只有20种状态是合法的。下面是几个不合法状态的例子：
1,0,1，1,2,1，2,3,1
鉴于存在不合法的状态，还会导致某些合法的状态不可达，例如状态0,0,1、0,3,0。因此，此问题总共只有16种可达的合法状态：
S0=3，3，1S1=3，2，1S2=3，1，1S3=2，2，1
S4=1，1，1S5=0，3，1S6=0，2，1S7=0，1，1
S8=3，2，0S9=3，1，0S10=3，0，0S11=2，2，0
S12=1，1，0S13=0，2，0S14=0，1，0S15=0，0，0
有了这些状态，还需要考虑可进行的操作。在此问题中，操作是指用船把修道士或野人从河的左岸运到右岸，或者从河的右岸运到左岸，并且每个操作都应该满足条件①、②。因此，操作应该由两部分组成，即条件部分和动作部分。操作只有当其条件具备时才能进行，动作则刻画了应用此操作所产生的结果。此处用符号Pij表示从左岸到右岸的运人操作，用符号Qij表示从右岸到左岸的运人操作，其中，i表示船上的修道士数，j表示船上的野人数。通过分析可以知道有10种操作可供选择，其操作集为
F={P01，P10,P11,P02,P20,Q01,Q10,Q11,Q02,Q20}
下面以P01和Q01为例说明这些操作的条件和动作：
操作符号条件动作
P01b=1,m=0或3，c1b=0,c=c-1
Q01b=0,m=0或3, c2b=1,c=c 1
从而可画出类似图3.2所示的状态空间图。例3.3猴子摘香蕉问题。在前面讨论谓词逻辑知识表示时曾经提到这一问题，现在用状态空间法求解。解： 问题状态可用四元组w,x,y,z来表示。其中，w表示猴子的水平位置； x表示箱子的水平位置； y表示猴子是否在箱子上，当猴子在箱子上时y取1，否则y取0； z表示猴子是否拿到香蕉，当拿到香蕉时z取1，否则z取0。所有可能的状态为S0： a,b,0,0初始状态S1： b,b,0,0S2： c,c,0,0S3： c,c,1,0S4： c,c,1,1目标状态允许的操作为Gotou： 猴子走到位置u，即w,x,0,0u,x,0,0。Pushboxv： 猴子推着箱子到水平位置v，即x,x,0,0v,v,0,0。Climbbox： 猴子爬上箱子，即x,x,0,0x,x,1,0。Grasp： 猴子拿到香蕉，即c,c,1,0c,c,1,1。这个问题的状态空间图如图3.3所示。由初始状态变为目标状态的操作序列为{Gotob,Pushboxc,Climbbox,Grasp}
图3.3猴子摘香蕉问题的状态空间图
3.1.3问题归约法问题归约法是另一种对问题进行描述及求解的办法。其基本思想是： 对问题进行分解和变换，将此问题最终变为一个子问题的集合，通过求解子问题达到求解原问题的目的。问题归约法适用于当初始问题比较复杂时，分解后的子问题的解可以直接得到，从而解决了初始问题的情况。所谓分解是指： 如果一个问题P可以归约为一组子问题P1,P2,,Pn，并且只有当所有子问题Pi都有解时原问题P才有解，任何一个子问题Pi无解都会导致原问题P无解，则称此种归约为问题的分解，即分解所得到的子问题的与与原问题P等价。所谓变换是指： 如果一个问题P可以归约为一组子问题P1,P2,,Pn，并且子问题Pi中只要有一个有解，则原问题P就有解，只有当所有子问题Pi都无解时原问题P才无解，称此种归约为问题的等价变换，简称变换，即变换所得到的子问题的或与原问题P等价。1. 问题归约描述问题归约表示由下面3个部分组成：1 一个初始问题的描述。2 一套把问题变换成为子问题的操作符。3 一套本原问题的描述。从目标要解决的问题出发逆向推理，建立子问题以及子问题的子问题，直至最后把初始问题归纳成为一个平凡的本原问题集合，这就是问题归约的实质。例3.4三阶梵塔问题。有3个柱子1，2，3和3个不同尺寸的圆盘A，B，C。在每个圆盘的中心有一个孔，所以圆盘可以堆叠在柱子上。最初，全部3个圆盘都堆在柱子1上，最大的圆盘C在底部，最小的圆盘A在顶部。要求把所有圆盘都移到柱子3上，每次只许移动一个，而且只能先搬动柱子顶部的圆盘，还不许把尺寸较大的圆盘堆放在尺寸较小的圆盘上。若采用状态空间法来求解这个问题，其状态空间有27个节点，每个节点代表柱子上的圆盘的一种正确位置。当然，也可以用简单的问题归约法来求解此问题。归约过程如下：1 移动圆盘A和B至柱子2的双圆盘移动问题。2 移动圆盘C至柱子3的单圆盘移动问题。3 移动圆盘A和B至柱子3的双圆盘移动问题。可以看出简化后的问题每一个都比原问题容易，所以原问题都可以变成易解决的本原问题。而将一个复杂的原问题归约成一系列本原问题的过程可以很方便地用与或树来表示。下面介绍有关与或树的相关内容。2. 与或树的相关概念1 节点与弧线父节点： 是一个初始问题或是可分解为子问题的问题节点。子节点： 是一个初始问题或是子问题分解的子问题节点。或节点： 只要解决某个问题就可解决其父问题的节点集合。与节点： 只有解决所有子问题，才能解决其父问题的节点集合。端节点： 没有子节点的节点。终止节点： 本原问题所对应的节点。由此可见，终止节点一定是端节点，而端节点却不一定是终止节点。弧线： 是父辈节点指向子节点的圆弧连线。2 或树、与或树和解树把一个原问题变换成若干个子问题可用一个或树来表示，如图3.4所示。把一个问题分解为若干个子问题可用一个与树来表示，如图3.5所示。
图3.4或树
图3.5与树
如果一个问题既需要通过分解，又需要通过变换才能得到其本原问题，其归约过程可以用一个与或树来表示，如图3.6所示。由可解节点构成，并且由这些可解节点可以推出初始节点它对应着原问题为可解节点的子树为解树。在解树中一定包含初始节点。例如，在图3.7所给的与或树中，用粗线表示的子树是一个解树。在该图中，节点P为原始问题节点，用t标出的节点是终止节点。
图3.6与或树
图3.7解树
3. 问题归约的例子如例3.4的三阶梵塔问题，此问题也可以用状态空间法来解，不过本例主要用它来说明如何用问题归约法来解决问题。首先，定义该问题的形式化表示方法。设用三元组i,j,k表示问题在任意时刻的状态，用表示状态的转换。在此三元组中，i代表圆盘C所在的柱子号，j代表圆盘B所在的柱子号，k代表圆盘A所在的柱子号。前面分解的3个子问题可分别表示如下。1 移动圆盘A和B至柱子2的双圆盘问题：
1,1,11,2,2
2 移动圆盘C至柱子3的单圆盘问题：
1,2,23,2,2
3 移动圆盘A和B至柱子3的双圆盘问题：
3,2,23,3,3
其中，子问题1、3都是一个二阶梵塔问题，它们都可以再继续进行分解； 子问题2是本原问题，它已经不需要再分解。三阶梵塔问题的分解过程可用图3.8所示的与或树来表示。在该与或树中，有7个终止节点，它们分别对应着7个本原问题。得到问题的解为
1,1,11,1,31,1,31,2,31,2,31,2,2
1,2,23,2,23,2,23,2,13,2,13,3,1
3,3,13,3,3
图3.8三阶梵塔问题的与或树表示
3.2状态空间搜索状态空间的搜索策略分为盲目搜索和启发式搜索两大类。下面讨论的广度优先搜索、深度优先搜索和有界深度优先搜索都属于盲目搜索策略。盲目搜索策略的一个共同特点是它们的搜索路线是已经决定好的，没有利用被求解问题的任何特征信息，在决定要被扩展的节点时，并没有考虑该节点到底是否可能出现在解的路径上，也没有考虑它是否有利于问题的求解以及所求的解是否为最优解。3.2.1盲目搜索1. 一般图搜索
一般图搜索是在状态空间中搜索从初始状态到目标状态解答路径的过程。由于问题的状态空间可以用一个有向图来表示，因此状态空间搜索实际上就是对有向图的搜索。从图搜索的角度来看，状态空间搜索的基本思想可以概括为： 将问题的初始状态作为当前扩展节点对其进行扩展，生成一组子节点，然后检查目标状态是否出现在这些节点中。如果出现，表明搜索成功，即找到了该问题的解； 如果没有出现，则再按照某一种搜索策略从已生成的子节点中选择一个节点作为当前的扩展节点。重复上述过程，直到目标状态出现在子节点中或者没有可供扩展的节点为止。所谓对一个节点进行扩展是指对该节点用某个可用操作施加作用，生成该节点的一组子节点。在开始搜索过程之前，先定义两个数据结构OPEN表与CLOSED表。OPEN表用于存放刚生成的节点，对于不同的搜索策略，节点在OPEN表中的排列顺序是不同的。例如，对广度优先搜索，节点按生成的顺序排列，先生成的节点排在前面，后生成的节点排在后面。CLOSED表用于存放将要扩展或已扩展的节点。搜索步骤如下：第1步，把初始节点S0放入OPEN表，并建立目前只包含S0的图，记为G。第2步，检查OPEN表是否为空，若为空则问题无解，失败退出。第3步，把OPEN表的第一个节点取出放入CLOSED表，并记该节点为节点n。第4步，判断节点n是否为目标节点。若是，则求得问题的解，成功退出。第5步，考查节点n，生成一组子节点。把其中不是节点n先辈的那些子节点记作集合M，并把这些子节点作为节点n的子节点加入G中。第6步，针对M中子节点的不同情况，分别进行如下处理： 对那些未曾在G中出现过的M成员设置一个指向父节点即节点n的指针，并将它们放入OPEN表。 对那些先前已在G中出现过的M成员，确定是否需要修改它指向父节点的指针。 对那些先前已经在G中出现并且已经扩展了的M成员，确定是否需要修改其后继节点指向父节点的指针。第7步，按某种搜索策略对OPEN表中的节点进行排序。第8步，转第2步。2. 广度优先搜索广度优先搜索又称为宽度优先搜索，是一种先生成的节点先扩展的简单策略。从初始节点S0开始逐层向下扩展，只有当同一层的节点全部被搜索完以后，才能进入下一层继续搜索。在搜索的过程中，要建立两个数据结构： OPEN表和CLOSED表，其形式分别如表3.1和表3.2所示。
表3.1OPEN表
节点父节点编号
表3.2CLOSED表
编号节点父节点编号
OPEN表用于存放刚生成的节点，对于不同的策略，节点在此表中的排列顺序是不同的。CLOSED表用于存放将要扩展或者已扩展的节点节点n的子节点。所谓对一个节点进行扩展，是指用合适的算符对该节点进行操作，生成一组子节点。一个节点经一个算符操作后一般只生成一个子节点，但对一个可使用的节点可能有多个，故此时会生成一组子节点。需要注意的是，在这些子节点中，可能有些是当前扩展节点节点n的父节点或者祖父节点等，此时不能把这些先辈节点作为当前扩展节点的子节点。在广度优先搜索策略中，OPEN表中的节点是按进入的先后排序，先进入OPEN表的节点排在前，后进入的节点排在后。因此，广度优先搜索的基本思想是： 从初始节点S0开始，逐层地对节点进行扩展并考察它是否为目标节点，在第n层的节点没有全部扩展并考察之前，不对第n 1层的节点进行扩展。其搜索过程如下：第1步，把初始节点S0放在OPEN表中。第2步，若OPEN表为空，则问题无解，退出。第3步，把OPEN表中的第一个节点记为节点n取出放入CLOSED表中。第4步，考察节点n是否为目标节点。若是，则得到问题的解，成功退出。第5步，若节点n不可扩展，则转第2步。第6步，扩展节点n，将其子节点放入OPEN表的尾部，并且为每一个子节点设置指向父节点的指针，然后转第2步。
图3.9重排九宫问题
例3.5重排九宫问题。在33的方格棋盘上，分别放置了标有数字1~8的8张牌，初始状态为S0,目标状态为Sg，如图3.9所示。可用的操作有空格左移、空格上移、空格右移、空格下移。即只允许把位于空格左、上、右、下的牌移入空格。要求用广度优先搜索策略寻找初始状态到目标状态的路径。解： 应用广度优先策略，可以在第四级得到解，搜索树如图3.10所示。可以看出，解的路径是
S0381626
图3.10重排九宫的广度优先搜索
由于广度优先搜索总是在生成扩展完n层的节点后才转到n 1层，所以总能找到最优解。但是实用意义不大，广度优先算法的主要缺点是盲目性较大，尤其是当目标节点距初始节点较远时，将产生许多无用节点，最后导致组合爆炸，尽管耗尽资源，在可利用的空间中也找不到解。
3. 深度优先搜索深度优先搜索总是先扩展后生成的节点。其基本思想是： 从初始节点S0开始，在其子节点中选择一个最新生成的节点进行考察，如果该子节点不是目标节点并且可以扩展，则扩展此子节点，再在此节点的子节点中选择一个最新生成的节点进行扩展，一直如此向下搜索。当到达某一子节点，此子节点既不是目标节点又不能继续扩展时，才选择其兄弟节点进行考察。其搜索过程如下：第1步，初始节点放入OPEN表中。第2步，若OPEN表为空，则问题无解，退出。第3步，把OPEN表中的第一个节点记为n取出放入CLOSED表中。第4步，考察节点n是否为目标节点，若是，则问题解求出，退出。第5步，若节点不可扩展，则转第2步。第6步，扩展节点n，将其子节点放入OPEN表的首部，并为其配置指向父节点的指针，然后转第2步。对比广度优先搜索与深度优先搜索，可以看出二者唯一的区别是，广度优先搜索时将节点n的子节点放到OPEN表的尾部，而深度优先搜索时把节点n的子节点放到OPEN表的首部。这一不同点使得搜索的路线完全不同。例3.6对例3.5的重排九宫问题进行深度优先搜索。解： 用深度优先搜索可得到图3.11所示的搜索树。但这只是搜索树的一部分，尚未到达目标节点，仍可继续往下搜索。
图3.11重排九宫的深度优先搜索
从深度优先搜索的算法可以看出，搜索一旦进入某个分支，就将沿着这个分支一直向下进行下去，如果目标恰好在这一个分支上，则可以很快找到解。但是，如果目标不在此分支上，且该分支是一个无穷分支，则搜索过程就不可能找到解。因此，深度优先搜索是一种不完备策略，即使问题有解也不一定能够找到。此外，即使能够找到解，此解也不一定是最短路径的解。广度优先搜索和深度优先搜索各有不足，为了弥补各自的不足，可以采用有界深度优先算法。顾名思义，这是对深度优先算法给出深度限制dm，当搜索深度达到了dm，即使没有找到目标，也要停止该分支的搜索，换到另一个分支进行搜索。折中的办法是广度优先和深度优先策略的一种结合。
4. 代价树搜索当路径的花费与弧有关时，我们常常想到的是花费最小的路径。例如，对于一个投递机器人，花费可能是两个位置之间的距离，需要解出距离最短的那条解路径。花费也可能是机器人按照弧实施动作所需要的各种资源。而在前面讨论的各种搜索策略中，并没有将注意力放在各边的代价上，因为默认各边的代价是相同的，且都为一个单位量。但是，对于许多实际问题，状态空间的各个边的代价不可能完全相同。为此，需要在搜索树中给每一条边都标上代价。这种标有代价的树称为代价树。1 代价树的代价表示
gn2=gn1 cn1,n2
其中，n1与n2分别表示某一父节点与其子节点，gn表示从初始节点S0到节点n的代价，用cn1,n2表示从父节点n1到其子节点n2的代价。在代价树中，最小代价的路径和最短路径即路径长度最短是有可能不同的。代价树搜索的目的是为了找到最优解，即找到一条代价最小的解路径。2 代价树的广度优先搜索代价树的广度优先搜索每次从OPEN表中选择节点以及往CLOSED表中存放节点时，总是选择代价最小的节点。即OPEN表中节点的顺序是按照其代价由小到大排列的，代价小的节点排在前面，代价大的节点排在后面，与节点在树中的位置无关。代价树的广度优先搜索算法如下：（1） 将初始节点S0放入OPEN表中，置S0的代价gS0=0。（2） 如果OPEN表为空，则问题无解，失败退出。（3） 把OPEN表的第一个节点取出放入CLOSED表，并记该节点为n。（4） 考察节点n是否为目标节点，若是，则找到了问题的解，成功退出； 否则继续。（5） 若节点n不可扩展，则转步骤（2）； 否则转步骤（6）。（6） 扩展节点n，生成其子节点nii=1,2,3,,将这些节点放入OPEN表中，并为每一个子节点设置指向父节点的指针。按公式gni=gn cn,nii=1,2,3,计算各节点的代价，并根据各节点的代价对OPEN表中的全部节点按照从小到大的顺序重新进行排序。（7） 转步骤2。代价树的广度优先搜索策略是完备的。如果问题有解，上述算法一定能找到它，并且找到的一定是最优解。
图3.12城市交通线路图
例3.7城市交通问题。设有5个城市，城市之间的交通线路如图3.12所示，图中的数字表示两个城市之间的交通费用，即代价。用代价树的广度优先搜索，求出从A市出发到E市费用最小的交通路线。解： 图3.12是一个网络图，不能直接用于搜索算法，需要将其先转换为代价树。把一个网络图转换为代价树的方法是： 从起始节点A开始，把与它直接邻接的节点作为其子节点。对其他的节点也做同样的处理。但当一个节点已作为某个节点的直系先辈节点时，就不能再作为这个节点的子节点。例如，图中与节点B直接相邻的节点有节点A、D、E，但由于A已经作为B的父节点在代价树中出现过了，因此A不能再作为B的子节点。此外，图中的节点除初始节点A外，其他节点都可能在代价树中出现多次，为区别它们的多次出现，分别用下标1，2，标出，但实际上是同一个节点。
图3.13城市交通线路图的代价树
转换后的代价树如图3.13所示。对如图3.13所示的代价树，按广度优先搜索可得到最优解：
AC1D1E2
其代价为8。可见，从A市到E市的最小费用路线为：
ACDE
3 代价树的深度优先搜索代价树的广度优先搜索每次都是从OPEN表的全体节点中选择一个代价最小的节点，而深度优先搜索是从刚扩展的子节点中选择一个代价最小的节点。即两种搜索策略的区别在于每次选择最小代价节点的方法不同。代价树的深度优先搜索算法如下：（1） 将初始节点S0放入OPEN表中，置S0的代价gS0=0。（2） 如果OPEN表为空，则问题无解，失败退出。（3） 把OPEN表的第一个节点取出放入CLOSED表，并记该节点为n。（4） 考察节点n是否为目标节点，若是，则找到了问题的解，成功退出。（5） 若节点不可扩展，则转第2步，否则转第6步。（6） 扩展节点n，生成其子节点nii=1,2,3,,将这些子节点按边代价由小到大放入OPEN表中的首部，并为每一个子节点设置指向父节点的指针。（7） 转第2步。对例3.7所给出的问题，用代价树的深度优先搜索策略找到的路径为
AC1D1E1
和广度优先搜索相比，深度优先搜索找到的路径是相同的。这只是一种巧合。一般来说，它找到的解不一定是最优解，即代价树的深度优先搜索策略是不完备的，甚至当搜索进入无穷分支时，算法将找不到解。3.2.2状态空间的启发式搜索3.2.1节介绍了状态空间的盲目搜索策略。例如状态空间的深度优先搜索和宽度优先搜索。这类方法进行的是一种蛮力搜索，因而效率低。本节介绍状态空间的启发式搜索策略，由于此种方法有较强的针对性，因此可以缩小搜索范围，提高搜索效率。1. 估价函数与启发式信息3.2.1节所介绍的所有搜索算法都是无指导信息的，并没有考虑目标节点在哪里。它们没有使用任何指引它们该去哪里的信息，除非它们无意中发现了目标。在搜索过程中，用于决定要扩展的下一个节点的信息，即用于指导搜索过程且与具体问题求解有关的控制信息称为启发信息； 决定下一步要控制的节点称作最有希望的节点，其希望的程度通常通过构造一个函数来表示，这种函数被称为估价函数。1 估价函数估价函数的任务是估计待搜索节点的重要程度，给它们排定顺序。在这里，把估价函数fn定义为从初始节点S0经过节点n到达目标节点的最小代价路径的代价估计值，它的一般形式为
fn=gn hn
其中，gn为初始节点S0到节点n已实际付出的代价； hn是从节点n到目标节点Sg最优路径的估计代价，搜索的启发式信息主要由hn来体现，故把hn称为启发函数。对gn的值，可以按指向父节点的指针，从节点n反向跟踪到初始节点S0，得到一条从初始节点S0到节点n的最小代价路径，然后把这条路径上的所有有向边的代价相加，就得到gn的值。2 启发信息启发信息是指与具体问题求解过程有关的，并可指导搜索过程朝着最有希望的方向前进的控制信息。一般有以下3种：（1） 有效地帮助确定扩展节点的信息。（2） 有效地帮助决定哪些后继节点应被生成的信息。（3） 能决定在扩展节点时哪些节点应从搜索树上删除的信息。一般来说，搜索过程所使用的启发性信息的启发能力越强，扩展的无用节点就越少。例3.8八数码难题。设问题的初始状态S0和目标状态Sg如图3.9所示，且估价函数为fn=dn Wn，式中，dn表示节点n在搜索树中的深度； Wn表示节点n中不在位的数码个数，请计算初始状态S0的估价函数值fS0。解： 在本例的估价函数中，取gn=dn,hn=Wn。此处用S0到n的路径上的单位代价表示实际代价，用n中不在位的数码个数作为启发信息。一般来说，某节点中的不在位的数码个数越多，说明它离目标节点越远。对初始节点S0,由于dS0=0,WS0=3,因此有
fS0=0 3=3
这个例子仅是为了说明估价函数的含义及估价函数值的计算。在问题搜索过程中，除了需要计算初始节点的估价函数之外，更多的是要计算新生成节点的估价函数值。2. A算法在搜索的每一步都利用估价函数fn=gn hn对OPEN表中的节点进行排序，则该搜索算法称为A算法。由于估价函数中带有问题自身的启发性信息，因此，A算法也称为启发式搜索算法。根据搜索过程中选择扩展节点的范围，启发式搜索算法可分为全局择优搜索算法和局部择优搜索算法。其中，全局择优搜索算法每当需要扩展节点时，总是从OPEN表的所有节点中选择一个估价函数值最小的节点进行扩展。局部择优搜索算法每当需要扩展节点时，总是从刚生成的子节点中选择一个估价函数最小的节点进行扩展。下面主要讨论全局择优搜索算法。全局择优搜索算法的搜索过程可描述如下：1 把初始节点S0放入OPEN表中，fS0=gS0 hS0。2 如果OPEN表为空，则问题无解，失败退出。3 把OPEN表的第一个节点取出放入CLOSED表，并标记该节点为n。4 考察节点n是否为目标节点，若是，则找到了问题的解，成功退出。5 若节点不可扩展，则转第2步。6 扩展节点n，生成其子节点nii=1,2,3,,计算每一个子节点的估价值fnii=1,2,3,,并为每个子节点设置指向父节点的指针，然后将这些子节点放入OPEN表中。7 根据各节点的估价函数值，对OPEN表中的全部节点按从小到大的顺序重新进行排序。8 转第2步。由于上述算法的第7步要对OPEN表中的全部节点按估价函数值从小到大重新进行排序，这样在算法第3步取出的节点就一定是OPEN表的所有节点中估价函数值最小的一个节点。因此，它是一种全局择优的搜索方式。对上述算法进一步分析还可以发现： 如果取估价函数fn=gn，则它将退化为代价树的广度优先搜索； 如果取估价函数fn=dn，则它将退化为广度优先搜索。可见，广度优先搜索和代价树的广度优先搜索是全局择优搜索的两个特例。例3.9八数码难题。设问题的初始状态S0和目标状态Sg如图3.9所示，估价函数与例3.8相同，请用全局择优搜索解决该问题。解： 这个问题的全局择优搜索树如图3.14所示，在图3.14中，每个节点旁边的数字是该节点的估价函数值。例如，对节点S2，其估价函数值的计算为
fS2=dS2 WS2=2 2=4
从图3.14还可以看出，该问题的解为
S0S1S2S3S4
图3.14全局择优搜索树
3. A*算法1 A*算法概述A*算法也是一种启发式搜索方法，它是对扩展节点的选择方法做了一些限制，选用了一个比较特殊的估价函数，这时的估价函数fn=gn hn是对函数f*n=g*n h*n的一种估计或近似，即，fn是对f*n的估计，gn是对g*n的估计，hn是对h*n的估计。函数f*n的定义是这样的： 它表示从节点S0到节点n的一条最佳路径的实际代价加上从节点n到目标节点Sg的一条最佳路径的代价之和。而g*n就是从节点S0到节点n之间最小代价路径的实际代价，h*n则是从节点n到目标节点Sg的最小代价路径上的代价。既然gn是对g*n的估计，所以gn是比较容易求得的，它就是从初始节点S0到节点n的路径代价，这可通过由节点n到节点S0回溯时把所遇各段弧线的代价加起来而得到，显然恒有gng*n。hn是对h*n的估计，它依赖于有关问题领域的启发信息，是上述提到的启发函数，其具体形式要根据问题特性来进行构造。在A*算法中要求启发函数hn是h*n的下界，即对所有的n均有hnh*n。这一要求十分重要，它能保证A*算法找到最优解。理论分析表明，若问题存在最优解，则此限制就可能保证找到最优解。虽然，这个限制可能产生无用搜索，但是不难想象，当某一节点n的hnh*n,则该节点就有可能失去优先扩展的机会，因而导致得不到最优解。2 A*算法性质A*算法具有可采纳性、单调性和信息性。1 可采纳性。所谓可采纳性是指对于可求解的状态空间图即从状态空间图的初始节点到目标节点有路径存在来说，如果一个搜索算法能在有限步内终止，并且能找到最优解，则称该算法是可采纳的。分3步证明如下：① 对于有限图，A*算法一定会在有限步内终止。对于有限图，其节点个数是有限的。可见A*算法在经过若干次循环之后只可能出现两种情况： 或者由于搜索到了目标节点而终止； 或者由于OPEN表中的节点被取完而终止。不管发生哪种情况，A*算法都在有限步内终止。② 对于无限图，只要初始节点到目标节点有路径存在，则A*算法也必然会终止。该证明分两步进行。证明在A*算法结束之前，OPEN表中总存在节点x。该节点是最优路径上的一个节点，且满足
fxf*S0
设最优路径是S0,x1,x2,,xm,S*g。由于A*算法中的hx满足hxh*x，所以fS0,fx1,fx2,,fxm均不大于fS*g，fS*g=f*S0。又因为A*算法是全局择优的，所以在它结束之前，OPEN表中一定含有S0,x1,x2,,xm,S*g中的一些节点。设x是最前面的一个，则它满足
fxf*S0
至此，第一步证明结束。现在来进行第二步的证明。这一步用反证法，即假设A*算法不终止，则会得出与上一步矛盾的结论，从而说明A*算法一定会终止。假设A*算法不终止，并设e是图中各条边的最小代价，d*xn是从S0到节点xn的最短路径长度，则显然有
g*xnd*xne
又因为
gxng*xn
所以有
gxnd*xne
因为
hxn0，fxngxn
故得到
fxnd*xne
由于A*算法不终止，随着搜索的进行，d*xn会无限增长，从而使fxn也无限增长。这就与上一步证明得出的结论矛盾。因为对可解状态空间来说，f*S0一定是有限值。所以，只要从初始节点到目标节点有路径存在，即使对于无限图，A*算法也一定会终止。③ A*算法一定终止在最优路径上。假设A*算法不是在最优路径上终止，而是在某个目标节点t处终止，即A*算法未能找到一条最优路径，则
ft=gt f*S0
但由②的证明可知，在A*算法结束之前，OPEN表中存在节点x，它在最优路径上，且满足
fxf*S0
此时，A*算法一定会选择x来扩展而不会选择t，这就与假设矛盾。显然，A*算法一定终止在最优路径上。根据可纳性的定义及以上证明可知A*算法是可采纳的。同时由上面的证明还可知，A*算法选择扩展的任何一个节点x都满足如下性质：
fxf*S0
2 单调性。在A*算法中，若对启发性函数加以适当的单调性条件限制，就可使它对所扩展的一系列节点的估价函数单调递增或非递减，从而减少对OPEN表或CLOSED表的检查和调整，提高搜索效率。所谓单调性限制是指hx满足如下两个条件：① hSg=0。② 设xj是节点xi的任一子节点，则有
hxi-hxjcxi,xj
其中，Sg是目标节点，cxi,xj是节点xi到其子节点xj的边代价。若把上述不等式改写为如下形式：
hxihxj cxi,xj
就可看出节点xi到目标节点最优费用的估价不会超过从xi到其子节点xj的边代价加上从xj到目标节点最优费用的估价。可以证明，当A*算法的启发式函数hx满足单调限制时，有如下两个结论：① 若A*算法选择节点xn进行扩展，则
gxn=g*xn
② 由A*算法所扩展的节点序列的估价值是非递减的。这两个结论都是在hx满足单调限制时才成立的。否则，它们不一定成立。例如，对于第②个结论，当hx不满足单调限制时，有可能某个要扩展的节点比以前扩展的节点的估价值小。3 信息性。A*算法的搜索效率主要取决于启发函数hn，在满足hnh*n的前提下，hn的值越大越好。hn的值越大，表明它携带的与求解问题相关的启发信息越多，搜索过程就会在启发信息指导下朝着目标节点逼近，少走弯路，提高搜索效率。设f1x与f2x是对同一问题的两个估价函数：
f1x=g1x h1x
f2x=g2x h2x
A*1与A*2分别是以f1x与f2x为估价函数的A*算法，且设对多有非目标节点x均有
h1x
|
|
購物車/收銀台(
0
) | 在線留言板
| 付款方式
| 運費計算
| 聯絡我們
| 幫助中心 |
加入書簽
HOME
新書上架
