人工智能ppt课件第2章

第二章

问题求解与搜索方法

问题求解(Problem-solving)是AI领域中的一大课题,它涉及规约、推断、决策、规划、常识推理、定理证明等相关过程的核心概念,是人工智能中研究得较早而且比较成熟的一个领域。River第二章问题求解与搜索方法问题求解(Problem-so12.1问题与问题空间AI早期的目的是想通过计算技术来求解这样一些问题：它们不存在现成的求解算法或求解方法非常复杂，而人使用其自身的智能都能较好地求解。为模拟这些问题的求解过程而发展的一种技术叫搜索。2.1问题与问题空间AI早期的目的是想通过计算技术来求解22.1.1如何把问题求解定义为问题状态空间的搜索在分析和研究了人运用智能求解的方法之后，人们发现许多问题的求解方法都是通过试探在某个可能的解空间内寻找一个解来求解问题，这种基于解答空间的问题表示和求解方法就是状态空间法，它是以状态和算法为基础来表示和求解问题的。这样一来，许多涉及智力的问题求解可看成状态空间的搜索。2.1.1如何把问题求解定义为问题状态空间的搜索在分析和3状态和状态空间状态（state）是为描述某些不同事物间的差别而引入的一组最少变量q0，q1，q2…,qn的有序集合,其形式如下:

Q=[q0,q1,…,qn]

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

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

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

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

y—表示3gallon水壶中所装的水量，y=0，1，2或3；（1）定义状态空间:11（1）定义状态空间初始状态为(0,0)目标状态为(2,?)？表示水量不限，因为问题中未规定在3加仑水壶里装多少水。（1）定义状态空间12（2）确定一组操作1（X，Y|X<4）→（4，Y）4加仑水壶不满时，将其装满；2（X，Y|Y<3）→（X，3）3加仑水壶不满时，将其装满；3（X，Y|X>0）→（X-D，Y）从4加仑水壶中倒出一些水；4（X，Y|Y>0）→（X，Y-D）从3加仑水壶中倒出一些水；5（X，Y|X>0）→（0，Y）把4加仑水壶中的水全部倒出；6（X，Y|Y>0）→（X，0）把3加仑水壶中的水全部倒出；（2）确定一组操作1（X，Y|X<4）→（4，Y）13（2）确定一组操作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加仑水壶装满为止；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加仑水壶里；（2）确定一组操作7（X，Y|X+Y≥4∧Y>0）→4，14（3）选择一种搜索策略

该策略为一个简单的循环控制结构：选择其左部匹配当前状态的某条规则，并按照该规则右部的行为对此状态作适当改变，然后检查改变后的状态是否为某一目标状态，若不是，则继续该循环。（3）选择一种搜索策略15人工智能ppt课件第2章164加仑水壶中3加仑水壶中所应用的含水加仑数含水加仑数规则0

00323093324270252094加仑水壶中3加仑水壶中所应用的17例2.2分配问题有两个液源A和B。A的流量为100L/m,B的流量为50L/m。现要求它们以75L/m的流量分别供应两个同样的洗涤槽C，D。液体从液源经过最大输出能力为75L/m的管道进行分配，A、B、C、D的位置、距离如图2-2所示。并且要求只允许管子在液源或洗涤槽位置有接头。例2.2分配问题有两个液源A和B。A的流量为100L/m18例2.2分配问题问：如何连接管子使得管材最少？图2-2液源分配问题示意图例2.2分配问题问：如何连接管子使得管材最少？图2-219例2.2分配问题(1)定义状态空间中的状态表示。状态以表的形式表示为：(A=?B=?C=?D=?)初态：(A=100B=50C=0D=0)目标状态：(A=0B=0C=75D=75)例2.2分配问题(1)定义状态空间中的状态表示。20例2.2分配问题(2)定义操作。现在取从一处到另一处流量的增量，为各点流量与各处所需流量的最大公约数(greatcommondivisor)。100、50、75的GCD为25，所以取增量为25。例2.2分配问题(2)定义操作。21例2.2分配问题(2)定义操作。

①本身到本身不必传递，用×表示；②洗涤槽不必往液源送，用×表示；例2.2分配问题(2)定义操作。①本身到本身不必传22例2.2分配问题(2)定义操作。1A→B(A≥75∧B<75)→(A-25，B+25，C,D)4km2A→C(A≥25∧C<75)→(A-25，B，C+25)5km3A→D(A≥25∧D<75)→(A-25，B，C，D+25)5km4B→C(B≥25∧C<75)→(A，B-25，C+25，D)3km例2.2分配问题(2)定义操作。23例2.2分配问题(3)定义策略。

因为现在没有给出任何知识可用来指导搜索,所以可采用耗尽式搜索，即每次却将7个操作试用一遍。对于该具体问题,搜索时要注意：①若操作重复时，只算一次距离;②边搜索边求出距离最短的管长。例2.2分配问题(3)定义策略。24分配问题搜索路径:分配问题搜索路径:252.1.2问题特征分析对问题的几个关键指标或特征加以分析。一般要考虑：

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

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

问题的全域可预测吗？2.1.2问题特征分析对问题的几个关键指标或特征262.1.2问题特征分析

在未与所有其它可能解作比较之前，能说当前的解是最好的吗？

用于求解问题的知识库是相容的吗？求解问题一定需要大量的知识吗？或者说，有大量知识时候，搜索时应加以限制吗？只把问题交给电脑，电脑就能返回答案吗？或者说，为得到问题的解，需要人机交互吗？2.1.2问题特征分析在未与所有其它可能解作比较272.1.2问题特征分析1．问题是否可分解？如果问题能分解成若干子问题，则将子问题解出后，原问题的解也就求出来了。人们称这种解决问题的方法为问题的归约。2.1.2问题特征分析1．问题是否可分解？282.1.2问题特征分析

例2.3符号积分不定积分的计算规则有：∫udv→uv-∫udv

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

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

因子规则

2.1.2问题特征分析例2.3符号积分29人工智能ppt课件第2章302.1.2问题特征分析例2.4积木问题──机器人规划的抽象模型积木问题关心的是积木块的相对位置：某一积木在桌上或某一积木在另一积木上。机器人只能一次拿一块积木，每次搬动时积木上面必须是空的。

2.1.2问题特征分析例2.4积木问题──机器人规划312.1.2问题特征分析

2.1.2问题特征分析322.1.2问题特征分析例2.4积木问题积木的相对位置可用谓词表示为：初始状态：ontabel(B)∧clear(B)∧ontabel(A)∧on(C,A)∧clear(C)目标状态：ontabel(C)∧on(B,C)∧on(A,B)2.1.2问题特征分析例2.4积木问题332.1.2问题特征分析例2.4积木问题其中目标状态可分解为：子问题1:ontabel(c)

子问题2:on(B,C)

子问题3:on(A,B)2.1.2问题特征分析例2.4积木问题342.1.2问题特征分析例2.4积木问题机器人所需完成的操作：

OP1：clear(x)→ontabel(x)

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

OP2：clear(x)∧clear(y)→On(x,y)若x，y上无物体，则可将x放在y上2.1.2问题特征分析例2.4积木问题352.1.2问题特征分析

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

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

对于子问题的之间的关系,实际上有两种:一种为子问题之间是独立的,其搜索路径为:2.1.2问题特征分析对于子问题的之间的关系,392.1.2问题特征分析

另一种是子问题之间有依赖关系,其搜索路径为:2.1.2问题特征分析另一种是子问题之间有依赖关402.1.2问题特征分析2．问题求解步骤是否可撤回？在问题求解的每一步骤完成后，分析一下它的“踪迹”，可分为：（1）求解步骤可忽略，如定理证明，证明定理的每一件事情都为真或者为假，且总是保存知识库里，它是怎样推出来的对下一步并不重要，因而控制结构不需要带回溯。2.1.2问题特征分析2．问题求解步骤是否可撤回？412.1.2问题特征分析（2）可复原如走迷宫，实在走不通，可退回一步重来。这种搜索需用回溯技术,例如:需用一定的控制结构；需采用堆栈技术。2.1.2问题特征分析（2）可复原422.1.2问题特征分析（3）不可复原如下棋、决策等问题，要提前分析每走一步后会导致的结果。不可回头重来,这需要使用规划技术。在后面的第十章还要讨论这个问题。2.1.2问题特征分析（3）不可复原432.1.2问题特征分析3．问题全域可预测否？

有些问题它的全域可预测，如水壶问题、定理证明,这些问题结局肯定，可只用开环控制结构。有些问题的全域不可预测，如变化环境下机器人的控制，特别是危险环境下工作的机器人随时可能出意外，必须利用反馈信息，应使用闭环控制结构。2.1.2问题特征分析3．问题全域可预测否？442.1.2问题特征分析4．问题要求的是最优解还是较满意解？一般说来，最佳路径问题的计算较任意路径问题的计算要困难。如果使用的启发式方法不理想，那么对这个解的搜索就不可能很顺利。有些问题要求找出真正的最佳路径，可能任何启发式法都不能适用。因此，得进行耗尽式搜索，2.1.2问题特征分析4．问题要求的是最优解还是较满意解452.2盲目的搜索方法盲目搜索方法又叫非启发式搜索，是一种无信息搜索，一般只适用于求解比较简单的问题。下面我们要讨论的几个搜索方法，它们均属于盲目搜索方法。2.2盲目的搜索方法462.2盲目的搜索方法2.2.1宽度优先搜索如果搜索是以同层邻近节点依次扩展节点的,那么这种搜索就叫宽度优先搜索,这种搜索是逐层进行的,在对下一层的任一节点进行搜索之前,必须搜索完本层的所有节点。2.2盲目的搜索方法2.2.1宽度优先搜索472.2盲目的搜索方法宽度优先搜索算法如下:1.令N为一个由初始状态构成的表；2.若N为空退出，标志失败；3.令n为N中第一个点，将n从N中删除；4.若n是目标，则退出，标态成功；5.若n不是目标，将n的后继点加入到N表的尾部，转2。2.2盲目的搜索方法宽度优先搜索算法如下:482.2盲目的搜索方法宽度优先搜索的优点是：若问题有解，则可找出最优解;宽度优先搜索的缺点是：效率低，组合爆炸问题难以解决。2.2盲目的搜索方法492.2盲目的搜索方法2.2.2深度优先搜索在深度优先搜索中，我们首先扩展最新产生的（即最深的）节点。深度相等的节点可以任意排列。2.2盲目的搜索方法502.2盲目的搜索方法深度优先搜索算法如下:1.令N为一个由初始状态构成的表；2.若N为空退出，标态失败；3.令n为N中第一个点，将n从N中删除；4.若n是目标，则退出，标态成功；5.若n不是目标，将n的后继加入到N表的首部转2。2.2盲目的搜索方法深度优先搜索算法如下:512.2盲目的搜索方法深度优先搜索的优点：节省大量时间和空间；深度优先搜索的缺点：不一定能找到解。因为在无限搜索树的情况下，最坏的情况可能是不停机。2.2盲目的搜索方法522.2盲目的搜索方法2.2.3分枝有界搜索（Branch-and-Bound）分枝有界搜索也是一种深度优先搜索，但每个分支都规定了一个统一的搜索深度，搜索到这个深度后，如果没有找到目标便自动退回到上一层，继续搜索。2.2盲目的搜索方法2.2.3分枝有界搜索（Branc532.2盲目的搜索方法1.令N为一由初始状态构成的表；2.若N为空退出，标志失败；3.令n为N中第一个点，将n从N中删除；4.若n是目标，则退出，标态成功；5.若n深度=预先定好的一个界dmax，则转2；6.若n不是目标，将n的后继加入到N表的首部转2；2.2盲目的搜索方法1.令N为一由初始状态构成的表；542.3启发式搜索方法如果能够找到一种方法用于排列待扩展节点的顺序，即选择最有希望的节点加以扩展，那么，搜索效率将会大大提高。启发式搜索就是基于这种想法,它是深度优先的改进。搜索时不是任取一个分枝，而是根据一些启发式信息，选择最佳一个分枝或几个分枝往下搜索。2.3启发式搜索方法552.3.1启发式信息的表示1．启发式搜索的依据（1）人们善于利用一些线索来帮助自己选择搜索方向，这些线索统称为启发式(Heuristics)信息，Heuristics一词来源于希腊语Heuriskein，即“发现”的意思。（2）现实问题往往只需一个解，而不要求最优解或全部解。（3）启发式信息可以避免某些领域里的组合爆炸问题。2.3.1启发式信息的表示1．启发式搜索的依据562.3.1启发式信息的表示启发信息按其形式可分为下列2种：（1）表示为估计函数，确定一个启发式函数f(n),n

为被搜索的节点,它把问题状态的描述映射成问题解决的程度，通常这种程度用数值来表示，就是启发式函数的值。这个值的大小用来决定最佳搜索路径。2.3.1启发式信息的表示启发信息按其形式可分为下列2种：572.3.1启发式信息的表示（2）表示成规则，如一条启发式规则为：如果存在一个有趣的二元函数f(x,y)，那么看看两变元相同时会发生什么？若f表示乘法：导致发现平方；若f表示集合并运算：导致发现恒等函数；若f表示思考：导致发现反省；若f表示谋杀：导致发现自杀。2.3.1启发式信息的表示（2）表示成规则，如一条启发式规582.3.1启发式信息的表示2．启发式函数的表示方法启发式函数是一种映射函数，它把对问题状态的描述映射成一种希望的程度。在搜索算法的设计中，考虑问题的状态的哪些方面、怎样对所考虑的方面作出估计、怎样对某些因素加权等，都取决于启发式函数的设计，取决于该函数对节点是否在解路径上作出尽可能准确的估计。2.3.1启发式信息的表示2．启发式函数的表示方法592.3.1启发式信息的表示启发式函数设计得好，对有效引导搜索过程有着重要的作用。在有的情况下，非常简单的启发式函数搜索路径能够作出非常令人满意的估计,当然也有一些场合需要使用非常复杂的启发式函数。下面就简单讨论一下如何构造启发式函数。（1）启发式函数能够根据问题的当前状态，确定用于继续求解问题的信息。2.3.1启发式信息的表示启发式函数设计得好，对有效引导搜602.3.1启发式信息的表示

例2.6利用启发式信息去求解水壶问题，人们决不盲目搜索，而是利用水壶容量信息4，3，0，考虑如何求得2。用这几个数字可以考虑4减2或3减1得到2。但前一个方法肯定不行，因为它用到2来求得2，用后一个方法要考虑如何求得1，这很容易在当前信息中找出，因为4减3等于1。因而导致求解路径为：（0，0）→（4，0）→（1，3）→（1，0）→（4，1）→（2，3）=目标2.3.1启发式信息的表示例2.6利用启发式信息去求解612.3.1启发式信息的表示

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

6475

例2.7八数码问题。1

238

4765a11a12a13a21a22a23a31a32a33

问题空间为：S0

Sg

2.3.1启发式信息的表示283例2.7632.3.1启发式信息的表示各状态间的转换规则为：Pr1:空格上移↑If□i，jandi≠1thenai-1,j←→□i，j

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

2.3.1启发式信息的表示各状态间的转换规则为：642.3.1启发式信息的表示Pr3:空格左移←If□i，jandj≠1thenai,j-1←→□i，j

Pr4:空格右移→If□i，jandj≠3thenai,j+1←→□i，j2.3.1启发式信息的表示65f1(S5)=4启发式函数f1=数字错放位置的个数，f1=0，则达到目标。2831647528316475283147652831476523184765283164752831476528316475f1(S0)=4f1(S1)=3f1(S2)=5f1(S3)=5f1(S4)=3f1(S6)=3f1(S7)=4f1(S5)=4启发式函数f1=数字错放位置的个数，f1=662.3.1启发式信息的表示当f1值相同时如何决定走步?现在定义：F2=所有数字当前位置次最短路径走到正确位置的步数之和。在这个定义之下，各状态的启发式函数值为：数码12345678F2(S0）=1+1+0+0+0+1+0+2=5F2(S1）=1+1+0+0+0+0+0+2=42.3.1启发式信息的表示当f1值相同时如何决定走步672.3.1启发式信息的表示数码12345678

F2(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）=2+1+0+0+0+0+0+2=52.3.1启发式信息的表示数码12682.3.1启发式信息的表示

(3)启发式函数应能够估计出可能加速达到目标的程度，这可以帮助确定当扩展一个节点时，那些节点应从搜索树中删除。启发式函数对搜索树(图)的每一节点的真正优点估计得愈精确,解题过程就愈少走弯路。2.3.1启发式信息的表示(3)启发式函数应能够估计出692.3.1启发式信息的表示

例2.8八皇后问题(8-Queensproblem）。在8*8棋盘要求放下8个皇后，要求没有一个皇后能够攻击其它皇后，即要使得在任何一行、一列或对角线上都不存在两个或两个以上的皇后。2.3.1启发式信息的表示例2.8八皇后问题(8-Q702.3.1启发式信息的表示求解这个问题的过程为：（a）定义状态空间。设状态空间的一点为：8*8矩阵。（b）定义操作规则。为简单起见，可按如下规则放置皇后：2.3.1启发式信息的表示求解这个问题的过程为：712.3.1启发式信息的表示第一个皇后放第一行。第二个皇后放在第二行且不与第一个皇后在同一列或对角线的空格上。……第i个皇后放在第i行且不与前面i–1个皇后在同一列或对角线的空格上。……2.3.1启发式信息的表示第一个皇后放第一行。722.3.1启发式信息的表示可使用如下启发式函数：设x为当前要放置Queen的空格f（x）=剩下未放行中能够用来放Queen的空格数不难看出，f（x）愈大愈好，应选择f（x）最大的空格来放置皇后。例如，在放置了三个Q后，第4个Q可放在第4行的A，B，C三个位置。2.3.1启发式信息的表示可使用如下启发式函数：732.3.1启发式信息的表示a为第4行A处放了皇后剩下可放Q的位置；

b为第4行B处放了皇后剩下可放Q的位置；c为第4行C处放了皇后剩下可放Q的位置。按照以上定义，可求得：f（A）=8，f（B）=9，f（C）=10。所以搜索可以从C对应的空格放置一个皇后开始，其余的空格对应的搜索树可以删除。2.3.1启发式信息的表示a为第4行A处放了皇后剩下可放Q742.3.1启发式信息的表示

Q

Q

Q