人工智能入门课件第2章 用搜索实现求解问题

第2章用搜索实现求解问题2.1搜索求解问题的基本思路AI早期的目的是想通过计算技术来求解这样一些问题：它们不存在现成的求解算法或求解方法非常复杂，而人使用其自身的智能都能较好地求解。为模拟这些问题的求解过程而发展的一种技术叫搜索。搜索的过程可理解为根据初始条件和约束条件及关联关系构造一个解答空间，并在这个空间中寻找符合目标状态的过程。2.2实现搜索过程的三大要素搜索过程的三大要素：搜索对象、搜索的扩展规则和搜索的目标测试。搜索对象是指在什么样的对象（即状态，这些状态就是可能解的表示）之上进行搜索；搜索的扩展规则是指如何控制从一种状态变化为另一种状态，使得搜索得以前进；搜索的目标测试是指搜索在什么条件下到达问题求解的要求。搜索终止时，搜索成功表示问题有解，否则表示问题无解。2.2.1搜索对象

利用搜索来求解问题是在某个可能的解空间内寻找一个解，这就首先要有一种恰当的解空间的表示方法。一般把这种可能的解都表示为一个状态。这个过程必须做到把所有和解决问题相关的信息（特征）全部抽象出来，存储这些特征的数据结构被叫做状态，它表示问题的一个可能解，这个数据结构下形成的各种有意义的状态，称为状态空间。状态（state）是为描述某些不同事物间的差别而引入的一组最少变量q0，q1，q2…,qn的有序集合,并表示为:

Q=（q0,q1,…,qn）其中，每个元素qⅰ称为状态变量。给定每个分量的一组值，就得到一个具体的状态。2.2.2扩展规则扩展规则由两部分组成：状态转移算子和状态扩展策略。状态转移算子使问题从一种状态变化为另一种状态的手段称为操作符或转移算子（operator）。操作符可以是一个动作（如下棋走步）、过程、规则、数学算子、运算符号或逻辑运算符等。2.2.2扩展规则状态扩展策略宏观地看，以怎样的次序对问题对应的搜索图进行搜索，是搜索的技巧，也是智能的体现。没有目的随机的选一个扩展的话很容易实现，但一般很难得到一个解或不能保证解的质量，即得不到一个满意解。而好的策略可以比一般的方法搜索更少的节点，更快地找到解。也就是说，根据问题的不同设计更合理的扩展策略可以提高搜索的效率。2.2.3目标测试

目标测试是在搜索过程中，对可能的解是否达到满意解的判断。它包含两种情况：一种是，解是否满足所有限制条件（宽条件，成立的前提）；另一种是，解是否就是既定的目标（紧条件，目标状态已知）。宽条件一般是指在目标状态未知，而求解只需要接近目标状态就行了的情况下设定的条件，比如说下棋，把对方将死的方式有很多种，满足一条就够了。紧条件是在目标状态已知的条件下，直接判定是否已经达到这些状态，比如说，玩魔方，成功的条件是六个面都是同色。2.3实现搜索的基本步骤一般在搜索时要定义状态空间Q，它包含三种类型的集合：初始状态集合S，操作符集合F（把每个完成的动作表达出来）目标状态集合G。因此，可把状态空间记为三元组（S，F，G）。问题状态空间法的基本思想是：

（1）将问题中的已知条件看成状态空间中初始状态；将问题中要求的目标看成状态空间中目标状态；将问题中其他可能的情况看成状态空间的任一状态。（2）设法在状态空间中寻找一条路径，由初始状态出发，能够沿着这条路径达到目标状态。问题状态空间法的基本步骤：（1）根据问题，定义出相应的状态空间，确定出状态的一般表示，它含有相关对象的各种可能的排列。这里仅仅是定义这个空间的状态，而不必枚举该状态空间的所有状态，但由此可以得出问题的初始状态、目标状态，并能够表示出所有其他状态。问题状态空间法的基本步骤：

(2)规定一组操作(算子),能够使状态从一个状态变为另一个状态。

(3)决定一种搜索策略，使得能够从初始状态出发，沿某个路径达到目标状态。水壶精确度量水量问题播放电影视频给定两个水壶，一个可装5加仑水，一个能装3加仑水。水壶上没有任何度量标记。有一水龙头可用来往壶中灌水。问题是怎样在能装5加仑的水壶里，恰好只装4加仑水

？（1）定义状态空间该问题只关心水壶所装水的多少，可将问题进行抽象，用数偶(x,y)来表示状态空间的任一状态。

x表示5加仑水壶中所装的水量，x=0到5；

y表示3加仑水壶中所装的水量，y=0到3；

