人工智能幻灯片第2章1

第二章 问题求解与搜索方法,问题求解(Problem-solving)是AI领域中的一大课题, 它涉及规约、推断、决策、规划、常识推理、定理证明等相关过程的核心概念, 是人工智能中研究得较早而且比较成熟的一个领域。River,2.1 问题与问题空间,AI早期的目的是想通过计算技术来求解这样一些问题：它们不存在现成的求解算法或求解方法非常复杂，而人使用其自身的智能都能较好地求解。为模拟这些问题的求解过程而发展的一种技术叫搜索。,2.1.1 如何把问题求解定义为问题状态空间的搜索,在分析和研究了人运用智能求解的方法之后，人们发现许多问题的求解方法都是通过试探在某个可能的解空间内寻找一个解来求解问题，这种基于解答空间的问题表示和求解方法就是状态空间法，它是以状态和算法为基础来表示和求解问题的。这样一来，许多涉及智力的问题求解可看成状态空间的搜索。,状态和状态空间,状态（state）是为描述某些不同事物间的差别而引入的一组最少变量q0，q1，q2,qn的有序集合,其形式如下: Q=q0,q1,qn 其中，每个元素q称为状态变量。给定每个分量的一组值，就得到一个具体的状态。 使问题从一种状态变化为另一种状态的手段称为操作符或算子（operator）。,状态和状态空间,操作符可能是走步（下棋）、过程、规则、数学算子、运算符号或逻辑运算符等。 问题的状态空间（state space）是一个表示该问题全部可能状态及其关系的集合。,状态和状态空间,它包含三种类型的集合，即该问题所有可能的 初始状态集合S， 操作符集合F 目标状态集合G。 因此，可把状态空间记为三元组（S，F，G）。,问题状态空间法的基本思想是：,（1）将问题中的已知条件看成状态空间中初始状态；将问题中要求的目标看成状态空间中目标状态；将问题中其它可能的情况看成状态空间的任一状态。 （2）设法在状态空间寻找一条路径，由初始状态出发，能够沿着这条路径达到目标状态。,问题状态空间法的基本算法：,（1）根据问题，定义出相应的状态空间，确定出状态的一般表示，它含有相关对象的各种可能的排列。当然，这里仅仅是定义这个空间，而不必枚举该状态空间的所有状态，但由此可以得出问题的初始状态、目标状态，并能够表示出所有其它状态。,问题状态空间法的基本算法：,(2) 规定一组操作(算子), 能够使状态从一个状态变为另一个状态。 (3) 决定一种搜索策略，使得能够从初始状态出发，沿某个路径达到目标状态。,水壶问题,给定两个水壶，一个可装4加仑水，一个能装3加仑水。水壶上没有任何度量标记。有一水泵可用来往壶中装水。问题是怎样在能装4加仑的水壶里恰好只装2加仑水。,（1）定义状态空间:,可将问题进行抽象，用数偶(x,y)表示状态空间的任一状态。 x表示4gallon水壶中所装的水量，x=0，1，2，3或4； y表示3gallon水壶中所装的水量，y=0，1，2或3；,（1）定义状态空间,初始状态为 (0,0) 目标状态为(2,?) ？表示水量不限，因为问题中未规定在3加仑水壶里装多少水。,（2）确定一组操作,1（X，Y|X0）（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，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 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=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) 4km 2 AC (A25C75)(A-25，B，C+25) 5km 3 AD (A25D75)(A-25，B，C，D+25) 5km 4 BC (B25C75)(A，B-25，C+25，D) 3km,例2.2 分配问题,(3) 定义策略。 因为现在没有给出任何知识可用来指导搜索, 所以可采用耗尽式搜索，即每次却将7个操作试用一遍。对于该具体问题,搜索时要注意： 若操作重复时，只算一次距离; 边搜索边求出距离最短的管长。,分配问题,搜索路径:,2.1.2 问题特征分析,对问题的几个关键指标或特征加以分析。一般要考虑： 问题可分解成为一组独立的、更小、更容易解决的子问题吗？ 当结果表明解题步骤不合适的时侯，能忽略或撤回吗？ 问题的全域可预测吗？,2.1.2 问题特征分析,在未与所有其它可能解作比较之前，能说当前的解是最好的吗？ 用于求解问题的知识库是相容的吗？ 求解问题一定需要大量的知识吗？或者说，有大量知识时候，搜索时应加以限制吗？ 只把问题交给电脑，电脑就能返回答案吗？或者说，为得到问题的解，需要人机交互吗？,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 因子规则,2.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 积木问题 其中目标状态可分解为： 子问题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 问题特征分析,但若从初态出发, 将on(A, B)作为子问题1 首先求解，这样会使搜索离目标越来越远。,2.1.2 问题特征分析,对于子问题的之间的关系, 实际上有两种:一种为子问题之间是独立的, 其搜索路径为:,2.1.2 问题特征分析,另一种是子问题之间有依赖关系, 其搜索路径为:,2.1.2 问题特征分析,2问题求解步骤是否可撤回？ 在问题求解的每一步骤完成后，分析一下它的“踪迹”，可分为： （1）求解步骤可忽略，如定理证明，证明定理的每一件事情都为真或者为假，且总是保存知识库里，它是怎样推出来的对下一步并不重要，因而控制结构不需要带回溯。,2.1.2 问题特征分析,（2）可复原 如走迷宫，实在走不通，可退回一步重来。这种搜索需用回溯技术,例如: 需用一定的控制结构； 需采用堆栈技术。,2.1.2 问题特征分析,（3）不可复原 如下棋、决策等问题，要提前分析每走一步后会导致的结果。不可回头重来,这需要使用规划技术。在后面的第十章还要讨论这个问题。,2.1.2 问题特征分析,3问题全域可预测否？ 有些问题它的全域可预测，如水壶问题、定理证明, 这些问题结局肯定，可只用开环控制结构。 有些问题的全域不可预测，如变化环境下机器人的控制，特别是危险环境下工作的机器人随时可能出意外，必须利用反馈信息，应使用闭环控制结构。,2.1.2 问题特征分析,4问题要求的是最优解还是较满意解？ 一般说来，最佳路径问题的计算较任意路径问题的计算要困难。如果使用的启发式方法不理想，那么对这个解的搜索就不可能很顺利。有些问题要求找出真正的最佳路径，可能任何启发式法都不能适用。因此，得进行耗尽式搜索，,2.2 盲目的搜索方法,盲目搜索方法又叫非启发式搜索，是一种无信息搜索，一般只适用于求解比较简单的问题。下面我们要讨论的几个搜索方法，它们均属于盲目搜索方法。,2.2 盲目的搜索方法,2.2.1 宽度优先搜索 如果搜索是以同层邻近节点依次扩展节点的, 那么这种搜索就叫宽度优先搜索,这种搜索是逐层进行的, 在对下一层的任一节点进行搜索之前,必须搜索完本层的所有节点。,2.2 盲目的搜索方法,宽度优先搜索算法如下: 1. 令N为一个由初始状态构成的表； 2. 若N为空退出，标志失败； 3. 令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中第一