第一部分用搜索方法求解问题

第一部分用搜索方法求解问题演示文稿第1页，共69页。优选第一部分用搜索方法求解问题第2页，共69页。1.1问题与问题空间AI早期的目的是想通过计算技术来求解这样一些问题：它们不存在现成的求解算法或求解方法非常复杂，而人使用其自身的智能都能较好地求解。为模拟这些问题的求解过程而发展的一种技术叫搜索。第3页，共69页。1.1.1把问题求解定义为状态空间的搜索在分析和研究了人运用智能求解的方法之后，人们发现许多问题的求解方法都是通过试探在某个可能的解空间内寻找一个解来求解问题，这种基于解答空间的问题表示和求解方法就是状态空间法。许多涉及智力的问题求解可看成状态空间的搜索。第4页，共69页。状态和状态空间状态（state）是为描述某些不同事物间的差别而引入的一组最少变量q0，q1，q2…,qn的有序集合,并表示为:

Q=（q0,q1,…,qn）其中，每个元素qⅰ称为状态变量。给定每个分量的一组值，就得到一个具体的状态。第5页，共69页。状态和状态空间使问题从一种状态变化为另一种状态的手段称为操作符或算子（operator）。操作符可能是走步（下棋）、过程、规则、数学算子、运算符号或逻辑运算符等。问题的状态空间（statespace）是一个表示该问题全部可能状态及其关系的集合。第6页，共69页。状态和状态空间它包含三种类型的集合，即该问题所有可能的初始状态集合S，操作符集合F目标状态集合G。因此，可把状态空间记为三元组（S，F，G）。第7页，共69页。问题状态空间法的基本思想是：

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

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

(3)决定一种搜索策略，使得能够从初始状态出发，沿某个路径达到目标状态。第10页，共69页。水壶问题给定两个水壶，一个可装4加仑水，一个能装3加仑水。水壶上没有任何度量标记。有一水泵可用来往壶中装水。问：怎样在能装4加仑的水壶里恰好只装2加仑水？第11页，共69页。（1）定义状态空间可将问题进行抽象，用数偶(x,y)表示状态空间的任一状态。

x—表示4gallon水壶中所装的水量，x=0，1，2，3或4；

y—表示3gallon水壶中所装的水量，y=0，1，2或3；第12页，共69页。初始状态为(0,0)目标状态为(2,?)？表示水量不限，因为问题中未规定在3加仑水壶里装多少水。第13页，共69页。（2）确定一组操作1（X，Y|X<4）→（4，Y）4加仑水壶不满时，将其装满；2（X，Y|Y<3）→（X，3）3加仑水壶不满时，将其装满；5（X，Y|X>0）→（0，Y）把4加仑水壶中的水全部倒出；第14页，共69页。6（X，Y|Y>0）→（X，0）把3加仑水壶中的水全部倒出；7（X，Y|X+Y≥4∧Y>0）→（4，Y-（4-X））把3加仑水壶中的水往4加仑水壶里倒，直至4加仑水壶装满为止8（X，Y|X+Y≥3∧X>0）→（X-（3-Y），3）把4加仑水壶中的水往3加仑水壶里倒，直至3加仑水壶装满为止；第15页，共69页。9（X，Y|X+Y≤4∧Y>0）→（X+Y，0）把3加仑水壶中的水全部倒进4加仑水壶里；10（X，Y|X+Y≤3∧X>0）→（0，X+Y）把4加仑水壶中的水全部倒进3加仑水壶里；第16页，共69页。（3）选择一种搜索策略

该策略为一个简单的循环控制结构：选择其左部匹配当前状态的某条规则，并按照该规则右部的行为对此状态作适当改变，然后检查改变后的状态是否为某一目标状态，若不是，则继续该循环。第17页，共69页。第18页，共69页。4加仑水壶中3加仑水壶中所应用的含水加仑数含水加仑数规则

0

0032309332427025209第19页，共69页。

1.1.2问题特征分析对问题的几个关键指标或特征加以分析。一般要考虑：

问题可分解成为一组独立的、更小、更容易解决的子问题吗？

当结果表明解题步骤不合适的时侯，能忽略或撤回吗？

问题的全域可预测吗？第20页，共69页。

1.1.2问题特征分析在未与所有其它可能解作比较之前，能说当前的解是最好的吗？

用于求解问题的知识库是相容的吗？求解问题一定需要大量的知识吗？或者说，有大量知识时候，搜索时应加以限制吗？只把问题交给电脑，电脑就能返回答案吗？或者说，为得到问题的解，需要人机交互吗？第21页，共69页。

1.1.2问题特征分析1．问题是否可分解？如果问题能分解成若干子问题，则将子问题解出后，原问题的解也就求出来了。人们称这种解决问题的方法为问题的归约。第22页，共69页。