初始状态为(0,0)，目标状态为(4,?)，？表示水量不限，因为问题中未规定在3加仑水壶里装多少水。初始状态为(0,0)目标状态为(2,?)？表示水量不限，因为问题中未规定在3加仑水壶里装多少水。（2）确定一组操作

用来求解该问题的算子可用如下10条规则来描述。r1:（X，Y|X<5）→（5，Y）5加仑水壶不满时，将其装满；r2:（X，Y|Y<3）→（X，3）3加仑水壶不满时，将其装满；r3:（X，Y|X>0）→（X-D，Y）

从5加仑水壶里倒出一些水；r4:（X，Y|Y>0）→（X，Y-D）

从3加仑水壶里倒出一些水；r5:（X，Y|X>0）→（0，Y）

把5加仑水壶中的水全部倒出；r6:（X，Y|Y>0）→（X，0）把3加仑水壶中的水全部倒出；r7:（X，Y|X+Y≥5∧Y>0→（5，Y-（5-X））把3加仑水壶中的水往5加仑水壶里倒，直至5加仑水壶装满为止；r8:（X，Y|X+Y≥3∧X>0）→（X-（3-Y），3）把5加仑水壶中的水往3加仑水壶里倒，直至3加仑水壶装满为止；r9:（X，Y|X+Y≤5∧Y>0）→（X+Y，0）把3加仑水壶中的水全部倒进5加仑水壶里；r10:（X，Y|X+Y≤3∧X>0）→（0，X+Y）把5加仑水壶中的水全部倒进3加仑水壶里

这些算子就是模拟倒水的动作，也就是求解问题的过程。算子中的“→”表示“如果……则……”；“∧”表示并且。比如说，第8个算子r8表示的意思是：如果两个水壶当前的水量为（x，y），两个水壶的水量加起来（即x+y）可以把3加仑水壶灌满（≥3）并且5加仑水壶里有水（X>0），则把3加仑水壶加满（y=3），而5加仑水壶的水量变为X-（3-Y），即已经导入3加仑水壶3-y的水量了，要从5加仑水壶里减去。（3）选择一种搜索策略为求解水壶问题，除上面给出的问题描述和算子外，还应该选择一种策略控制搜索。该问题的策略为一个简单的循环控制结构：选择其左部匹配当前状态的某条规则，并按照该规则右部的描述，对此状态作适当改变，然后检查改变后的状态是否为某一目标状态，若不是，则继续该循环。。该循环结构如图2.3所示。这样搜索下去，直到出现(4,?)状态为止，从(0,0)到(4,?)的路径上所用的操作序列就为所求的解。图2.4是求解问题的搜索图。图2.4中有多个算子序列可以求解水壶问题，也就是有多条路径到达目标，下面就是求解问题的搜索路径之一：5加仑水壶中含水量3加仑水壶中含水量

所应用的规则00初始状态50r123r320r602r1052r143r8（动画实现）2.4搜索的几种基本策略搜索的基本策略根据扩展的利用问题的特征信息的方式可分为盲目搜索、启发式搜索方法。盲目搜索方法又叫非启发式搜索，是一种无信息搜索（UninformedSearch），一般只适用于求解比较简单的问题。启发式搜索就是要利用问题的特征信息（或一些线索）来帮助（启发）自己选择搜索方向。2.4.1盲目的搜索方法当我们在慌乱之中寻找东西的时候，毫无目标到处乱翻，就是随机查找。当我们清醒时有条理地寻找东西的方法又大致可以分成两类：一种是找眼镜模式。它指的是眼镜掉了的时候总是从最近的地方开始寻找慢慢的扩大搜索范围的搜索方法。一种是走迷宫的方式。它指的是在走迷宫的时候由于无法获得其他信息，只有一条路走到底，碰壁后再回溯寻找其他途径的这种走法。这三种方法分别对应的就是随机搜索、广度优先搜索和深度优先搜索。1.宽度优先搜索现在讨论的盲目的搜索算法中存放节点都采用一种简单的数据结构——表，表是将节点按一定的顺序用逗号隔开放在一对括号中的一种数据结构，在表的首部和尾部的都可以加入和删除节点。如果搜索是以同层邻近节点依次扩展节点的,那么这种搜索就叫宽度优先搜索,这种搜索是逐层进行的,在对下一层的任一节点进行搜索之前,必须搜索完本层的所有节点。宽度优先搜索算法如下:1.令N为一个由初始状态构成的表；

2.若N为空退出，标志失败；

3.令n为N中第一个点，将n从N中删除；

4.若n是目标，则退出，标态成功；

