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

《第一部分用搜索方法求解问题.ppt》由会员分享，可在线阅读，更多相关《第一部分用搜索方法求解问题.ppt（71页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、第一部分用搜索方法求解问题现在学习的是第1页，共71页l 问题求解(Problem-solving)是AI领域中的一大课题,它涉及规约、推断、决策、规划、常识推理、定理证明等相关过程的核心概念,是人工智能中研究得较早而且比较成熟的一个领域。现在学习的是第2页，共71页1.1 问题与问题空间 lAI早期的目的是想通过计算技术来求解这样一些问题：它们不存在现成的求解算法或求解方法非常复杂，而人使用其自身的智能都能较好地求解。l为模拟这些问题的求解过程而发展的一种技术叫搜索。现在学习的是第3页，共71页1.1.1 把问题求解定义为状态空间的搜索 l在分析和研究了人运用智能求解的方法之后，人们发现许多

2、问题的求解方法都是通过试探在某个可能的解空间内寻找一个解来求解问题，这种基于解答空间的问题表示和求解方法就是状态空间法。许多涉及智力的问题求解可看成状态空间的搜索。现在学习的是第4页，共71页状态和状态空间 状态（state）是为描述某些不同事物间的差别而引入的一组最少变量q0，q1，q2,qn的有序集合,并表示为:Q=（q0,q1,qn）其中，每个元素q称为状态变量。给定每个分量的一组值，就得到一个具体的状态。现在学习的是第5页，共71页状态和状态空间l使问题从一种状态变化为另一种状态的手段称为操作符或算子（operator）。l操作符可能是走步（下棋）、过程、规则、数学算子、运算符号或逻辑

3、运算符等。l问题的状态空间（state space）是一个表示该问题全部可能状态及其关系的集合。现在学习的是第6页，共71页状态和状态空间它包含三种类型的集合，即该问题所有可能的l l初始状态集合S，l l操作符集合Fl l目标状态集合G。因此，可把状态空间记为三元组（S，F，G）。现在学习的是第7页，共71页问题状态空间法的基本思想是：l（1）将问题中的已知条件看成状态空间中初始状态；将问题中要求的目标看成状态空间中目标状态；将问题中其它可能的情况看成状态空间的任一状态。l （2）设法在状态空间寻找一条路径，由初始状态出发，能够沿着这条路径达到目标状态。现在学习的是第8页，共71页问题状态空

4、间法的基本算法l（1）根据问题，定义出相应的状态空间，确定出状态的一般表示，它含有相关对象的各种可能的排列。这里仅仅是定义这个空间的状态，而不必枚举该状态空间的所有状态，但由此可以得出问题的初始状态、目标状态，并能够表示出所有其它状态。现在学习的是第9页，共71页问题状态空间法的基本算法：l(2)规定一组操作(算子),能够使状态从一个状态变为另一个状态。l(3)决定一种搜索策略，使得能够从初始状态出发，沿某个路径达到目标状态。现在学习的是第10页，共71页水壶问题 l 给定两个水壶，一个可装4加仑水，一个能装3加仑水。水壶上没有任何度量标记。有一水泵可用来往壶中装水。l 问：怎样在能装4加仑的

5、水壶里恰好只装2加仑水？现在学习的是第11页，共71页（1）定义状态空间）定义状态空间可将问题进行抽象，用数偶(x,y)表示状态空间的任一状态。x表示4gallon水壶中所装的水量，x=0，1，2，3或4；y表示3gallon水壶中所装的水量，y=0，1，2或3；现在学习的是第12页，共71页l初始状态为 (0,0)l目标状态为(2,?)？表示水量不限，因为问题中未规定在3加仑水壶里装多少水。现在学习的是第13页，共71页（2）确定一组操作）确定一组操作1（X，Y|X4）（4，Y）4加仑水壶不满时，将其装满；2（X，Y|Y0）（0，Y）把4加仑水壶中的水全部倒出；现在学习的是第14页，共71页