1.1.2问题特征分析例1.3符号积分不定积分的计算规则有：∫udv→uv-∫udv

分部积分产生式规则∫f(x)+g(x)dx→∫f(x)dx+∫g(x)dx

和式分解规则∫kf(x)dx→k∫f(x)dx因子规则

第23页，共69页。1.1.2问题特征分析例1.4积木问题──机器人规划的抽象模型积木问题关心的是积木块的相对位置：某一积木在桌上或某一积木在另一积木上。机器人只能一次拿一块积木，每次搬动时积木上面必须是空的。

第24页，共69页。

1.1.2问题特征分析

第25页，共69页。

1.1.2问题特征分析例1.4积木问题积木的相对位置可用谓词表示为：初始状态：ontabel(B)∧clear(B)∧ontabel(A)∧on(C,A)∧clear(C)目标状态：ontabel(C)∧on(B,C)∧on(A,B)第26页，共69页。

1.1.2问题特征分析其中目标状态可分解为：子问题1:ontabel(c)

子问题2:on(B,C)

子问题3:on(A,B)第27页，共69页。

1.1.2问题特征分析例1.4积木问题机器人所需完成的操作：

OP1：clear(x)→ontabel(x)

无论x在何处，若x上无物体，则可将x放于桌上

OP2：clear(x)∧clear(y)→On(x,y)若x，y上无物体，则可将x放在y上第28页，共69页。

1.1.2问题特征分析

这个问题的求解方法有两种：一种方法是采用全面搜索的方法；一种是用分解子问题的方法。从目标来看，总问题可分解成三个子问题，但这三个子问题不能按任意次序求解。第29页，共69页。

第30页，共69页。

1.1.2问题特征分析但若从初态出发,将on(A,B)作为子问题1首先求解，这样会使搜索离目标越来越远。第31页，共69页。

1.1.2问题特征分析对于子问题的之间的关系,实际上有两种:一种为子问题之间是独立的,其搜索路径为:第32页，共69页。

1.1.2问题特征分析

另一种是子问题之间有依赖关系,其搜索路径为:第33页，共69页。1.1.2问题特征分析2．问题求解步骤是否可撤回？在问题求解的每一步骤完成后，分析一下它的“踪迹”，可分为3类：（1）求解步骤可忽略如定理证明，证明定理的每一件事情都为真或者为假，且总是保存知识库里，它是怎样推出来的对下一步并不重要，因而控制结构不需要带回溯。第34页，共69页。1.1.2问题特征分析（2）可复原

如走迷宫，实在走不通，可退回一步重来。这种搜索需用回溯技术,例如:需用一定的控制结构；需采用堆栈技术。第35页，共69页。1.1.2问题特征分析（3）不可复原如下棋、决策等问题，要提前分析每走一步后会导致的结果。不可回头重来,这需要使用规划技术。第36页，共69页。1.1.2问题特征分析3．问题全域可预测否？

有些问题它的全域可预测，如水壶问题、定理证明,这些问题结局肯定，可只用开环控制结构。有些问题的全域不可预测，如变化环境下机器人的控制，特别是危险环境下工作的机器人随时可能出意外，必须利用反馈信息，应使用闭环控制结构。第37页，共69页。1.1.2问题特征分析4．问题要求的是最优解还是较满意解？一般说来，最佳路径问题的计算较任意路径问题的计算要困难。如果使用的启发式方法不理想，那么对这个解的搜索就不可能很顺利。有些问题要求找出真正的最佳路径，可能任何启发式法都不能适用。因此，得进行耗尽式搜索，第38页，共69页。1.2盲目的搜索方法盲目搜索方法又叫非启发式搜索，是一种无信息搜索，一般只适用于求解比较简单的问题。下面我们要讨论的几个搜索方法，它们均属于盲目搜索方法。第39页，共69页。1.2.1宽度优先搜索如果搜索是以同层邻近节点依次扩展节点的,那么这种搜索就叫宽度优先搜索,这种搜索是逐层进行的,在对下一层的任一节点进行搜索之前,必须搜索完本层的所有节点。第40页，共69页。宽度优先搜索算法如下:1.令N为一个由初始状态构成的表；

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

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

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

5.若n不是目标，将n的后继点加入到N表的尾部，转2。第41页，共69页。宽度优先搜索的优点是：若问题有解，则可找出最优解;宽度优先搜索的缺点是:效率低，组合爆炸问题难以解决。第42页，共69页。1.2.2深度优先搜索在深度优先搜索中，首先扩展最新产生的（即最深的）节点。深度相等的节点可以任意排列。第43页，共69页。1.2.2深度优先搜索深度优先搜索算法如下:1.令N为一个由初始状态构成的表；2.若N为空退出，标态失败；3.令n为N中第一个点，将n从N中删除；4.若n是目标，则退出，标态成功；5.若n不是目标，将n的后继加入到N表的首部转2。第44页，共69页。1.2.2深度优先搜索深度优先搜索的优点：节省大量时间和空间；深度优先搜索的缺点：不一定能找到解。因为在无限搜索树的情况下，最坏的情况可能是不停机。第45页，共69页。1.2.3分枝有界搜索

