1、第二章 问题求解与搜索方法 问题求解(Problem-solving)是AI领域中的一大课题, 它涉及规约、推断、决策、规划、常识推理、定理证明等相关过程的核心概念, 是人工智能中研究得较早而且比较成熟的一个领域。River2.1 问题与问题空间 AI早期的目的是想通过计算技术来求解这样一些问题：它们不存在现成的求解算法或求解方法非常复杂，而人使用其自身的智能都能较好地求解。为模拟这些问题的求解过程而发展的一种技术叫搜索。2.1.1 如何把问题求解定义为问题状态空间的搜索 在分析和研究了人运用智能求解的方法之后，人们发现许多问题的求解方法都是通过试探在某个可能的解空间内寻找一个解来求解问题，这
2、种基于解答空间的问题表示和求解方法就是状态空间法，它是以状态和算法为基础来表示和求解问题的。这样一来，许多涉及智力的问题求解可看成状态空间的搜索。状态和状态空间 状态（state）是为描述某些不同事物间的差别而引入的一组最少变量q0，q1，q2,qn的有序集合,其形式如下: Q=q0,q1,qn 其中，每个元素q称为状态变量。给定每个分量的一组值，就得到一个具体的状态。 使问题从一种状态变化为另一种状态的手段称为操作符或算子（operator）。状态和状态空间 操作符可能是走步（下棋）、过程、规则、数学算子、运算符号或逻辑运算符等。 问题的状态空间（state space）是一个表示该问题全部
3、可能状态及其关系的集合。状态和状态空间 它包含三种类型的集合，即该问题所有可能的 初始状态集合S， 操作符集合F 目标状态集合G。 因此，可把状态空间记为三元组（S，F，G）。 问题状态空间法的基本思想是： （1）将问题中的已知条件看成状态空间中初始状态；将问题中要求的目标看成状态空间中目标状态；将问题中其它可能的情况看成状态空间的任一状态。 （2）设法在状态空间寻找一条路径，由初始状态出发，能够沿着这条路径达到目标状态。问题状态空间法的基本算法： （1）根据问题，定义出相应的状态空间，确定出状态的一般表示，它含有相关对象的各种可能的排列。当然，这里仅仅是定义这个空间，而不必枚举该状态空间的所
4、有状态，但由此可以得出问题的初始状态、目标状态，并能够表示出所有其它状态。 问题状态空间法的基本算法： (2) 规定一组操作(算子), 能够使状态从一个状态变为另一个状态。 (3) 决定一种搜索策略，使得能够从初始状态出发，沿某个路径达到目标状态。水壶问题 给定两个水壶，一个可装4加仑水，一个能装3加仑水。水壶上没有任何度量标记。有一水泵可用来往壶中装水。问题是怎样在能装4加仑的水壶里恰好只装2加仑水。 （1）定义状态空间: 可将问题进行抽象，用数偶(x,y)表示状态空间的任一状态。 x表示4gallon水壶中所装的水量，x=0，1，2，3或4； y表示3gallon水壶中所装的水量，y=0，
5、1，2或3；（1）定义状态空间 初始状态为 (0,0) 目标状态为(2,?) ？表示水量不限，因为问题中未规定在3加仑水壶里装多少水。 （2）确定一组操作 1（X，Y|X4）（4，Y） 4加仑水壶不满时，将其装满； 2（X，Y|Y0）（X-D，Y） 从4加仑水壶中倒出一些水； 4（X，Y|Y0）（X，Y -D ） 从3加仑水壶中倒出一些水； 5（X，Y|X0）（0，Y） 把4加仑水壶中的水全部倒出； 6（X，Y|Y0）（X，0） 把3加仑水壶中的水全部倒出； （2）确定一组操作 7 （X，Y|X+Y4Y0）4，Y-（4-X） 把3加仑水壶中的水往4加仑水壶里倒，直至4加仑水壶装满为止； 8（X
6、，Y|X+Y3X0）X-（3-Y），3） 把4加仑水壶中的水往3加仑水壶里倒，直至3加仑水壶装满为止； 9 （X，Y|X+Y4Y0）（X+Y，0） 把3加仑水壶中的水全部倒进4加仑水壶里； 10 （X，Y|X+Y3X0）（0，X+Y） 把4加仑水壶中的水全部倒进3加仑水壶里；（3）选择一种搜索策略 该策略为一个简单的循环控制结构：选择其左部匹配当前状态的某条规则，并按照该规则右部的行为对此状态作适当改变，然后检查改变后的状态是否为某一目标状态，若不是，则继续该循环。 4加仑水壶中 3加仑水壶中 所应用的 含水加仑数 含水加仑数 规则 0 0 0 3 2 3 0 9 3 3 2 4 2 7 0
7、2 5 2 0 9 例2.2 分配问题 有两个液源A和B。A的流量为100L/m ,B的流量为50L/m。现要求它们以75L/m的流量分别供应两个同样的洗涤槽C，D。液体从液源经过最大输出能力为75L/m的管道进行分配，A、B、C、D的位置、距离如图2-2所示。并且要求只允许管子在液源或洗涤槽位置有接头。 例2.2 分配问题 问：如何连接管子使得管材最少？ 图2-2 液源分配问题示意图例2.2 分配问题 (1) 定义状态空间中的状态表示。 状态以表的形式表示为： (A=? B=? C=? D=? ) 初 态：(A=100 B=50 C=0 D=0 ) 目标状态：(A=0 B=0 C=75 D=
8、75)例2.2 分配问题 (2) 定义操作。 现在取从一处到另一处流量的增量，为各点流量与各处所需流量的最大公约数(great common divisor)。100、50、75的GCD为25，所以取增量为25。 例2.2 分配问题 (2) 定义操作。 本身到本身不必传递，用表示； 洗涤槽不必往液源送，用表示； 例2.2 分配问题 (2) 定义操作。1 AB (A75B75)(A-25，B+25，C,D) 4km2 AC (A25C75)(A-25，B，C+25) 5km3 AD (A25D75)(A-25，B，C，D+25) 5km4 BC (B25C75)(A，B-25，C+25，D) 3
9、km例2.2 分配问题 (3) 定义策略。 因为现在没有给出任何知识可用来指导搜索, 所以可采用耗尽式搜索，即每次却将7个操作试用一遍。对于该具体问题,搜索时要注意： 若操作重复时，只算一次距离; 边搜索边求出距离最短的管长。分配问题 搜索路径: 2.1.2 问题特征分析 对问题的几个关键指标或特征加以分析。一般要考虑： 问题可分解成为一组独立的、更小、更容易解决的子问题吗？ 当结果表明解题步骤不合适的时侯，能忽略或撤回吗？ 问题的全域可预测吗？ 2.1.2 问题特征分析 在未与所有其它可能解作比较之前，能说当前的解是最好的吗？ 用于求解问题的知识库是相容的吗？ 求解问题一定需要大量的知识吗？
10、或者说，有大量知识时候，搜索时应加以限制吗？ 只把问题交给电脑，电脑就能返回答案吗？或者说，为得到问题的解，需要人机交互吗？ 2.1.2 问题特征分析 1问题是否可分解？问题是否可分解？ 如果问题能分解成若干子问题，则将子问题解出后，原问题的解也就求出来了。人们称这种解决问题的方法为问题的归约。 2.1.2 问题特征分析 例例2.3 符号积分符号积分 不定积分的计算规则有： udv uv-udv 分部积分产生式规则 f(x)+g(x)dx f(x)dx+g(x)dx 和式分解规则 kf(x)dx kf(x)dx 因子规则 dxxxf2524)1 ( dyyyf44cossinydyf4tand
11、zzzf241dzzzf)11122（dzf1dzfz2dzzf)112（fdwyztanwztan2.1.2 问题特征分析 例2.4 积木问题机器人规划的抽象模型 积木问题关心的是积木块的相对位置：某一积木在桌上或某一积木在另一积木上。机器人只能一次拿一块积木，每次搬动时积木上面必须是空的。 2.1.2 问题特征分析 2.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
12、积木问题其中目标状态可分解为： 子问题1: ontabel(c) 子问题2: on(B, C) 子问题3: on(A, B) 2.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.1.2 问题特征分析 但若从初态
13、出 发 , 将on(A, B)作为子问题1 首先求解，这 样 会 使搜 索 离 目标 越 来 越远。 2.1.2 问题特征分析 对于子问题的之间的关系, 实际上有两种:一种为子问题之间是独立的, 其搜索路径为: 2.1.2 问题特征分析 另一种是子问题之间有依赖关系, 其搜索路径为: 2.1.2 问题特征分析 2问题求解步骤是否可撤回？问题求解步骤是否可撤回？ 在问题求解的每一步骤完成后，分析一下它的“踪迹”，可分为： （1）求解步骤可忽略，如定理证明，证明定理的每一件事情都为真或者为假，且总是保存知识库里，它是怎样推出来的对下一步并不重要，因而控制结构不需要带回溯。2.1.2 问题特征分析（
14、2）可复原 如走迷宫，实在走不通，可退回一步重来。这种搜索需用回溯技术,例如:需用一定的控制结构；需采用堆栈技术。 2.1.2 问题特征分析（3）不可复原 如下棋、决策等问题，要提前分析每走一步后会导致的结果。不可回头重来,这需要使用规划技术。在后面的第十章还要讨论这个问题。2.1.2 问题特征分析3问题全域可预测否？问题全域可预测否？ 有些问题它的全域可预测，如水壶问题、有些问题它的全域可预测，如水壶问题、定理证明定理证明, 这些问题结局肯定，可只用开环这些问题结局肯定，可只用开环控制结构。控制结构。 有些问题的全域不可预测，如变化环境有些问题的全域不可预测，如变化环境下机器人的控制，特别是
15、危险环境下工作的下机器人的控制，特别是危险环境下工作的机器人随时可能出意外，必须利用反馈信息，机器人随时可能出意外，必须利用反馈信息，应使用闭环控制结构。应使用闭环控制结构。2.1.2 问题特征分析4问题要求的是最优解还是较满意解？问题要求的是最优解还是较满意解？ 一般说来，最佳路径问题的计算较任一般说来，最佳路径问题的计算较任意路径问题的计算要困难。如果使用的启意路径问题的计算要困难。如果使用的启发式方法不理想，那么对这个解的搜索就发式方法不理想，那么对这个解的搜索就不可能很顺利。有些问题要求找出真正的不可能很顺利。有些问题要求找出真正的最佳路径，可能任何启发式法都不能适用。最佳路径，可能任
16、何启发式法都不能适用。因此，得进行耗尽式搜索，因此，得进行耗尽式搜索，2.2 盲目的搜索方法盲目的搜索方法 盲目搜索方法又叫非启发式搜索，是一种无信息搜索，一般只适用于求解比较简单的问题。下面我们要讨论的几个搜索方法，它们均属于盲目搜索方法。2.2 盲目的搜索方法盲目的搜索方法2.2.1 宽度优先搜索 如果搜索是以同层邻近节点依次扩展节点的, 那么这种搜索就叫宽度优先搜索,这种搜索是逐层进行的, 在对下一层的任一节点进行搜索之前,必须搜索完本层的所有节点。 2.2 盲目的搜索方法盲目的搜索方法宽度优先搜索算法如下: 1. 令N为一个由初始状态构成的表； 2. 若N为空退出，标志失败； 3. 令
17、n为N中第一个点，将n从N中删除； 4. 若n是目标，则退出，标态成功； 5. 若n不是目标，将n的后继点加入到N表的尾部，转2。 2.2 盲目的搜索方法盲目的搜索方法宽度优先搜索的优点是：若问题有解，则可找出最优解;宽度优先搜索的缺点是： 效率低，组合爆炸问题难以解决。 2.2 盲目的搜索方法盲目的搜索方法2.2.2深度优先搜索 在深度优先搜索中，我们首先扩展最新产生的（即最深的）节点。深度相等的节点可以任意排列。 2.2 盲目的搜索方法盲目的搜索方法 深度优先搜索算法如下: 1. 令N为一个由初始状态构成的表； 2. 若N为空退出，标态失败； 3. 令n为N中第一个点，将n从N中删除； 4
18、. 若n是目标，则退出，标态成功； 5. 若n不是目标，将n的后继加入到N表的首部转2。 2.2 盲目的搜索方法盲目的搜索方法 深度优先搜索的优点：节省大量时间和空间； 深度优先搜索的缺点：不一定能找到解。因为在无限搜索树的情况下，最坏的情况可能是不停机。2.2 盲目的搜索方法盲目的搜索方法 2.2.3 分枝有界搜索（分枝有界搜索（Branch-and-Bound） 分枝有界搜索也是一种深度优先搜索，但每个分支都规定了一个统一的搜索深度，搜索到这个深度后，如果没有找到目标便自动退回到上一层，继续搜索。 2.2 盲目的搜索方法 1. 令N为一由初始状态构成的表； 2. 若N为空退出，标志失败；
19、3. 令n为N中第一个点，将n从N中删除； 4. 若n是目标，则退出，标态成功； 5. 若n深度=预先定好的一个界dmax，则转2； 6. 若n不是目标，将n的后继加入到N表的首部转2；2.3 启发式搜索方法启发式搜索方法如果能够找到一种方法用于排列待扩展节点的顺序，即选择最有希望的节点加以扩展，那么，搜索效率将会大大提高。启发式搜索就是基于这种想法,它是深度优先的改进。搜索时不是任取一个分枝，而是根据一些启发式信息，选择最佳一个分枝或几个分枝往下搜索。2.3.1 启发式信息的表示启发式信息的表示1启发式搜索的依据启发式搜索的依据 （1）人们善于利用一些线索来帮助自己选择搜索方向，这些线索统称
20、为启发式(Heuristics)信息，Heuristics一词来源于希腊语Heuriskein，即“发现”的意思。 （2）现实问题往往只需一个解，而不要求最优解或全部解。 （3）启发式信息可以避免某些领域里的组合爆炸问题。 2.3.1 启发式信息的表示启发式信息的表示 启发信息按其形式可分为下列2种： （1）表示为估计函数，确定一个启发式函数f(n), n 为被搜索的节点,它把问题状态的描述映射成问题解决的程度，通常这种程度用数值来表示，就是启发式函数的值。这个值的大小用来决定最佳搜索路径。2.3.1 启发式信息的表示启发式信息的表示（2）表示成规则，如一条启发式规则为：如果存在一个有趣的二元
21、函数f(x,y)，那么看看两变元相同时会发生什么？ 若f表示乘法：导致发现平方； 若f表示集合并运算：导致发现恒等函数； 若f表示思考：导致发现反省； 若f表示谋杀：导致发现自杀。2.3.1 启发式信息的表示启发式信息的表示2启发式函数的表示方法启发式函数的表示方法 启发式函数是一种映射函数，它把对问题状态的描述映射成一种希望的程度。 在搜索算法的设计中，考虑问题的状态的哪些方面、怎样对所考虑的方面作出估计、怎样对某些因素加权等，都取决于启发式函数的设计，取决于该函数对节点是否在解路径上作出尽可能准确的估计。 2.3.1 启发式信息的表示启发式信息的表示 启发式函数设计得好，对有效引导搜索过程
22、有着重要的作用。在有的情况下，非常简单的启发式函数搜索路径能够作出非常令人满意的估计, 当然也有一些场合需要使用非常复杂的启发式函数。下面就简单讨论一下如何构造启发式函数。 （1）启发式函数能够根据问题的当前状态，确定用于继续求解问题的信息。2.3.1 启发式信息的表示启发式信息的表示 例2.6 利用启发式信息去求解水壶问题，人们决不盲目搜索，而是利用水壶容量信息4，3，0，考虑如何求得2。用这几个数字可以考虑4减2或3减1得到2。但前一个方法肯定不行，因为它用到2来求得2，用后一个方法要考虑如何求得1，这很容易在当前信息中找出，因为4减3等于1。因而导致求解路径为：（0，0）（4，0）（1，
23、3）（1，0）（4，1）（2，3）=目标2.3.1 启发式信息的表示 (2) 启发式函数能够估计已找到的状态与达到目标的有利程度。这样的启发式函数能够有效地帮助决定那些后继节点应被产生。2.3.1 启发式信息的表示2 8 31 6 47 5 例2.7 八数码问题。 1 2 38 47 6 5a11 a12 a13a21 a22 a23a31 a32 a33 问题空间为： S0 Sg 2.3.1 启发式信息的表示 各状态间的转换规则为： Pr1: 空格上移 If i，j and i1 then ai-1,j i，j Pr2: 空格下移 If i，j and i3 then ai+1,j i，j
24、2.3.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(S5)=4启发式函数f1= 数字错放位置的个数，f1=0，则达到目标。 2 8 3 1 6 47 52 8 31 6 4 7 52 8 31 47 6 52 8 3 1 47 6 52 31 8 47 6 52 8 3 1 6 47 52 8 31 47 6 52 8 31 6 47 5f1(S0)=4f1(S1)=3f1(S2)=5f1(S3)=5f1(S4)=3f1(S6)=3f1(S7)=42.
25、3.1 启发式信息的表示 当f1值相同时如何决定走步? 现在定义：F2 = 所有数字当前位置次最短路径走到正确位置的步数之和。 在这个定义之下，各状态的启发式函数值为： 数码 1 2 3 4 5 6 7 8F2(S0）= 1 + 1 +0 +0 + 0 + 1 +0 + 2 =5 F2(S1）= 1 + 1 +0 +0 + 0 + 0 +0 + 2 =42.3.1 启发式信息的表示数码 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
26、+0 +0 + 0 + 0 +0 + 1 =3F2(S5）= 1 + 1 +0 +0 + 0 + 1 +0 + 2 =5 F2(S6）= 2 + 1+0 +0 + 0 + 0 +0 + 2 =52.3.1 启发式信息的表示 (3) 启发式函数应能够估计出可能加速达到目标的程度，这可以帮助确定当扩展一个节点时，那些节点应从搜索树中删除。 启发式函数对搜索树(图)的每一节点的真正优点估计得愈精确,解题过程就愈少走弯路。2.3.1 启发式信息的表示 例 2 . 8 八 皇 后 问 题 ( 8 - Q u e e n s problem）。 在8*8棋盘要求放下8个皇后，要求没有一个皇后能够攻击其它皇
27、后，即要使得在任何一行、一列或对角线上都不存在两个或两个以上的皇后。2.3.1 启发式信息的表示求解这个问题的过程为： （a）定义状态空间。设状态空间的一点为：8*8矩阵。 （b）定义操作规则。为简单起见，可按如下规则放置皇后：2.3.1 启发式信息的表示 第一个皇后放第一行。 第二个皇后放在第二行且不与第一个皇后在同一列或对角线的空格上。 第i个皇后放在第i行且不与前面i 1个皇后在同一列或对角线的空格上。 2.3.1 启发式信息的表示可使用如下启发式函数： 设x为当前要放置Queen的空格 f（x）= 剩下未放行中能够用来放Queen的空格数 不难看出，f（x）愈大愈好，应选择f（x）最大
28、的空格来放置皇后。 例如，在放置了三个Q后，第4个Q可放在第4行的A，B，C三个位置。2.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 启发式信息的表示 Q Q Q A BC abc bc ab bc c ac abc b acb ac acabbc 2.3.1 启发式信息的表示 （c）定义搜索策略。第i个皇后放到第i行中的那个
29、与前面i-l个皇后不在同一列或对角线上且f（x）值最大的空格中。 由此可见,启发式信息是某些领域里的知识信息，它能使计算机系统在这些知识信息提示以后可能采取的某些可能的动作或避免某些不可能的动作，它能够说明动作适合的条件或不适合的条件。 2.3.1 启发式信息的表示 启发式搜索方法按其适用的范围也可以分为两种: 一种是适用于特定的领域，如果这个领域很窄，这种启发式搜索方法就变成了类似于计算方法中的算法； 一种是适用于较广泛领域的通用启发式搜索算法，这类算法是后面要讨论的弱法。2.3.1 启发式信息的表示 3搜索方向的选择搜索方向的选择 搜索过程：在问题空间中找出从开始状态到目标状态的一条最好的
30、或较好的路径。这种搜索可按两个方向进行： 正向搜索：从初始状态朝着目标状态方向搜索； 逆向搜索：从目标状态朝着初始状态方向搜索。 将以上两种搜索方法结合起来，就产生了双向搜索 2.3.1 启发式信息的表示 正向搜索 和 逆向搜索 S0 S0 Sg Sg 2.3.1 启发式信息的表示 搜索方向的选择： (1) 朝分枝因子低的方向更有效。 分子因子指从一点出发可以直接到达的平均结点数。朝着分枝因子低的方向搜索意味着朝着“收敛”的方向搜索，例如定理证明, 一般是从公理或定理出发，推出新的定理。公理是有限的，而定理是大量的。 2.3.1 启发式信息的表示 (2) 由状态少的一方出发，朝着大量的可识别的状态的方向搜索，会容易一些。 例如符号积分问题, 正向搜索意味着从被积函数出发，按照积分规则，寻找原函数。而逆向搜索，则要从大量的原函数的任意组合出发，通过积分规则，找出被积函数，这显然要困难得多，我们在人工演算积分问题时决不会这么去做。 2.3.1 启发式信息的表示 (3) 依据用户可接受的方向。 特别是需要向用户解释推理过程时，顺应用户的心理，选择搜索方向会使系统显得更自然一些。在建造专家系统时，向用户解释为什么系统会得出某个结论, 这一步骤是必不可少的，所以尤其要考虑这个问题。