5.若n不是目标，将n的后继点加入到N表的尾部，转2。宽度优先搜索的优点是：若问题有解，则可找出最优解;宽度优先搜索的缺点是:效率低，组合爆炸问题难以解决。2.深度优先搜索在深度优先搜索中，我们首先扩展最新产生的（即最深的）节点。深度相等的节点可以任意排列。2.深度优先搜索深度优先搜索算法如下:1.令N为一个由初始状态构成的表；2.若N为空退出，标态失败；3.令n为N中第一个点，将n从N中删除；4.若n是目标，则退出，标态成功；5.若n不是目标，将n的后继加入到N表的首部转2。2.深度优先搜索

深度优先搜索的优点：节省大量时间和空间；深度优先搜索的缺点：不一定能找到解。因为在无限搜索树的情况下，最坏的情况可能是不停机。3.分枝有界搜索

（Branch-and-Bound）

分枝有界搜索也是一种深度优先搜索，但每个分支都规定了一个统一的搜索深度，搜索到这个深度后，如果没有找到目标便自动退回到上一层，继续搜索。1.令N为一由初始状态构成的表；2.若N为空退出，标志失败；3.令n为N中第一个点，将n从N中删除；4.若n是目标，则退出，标态成功；5.若n深度=预先定好的一个界dmax，则转2；6.若n不是目标，将n的后继加入到N表的首部转2；2.4.2启发式搜索盲目搜索的效率低，耗费过多的搜索时间。如果能够找到一种方法用于排列待扩展节点的顺序，即选择最有希望的节点加以扩展，那么，搜索效率将会大大提高。启发式搜索就是基于这种想法,它是深度优先的改进。搜索时不是任取一个分枝，而是根据一些启发式信息，选择最佳一个分枝或几个分枝往下搜索。1.启发式信息的表示1）启发式搜索的依据（1）人们善于利用一些线索来帮助自己选择搜索方向，这些线索统称为启发式(Heuristics)信息。（2）现实问题往往只需一个解，而不要求最优解或全部解。（3）启发式信息可以避免某些领域里的组合爆炸问题。1.启发式信息的表示2）启发式信息表示启发信息按其形式可分为下列2种：（1）表示为估计函数确定一个启发式函数f(n),n

为被搜索的节点,它把问题状态的描述映射成问题解决的程度，通常这种程度用数值来表示，就是启发式函数的值。这个值的大小用来决定最佳搜索路径。1.启发式信息的表示（2）表示成规则把启发式信息表示为一条规则，如果当前状态匹配这条规则的前件，则采用该规则，以规则的后件作为当前状态。如AM的一条启发式规则为：如果存在一个有趣的二元函数f(x,y)，那么看看两变元相同时会发生什么？若f表示乘法：导致发现平方；若f表示集合并运算：导致发现恒等函数；若f表示思考：导致发现反省；若f表示谋杀：导致发现自杀。1.启发式信息的表示启发式函数是一种映射函数，它把对问题状态的描述映射成一种希望的程度。启发式函数设计得好，对有效引导搜索过程有着重要的作用。非常简单的启发式函数搜索路径能够作出非常令人满意的估计。1.启发式信息的表示如何构造启发式函数？（1）启发式函数能够根据问题的当前状态，确定用于继续求解问题的信息。这样的启发式函数能够有效地帮助决定那些后继节点应被产生。1.启发式信息的表示283

1

6475

例2.7八数码问题。1

238

4765a11a12a13a21a22a23a31a32a33

问题空间为：S0

Sg

1.启发式信息的表示各状态间的转换规则为：Pr1:空格上移↑

If□i，jandi≠1thenai-1,j←→□i，j

Pr2:空格下移↓

If□i，jandi≠3thenaI+1,j←→□i，j

1.启发式信息的表示Pr3:空格左移←If□i，jandj≠1thenai,j-1←→□i，j

Pr4:空格右移→If□i，jandj≠3thenai,j+1←→□i，j启发式函数f1=数字错放位置的个数，f1=0，则达到目标。28316475283164752831476528314765231847652831647528314765283164751.启发式信息的表示

当f1值相同时如何决定走步?