（Branch-and-Bound）分枝有界搜索也是一种深度优先搜索，但每个分支都规定了一个统一的搜索深度，搜索到这个深度后，如果没有找到目标便自动退回到上一层，继续搜索。第46页，共69页。1.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；第47页，共69页。1.3启发式搜索方法如果能够找到一种方法用于排列待扩展节点的顺序，即选择最有希望的节点加以扩展，那么，搜索效率将会大大提高。启发式搜索就是基于这种想法,它是深度优先的改进。搜索时不是任取一个分枝，而是根据一些启发式信息，选择最佳一个分枝或几个分枝往下搜索。第48页，共69页。1.3.1启发式信息的表示1．启发式搜索的依据（1）人们善于利用一些线索来帮助自己选择搜索方向，这些线索统称为启发式(Heuristics)信息。（2）现实问题往往只需一个解，而不要求最优解或全部解。（3）启发式信息可以避免某些领域里的组合爆炸问题。第49页，共69页。1.3.1启发式信息的表示启发信息按其形式可分为下列2种：（1）表示为估计函数确定一个启发式函数f(n),n

为被搜索的节点,它把问题状态的描述映射成问题解决的程度，通常这种程度用数值来表示，就是启发式函数的值。这个值的大小用来决定最佳搜索路径。第50页，共69页。1.3.1启发式信息的表示（2）表示成规则如AM的一条启发式规则为：如果存在一个有趣的二元函数f(x,y)，那么看看两变元相同时会发生什么？若f表示乘法：导致发现平方；若f表示集合并运算：导致发现恒等函数；若f表示思考：导致发现反省；若f表示谋杀：导致发现自杀。第51页，共69页。1.3.1启发式信息的表示2．启发式函数的表示方法启发式函数是一种映射函数，它把对问题状态的描述映射成一种希望的程度。启发式函数设计得好，对有效引导搜索过程有着重要的作用。在有的情况下，非常简单的启发式函数搜索路径能够作出非常令人满意的估计,当然也有一些场合需要使用非常复杂的启发式函数。第52页，共69页。1.3.1启发式信息的表示如何构造启发式函数？（1）启发式函数能够根据问题的当前状态，确定用于继续求解问题的信息。第53页，共69页。1.3.1启发式信息的表示利用启发式信息去求解水壶问题，人们决不盲目搜索，而是利用水壶容量信息4，3，0，考虑如何求得2。用这几个数字可以考虑4减2或3减1得到2。这很容易在当前信息中找出，因为4减3等于1。因而导致求解路径为：（0，0）→（4，0）→（1，3）→（1，0）→（4，1）→（2，3）=目标第54页，共69页。1.3.1启发式信息的表示

(2)启发式函数能够估计已找到的状态与达到目标的有利程度。这样的启发式函数能够有效地帮助决定那些后继节点应被产生。第55页，共69页。1.3.1启发式信息的表示

283

1

6475

例1.7八数码问题。

1

238

4765

a11a12a13a21a22a23a31a32a33

问题空间为：S0

Sg

第56页，共69页。1.3.1启发式信息的表示各状态间的转换规则为：Pr1:空格上移↑If□i，jandi≠1thenai-1,j←→□i，j

Pr2:空格下移↓If□i，jandi≠3thenaI+1,j←→□i，j

第57页，共69页。1.3.1启发式信息的表示Pr3:空格左移←If□i，jandj≠1thenai,j-1←→□i，j

Pr4:空格右移→If□i，jandj≠3thenai,j+1←→□i，j第58页，共69页。启发式函数f1=数字错放位置的个数，f1=0，则达到目标。2831647528316475283147652831476523184765283164752831476528316475第59页，共69页。1.3.1启发式信息的表示当f1值相同时如何决定走步?

现在定义：f2=所有数字当前位置以最短路径走到正确位置的步数之和。在这个定义之下，各状态的启发式函数值为：

数码12345678F2(S0）=1+1+0+0+0+1+0+2=5F2(S1）=1+1+0+0+0+0+0+2=4第60页，共69页。1.3.1启发式信息的表示数码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=5第61页，共69页。1.3.1启发式信息的表示

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

这可以帮助确定当扩展一个节点时，那些节点应从搜索树中删除。启发式函数对搜索树(图)的每一节点的真正优点估计得愈精确,解题过程就愈少走弯路。第62页，共69页。1