1、第2章 用搜索实现求解问题2.1 搜索求解问题的基本思路搜索求解问题的基本思路lAI早期的目的是想通过计算技术来求解这样一些问题：它们不存在现成的求解算法或求解方法非常复杂，而人使用其自身的智能都能较好地求解。为模拟这些问题的求解过程而发展的一种技术叫搜索。l搜索的过程可理解为根据初始条件和约束条件及关联关系构造一个解答空间，并在这个空间中寻找符合目标状态的过程。2.2实现搜索过程的三大要素实现搜索过程的三大要素l搜索过程的三大要素：搜搜索索对对象象、搜索的扩扩展展规规则则和搜索的目标测试目标测试。l搜搜索索对对象象是指在什么样的对象（即状态，这些状态就是可能解的表示）之上进行搜索；搜索的扩扩
2、展展规规则则是指如何控制从一种状态变化为另一种状态，使得搜索得以前进；搜索的目目标标测测试试是指搜索在什么条件下到达问题求解的要求。搜索终止时，搜索成功表示问题有解，否则表示问题无解。2.2.1 搜索搜索对象对象l 利用搜索来求解问题是在某个可能的解空间内寻找一个解，这就首先要有一种恰当的解空间的表示方法。一般把这种可能的解都表示为一个状态。这个过程必须做到把所有和解决问题相关的信息（特征）全部抽象出来，存储这些特征的数据结构被叫做状状态态，它表示问题的一个可可能能解解，这个数据结构下形成的各种有意义的状态，称为状态空间状态空间。l状态（state）是为描述某些不同事物间的差别而引入的一组最少
3、变量q0，q1，q2,qn的有序集合,并表示为:Q=（q0,q1,qn）其中，每个元素q称为状态变量。给定每个分量的一组值，就得到一个具体的状态。2.2.2 扩展规则l扩扩展展规规则则由两部分组成：状态转转移移算算子子和状态扩扩展展策略策略。l状态转移算子状态转移算子使问题从一种状态变化为另一种状态的手段称为操作符或转移算子（operator）。操作符可以是一个动作（如下棋走步）、过程、规则、数学算子、运算符号或逻辑运算符等。2.2.2 扩展规则状态扩展策略状态扩展策略 l宏观地看，以怎样的次序对问题对应的搜索图进行搜索，是搜索的技巧，也是智能的体现。没有目的随机的选一个扩展的话很容易实现，但
4、一般很难得到一个解或不能保证解的质量，即得不到一个满意解。而好的策略可以比一般的方法搜索更少的节点，更快地找到解。也就是说，根据问题的不同设计更合理的扩展策略可以提高搜索的效率。2.2.3目标测试 目标目标测试测试是在搜索过程中，对可能的解是否达到满意解的判断。它包含两种情况：l一种是，解是否满足所有限制条件（宽条件，成立的前提）；l另一种是，解是否就是既定的目标（紧条件，目标状态已知）。l宽条件宽条件一般是指在目标状态未知，而求解只需要接近目标状态就行了的情况下设定的条件，比如说下棋，把对方将死的方式有很多种，满足一条就够了。l紧条件紧条件是在目标状态已知的条件下，直接判定是否已经达到这些状
5、态，比如说，玩魔方，成功的条件是六个面都是同色。2.3 实现搜索的基本步骤实现搜索的基本步骤l一般在搜索时要定义状态空间Q，它包含三种类型的集合：l l初始状态集合S，l l操作符集合F（把每个完成的动作表达出来）l l目标状态集合G。l因此，可把状态空间记为三元组（S，F，G）。问题状态空间法的基本思想是：l（1）将问题中的已知条件看成状态空间中初始状态；将问题中要求的目标看成状态空间中目标状态；将问题中其他可能的情况看成状态空间的任一状态。l（2）设法在状态空间中寻找一条路径，由初始状态出发，能够沿着这条路径达到目标状态。问题状态空间法的基本步骤：（1）根据问题，定义出相应的状态空间，确定
6、出状态的一般表示，它含有相关对象的各种可能的排列。这里仅仅是定义这个空间的状态，而不必枚举该状态空间的所有状态，但由此可以得出问题的初始状态、目标状态，并能够表示出所有其他状态。问题状态空间法的基本步骤：(2)规定一组操作(算子),能够使状态从一个状态变为另一个状态。(3)决定一种搜索策略，使得能够从初始状态出发，沿某个路径达到目标状态。水壶精确度量水量问题l播放电影视频给定两个水壶，一个可装5加仑水，一个能装3加仑水。水壶上没有任何度量标记。有一水龙头可用来往壶中灌水。问题是怎样在能装5加仑的水壶里，恰好只装4加仑水 l？（1）定义状态空间l该问题只关心水壶所装水的多少，可将问题进行抽象，用
7、数偶(x,y)来表示状态空间的任一状态。l x表示5加仑水壶中所装的水量，x=0到5；l y表示3加仑水壶中所装的水量，y=0到3；初始状态为(0,0)，目标状态为(4,?)，？表示水量不限，因为问题中未规定在3加仑水壶里装多少水。l初始状态为 (0,0)l目标状态为 (2,?)l？表示水量不限，因为问题中未规定在3加仑水壶里装多少水。（2）确定一组操作）确定一组操作l用来求解该问题的算子可用如下10条规则来描述。lr1:（X，Y|X5）（5，Y）5加仑水壶不满时，将其装满；lr2:（X，Y|Y0）（X-D，Y）从5加仑水壶里倒出一些水；lr4:（X，Y|Y0）（X，Y-D）从3加仑水壶里倒出
8、一些水；lr5:（X，Y|X0）（0，Y）把5加仑水壶中的水全部倒出；r6:（X，Y|Y0）（X，0）把3加仑水壶中的水全部倒出；r7:（X，Y|X+Y5Y0（5，Y-（5-X）把3加仑水壶中的水往5加仑水壶里倒，直至5加仑水壶装满为止；r8:（X，Y|X+Y3X0）（X-（3-Y），3）把5加仑水壶中的水往3加仑水壶里倒，直至3加仑水壶装满为止；r9:（X，Y|X+Y5Y0）（X+Y，0）把3加仑水壶中的水全部倒进5加仑水壶里；r10:（X，Y|X+Y3X0）（0，X+Y）把5加仑水壶中的水全部倒进3加仑水壶里 l这些算子就是模拟倒水的动作，也就是求解问题的过程。算子中的“”表示“如果则”；
9、“”表示并且。比如说，第8个算子r8表示的意思是：l如果两个水壶当前的水量为（x，y），两个水壶的水量加起来（即x+y）可以把3加仑水壶灌满（3）并且5加仑水壶里有水（X0），则把3加仑水壶加满（y=3），而5加仑水壶的水量变为X-（3-Y），即已经导入3加仑水壶3-y的水量了，要从5加仑水壶里减去。（3）选择一种搜索策略）选择一种搜索策略为求解水壶问题，除上面给出的问题描述和算子外，还应该选择一种策略控制搜索。该问题的策略为一个简单的循环控制结构：选择其左部匹配当前状态的某条规则，并按照该规则右部的描述，对此状态作适当改变，然后检查改变后的状态是否为某一目标状态，若不是，则继续该循环。该循环
10、结构如图2.3所示。l这样搜索下去，直到出现(4,?)状态为止，从(0,0)到(4,?)的路径上所用的操作序列就为所求的解。图2.4是求解问题的搜索图。l图2.4中有多个算子序列可以求解水壶问题，也就是有多条路径到达目标，下面就是求解问题的搜索路径之一：l5加仑水壶中含水量 3加仑水壶中含水量 所应用的规则l0 0 初始状态l5 0 r1l2 3 r3 l2 0 r6l0 2 r10 l5 2 r1 l4 3 r8 （动画实现）2.4 搜索的几种基本策略搜索的几种基本策略搜索的基本策略根据扩展的利用问题的特征信息的方搜索的基本策略根据扩展的利用问题的特征信息的方式可分为式可分为盲目搜索盲目搜索
11、、启发式搜索启发式搜索方法方法。盲目搜索方法盲目搜索方法又叫非启发式搜索，是一种无信息搜索又叫非启发式搜索，是一种无信息搜索（Uninformed Search），一般只适用于求解比较简），一般只适用于求解比较简单的问题。单的问题。启发式搜索启发式搜索就是要利用问题的特征信息（或一些线索）就是要利用问题的特征信息（或一些线索）来帮助（启发）自己选择搜索方向来帮助（启发）自己选择搜索方向。2.4.1 盲目的搜索方法盲目的搜索方法l当当我们在慌乱之中寻找东西的时候，毫无目标到处乱翻我们在慌乱之中寻找东西的时候，毫无目标到处乱翻，就是就是随机查找。随机查找。l当我们清醒时有条理地寻找东西的方法又大致
12、可以分成两当我们清醒时有条理地寻找东西的方法又大致可以分成两类：类：一种是找眼镜模式。它指的是眼镜掉了的时候总是从最近一种是找眼镜模式。它指的是眼镜掉了的时候总是从最近的地方开始寻找慢慢的扩大搜索范围的搜索方法。的地方开始寻找慢慢的扩大搜索范围的搜索方法。一种是走迷宫的方式。它指的是在走迷宫的时候由于无法一种是走迷宫的方式。它指的是在走迷宫的时候由于无法获得其他信息，只有一条路走到底，碰壁后再回溯寻找其获得其他信息，只有一条路走到底，碰壁后再回溯寻找其他途径的这种走法。他途径的这种走法。这三种方法分别对应的就是随机搜索、广度优先搜索和深度这三种方法分别对应的就是随机搜索、广度优先搜索和深度优先
13、搜索。优先搜索。1.宽度优先搜索宽度优先搜索l现在讨论的盲目的搜索算法中存放节点都采用一种简单的数据结构表，表是将节点按一定的顺序用逗号隔开放在一对括号中的一种数据结构，在表的首部和尾部的都可以加入和删除节点。l如果搜索是以同层邻近节点依次扩展节点的,那么这种搜索就叫宽度优先搜索,这种搜索是逐层进行的,在对下一层的任一节点进行搜索之前,必须搜索完本层的所有节点。宽度优先搜索宽度优先搜索算法如下:1.令N为一个由初始状态构成的表；2.若N为空退出，标志失败；3.令n为N中第一个点，将n从N中删除；4.若n是目标，则退出，标态成功；5.若n不是目标，将n的后继点加入到N表的尾部，转2。l宽度优先搜
14、索的优点是：若问题有解，则可找出最优解;l宽度优先搜索的缺点是:效率低，组合爆炸问题难以解决。2.深度优先搜索深度优先搜索在深度优先搜索中，我们首先扩展最新产生的（即最深的）节点。深度相等的节点可以任意排列。2.深度优先搜索深度优先搜索深度优先搜索算法如下:1.令N为一个由初始状态构成的表；2.若N为空退出，标态失败；3.令n为N中第一个点，将n从N中删除；4.若n是目标，则退出，标态成功；5.若n不是目标，将n的后继加入到N表的首部转2。2.深度优先搜索深度优先搜索l 深度优先搜索的优点：节省大量时间和空间；l 深度优先搜索的缺点：不一定能找到解。因为在无限搜索树的情况下，最坏的情况可能是不
15、停机。3.分枝有界搜索分枝有界搜索（Branch-and-Bound）l 分枝有界搜索也是一种深度优先搜索，但每个分支都规定了一个统一的搜索深度，搜索到这个深度后，如果没有找到目标便自动退回到上一层，继续搜索。1.令N为一由初始状态构成的表；2.若N为空退出，标志失败；3.令n为N中第一个点，将n从N中删除；4.若n是目标，则退出，标态成功；5.若n深度=预先定好的一个界dmax，则转2；6.若n不是目标，将n的后继加入到N表的首部转2；2.4.2 启发式搜索启发式搜索l盲目搜索的效率低，耗费过多的搜索时间。如果能够找到一种方法用于排列待扩展节点的顺序，即选择最有希望的节点加以扩展，那么，搜索
16、效率将会大大提高。启发式搜索就是基于这种想法,它是深度优先的改进。搜索时不是任取一个分枝，而是根据一些启发式信息，选择最佳一个分枝或几个分枝往下搜索。1.启发式信息的表示启发式信息的表示1）启发式搜索的依据）启发式搜索的依据（1）人们善于利用一些线索来帮助自己选择搜 索 方 向，这 些 线 索 统 称 为 启 发 式(Heuristics)信息。（2）现实问题往往只需一个解，而不要求最优解或全部解。（3）启发式信息可以避免某些领域里的组合爆炸问题。1.启发式信息的表示启发式信息的表示2）启发式信息表示）启发式信息表示启发信息按其形式可分为下列2种：（1）表示为估计函数）表示为估计函数l 确定一
17、个启发式函数f(n),n 为被搜索的节点,它把问题状态的描述映射成问题解决的程度，通常这种程度用数值来表示，就是启发式函数的值。这个值的大小用来决定最佳搜索路径。1.启发式信息的表示启发式信息的表示（2）表示成规则）表示成规则把启发式信息表示为一条规则，如果当前状态匹配这条规则的前件，则采用该规则，以规则的后件作为当前状态。如AM的一条启发式规则为：如果存在一个有趣的二元函数f(x,y)，那么看看两变元相同时会发生什么？l若f表示乘法：导致发现平方；l若f表示集合并运算：导致发现恒等函数；l若f表示思考：导致发现反省；l若f表示谋杀：导致发现自杀。1.启发式信息的表示启发式信息的表示l启发式函
18、数是一种映射函数，它把对问题状态的描述映射成一种希望的程度。l启发式函数设计得好，对有效引导搜索过程有着重要的作用。非常简单的启发式函数搜索路径能够作出非常令人满意的估计。1.启发式信息的表示启发式信息的表示l如何构造启发式函数？（1）启发式函数能够根据问题的当前状态，确定用于继续求解问题的信息。这样的启发式函数能够有效地帮助决定那些后继节点应被产生。1.启发式信息的表示启发式信息的表示28316475例2.7八数码问题。12384765a11a12a13a21a22a23a31a32a33问题空间为：S0Sg1.启发式信息的表示启发式信息的表示各状态间的转换规则为：Pr1:空格上移 If i
19、，j and i1 then ai-1,j i，j Pr2:空格下移 If i，j and i3 then aI+1,j i，j 1.启发式信息的表示启发式信息的表示Pr3:空格左移 If i，j and j1 then ai,j-1 i，j Pr4:空格右移 If i，j and j3 then ai,j+1 i，j 启发式函数f1=数字错放位置的个数，f1=0，则达到目标。28316475283164752831476528314765231847652831647528314765283164751.启发式信息的表示启发式信息的表示 当f1值相同时如何决定走步?现在定义：f2=所有数字当
20、前位置以最短路径走到正确位置的步数之和。在这个定义之下，各状态的启发式函数值为：数码 1 2 3 4 5 6 7 8 F2(S0）=1+1+0+0+0+1+0+2=5 F2(S1）=1+1+0+0+0+0+0+2=41.启发式信息的表示启发式信息的表示数码 1 2 3 4 5 6 7 8 F2(S2）=1+1+0+0+0+1+1+2=6 F2(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=5 F2(S6）=1+2+0+0+0+0+0+2=51.启发式信息的表示启发式信息的表示(2)启发式函数应能够估计出可
21、能加速达到目标的程度 这可以帮助确定当扩展一个节点时，那些节点应从搜索树中删除。启发式函数对搜索树(图)的每一节点的真正优点估计得愈精确,解题过程就愈少走弯路。1.启发式信息的表示启发式信息的表示l例 2.8 八 皇 后 问 题(8-Queens problem）在8*8棋盘要求放下8个皇后，要求没有一个皇后能够攻击其他皇后，即要使得在任何一行、一列或对角线上都不存在两个或两个以上的皇后。1.启发式信息的表示启发式信息的表示求解这个问题的过程为：（a）定义状态空间。设状态空间的一点为：8*8矩阵。（b）定义操作规则。按如下规则放置皇后：1.启发式信息的表示启发式信息的表示 第一个皇后放第一行。
22、第二个皇后放在第二行且不与第一个皇后在同一列或对角线的空格上。第i个皇后放在第i行且不与前面i 1个皇后在同一列或对角线的空格上。1.启发式信息的表示启发式信息的表示可使用如下启发式函数：l设x为当前要放置Queen的空格lf（x）=剩下未放行中能够用来放Queen的空格数l不难看出，f（x）愈大愈好，应选择f（x）最大的空格来放置皇后。例如，在放置了三个Q后，第4个Q可放在第4行的A，B，C三个位置。QQQABCabcbcabbccacabcbacbacacabbc1.启发式信息的表示启发式信息的表示a为第4行A处放了皇后剩下可放Q的位置；b为第4行B处放了皇后剩下可放Q的位置；c为第4行C
23、处放了皇后剩下可放Q的位置。按照以上定义，可求得：f（A）=8，f（B）=9，f（C）=10。所以搜索可以从C对应的空格放置一个皇后开始，其余的空格对应的搜索树可以删除。1.启发式信息的表示启发式信息的表示（c）定义搜索策略第i个皇后放到第i行中的那个与前面i-l个皇后不在同一列或对角线上且f（x）值最大的空格中。启发式信息是某些领域里的知识信息，它能使计算机系统在这些知识信息提示以后可能采取的某些可能的动作或避免某些不可能的动作。作者 朱福喜 朱三元2.几种经典的搜索策略几种经典的搜索策略 l下面主要介绍采用Best-first策略的几个基本方法，这些方法构成了许多数AI系统的构架，其效率取
24、决于问题所在领域知识的利用与开发。由于这些方法的通用性，并且难于克服搜索过程的组合爆炸问题，所以又称为弱法(Weak method）。2.几种经典的搜索策略几种经典的搜索策略 l 弱法主要包括：最佳优先法 生成测试法爬山法广度优先法问题归约法约束满足法手段目的分析法。1）生成测试法）生成测试法(Generate-and-test）生成测试法的基本步骤为：1.生成一个可能的解，此解是状态空间一个点，或一条始于S0的路径。2.用生成的“解”与目标比较。3.达到目标则停止，否则转第一步。1）生成测试法）生成测试法(Generate-and-test）l 此方法属于深度优先搜索(depth-first
25、-search）,因为要产生一个完全的解后再判断，若不是目标又要生成下一个“解”。这种方法几乎接近耗尽式搜索，因而效率低。于是人们考虑能否利用反馈信息以帮助决定生成什么样的解，这种改进就是下面要讲的爬山法。2）爬山法）爬山法(Hill-climbing）1 生成第一个可能的解。若是目标，则停止；否则转下一步。2 从当前可能的解出发，生成新的可能解集。2.1 2.1 用用测测试试函函数数测测试试新新的的可可能能解解集集中中的的元元素素，若若是是解，则停止；否则转解，则停止；否则转2.22.2。2.22.2若若不不是是解解，则则将将它它与与至至今今已已测测试试过过的的“解解”比比较较。若若它它最最
26、接接近近解解，则则保保留留作作为为最最佳佳元元素素；若它不最接近解，则舍弃。若它不最接近解，则舍弃。3 以当前最佳元素为起点，转(）。爬山法在生成的元素中寻找最优解，这种最优是局部最优。爬山法会产生下述问题：(1）找到的是局部最大值。(如左图)(2）碰到平顶时无法处理。(如右图)2）爬山法）爬山法(Hill-climbing）2）爬山法）爬山法(Hill-climbing）(3）碰到山脊时无法处理。碰到山脊的克服办法是：(1)退回较大一步，即允许回朔。(2)向前跨一大步。(3)多设几个初始点，从几个初始点同时或先后进行搜索。3）最佳优先搜索）最佳优先搜索(Best-first search)1
27、 生成第一个可能的解。若是目标，则停止；否则转下一步。2 从该可能的解出发，生成新的可能解集。2.1 2.1 用用测测试试函函数数测测试试新新的的可可能能解解集集中中的的元元素素，若是解，则停止；否则转若是解，则停止；否则转a a。2.2 2.2 若若不不是是解解，则则将将新新生生成成的的“解解”集集加加入入到原可能到原可能“解解”集中。集中。3从解集中挑选最好的元素作为起点，再转。爬山法与最佳优先的比较4）模拟退火法模拟退火法(simulated Annealing)退火是冶金专家为了达到某些特种晶体结构重复将金属加热或冷却的过程,该过程的控制参数为温度T。这种思想应用于许多优化问题就产生了
28、模拟退火算法,模拟退火法的基本思想是,在系统朝着能量减小的趋势这样一个变化过程中,偶尔允许系统跳到能量较高的状态，以避开局部极小点,最终稳定到全局最小点。作者 朱福喜 朱三元4）模拟退火法模拟退火法(simulated Annealing)l如图所示，若使能量在C点突然增加h，就能跳过局部极小点B,而找到全局最小点A。l现在的问题是何时增加能量？应该增加多少能量？为此，柯克帕特里克(S.Kirkpatrick）提出了模拟退火算法。BAC4）模拟退火法模拟退火法(simulated Annealing)模拟退火算法：1随机挑选一单元k，并给它一个随机的位移，求出系统因此而产生的能量变化EK；2若
29、EK0，该位移可采纳，而变化后的系统状态可作为下次变化的起点；若EK 0，位移后的状态可采纳的概率为:PK=1/(1+e-EK/T)4）模拟退火法模拟退火法(simulated Annealing)式中T为温度,然后从(0，1）区间均匀分布的随机数中挑选一个数R。若RPK，则将变化后的状态作为下次的起点，否则,将变化前的状态作为下次的起点。3.转1继续执行，直至达到平衡状态为止。4)模拟退火法模拟退火法(simulated Annealing)l对于搜索问题中的爬山法,利用模拟退火算法,可以不但变化的随机选择一些大的步长,以跨过局部极小点.通常的作法是:最初阶段倾向于取大步；后阶段倾向于取小步。4)模拟退火法模拟退火法(simulated Annealing)如果希望小球离开A点然后停在B点,使用能量减小的的方法来摇动系统,这小球只能停在A点。若开始以较大的速度摇动,后来慢慢地减轻,则小球很可能就会落在B点,且小球到B点之后,就不易再从B点摇到A点。A B
