新書推薦：
《
万有引力书系·基辅罗斯：东斯拉夫文明的起源
》
售價：HK$
141.6
《
康熙的红票：全球化中的清朝
》
售價：HK$
93.6
《
PyTorch语音识别实战
》
售價：HK$
82.8
《
多卖三倍
》
售價：HK$
54.0
《
哲学思维：清晰思考的12条关键原则
》
售價：HK$
82.8
《
海盗之书
》
售價：HK$
81.6
《
亲美与反美：战后日本的政治无意识
》
售價：HK$
69.6
《
亲爱的安吉维拉：或一份包含15条建议的女性主义宣言
》
售價：HK$
58.8
|
| 編輯推薦： |
|
本书参考了许多较新的国外同类教材和其他文献，力图保持新颖性和实用性，强调基本概念和基本观点，注重理论和实际相结合，配备有大量辅助教学的演示实例及推理系统。 本书作为大学本科学习人工智能的教科书, 虽然内容较多, 但可以选择一些基本内容，如问题求解、知识表达、推理等基本方法与技术、数据挖掘技术等进行讲授。本书也可以作为研究生教材和计算机专业工作者了解人工智能的自学用书。
|
| 內容簡介： |
本书系统地阐述了人工智能的基本原理、实现技术及其应用，全面地反映了国内外人工智能研究领域的*进展和发展方向。全书共19章，分为4个部分： 第1部分是搜索与问题求解，用8章的篇幅系统地叙述了人工智能中各种搜索方法求解的原理和方法，内容包括状态空间和传统的图搜索算法、和声算法、禁忌搜索算法、遗传算法、免疫算法、粒子群算法、蚁群算法和Agent技术等；第2部分为知识与推理，用4章的篇幅讨论各种知识表示和处理技术、各种典型的推理技术，还包括非经典逻辑推理技术和非协调逻辑推理技术；第3部分为学习与发现，用3章的篇幅讨论传统的机器学习算法、神经网络学习算法、数据挖掘和知识发现技术；第4部分为领域应用，用3章分别讨论专家系统开发技术和自然语言处理原理和方法。
这些内容能够使读者对人工智能的基本概念和人工智能系统的构造方法有一个比较清楚的认识，对人工智能研究领域里的*成果有所了解。
本书强调先进性、实用性和可读性，可作为计算机、信息处理、自动化和电信等IT相关专业的高年级本科生和研究生学习人工智能的教材，也可供从事计算机科学研究、开发和应用的教学和科研人员参考。
|
| 目錄：
|
目录
第1章概述
1.1人工智能概述
1.2AI的产生及主要学派
1.3人工智能、专家系统和知识工程
1.4AI模拟智能成功的标准
1.5人工智能应用系统
1.6人工智能的技术特征
习题1
第1部分搜索与问题求解
第2章用搜索求解问题的基本原理
2.1搜索求解问题的基本思路
2.2实现搜索过程的三大要素
2.2.1搜索对象
2.2.2扩展规则
2.2.3目标测试
2.3通过搜索求解问题
2.4问题特征分析
2.4.1问题的可分解性
2.4.2问题求解步骤的撤回
2.4.3问题全域的可预测性
2.4.4问题要求的解的满意度
习题2
第3章搜索的基本策略
3.1盲目搜索方法
3.1.1宽度优先搜索
3.1.2深度优先搜索
3.1.3分支有界搜索
3.1.4迭代加深搜索
3.1.5一个盲目搜索问题的几种实现
3.2启发式搜索
3.2.1启发式信息的表示
3.2.2几种最基本的搜索策略
3.3随机搜索
3.3.1模拟退火法
3.3.2其他典型的随机搜索算法
习题3
第4章图搜索策略
4.1或图搜索策略
4.1.1通用或图搜索算法
4.1.2A算法与A*算法
4.2与或图搜索
4.2.1问题归约求解方法与与或图
4.2.2与或图搜索
4.2.3与或图搜索的特点
4.2.4与或图搜索算法AO*
4.2.5对AO*算法的进一步观察
4.2.6用AO*算法求解一个智力难题
习题4
第5章博弈与搜索
5.1人机大战
5.1.1国际象棋人机大战
5.1.2围棋人机大战
5.2博弈与对策
5.3极小极大搜索算法
5.3.1极小极大搜索的思想
5.3.2极小极大搜索算法
5.3.3算法分析与举例
5.4-剪枝算法
习题5
第6章演化搜索算法
6.1遗传算法的基本概念
6.1.1遗传算法的基本定义
6.1.2遗传算法的基本流程
6.2遗传编码
6.2.1二进制编码
6.2.2Gray编码
6.2.3实数编码
6.2.4有序编码
6.2.5结构式编码
6.3适应值函数
6.4遗传操作
6.4.1选择
6.4.2交叉操作
6.4.3变异操作
6.5初始化群体
6.6控制参数的选取
6.7算法的终止准则
6.8遗传算法的基本理论
6.8.1模式定理
6.8.2隐含并行性
6.8.3构造块假设
6.8.4遗传算法的收敛性
6.9遗传算法简例
6.10遗传算法的应用领域
6.11免疫算法
6.11.1免疫算法的发展
6.11.2免疫算法的基本原理
6.11.3生物免疫系统与人工免疫系统的对应关系
6.11.4免疫算法的基本类型和步骤
6.12典型免疫算法分析
6.12.1阴性选择算法
6.12.2免疫遗传算法
6.12.3克隆选择算法
6.12.4基于疫苗的免疫算法
6.13免疫算法设计分析
6.14免疫算法与遗传算法比较
6.14.1免疫算法与遗传算法的基本步骤比较
6.14.2免疫算法与遗传算法不同之处
6.14.3仿真实验及讨论
6.15免疫算法研究的展望
习题6
第7章群集智能算法
7.1群集智能算法的研究背景
7.2群集智能的基本算法介绍
7.2.1蚁群算法
7.2.2flock算法
7.2.3粒子群算法
7.3集智系统介绍
7.3.1人工鱼
7.3.2Terrarium世界
7.4群集智能的优缺点
习题7
第8章记忆型搜索算法
8.1禁忌搜索算法
8.1.1禁忌搜索算法的基本思想
8.1.2禁忌搜索算法的基本流程
8.1.3禁忌搜索示例
8.1.4禁忌搜索算法的基本要素分析
8.1.5禁忌搜索算法流程的特点
8.1.6禁忌搜索算法的改进
8.2和声搜索算法
8.2.1和声搜索算法简介和原理
8.2.2算法应用
8.2.3算法比较与分析
习题8
第9章基于Agent的搜索
9.1DAI概述
9.2分布式问题求解
9.3Agent的定义
9.3.1Agent的弱定义
9.3.2Agent的强定义
9.4Agent的分类
9.4.1按功能划分
9.4.2按属性划分
9.5Agent通信
9.5.1Agent通信概述
9.5.2言语动作
9.5.3SHADE通信机制
9.6移动Agent
9.6.1移动Agent系统的一般结构
9.6.2移动Agent的分类
9.6.3移动Agent的优点
9.6.4移动Agent的技术难点
9.6.5移动Agent技术的标准化
9.7移动Agent平台的介绍
9.7.1General Magic公司的Odysses
9.7.2IBM公司的Aglet
习题9
第2部分知识与推理
第10章知识表示与处理方法
10.1概述
10.1.1知识和知识表示的含义
10.1.2知识表示方法分类
10.1.3AI对知识表示方法的要求
10.1.4知识表示要注意的问题
10.2逻辑表示法
10.3产生式表示法
10.3.1产生式系统的组成
10.3.2产生式系统的知识表示
10.3.3产生式系统的推理方式
10.3.4产生式规则的选择与匹配
10.3.5产生式表示的特点
10.4语义网络表示法
10.4.1语义网络结构
10.4.2二元语义网络的表示
10.4.3多元语义网络的表示
10.4.4连接词和量词的表示
10.4.5语义网络的推理过程
10.4.6语义网络的一般描述
10.5框架表示法
10.5.1框架理论
10.5.2框架结构
10.5.3框架表示下的推理
10.6过程式知识表示
习题10
第11章谓词逻辑的归结原理及其应用
11.1命题演算的归结方法
11.1.1基本概念
11.1.2命题演算的归结方法
11.2谓词演算的归结
11.2.1谓词演算的基本问题
11.2.2将公式化成标准子句形式的步骤
11.2.3合一算法
11.2.4变量分离标准化
11.2.5谓词演算的归结算法
11.3归结原理
11.3.1谓词演算的基本概念
11.3.2归结方法可靠性证明
11.3.3归结方法的完备性
11.4归结过程的控制策略
11.4.1简化策略
11.4.2支撑集策略
11.4.3线性输入策略
11.4.4几种推理规则及其应用
11.5应用实例
11.5.1归约在逻辑电路设计中的应用
11.5.2利用推理破案的实例
习题11
第12章非经典逻辑的推理
12.1非单调推理
12.1.1单调推理与非单调推理的概念
12.1.2默认逻辑
12.1.3默认逻辑非单调推理系统
12.2DempsterShater（DS）证据理论
12.2.1识别框架
12.2.2基本概率分配函数
12.2.3置信函数BelA
12.2.4置信区间
12.2.5证据的组合函数
12.2.6DS理论的评价
12.3不确定性推理
12.3.1不确定性
12.3.2主观概率贝叶斯方法
12.4MYCIN系统的推理模型
12.4.1理论和实际的背景
12.4.2MYCIN模型
12.4.3MYCIN模型分析
12.4.4MYCIN推理网络的基本模式
12.4.5MYCIN推理模型的评价
12.5模糊推理
12.5.1模糊集论与模糊逻辑
12.5.2Fuzzy聚类分析
12.6基于案例的推理
12.6.1基于案例推理的基本思想
12.6.2案例的表示与组织
12.6.3案例的检索
12.6.4案例的改写
12.7归纳法推理
12.7.1归纳法推理的理论基础
12.7.2归纳法推理的基本概念
12.7.3归纳法推理中的主要难点
12.7.4归纳法推理的应用
习题12
第13章次协调逻辑推理
13.1次协调逻辑的含义
13.1.1传统的人工智能与经典逻辑
13.1.2人工智能中不协调的数据和知识库
13.1.3次协调逻辑
13.2注解谓词演算
13.2.1多真值格
13.2.2注解逻辑
13.2.3注解谓词公式的语义
13.2.4APC中的不协调、非、蕴涵
13.3基于APC的SLDa推导和SLDa反驳
13.3.1SLDa推导和SLDa反驳
13.3.2注解逻辑推理方法
13.3.3注解逻辑推理举例
13.4注解逻辑的归结原理
13.5应用实例
13.6控制策略
习题13
第3部分学习与发现
第14章机器学习
14.1概述
14.1.1机器学习的定义和意义
14.1.2机器学习的研究简史
14.1.3机器学习方法的分类
14.1.4机器学习中的推理方法
14.2归纳学习
14.2.1归纳概念学习的定义
14.2.2归纳概念学习的形式描述
14.2.3归纳概念学习算法的一般步骤
14.2.4归纳概念学习的基本技术
14.3基于解释的学习
14.3.1基于解释学习的基本原理
14.3.2基于解释学习的一般框架
14.3.3基于解释的学习过程
14.4基于类比的学习
14.4.1类比学习的一般原理
14.4.2类比学习的表示
14.4.3类比学习的求解
14.4.4逐步推理和监控的类比学习
习题14
第15章人工神经网络
15.1人工神经网络的特点
15.2人工神经网络的基本原理
15.3人工神经网络的基本结构模式
15.4人工神经网络互连结构
15.5神经网络模型分类
15.6几种基本的神经网络学习算法介绍
15.6.1Hebb型学习
15.6.2误差修正学习方法
15.6.3随机型学习
15.6.4竞争型学习
15.6.5基于记忆的学习
15.6.6结构修正学习
15.7几种典型神经网络简介
15.7.1单层前向网络
15.7.2多层前向网络及BP学习算法
15.7.3Hopfield神经网络
15.8人工神经网络与人工智能其他技术的比较
15.9人工神经网络的应用领域
习题15
第16章数据挖掘与知识发现
16.1数据挖掘
16.1.1数据挖掘的定义与发展
16.1.2数据挖掘研究的主要内容
16.1.3数据挖掘的特点
16.1.4数据挖掘的分类
16.1.5数据挖掘常用的技术
16.1.6数据挖掘过程
16.1.7数据挖掘研究面临的困难
16.1.8关联规则挖掘
16.1.9聚类分析
16.2Web挖掘
16.2.1Web挖掘概述
16.2.2Web内容挖掘
16.2.3Web结构挖掘
16.2.4Web使用挖掘
16.2.5Web数据挖掘的技术难点
16.2.6XML与Web数据挖掘技术
16.3文本挖掘
16.3.1文本挖掘的概念
16.3.2文本挖掘预处理
16.3.3文本挖掘的关键技术
16.3.4文本挖掘系统的评价标准
习题16
第4部分领域应用
第17章专家系统
17.1专家系统概述
17.1.1专家系统的定义
17.1.2专家系统的结构
17.1.3专家系统的特点
17.1.4专家系统的类型
17.1.5几个成功的专家系统简介
17.2专家系统中的知识获取
17.2.1概述
17.2.2知识获取的直接方法
17.2.3知识获取的新进展
17.3专家系统的解释机制
17.3.1预制文本解释法
17.3.2路径跟踪解释法
17.3.3自动程序员解释法
17.3.4策略解释法
17.4专家系统开发工具与环境
17.4.1专家系统开发工具的基本概念
17.4.2专家系统工具JESS
17.4.3JESS中的Rete匹配算法和逆向推理机制
17.5专家系统开发
17.5.1专家系统开发的步骤
17.5.2专家系统开发方法
17.6专家系统开发实例
17.6.1动物识别专家系统
17.6.2MYCIN专家系统
习题17
第18章自然语言处理
18.1语言的组成
18.1.1自然语言的基本要素
18.1.2实词和虚词
18.1.3短语结构
18.2上下文无关语法
18.2.1重写规则
18.2.2语法分析
18.3上下文无关语法分析
18.3.1产生后继状态的算法
18.3.2利用词典
18.3.3建立语法分析树
18.4特殊语法的分析
18.4.1引进特征
18.4.2特征匹配
18.5利用图表的高效语法分析
18.5.1chart数据结构
18.5.2有多种解释的句子
18.6语义解释
18.6.1词的意思
18.6.2利用特征的语义解释
18.6.3词义排歧
18.7生成自然语言
18.8在上下文中的自然语言
18.8.1言语的行为
18.8.2创建引用
18.8.3处理数据库的断言和问题
习题18
第19章智能机器人
19.1智能机器人的定义
19.2智能机器人的分类
19.2.1工业机器人
19.2.2服务机器人
19.2.3军用机器人
19.2.4仿生机器人
19.2.5网络机器人
19.3智能机器人的关键技术
19.3.1导航技术
19.3.2路径规划技术
19.3.3机器人视觉技术
19.3.4智能控制技术
19.3.5智能认知与感知技术
19.3.6多模式网络化交互技术
19.4智能机器人未来的发展
19.4.1人工智能技术的应用
19.4.2云机器人
19.4.3移动技术
19.4.4仿生技术
19.4.5机器人体系结构
习题19
参考文献
|
| 內容試閱：
|
前言
人工智能作为研究机器智能和智能机器的一门综合性高技术学科，产生于20世纪50年代，曾经在20世纪末经历了一个轰轰烈烈的研究和发展时期，并且取得过不少令人鼓舞的成就，至今它仍然是计算机科学中备受人们重视和非常具有吸引力的前沿学科，并不断衍生出很多新的研究方向。使计算机程序具有智能，能够模拟人的思维和行为，一直是计算机科学工作者的理想和追求。尽管人工智能的发展道路崎岖不平，自始至终充满了艰辛，但不畏艰难地从事人工智能研究的科学工作者们并没有放弃对这个理想的追求；尽管计算机科学其他分支的发展也非常迅猛，并不断出现些新的学科领域，但是当这些学科的发展进一步深化的时候，人们不会忘记这样一个共同的目标：要使计算机更加智能化。所以不同知识背景和专业的人们都密切关注人工智能这门具有崭新思想和实用价值的综合性学科，并正从这个领域发现某些新思想和新方法。 人工智能的研究范畴不只局限于计算机科学和技术，而是涉及心理学、认知科学、思维科学、信息科学、系统科学和生物科学等多个学科，目前已在知识处理、模式识别、自然语言处理、博弈、自动定理证明、自动程序设计、专家系统、知识库、智能机器人、智能计算、数据挖掘和知识发现等多个领域取得了举世瞩目的成果，并形成了多元化的发展方向。近几年来，随着计算机网络，尤其是Internet的发展，多媒体、分布式人工智能和开放分布式环境下的多智体（multiagent）以及知识挖掘等计算机主流技术的兴起，使得人工智能研究更加活跃，拓宽了其研究和应用的领域，正朝着健康和成熟的方向发展。然而，也必须看到尽管人工智能取得了以上所述的许多成果，但是比起人工智能刚刚兴起时许多专家的预想还相差甚远，很多在当时过于乐观的设想并没有实现，探究其原因也许要追溯到目前人类对自身的思维规律和智能行为研究仍然处于探索阶段，因此，人工智能研究要比这些专家的预想艰难、复杂得多。甚至到今天，对机器能否实现智能仍有争论。这种状况正如Lovelace女士一百多年前曾经说过的：
在考虑任何新颖课题时，常常存在一种倾向，先是过高估计已发现是有趣或值得注意的东西。接着，当发现所研究的概念已超过曾一度保持不变的那些概念时，作为一种自然的反应，就会过低估计该事件的真实状况。
因此，我们必须清楚地认识到：人工智能研究道路的曲折和艰难以及许多尖锐的争论并不表明人工智能学科没有前景，它只是向我们表明理解人类认知和智能的机制，探索智力的形成是人类面临的最困难、最复杂的课题之一。摆在人工智能学科面前的任务是极其艰巨和复杂的，这需要广大的计算机科学工作者不畏艰难，勇于探索，辛勤耕耘，共同开创人工智能发展的美好未来。 本书系统地阐述了人工智能的基本原理、实现技术及其应用，全面地反映了国内外人工智能研究领域的最新进展和发展方向。全书共19章，分为4个部分。第1部分是搜索与问题求解，用8章的篇幅系统地叙述了人工智能中用各种搜索方法求解的原理和方法，内容包括状态空间和传统的图搜索算法、和声算法、禁忌搜索算法、遗传算法、免疫算法、粒子群算法、蚁群算法和Agent技术等；第2部分为知识与推理，用4章的篇幅讨论各种知识表示和处理技术、各种典型的推理技术，还包括非经典逻辑推理技术和非协调逻辑推理技术；第3部分为学习与发现，用3章的篇幅讨论传统的机器学习算法、神经网络学习算法、数据挖掘和知识发现技术；第4部分为领域应用，用3章分别讨论专家系统开发技术和自然语言处理原理和方法以及智能机器人技术。本书参考了许多较新的国外同类教材和其他文献，力求保持新颖性和实用性，强调基本概念和基本观点，注重理论和实际相结合，配备有大量辅助教学的演示实例及推理系统。 本书作为大学本科学习人工智能的教科书, 虽然内容较多, 但可以选择一些基本内容，如问题求解、知识表达、推理等基本方法与技术以及数据挖掘技术等进行讲授。本书也可以作为研究生教材和计算机专业工作者了解人工智能的自学用书。 作者在编写本书时经过了漫长的总结经验和收集意见的过程，并与若干老师和同事合作编写了多种同类教材，得到了他们大量的帮助，在此向这些老师和同事表示衷心的感谢。 在本书的编写过程中, 作者参考了刘娟博士、金涛博士的博士论文, 在编写和搜集资料方面还得到了朱三元、粟藩臣、金敏、杨云水、操郡、朱炜、王丁彬、李珂、贺亢、陈杰、方博、何淼、刘岩、林仁富、黄一钊、刘思等博士和硕士研究生的大力支持，在此向他们表示衷心感谢。 由于水平所限，书中难免存在不足之处，恳请读者批评指正，使本书得以改进和完善。
作者2016年10月于汉口学院
第3章搜索的基本策略
本章主要讨论搜索的基本策略，即怎样搜索才可以最有效地达到目标。搜索的基本策略根据扩展的利用问题的特征信息的方式可分为盲目搜索、启发式搜索和随机搜索。如果没有利用问题的特征信息，一般的搜索方式与平时找东西在策略上可以说是相同的：当我们在慌乱之中寻找东西的时候通常使用的就是随机搜索。当我们在清醒时，有条理地寻找东西的方法大致可以分成两类： 一种是找眼镜模式，它指的是眼镜掉了的时候总是从最近的地方开始寻找，慢慢地扩大搜索的范围； 另一种是走迷宫模式，它指的是在走迷宫的时候由于无法分身只有一条路走到底，走不通再回溯的走法。这3种方法分别对应的就是随机搜索、广度搜索和深度搜索。下面按是否利用问题的特征信息划分搜索策略的方法，讨论盲目搜索、启发式搜索和随机搜索。3.1盲目搜索方法盲目搜索方法又叫非启发式搜索，是一种无信息搜索（uninformed search），一般只适用于求解比较简单的问题。下面将要讨论的几个搜索方法，它们均属于盲目搜索方法，虽然其他课程也讨论类似的算法，但我们要注重在这里的算法表达方法。3.1.1宽度优先搜索在一个搜索树中，如果搜索是以同层邻近节点依次扩展节点的，那么这种搜索就叫宽度优先搜索（breathfirst search）。这种搜索是逐层进行的，在对下一层的任一节点进行搜索之前，必须搜索完本层的所有节点。在本节讨论的盲目搜索算法中存放节点都采用一种简单的数据结构表，表是将节点按一定的顺序用逗号隔开放在一对括号中的一种数据结构，在表的首部和尾部都可以加入和删除节点。宽度优先搜索算法如下。 （1） 令N为一个由初始状态构成的表。 （2） 若N为空退出，标志失败。 （3） 令n为N中第一个节点，将n从N中删除。 （4） 若n是目标，则退出，标志成功。 （5） 若n不是目标，将n的后继节点加入到N表的末端，转第（2）步。宽度优先搜索的优点： 若问题有解，则可找出最优解。缺点： 效率低，组合爆炸问题难以解决。3.1.2深度优先搜索与宽度优先搜索对应的一种盲目搜索叫做深度优先搜索depthfirst search。在深度优先搜索中，首先扩展最新产生的（即最深的）节点到表中。深度相等的节点可以任意排列。深度优先搜索算法如下。（1） 令N为一个由初始状态构成的表。（2） 若N为空退出，标志失败。（3） 令n为N中第一个节点，将n从N中删除。（4） 若n是目标，则退出，标志成功。（5） 若n不是目标，将n的后继节点加入到N表的首部，转第（2）步。
深度优先搜索的优点： 节省大量时间和空间。缺点： 不一定能找到解。因为在深度无限搜索树的情况下，最坏的情况可能是不能停机。广度和深度优先搜索虽然在搜索的策略上走了两个极端，但是它们在控制策略上的差异并不大。它们大都假设以队列作为数据结构，每次选队列的第一个节点进行拓展。广度和深度优先搜索的区别在于： 广度优先搜索把结果存在队列的尾部； 而深度优先搜索则是把它存在首部，只有一字之差。3.1.3分支有界搜索分支有界搜索（branchandbound）也是一种深度优先搜索，但每个分支都规定了一个统一的搜索深度，搜索到这个深度后，如果没有找到目标便自动退回到上一层，继续按深度优先搜索。其算法如下。（1） 令N为一由初始状态构成的表。（2） 若N为空退出，标志失败。（3） 令n为N中第一个节点，将n从N中删除。（4） 若n是目标，则退出，标志成功。（5） 若n深度为预先定好的一个界dmax，则转第（2）步。（6） 若n不是目标，将n的后继节点加入到N表的首部，转第（2）步。此方法若被搜索树的深度远大于目标点的深度，则快于深度优先搜索。3.1.4迭代加深搜索迭代加深搜索（iterative deepening）是在分支有界搜索的基础上，对dmax进行迭代，即逐步加深。这是一种同时兼顾深度和宽度的搜索方法。在限定的深度内，保证了对宽度节点的搜索，如果没有找到解，再加深深度。3.1.5一个盲目搜索问题的几种实现这里给出一个简单的盲目搜索问题： 对于中国象棋，如果马（棋子的名称）当前所在位置是x,y，它跳一步可能到达的位置最多有8个，如图31所示。要求设计一个算法，对于任意给定的棋盘上的坐标位置tp，输出马从当前位置cp出发通过搜索到达的该坐标位置tp。
x
1234567
1
2
3
4
3
2
5y4
5
1
6
6
8
7
7
图31中国象棋中跳马可能到达的8个位置求解过程如下：1. 定义状态空间设状态空间的一点为109矩阵。2. 定义操作规则马走棋盘可以模拟为一个搜索过程： 每到一处，总让它按东、东南、南、西南、西、西北、北、东北8个方向顺序试探下一个位置； 如果某方向可以通过，并且在前面的搜索过程中不曾到达，则可以前进一步； 在新位置上按上述方法就可以重新进行搜索，并将到达的位置标记*。对这8个方向，从东开始，按顺时针的顺序依次编号为1，2，，8。算法中，设计move数组是一个二维数组，记录了8个方向上的行下标增量和列下标增量。如果当前所在位置是x,y，则沿第i0i7个方向前进一步，到达新位置x1,y1，其下标可以借助move数组确定：
x1=x move［i］［0］
y1=y move［i］［1］
3. 定义搜索策略为了避免重复，可以对搜索过的地方做一个标记，不同的搜索分支可以避开搜索这个地方。1 宽度优先搜索。搜索过程为： 沿着8个方向，如果可行，都前进一步，看是否达到位置tp。如果没有达到，则依次从新的位置为起点，沿着8个方向继续前进一步直到搜索到目标位置tp，或找不到未搜索的位置为止。2 深度优先搜索。搜索过程为： 沿着8个方向中的某一个，比如，从朝东方向开始，前进一步，看是否达到位置tp。如果没有达到，则以这个位置为起点，沿着8个方向中的某一个继续前进一步某个分支搜索不通时，再沿着当前位置8个方向的下一个方向继续搜索。直到搜索到目标位置tp，或找不到未搜索的位置为止。3 分支有界搜索。搜索过程为： 沿着8个方向中的某一个，比如，从朝东方向开始，前进一步，看是否达到位置tp。如果没有达到，则以这个位置为起点，沿着8个方向中的某一个继续前进一步如果搜索到第k步或某个分支搜索不通时，再沿着当前位置8个方向的下一个方向继续搜索。直到搜索到目标位置tp，或所有的分支都搜索到了第k步，或找不到未搜索的位置为止。3.2启发式搜索盲目搜索的效率低，耗费过多的搜索时间。如果能够找到一种方法选择最有希望的节点加以扩展，那么，搜索效率将会大大提高。启发式搜索就是基于这种想法，它是深度优先搜索的改进。搜索时不是任取一个分支，而是根据一些启发式信息，选择最佳的一个或几个分支往下搜索。3.2.1启发式信息的表示1. 启发式搜索的依据
启发式搜索作为一种基本的搜索方法，其主要根据如下。（1） 人们善于利用一些线索来帮助自己选择搜索方向，这些线索统称为启发式heuristics信息，heuristics一词来源于希腊语heuriskein，即发现的意思。（2） 现实问题往往只需一个解，而不要求最优解或全部解。（3） 使用启发式信息可以避免某些领域里的组合爆炸问题。例3.1计算机下棋问题，若采用将所有可能的走法都试一遍，并从中找出最佳的一步，下面几种棋的可能走法分别为：一字棋： 9！步。国际象棋： 10120步，如果计算机以最快速度一年走10104步，需1016年才能完成。围棋： 10761步，需要的时间更长。像这样一类问题必须利用启发式信息来求解。这些问题的初始状态、算子和目标状态的定义都是完全确定的，并且有一个确定的搜索空间。现在的问题就在于如何有效地搜索这个空间，因为这个空间太大。进行这种搜索的技术一般需要某些有关具体问题领域的特性的信息。这些信息常常可以用来简化搜索。把这种信息叫做启发式信息，并把利用启发式信息进行的搜索方法叫做启发式搜索方法。启发式信息按其形式可分为下列两种。（1） 表示为估计函数。确定一个启发式函数fn，n为被搜索的节点，fn把n所处的问题状态的描述映射成问题解决的程度，通常这种程度用数值来表示，就是启发式函数的值。这个值的大小用来决定最佳搜索路径。（2） 表示成规则。如Lennat编制了一个程序AM，从数论、集合论的一些基本概念出发，发现了标准数论大量的定理，其中一条启发式规则如下：如果存在一个有趣的二元函数fx,y，那么看看两变元相同时会发生什么？若f表示乘法： 导致发现平方。若f表示集合并运算： 导致发现恒等函数。若f表示思考： 导致发现反省。若f表示谋杀： 导致发现自杀。（3） 表示成元规则。还有一些启发式规则用于如何控制使用状态空间中的搜索规则（或算子），即这个规则体现了状态空间的搜索策略，这个策略用到启发式信息。这样的启发式规则也称为元规则（meta rule），是如何使用规则的规则。2. 启发式函数的表示方法启发式函数是一种映射函数，它把对问题的当前状态的描述映射成一种接近目标的程度。使用这个函数，可以引导人们如何解决当前的问题。在搜索算法的设计中，考虑问题的状态的各种因素、各种特征，怎样对所考虑的方面作出估计，怎样对某些因素加权等，都用于启发式函数的设计，只要这些因素有助于该函数对节点是否在解路径上作出尽可能准确的估计。启发式函数设计得好，对有效引导搜索过程有着重要的作用。在有的情况下，非常简单的启发式函数搜索路径能够作出非常令人满意的估计，对有些场合还需要使用非常复杂的启发式函数。下面就简单讨论一下如何构造启发式函数。（1） 设计的启发式函数应能够根据问题的当前状态，确定用于继续求解问题的信息。例3.2考虑利用启发式信息去求解水壶问题即如何通过两个容量为4升、3升的水壶得到2升水，人们绝不盲目搜索，而是利用水壶容量信息4，3，0，考虑如何求得2。用这几个数字可以考虑4减2或3减1得到2。但考虑4减2肯定不行，因为它用到2来求得2，用后一个方法要考虑如何求得1。这很容易在当前信息中找出，因为4减3等于1。由于这里的减去是从某个水壶中向外倒水，可以从加满水的4升水壶里向空的3升水壶里加满，这样4升水壶里只剩下1升。这样得到数字1。再从现有数字中不难想到3-1＝2。由3-1＝2又可以想到把3升水壶倒空，再把4升水壶的1升水倒入3升水壶中，3升水壶还缺2升水，现在有数字2了，可以考虑4-2＝2。也就是将4升水壶的水加满，然后用4升水壶中的水将3升的水壶加满。这样4升水壶中就只剩下2升了。用只有两个元素的表： （4升水壶的水量，3升水壶的水量），上述的求解路径可表示为（0，0）（4，0）（1，3）（1，0）（0，1）（4，1）（2，3）=目标其搜索过程如图32所示。
图32利用启发式信息求解水壶问题的搜索过程
2 设计的启发式函数应能够估计已找到的状态与达到目标的有利程度。这样的启发式函数能够有效地帮助决定哪些后继节点应被作为下一步搜索的起点。例3.38数码问题。初始状态S0283
164
7 5目标状态Sg123
8 4
765一般状态，即问题空间为a11a12a13
a21a22a23
a31a32a33
各状态间的转换规则为：Pr1： 空格上移If □i，j and i1 then ai-1,j □i，j Pr2： 空格下移If □i，j and i3 then ai 1,j □i，j Pr3： 空格左移If □i，j and j1 then ai,j-1 □i，j Pr4： 空格右移If □i，j and j3 then ai,j 1 □i，j其中Pr表示产生式规则（production rule），它类似于有限自动机的转换规则； ai 1,j□i，j表示处在第i＋1行第j列的元素与第i行第j列的空格交换。定义启发式函数f1=数字错放位置的个数。f1=0，则达到目标。其搜索过程如图33所示。
图33利用启发式函数求解8数码问题的搜索过程
但利用这个启发式函数搜索到第3层时，S5是应避开的（不应生成的），又由于f2S4）=f2S6）=3，这称为均势（tie），因此下一步还得确定一个策略，以决定当f1值相同时如何打破均势（break tie），向下搜索。这意味着要定义一个新的启发式函数。由此可以看出，同一问题启发式函数可能有多种选择。现在定义新的启发式函数为f2=所有数字当前位置次最短路径走到正确位置的步数之和在这个定义之下，各状态的启发式函数值为数码12345678f2S0）=1 1 0 0 0 1 0 2=5f2S1）=1 1 0 0 0 0 0 2=4f2S2）=1 1 0 0 0 1 1 2=6f2S3）=1 1 0 0 1 1 0 2=6f2S4）=1 1 0 0 0 0 0 1=3f2S5）=1 1 0 0 0 1 0 2=5f2S6）=1 2 0 0 0 0 0 2=5其中每个函数中加法的每一项表示对应数码移动的步数。现在可以看出，原来有f2S4）=f2S6）=3，现在f1S4）0，位移后的状态可采纳的概率为
Pk=11 e-EkT
式中T为温度，然后从0，1区间均匀分布的随机数中挑选一个数R。若RE，则PP1，说明能量越小，则平衡状态概率越大，因而系统处于能量较小的平衡状态的可能性也越大。另外，温度T对系统的影响如下。① 温度越高，系统越容易达到平衡状态，但却使PP值越小，故相对而言，在平衡状态下处于能量较小状态的可能性也越小。② 温度越低，系统达到平衡状态的速度虽慢，但PP值越大，故系统可能达到能量较小的平衡状态。对于搜索问题中的爬山法，利用模拟退火法，不但可以使变化的随机选择大一些的步长，而且
图312使小球跳过局部极小点可以跨过局部极小点。通常的做法是： 最初阶段倾向于取大步； 后续阶段倾向于取小步。
这个过程的原理可以根据图312所示形象地去理解，如果希望小球离开A点然后停在B点（全局最小，使用较小的能量来摇动系统，这小球只能停在A点。若开始以较大的速度摇动，后来慢慢地减轻，则小球很可能就会落在B点，且小球到B点之后，就不易从B点摇到A点。模拟退火法就类似于这个过程。
3.3.2其他典型的随机搜索算法在许多搜索算法中，采取的搜索策略并非只是一种，而随机搜索就是所采取的策略之一。采用随机搜索的目的往往是增加算法的灵活性和搜索过程扩展方式的多样性，使得算法避免陷入过早收敛的境地。这样的一些算法常常给启发式函数加入一些带有随机性的调控参数，如参数中有rand函数或其他随机控制手段，这类算法有遗传算法、粒子群算法、蚁群算法和人工免疫算法等。1. 遗传算法遗传算法（genetic algorithm）的基本思想来源于达尔文的进化论。达尔文认为： 每个物种初生个体的数目总是比能够生存下来的个体数目多，因此个体之间为了生存而相互竞争。如果某个个体的特征发生微小的变异，尽管很小，但使得其适应能力有所提高，那么在复杂的、不断变化的自然环境中，这个个体就有更大机会生存下来，这就是自然选择（natural selection）。变异得到的特征经过遗传由后代继承。通过遗传、变异和自然选择，生物物种能够不断进化。遗传算法则是模拟生物进化的自然选择和遗传机制的一种随机搜索方法，适用于复杂的非线性问题。该算法的主要步骤为： 编码； 产生初始种群； 计算适应度； 选择； 交叉； 变异。由于遗传算法只使用目标函数（适应值）进行搜索，可以处理很多类型的问题。遗传算法使用的遗传算子是一种随机操作，而不是确定性规则，其中选择、交叉和变异操作都是由一定概率来控制的。2. 人工免疫算法人工免疫算法是模拟了人体的免疫细胞的工作机制设计出来的算法。它和遗传算法相比，只是把遗传算子和控制参数的部分操作做了一些改变。该算法从种群中选择适应值最高的一批个体并对它们进行变异操作，而这里变异操作的概率随着适应度的增加而减少。在原来的种群中把一部分适应度差的淘汰掉,并从变异完成的个体中找出适应度最高的那部分组成新的种群。该算法的框架也与遗传算法基本相似，但有的只采用了变异操作和选择操作，有的又增加了一些操作。它增加了群体的多样性，保留了更多且不同的最优个体，随进化过程的进行而不断更新这些个体，这样能加速算法找到全局最优值。经仿真实验证明在优化几个相关的概率后，对很多问题该算法的处理效率比遗传算法要好。3. 蚁群算法蚁群算法于20世纪90年代早期由Marco DorigoMilan,Italy等提出发展并完善。蚁群算法模拟蚂蚁从巢穴出发，通过对信息素pheromone的追踪来找到从巢穴到食物之间的最短路径。模拟过程中假定： 每只蚂蚁都是随机移动的。 信息素被洒到经历过的路径上。 蚂蚁能感知周围的信息素。 一条路径上的信息素的浓度越高，则其被其他蚂蚁选择的可能性越大。模拟过程由以下6个规则控制。（1） 范围。蚂蚁观察到的范围是一个方格世界，蚂蚁有一个参数为速度半径（一般是3），那么它能观察到的范围就是33个方格世界。（2） 环境。蚂蚁所在的环境是一个虚拟的世界，其中有障碍物，有别的蚂蚁，还有信息素。信息素有两种，一种是找到食物的蚂蚁洒下的食物信息素，另一种是找到窝的蚂蚁洒下的窝的信息素。环境以一定的速率让信息素消失。（3） 觅食规则。在感知范围内寻找是否有食物，如果有就直接过去； 否则看是否有食物信息素，并且比较在能感知的范围内哪一点的信息素最多，就朝信息素多的地方走。由于每只蚂蚁多会以小概率犯错误，所以并不是总往信息素最多的点移动。（4） 移动规则。每只蚂蚁都朝向信息素最多的方向移动，并且当周围没有信息素指引时，蚂蚁会按照自己原来运动的方向惯性地运动下去，并且在运动的方向上有一个随机的小扰动。（5） 避障规则。如果蚂蚁要移动的方向有障碍物挡住，它会随机地选择另一个方向，并且有信息素指引的话，它会按照觅食找窝的规则行动。（6） 播撒信息素规则。在不同的蚁群优化算法中，有的蚂蚁每次撒播的信息素是一个常量，有的蚂蚁撒播的信息素是一个变量，但是这些信息素都是动态变化并随时间逐渐消失的。从模拟过程中的假设和控制规则可以看出，随机搜索是该搜索算法的主要特点之一。4. 粒子群算法粒子群算法简称PSOParticle Swarm Optimization，它具有蚁群和遗传算法两者的特点，它和蚁群算法一样采用的是增量方式进行搜索，但是在结构上，不论是种群的初始化、适应性函数、终止条件，还是其他方面和遗传算法是基本一致的。PSO中粒子就相当于遗传中的个体，和个体不同的是每个粒子有一个速度决定它们飞翔的方向和距离，然后粒子们就追随当前的估价函数评出的最优粒子在解空间中搜索。PSO 初始化和遗传一样，然后通过迭代找到最优解。在每一次迭代中，粒子通过跟踪两个极值来更新自己。第一个极值就是粒子本身所找到的最优解，这个解叫做个体极值pbest； 另一个极值是整个种群目前找到的最优解，这个极值是全局极值gbest。在找到这两个最优值时，粒子根据以下公式来更新自己的速度和新的位置，即
v［］=w*v［］ c1*rand * pbest［］ - present［］
c2 * rand * gbest［］-present［］31
present［］=present［］ v［］32
其中，v［］是粒子的速度； present［］是当前粒子的位置； rand 是介于（0，1）之间的随机数； c1、c2是学习因子； w称为惯性因子，w较大适于对解空间进行大范围探查，w较小适于进行小范围开挖，w越小收敛得越快，但是容易收敛于局部极值，所以通常采取随着迭代的加深线性减少w的取值的方法来进行优化。这种算法有其实现容易、精度高、收敛快的特点； 而它的弊端和遗传算法一样，也是它容易收敛到局部的极值。5. 混合随机算法一般弥补随机算法缺陷的方法有两种： 一种是提高自己，比如调整控制机制、优化参数等； 另一种就是混合其他算法的优势来提升自己的性能。以下是几种常见的混合方式。1 模拟退火与遗传算法及PSO的结合。PSO和遗传算法都有十分强的全局搜索能力，但是容易陷入局部最优值，而模拟退火的metropolis法则可以帮助它们跳出局部最优，得到更快的收敛速度。2 蚁群算法与遗传算法及PSO的结合。它们的互补在于局部搜索和全局搜索。结合分两种： 一种以蚁群算法为基础； 另一种以遗传算法为基础。第一种思想主要是在蚁群中加入交叉和变异算子来实现，或是由遗传算出大致的最优点分布作为蚁群的信息素出现。第二种策略是先用遗传算出一个解，再用蚁群来进行局部优化或是让蚁群算法改善变异算子。以上这些算法还将用单独的章节分别予以详细讨论。习题33.1对N=5，k3的传教士和野人问题，定义两个h函数（非零），并给出用这两个启发式函数的A算法搜索图。讨论用这两个启发式函数求解该问题时是否能得到最佳解。3.2在33的空格内，用1，2，，9的9个数字填入9个空格内，使得每行数字组成的十进制数平方根为整数。试用启发式搜索算法求解，分析问题空间的规模和有用的启发式信息。3.3试给出爬山法和最佳优先搜索算法搜索图313所示的搜索路径。3.4找出深度优先搜索算法与广度优先搜索算法在文字叙述中的区别。3.5在哪种问题空间，深度优先搜索好于广度优先搜索?3.6在什么时候最佳优先搜索比广度优先搜索差?3.7考虑将图314a中的积木形式转成图314b中的积木形状这一问题,可以使用的操作符有PICKUP、PUTDOWM、STACK和UNSTACK。用爬山法求解这一问题有解吗？为什么？
图313搜索路径
图314习题3.7用图
3.8一个经理有3个女儿，3个女儿的年龄加起来等于13，3个女儿的年龄乘起来等于经理自己的年龄，有一个下属已知道经理的年龄，但仍不能确定经理3个女儿的年龄，这时经理说只有一个女儿在上学，然后这个下属就知道了经理3个女儿的年龄。请问3个女儿的年龄分别是多少？为什么？请找出启发式信息。3.9假设要写一道问题求解搜索程序去求解下面的每一类问题，试确定搜索是正向进行还是逆向进行： a.模式识别;b.积木世界;c.语言理解。3.10对下面的每类问题，试描述一个好的启发式函数： a.积木世界;b.定理证明;c.传教士和野人。3.11分析宽度优先搜索和深度优先搜索的优、缺点，举出它们的正例和反例。3.12有一个农夫带一只狐狸、一只小羊和一篮菜过河。假设农夫每次只能带一样东西过河，考虑安全，无农夫看管时，狐狸和小羊不能在一起，小羊和菜篮不能在一起。试设计求解该问题的状态空间，并画出状态空间图。
|
|
購物車/收銀台(
0
) | 在線留言板
| 付款方式
| 運費計算
| 聯絡我們
| 幫助中心 |
加入書簽
HOME
新書上架
