1、第第2章章 用搜索求解问题的基用搜索求解问题的基本原理本原理 2.1 问题与问题空间 lAI早期的目的是想通过计算技术来求解这样一些问题：它们不存在现成的求解算法或求解方法非常复杂，而人使用其自身的智能都能较好地求解。为模拟这些问题的求解过程而发展的一种技术叫搜索。把问题求解定义为状态空间的搜索 l在分析和研究了人运用智能求解的方法之后，人们发现许多问题的求解方法都是通过试探在某个可能的解空间内寻找一个解来求解问题，这种基于解答空间的问题表示和求解方法就是状态空间法。许多涉及智力的问题求解可看成状态空间的搜索。状态和状态空间 l状态（state）是为描述某些不同事物间的差别而引入的一组最少变量
2、q0，q1，q2,qn的有序集合,并表示为:l Q = （q0,q1,qn） l 其中，每个元素q称为状态变量。给定每个分量的一组值，就得到一个具体的状态。状态和状态空间l使问题从一种状态变化为另一种状态的手段称为操作符或算子（operator）。l操作符可能是走步（下棋）、过程、规则、数学算子、运算符号或逻辑运算符等。l问题的状态空间（state space）是一个表示该问题全部可能状态及其关系的集合。状态和状态空间l它包含三种类型的集合，即该问题所有可能的l因此，可把状态空间记为三元组（S，F，G）。 问题状态空间法的基本思想是： l （1）将问题中的已知条件看成状态空间中初始状态；将问题
3、中要求的目标看成状态空间中目标状态；将问题中其它可能的情况看成状态空间的任一状态。l （2）设法在状态空间寻找一条路径，由初始状态出发，能够沿着这条路径达到目标状态。问题状态空间法的基本算法： （1）根据问题，定义出相应的状态空间，确定出状态的一般表示，它含有相关对象的各种可能的排列。这里仅仅是定义这个空间的状态，而不必枚举该状态空间的所有状态，但由此可以得出问题的初始状态、目标状态，并能够表示出所有其它状态。 问题状态空间法的基本算法： (2) 规定一组操作(算子), 能够使状态从一个状态变为另一个状态。 (3) 决定一种搜索策略，使得能够从初始状态出发，沿某个路径达到目标状态。水壶问题 l
4、 给定两个水壶，一个可装4加仑水，一个能装3加仑水。水壶上没有任何度量标记。有一水泵可用来往壶中装水。l 问：怎样在能装4加仑的水壶里恰好只装2加仑水？ （1）定义状态空间l可将问题进行抽象，用数偶(x,y)表示状态空间的任一状态。l x表示4gallon水壶中所装的水量，x=0，1，2，3或4；l y表示3gallon水壶中所装的水量，y=0，1，2或3；l初始状态为 (0,0)l目标状态为 (2,?)l？表示水量不限，因为问题中未规定在3加仑水壶里装多少水。 （2）确定一组操作）确定一组操作1（X，Y|X4）（4，Y） 4加仑水壶不满时，将其装满；2（X，Y|Y0）（0，Y） 把4加仑水壶
5、中的水全部倒出；6（X，Y|Y0）（X，0） 把3加仑水壶中的水全部倒出； 7 （X，Y|X+Y4Y0） （4，Y-（4-X） 把3加仑水壶中的水往4加仑水壶里倒，直至4加仑水壶装满为止8 （X，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）选择一种搜索策略）选择一种搜索策略 该策略为一个简单的循环控制结构：选择其左部匹配当前状态的某条规则，并按照该规则右部的
6、行为对此状态作适当改变，然后检查改变后的状态是否为某一目标状态，若不是，则继续该循环。 l4加仑水壶中 3加仑水壶中 所应用的 含水加仑数 含水加仑数 规则l 0 0 l 0 3 2l 3 0 9 l 3 3 2l 4 2 7 l 0 2 5 l 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 分配问题 l问：如何连接管子使得管材最少？
7、 图2-2 液源分配问题示意图例2.2 分配问题 (1) 定义状态空间中的状态表示定义状态空间中的状态表示状态以表的形式表示为： (A=? B=? C=? D=? )初 态：(A=100 B=50 C=0 D=0 )目标状态：(A=0 B=0 C=75 D=75)例2.2 分配问题 (2) 定义操作定义操作 现在取从一处到另一处流量的增量，为各点流量与各处所需流量的最大公约数(greatest common divisor)。100、50、75的GCD为25，所以取增量为25。 例2.2 分配问题 l 本身到本身不必传递，本身到本身不必传递，用用表示；表示； 洗涤槽不必往液源送，洗涤槽不必往液
8、源送，用用表示；表示； 例2.2 分配问题 1 AB (A25B75)(A-25，B+25，C,D) 4km2 AC (A25C75)(A-25，B，C+25，D) 5km3 AD (A25D75)(A-25，B，C，D+25) 5km4 BC (B25C75)(A，B-25，C+25，D) 3km例2.2 分配问题 5 BD (B25D75)(A，B-25，C，D+25) 3km6 CD (C25D75)(A，B，C-25，D+25) 6km7 DC (C75 D25)(A，B，C+25，D-25) 6km例2.2 分配问题 (3) 定义策略定义策略因为现在没有给出任何知识可用来指导搜索,
9、所以可采用耗尽式搜索，即每次却将7个操作试用一遍。对于该具体问题,搜索时要注意： 若操作重复时，只算一次距离; 边搜索边求出距离最短的管长。分配问题 l搜索路径: 2.4 问题特征分析问题特征分析对问题的几个关键指标或特征加以分析。一般要考虑：l 问题可分解成为一组独立的、更小、更容易解决的子问题吗？l 当结果表明解题步骤不合适的时侯，能忽略或撤回吗？l 问题的全域可预测吗？ 2.4 问题特征分析问题特征分析 l 在未与所有其它可能解作比较之前，能说当前的解是最好的吗？l 用于求解问题的知识库是相容的吗？l 求解问题一定需要大量的知识吗？或者说，有大量知识时候，搜索时应加以限制吗？l 只把问题
10、交给电脑，电脑就能返回答案吗？或者说，为得到问题的解，需要人机交互吗？ 2.4.1 问题是否可分解？问题是否可分解？如果问题能分解成若干子问题，则将子问题解出后，原问题的解也就求出来了。人们称这种解决问题的方法为问题的归约。 例例2.3 符号积分符号积分 不定积分的计算规则有： udv uv-vdu 分部积分产生式规则 （f(x)+g(x)）dx f(x)dx+g(x)dx 和式分解规则 kf(x)dx kf(x)dx 因子规则 例2.4 积木问题机器人规划的抽象模型 积木问题关心的是积木块的相对位置：某一积木在桌上或某一积木在另一积木上。机器人一次只能拿一块积木，每次搬动时积木上面必须是空的
11、。 例2.4 积木问题 积木的相对位置可用谓词表示为：初始状态：ontabel(B)clear(B) ontabel(A) on(C,A)clear(C)目标状态：ontabel(C)on(B, C)on(A, B) 其中目标状态可分解为： 子问题1: ontabel(c) 子问题2: on(B, C) 子问题3: on(A, B) 例2.4 积木问题机器人所需完成的操作： OP1：clear(x)ontabel(x) 无论x在何处，若x上无物体，则可将x放于桌上 OP2：clear(x)clear(y)On(x, y) 若x，y上无物体，则可将x放在y上 这个问题的求解方法有两种： 从目标来
12、看，总问题可分解成三个子问题，但这三个子问题不能按任意次序求解。 但 若 从但 若 从初态出发初态出发, 将将on(A, B)作 为 子 问作 为 子 问题题1 首先求首先求解 ， 这 样解 ， 这 样会 使 搜 索会 使 搜 索离 目 标 越离 目 标 越来越远。来越远。 对于子问题的之间的关系, 实际上有两种:一种为子问题之间是独立的, 其搜索路径为: l 另 一 种是子问题之间有依赖 关 系 , 其搜索路径为: 2.4.2 问题求解步骤是否可撤回？问题求解步骤是否可撤回？ 在问题求解的每一步骤完成后，分析一下它的“踪迹”，可分为3类：（1）求解步骤可忽略如定理证明，证明定理的每一件事情都
13、为真或者为假，且总是保存知识库里，它是怎样推出来的对下一步并不重要，因而控制结构不需要带回溯。（2）可复原 如走迷宫，实在走不通，可退回一步重来。这种搜索需用回溯技术,例如:（3）不可复原如下棋、决策等问题，要提前分析每走一步后会导致的结果。不可回头重来,这需要使用规划技术。2.4.3 问题全域可预测否？问题全域可预测否？ 有些问题它的全域可预测，如水壶问题、定理证明, 这些问题结局肯定，可只用开环控制结构。 有些问题的全域不可预测，如变化环境下机器人的控制，特别是危险环境下工作的机器人随时可能出意外，必须利用反馈信息，应使用闭环控制结构。2.4.4 问题要求的是最优解还是问题要求的是最优解还是较满意解？较满意解？一般说来，最佳路径问题的计算较任意路径问题的计算要困难。如果使用的启发式方法不理想，那么对这个解的搜索就不可能很顺利。有些问题要求找出真正的最佳路径，可能任何启发式法都不能适用。因此，得进行耗尽式搜索，