6、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加仑水壶装满为止；现在学习的是第15页，共71页9（X，Y|X+Y4Y0）（X+Y，0）把3加仑水壶中的水全部倒进4加仑水壶里；10（X，Y|X+Y3X0）（0，X+Y）把4加仑水壶中的水全部倒进3加仑水壶里；现在学习的是第16页，共71页（3）选择一种搜索策略）选择一种搜索策略 该策略为一个简单的循环控制结构：选择其左部匹配当前状态的某条规则，并

7、按照该规则右部的行为对此状态作适当改变，然后检查改变后的状态是否为某一目标状态，若不是，则继续该循环。现在学习的是第17页，共71页现在学习的是第18页，共71页4加仑水壶中 3加仑水壶中 所应用的 含水加仑数 含水加仑数 规则 0 0 0 3 2 3 0 9 3 3 2 4 2 7 0 2 5 2 0 9 现在学习的是第19页，共71页 1.1.2 问题特征分析 对问题的几个关键指标或特征加以分析。一般要考虑：l 问题可分解成为一组独立的、更小、更容易解决的子问题吗？l 当结果表明解题步骤不合适的时侯，能忽略或撤回吗？l 问题的全域可预测吗？现在学习的是第20页，共71页 1.1.2 问题特

8、征分析 l 在未与所有其它可能解作比较之前，能说当前的解是最好的吗？l 用于求解问题的知识库是相容的吗？l 求解问题一定需要大量的知识吗？或者说，有大量知识时候，搜索时应加以限制吗？l 只把问题交给电脑，电脑就能返回答案吗？或者说，为得到问题的解，需要人机交互吗？现在学习的是第21页，共71页 1.1.2 问题特征分析 1问题是否可分解？问题是否可分解？如果问题能分解成若干子问题，则将子问题解出后，原问题的解也就求出来了。人们称这种解决问题的方法为问题的归约。现在学习的是第22页，共71页 1.1.2 问题特征分析 例例1.3 符号积分符号积分 不定积分的计算规则有：udv uv-udv 分部

9、积分产生式规则 f(x)+g(x)dx f(x)dx+g(x)dx 和式分解规则 kf(x)dx kf(x)dx 因子规则 现在学习的是第23页，共71页1.1.2 问题特征分析 例1.4 积木问题机器人规划的抽象模型 积木问题关心的是积木块的相对位置：某一积木在桌上或某一积木在另一积木上。机器人只能一次拿一块积木，每次搬动时积木上面必须是空的。现在学习的是第24页，共71页 1.1.2 问题特征分析 现在学习的是第25页，共71页 1.1.2 问题特征分析 例1.4 积木问题 积木的相对位置可用谓词表示为：初始状态：ontabel(B)clear(B)ontabel(A)on(C,A)cle

10、ar(C)目标状态：ontabel(C)on(B,C)on(A,B)现在学习的是第26页，共71页 1.1.2 问题特征分析 其中目标状态可分解为：子问题1:ontabel(c)子问题2:on(B,C)子问题3:on(A,B)现在学习的是第27页，共71页 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页，共71页 1.1.2 问题特征分析 这个问题的求解方法有两种：l l一种方法

11、是采用全面搜索的方法；l l一种是用分解子问题的方法。从目标来看，总问题可分解成三个子问题，但这三个子问题不能按任意次序求解。现在学习的是第29页，共71页 现在学习的是第30页，共71页 1.1.2 问题特征分析 但若从初态出发,将on(A,B)作为子问题1 首先求解，这样会使搜索离目标越来越远。现在学习的是第31页，共71页 1.1.2 问题特征分析 对于子问题的之间的关系,实际上有两种:一种为子问题之间是独立的,其搜索路径为:现在学习的是第32页，共71页 1.1.2 问题特征分析 另一种是 子 问题 之 间有 依 赖关系,其搜 索 路径为:现在学习的是第33页，共71页1.1.2 问题

