文档介绍：第4章搜索策略二、研究和选用搜索算法的原则
一、搜索
对于无成熟方法可用的问题求解,必 1、有限搜索还是无限搜索?
须一步步地摸索求解,这种问题求解过程
就是搜索。若搜索空间有限,则任何一种穷举
算法均能完成任务。
注:搜索技术是人工智能的核心技术之一。
二、研究和选用搜索算法的原则二、研究和选用搜索算法的原则
2、搜索空间是静态的还是动态生成的? 3、已知目标还是未知目标?
对于一般搜索,搜索空间基本是静
态的,或表或数组或数据库。
4、只要目标还是也要路径?
在人工智能中,搜索的对象(常称状路径是解题过程中应用的操作序列。
态)是在搜索过程中逐步生成的,需将搜
索对象的生成和评估的代价计算在内。
二、研究和选用搜索算法的原则二、研究和选用搜索算法的原则
5、状态空间搜索还是问题空间搜索? 6、有约束还是无约束?
在解题过程中的每一时刻,所要解决的问问题空间搜索时,若子问题间互相
题均处于一定的状态,搜索过程只是将一个状无约束关系,则求接比较简单,否则,
态变成另一个状态(如,一盘棋局变成另一盘棋
局),则称为状态空间搜索。一般需要回溯,即,放弃已解决的子问
若搜索的对象是问题,搜索的原则是把一题,走回头路,寻找新的解法。
个复杂的问题化为一组比较简单的子问题(如把 7、数据驱动还是目标驱动?
一个复杂的下棋策略分为几个子策略),则称为数据驱动是向前搜索,目标驱动是
问题空间搜索。向后搜索。
注:问题空间搜索常常比状态空间搜索有效,但 8、单向搜索还是双向搜索?
算法要复杂些。
1
二、研究和选用搜索算法的原则二、研究和选用搜索算法的原则
9、盲目搜索还是启发式搜索? 10、有对手搜索还是无对手搜索?
按照预定的控制策略实行搜索,在搜索过若有两个控制源均能改变同一状态
程中获取的中间信息不用来改进控制策略,称空间,并且任何一方向目标前进时,另
为盲目搜索,反之,称为启发式搜索。
一方均试图将它从目标拉开,则称为有
注:关于“启发式”,可有两种看法:1)任何有助对手搜索,通常称为博弈搜索。
于找到问题的解,但不能保证找到解的方法均
是启发式方法;2)有助于加速求解过程和找到注:博弈搜索算法可以看成是一种特殊
较优解的方法是启发式方法。的问题空间搜索。
三、一般搜索方法分类三、一般搜索方法分类
1、盲目搜索
、启发式搜索
1)无变量的盲目搜索 2
状态空间、问题空间的盲目搜索 9 把要求解的问题的具体领域的知识
深度优先、广度优先、代价优先、混合加进搜索算法中,控制搜索过程,以提
向前、向后、双向高算法效率的搜索方法,称为启发式搜
2)有变量的盲目搜索索。
通代
问题求解过程的形式表示
求解一个问题,一般有如下三个步骤:
㈠定义问题
•为了进行搜索,首先必须考虑问题及其
求解过程的形式表示, 其表示是否适一个问题的定义就是对该问题进行形式化描述。
当,将直接影响到搜索求解的效率。说明开始是什么?最终是什么?
数学问题的描述特点:建立变量之间的关系
智能问题的描述特点:建立状态的变化
2
㈡分析问题㈢具体求解
寻找问题求解的措施和途径。按求解措施和途径,由开始状态一
1、数学问题:求解途径是算法步一步地推演,最后到达目标状态。
2、数据处理:求解途径是数据处理流程人工智能问题的求解不同于数学问题
3、智能问题:求解途径是从一个状态到另的求解。
一个状态的变化
一、水杯问题水杯问题(续)
9 给定两个水杯,一个可装4斤水,一个可装3斤如果用数对的形式表示,即(x,y)表示两个水
水。现想在装4斤水的杯中得到2斤水,问如何得杯分别装x斤、y斤水的状态。
到。自然有可能情况:
这两个水杯因没有度量标记,它可以装满水, x=0,1,2,3,4; y=0,1,2,
也可以倒空,可以装大于0,小于该杯最大容量 3;
的水。问题的初始状态为(0,0)
问题的目标状态为(2,0)
这个问题如何形式化描述? 初始状态到目标状态的求解措施只能是:
⑴杯外向两杯倒水
⑵两杯向外倒水
⑶两杯之间倒水
水杯问题(续) 水杯问题(续)
把求解措施写成状态之间的转换,可以得到如下八条规则:
注:各规则的执行有一定条件:
1、(x,y)→(4,y) 4斤杯满
5条的条件: x+y≥4,y>0 1条:x<4
2、(x,y)→(x,3) 3斤杯满
6条的条件: x+y≥3,x>0 2条:y<3
3、(x,y)→(0,y) 4斤杯空
条的条