现在定义：f2=所有数字当前位置以最短路径走到正确位置的步数之和。在这个定义之下，各状态的启发式函数值为：数码12345678F2(S0）=1+1+0+0+0+1+0+2=5F2(S1）=1+1+0+0+0+0+0+2=41.启发式信息的表示数码12345678F2(S2）=1+1+0+0+0+1+1+2=6F2(S3）=1+1+0+0+1+1+0+2=6F2(S4）=1+1+0+0+0+0+0+1=3F2(S5）=1+1+0+0+0+1+0+2=5F2(S6）=1+2+0+0+0+0+0+2=51.启发式信息的表示

(2)启发式函数应能够估计出可能加速达到目标的程度

这可以帮助确定当扩展一个节点时，那些节点应从搜索树中删除。启发式函数对搜索树(图)的每一节点的真正优点估计得愈精确,解题过程就愈少走弯路。1.启发式信息的表示例2.8八皇后问题(8-Queensproblem）

在8*8棋盘要求放下8个皇后，要求没有一个皇后能够攻击其他皇后，即要使得在任何一行、一列或对角线上都不存在两个或两个以上的皇后。1.启发式信息的表示求解这个问题的过程为：

（a）定义状态空间。设状态空间的一点为：8*8矩阵。

（b）定义操作规则。按如下规则放置皇后：1.启发式信息的表示

第一个皇后放第一行。第二个皇后放在第二行且不与第一个皇后在同一列或对角线的空格上。

……

第i个皇后放在第i行且不与前面i–1个皇后在同一列或对角线的空格上。

……1.启发式信息的表示可使用如下启发式函数：设x为当前要放置Queen的空格f（x）=剩下未放行中能够用来放Queen的空格数不难看出，f（x）愈大愈好，应选择f（x）最大的空格来放置皇后。例如，在放置了三个Q后，第4个Q可放在第4行的A，B，C三个位置。

Q

Q

Q

A

BC

abc

bc

ab

bc

c

ac

abc

b

acb

ac

acabbc

1.启发式信息的表示a为第4行A处放了皇后剩下可放Q的位置；

b为第4行B处放了皇后剩下可放Q的位置；c为第4行C处放了皇后剩下可放Q的位置。按照以上定义，可求得：

f（A）=8，f（B）=9，f（C）=10。所以搜索可以从C对应的空格放置一个皇后开始，其余的空格对应的搜索树可以删除。1.启发式信息的表示（c）定义搜索策略第i个皇后放到第i行中的那个与前面i-l个皇后不在同一列或对角线上且f（x）值最大的空格中。启发式信息是某些领域里的知识信息，它能使计算机系统在这些知识信息提示以后可能采取的某些可能的动作或避免某些不可能的动作。

作者朱福喜朱三元2.几种经典的搜索策略下面主要介绍采用Best-first策略的几个基本方法，这些方法构成了许多数AI系统的构架，其效率取决于问题所在领域知识的利用与开发。由于这些方法的通用性，并且难于克服搜索过程的组合爆炸问题，所以又称为弱法(Weakmethod）。2.几种经典的搜索策略

弱法主要包括：．最佳优先法．生成测试法．爬山法．广度优先法．问题归约法．约束满足法．手段目的分析法。1）生成测试法(Generate-and-test）

生成测试法的基本步骤为：

1.生成一个可能的解，此解是状态空间一个点，或一条始于S0的路径。

2.用生成的“解”与目标比较。

3.达到目标则停止，否则转第一步。1）生成测试法(Generate-and-test）

此方法属于深度优先搜索(depth-first-search）,因为要产生一个完全的解后再判断，若不是目标又要生成下一个“解”。这种方法几乎接近耗尽式搜索，因而效率低。于是人们考虑能否利用反馈信息以帮助决定生成什么样的解，这种改进就是下面要讲的爬山法。2）爬山法(Hill-climbing）1生成第一个可能的解。若是目标，则停止；否则转下一步。2从当前可能的解出发，生成新的可能解集。2.1用测试函数测试新的可能解集中的元素，若是解，则停止；否则转2.2。

2.2若不是解，则将它与至今已测试过的“解”比较。若它最接近解，则保留作为最佳元素；若它不最接近解，则舍弃。

3以当前最佳元素为起点，转(２）。

爬山法在生成的元素中寻找最优解，这种最优是局部最优。爬山法会产生下述问题：

(1）找到的是局部最大值。(如左图)(2）碰到平顶时无法处理。(如右图)2）爬山法(Hill-climbing）2）爬山法(Hill-climbing）

(3）碰到山脊时无法处理。碰到山脊的克服办法是：

(1)退回较大一步，即允许回朔。

(2)向前跨一大步。

(3)多设几个初始点，从几个初始点同时或先后进行搜索。3）最佳优先搜索(Best-firstsearch)1生成第一个可能的解。若是目标，则停止；否则转下一步。

2从该可能的解出发，生成新的可能解集。

2.1用测试函数测试新的可能解集中的元素，若是解，则停止；否则转a。

2.2若不是解，则将新生成的“解”集加入到原可能“解”集中。从解集中挑选最好的元素作为起点，再转２。

爬山法与最佳