12、特征分析2问题求解步骤是否可撤回？问题求解步骤是否可撤回？在问题求解的每一步骤完成后，分析一下它的“踪迹”，可分为3类：（1）求解步骤可忽略如定理证明，证明定理的每一件事情都为真或者为假，且总是保存知识库里，它是怎样推出来的对下一步并不重要，因而控制结构不需要带回溯。现在学习的是第34页，共71页1.1.2 问题特征分析（2）可复原 如走迷宫，实在走不通，可退回一步重来。这种搜索需用回溯技术,例如:l l需用一定的控制结构；l l需采用堆栈技术。现在学习的是第35页，共71页1.1.2 问题特征分析（3）不可复原l如下棋、决策等问题，要提前分析每走一步后会导致的结果。不可回头重来,这需要使用规

13、划技术。现在学习的是第36页，共71页1.1.2 问题特征分析3问题全域可预测否？问题全域可预测否？有些问题它的全域可预测，如水壶问题、定理证明,这些问题结局肯定，可只用开环控制结构。有些问题的全域不可预测，如变化环境下机器人的控制，特别是危险环境下工作的机器人随时可能出意外，必须利用反馈信息，应使用闭环控制结构。现在学习的是第37页，共71页1.1.2 问题特征分析4问题要求的是最优解还是较满意问题要求的是最优解还是较满意解？解？一般说来，最佳路径问题的计算较任意路径问题的计算要困难。如果使用的启发式方法不理想，那么对这个解的搜索就不可能很顺利。有些问题要求找出真正的最佳路径，可能任何启发式

14、法都不能适用。因此，得进行耗尽式搜索，现在学习的是第38页，共71页1.2 盲目的搜索方法盲目的搜索方法l 盲目搜索方法又叫非启发式搜索，是一种无信息搜索，一般只适用于求解比较简单的问题。下面我们要讨论的几个搜索方法，它们均属于盲目搜索方法。现在学习的是第39页，共71页1.2.1 宽度优先搜索 如果搜索是以同层邻近节点依次扩展节点的,那么这种搜索就叫宽度优先搜索,这种搜索是逐层进行的,在对下一层的任一节点进行搜索之前,必须搜索完本层的所有节点。现在学习的是第40页，共71页宽度优先搜索算法如下:1.令N为一个由初始状态构成的表；2.若N为空退出，标志失败；3.令n为N中第一个点，将n从N中删

15、除；4.若n是目标，则退出，标态成功；5.若n不是目标，将n的后继点加入到N表的尾部，转2。现在学习的是第41页，共71页l宽度优先搜索的优点是：若问题有解，则可找出最优解;l宽度优先搜索的缺点是:效率低，组合爆炸问题难以解决。现在学习的是第42页，共71页1.2.2 深度优先搜索在深度优先搜索中，首先扩展最新产生的（即最深的）节点。深度相等的节点可以任意排列。现在学习的是第43页，共71页1.2.2 深度优先搜索深度优先搜索算法如下:1.令N为一个由初始状态构成的表；2.若N为空退出，标态失败；3.令n为N中第一个点，将n从N中删除；4.若n是目标，则退出，标态成功；5.若n不是目标，将n的

16、后继加入到N表的首部转2。现在学习的是第44页，共71页1.2.2 深度优先搜索l 深度优先搜索的优点：节省大量时间和空间；l 深度优先搜索的缺点：不一定能找到解。因为在无限搜索树的情况下，最坏的情况可能是不停机。现在学习的是第45页，共71页1.2.3 分枝有界搜索分枝有界搜索（Branch-and-Bound）l 分枝有界搜索也是一种深度优先搜索，但每个分支都规定了一个统一的搜索深度，搜索到这个深度后，如果没有找到目标便自动退回到上一层，继续搜索。现在学习的是第46页，共71页1.2.3 分枝有界搜索分枝有界搜索（Branch-and-Bound）1.令N为一由初始状态构成的表；2.若N为

17、空退出，标志失败；3.令n为N中第一个点，将n从N中删除；4.若n是目标，则退出，标态成功；5.若n深度=预先定好的一个界dmax，则转2；6.若n不是目标，将n的后继加入到N表的首部转2；现在学习的是第47页，共71页1.3 启发式搜索方法启发式搜索方法l 如果能够找到一种方法用于排列待扩展节点的顺序，即选择最有希望的节点加以扩展，那么，搜索效率将会大大提高。启发式搜索就是基于这种想法,它是深度优先的改进。搜索时不是任取一个分枝，而是根据一些启发式信息，选择最佳一个分枝或几个分枝往下搜索。现在学习的是第48页，共71页1.3.1 启发式信息的表示启发式信息的表示1启发式搜索的依据启发式搜索的

18、依据（1）人们善于利用一些线索来帮助自己选择搜 索 方 向，这 些 线 索 统 称 为 启 发 式(Heuristics)信息。（2）现实问题往往只需一个解，而不要求最优解或全部解。（3）启发式信息可以避免某些领域里的组合爆炸问题。现在学习的是第49页，共71页1.3.1 启发式信息的表示启发式信息的表示启发信息按其形式可分为下列2种：（1）表示为估计函数）表示为估计函数 确定一个启发式函数f(n),n 为被搜索的节点,它把问题状态的描述映射成问题解决的程度，通常这种程度用数值来表示，就是启发式函数的值。这个值的大小用来决定最佳搜索路径。现在学习的是第50页，共71页1.3.1 启发式信息的表

19、示启发式信息的表示（2）表示成规则）表示成规则如AM的一条启发式规则为：如果存在一个有趣的二元函数f(x,y)，那么看看两变元相同时会发生什么？l若f表示乘法：导致发现平方；l若f表示集合并运算：导致发现恒等函数；l若f表示思考：导致发现反省；l若f表示谋杀：导致发现自杀。现在学习的是第51页，共71页1.3.1 启发式信息的表示启发式信息的表示2启发式函数的表示方法启发式函数的表示方法l启发式函数是一种映射函数，它把对问题状态的描述映射成一种希望的程度。l启发式函数设计得好，对有效引导搜索过程有着重要的作用。在有的情况下，非常简单的启发式函数搜索路径能够作出非常令人满意的估计,当然也有一些场

20、合需要使用非常复杂的启发式函数。现在学习的是第52页，共71页1.3.1 启发式信息的表示启发式信息的表示如何构造启发式函数？（1）启发式函数能够根据问题的当前状态，确定用于继续求解问题的信息。现在学习的是第53页，共71页1.3.1 启发式信息的表示启发式信息的表示l利用启发式信息去求解水壶问题，人们决不盲目搜索，而是利用水壶容量信息4，3，0，考虑如何求得2。用这几个数字可以考虑4减2或3减1得到2。这很容易在当前信息中找出，因为4减3等于1。因而导致求解路径为：l（0，0）（4，0）（1，3）（1，0）（4，1）（2，3）=目标现在学习的是第54页，共71页1.3.1 启发式信息的表示l

21、(2)启发式函数能够估计已找到的状态与达到目标的有利程度。l这样的启发式函数能够有效地帮助决定那些后继节点应被产生。现在学习的是第55页，共71页1.3.1 启发式信息的表示28316475例1.7八数码问题。12384765a11a12a13a21a22a23a31a32a33问题空间为：S0Sg现在学习的是第56页，共71页1.3.1 启发式信息的表示l各状态间的转换规则为：lPr1:空格上移 lIf i，j and i1 then ai-1,j i，j llPr2:空格下移 lIf i，j and i3 then aI+1,j i，j 现在学习的是第57页，共71页1.3.1 启发式信息

22、的表示lPr3:空格左移 lIf i，j and j1 then ai,j-1 i，j lPr4:空格右移 lIf i，j and j3 then ai,j+1 i，j 现在学习的是第58页，共71页启发式函数f1=数字错放位置的个数，f1=0，则达到目标。2831647528316475283147652831476523184765283164752831476528316475现在学习的是第59页，共71页1.3.1 启发式信息的表示 当f1值相同时如何决定走步?现在定义：f2=所有数字当前位置以最短路径走到正确位置的步数之和。在这个定义之下，各状态的启发式函数值为：数码 1 2 3 4

23、 5 6 7 8 F2(S0）=1+1+0+0+0+1+0+2=5F2(S1）=1+1+0+0+0+0+0+2=4现在学习的是第60页，共71页1.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+0+0+0+0+0+1=3F2(S5）=1+1+0+0+0+1+0+2=5 F2(S6）=1+2+0+0+0+0+0+2=5现在学习的是第61页，共71页1.3.1 启发式信息的表示(3)启发式函数应能够估计出可能加速达到目标的程度 这可以帮助确定当扩展一个节点时，那些

24、节点应从搜索树中删除。启发式函数对搜索树(图)的每一节点的真正优点估计得愈精确,解题过程就愈少走弯路。现在学习的是第62页，共71页1.3.1 启发式信息的表示l例1.8 八皇后问题(8-Queens problem）在8*8棋盘要求放下8个皇后，要求没有一个皇后能够攻击其它皇后，即要使得在任何一行、一列或对角线上都不存在两个或两个以上的皇后。现在学习的是第63页，共71页1.3.1 启发式信息的表示求解这个问题的过程为：（a）定义状态空间。设状态空间的一点为：8*8矩阵。（b）定义操作规则。按如下规则放置皇后：现在学习的是第64页，共71页1.3.1 启发式信息的表示 第一个皇后放第一行。第

25、二个皇后放在第二行且不与第一个皇后在同一列或对角线的空格上。第i个皇后放在第i行且不与前面i 1个皇后在同一列或对角线的空格上。现在学习的是第65页，共71页1.3.1 启发式信息的表示可使用如下启发式函数：设x为当前要放置Queen的空格f（x）=剩下未放行中能够用来放Queen的空格数不难看出，f（x）愈大愈好，应选择f（x）最大的空格来放置皇后。例如，在放置了三个Q后，第4个Q可放在第4行的A，B，C三个位置。现在学习的是第66页，共71页1.3.1 启发式信息的表示QQQABCabcbcabbccacabcbacbacacabbc现在学习的是第67页，共71页1.3.1 启发式信息的表

26、示a为第4行A处放了皇后剩下可放Q的位置；b为第4行B处放了皇后剩下可放Q的位置；c为第4行C处放了皇后剩下可放Q的位置。按照以上定义，可求得：f（A）=8，f（B）=9，f（C）=10。所以搜索可以从C对应的空格放置一个皇后开始，其余的空格对应的搜索树可以删除。现在学习的是第68页，共71页1.3.1 启发式信息的表示（c）定义搜索策略。第i个皇后放到第i行中的那个与前面i-l个皇后不在同一列或对角线上且f（x）值最大的空格中。启发式信息是某些领域里的知识信息，它能使计算机系统在这些知识信息提示以后可能采取的某些可能的动作或避免某些不可能的动作。现在学习的是第69页，共71页搜索方向的选择搜索方向的选择 搜索过程：在问题空间中找出从开始状态到目标状态的一条最好的或较好的路径。这种搜索可按两个方向进行：正向搜索：从初始状态朝着目标状态方向搜索；逆向搜索：从目标状态朝着初始状态方向搜索。将以上两种搜索方法结合起来，就产生了双向搜索 现在学习的是第70页，共71页搜索方向的选择搜索方向的选择l正向搜索 和 逆向搜索 S0S0SgSg现在学习的是第71页，共71页