《人工智能》搜索技术.pptx

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,2021/2/8,#,第四章 搜索技术,状态空间法,问题归约法,博弈树搜索,局部搜索,How to find the best path in game?,迷宫问题,s-s s s s,s s-s-s-s,s-s-s-s s,s s s s s,s-s-s-s-s,S0,Sg,搜索的挑战组合爆炸,魔方问题,博弈问题,皇后问题,行商问题,排课问题（调度问题）,背包问题,数码问题,1,2,3,8,4,5,6,7,1,2,3,8,4,5,6,7,（目标状态）,（初始状态,）,八数码难题（8-puzzle problem）,4,2,6,1,8,3,5,7,4.1 状态图概念,状态图的概念,状态图(状态空间图)实际上是一类问题的抽象表示。,许多智力问题(八数码问题、梵塔问题、旅行商问题、八皇后问题、,农夫过河问题,等)。,实际问题（如路径规划、定理证明、演绎推理、机器人行动规划等）都可以归结为在某一状态图中寻找目标或路径的问题。,农夫过河问题,有一个农夫带一条狼、一只羊和一棵白菜过河。如果没有农夫看管，则狼要吃羊，羊要吃白菜。但是船很小，只够农夫带一样东西过河。问农夫该如何解此难题？,农夫过河问题,状态空间法表示,以向量（人，狼，羊，菜）表示状态，其中每个变元可取0或1，取0表示在左岸（出发点），取1表示在右岸,初态是：（0，0，0，0）,终态是：（1，1，1，1）,非法中间状态有：,（0，0，1，1），（0，1，1，0），（0，1，1，1），（1，1，0，0），（1，0，0，1），（1，0，0，0）。,（1，0，0，1）,（0，0，0，0）,（1，0，1，0）,（1，1，0，0）,（0，0，1，0）,（1，1，1，0）,（1，0，1，1）,（0，1，1，0）,（0，0，1，1）,（人，狼，羊，菜）,（0，0，0，1）,（1，1，0，1）,（0，1，0，1）,（1，1，1，1）,4.2 状态空间法,问题的,状态空间,表示(状态图表示),状态空间的三元组(S,O,G)表示.,S:初始状态集合;O:操作集合;,G:目标状态集合,状态空间的搜索策略(状态图搜索),广度优先搜索,深度优先搜索,启发式搜索,状态空间表示的概念,例如下棋、迷宫及各种游戏。,Original,State,Middle,State,Goal,State,三数码难题,1,2,3,1,2,3,1,2,3,3,1,2,3,1,2,3,1,2,初始棋局,目标棋局,1,2,3,8,4,5,6,7,1,2,3,8,4,1,2,3,8,4,5,6,7,4,1,2,3,8,5,6,7,1,2,3,8,4,1,2,3,8,4,5,6,7,1,2,3,8,4,5,6,7,1,2,3,8,4,5,6,7,6,7,8,9,10,11,12,13,1,2,3,8,4,5,6,7,5,6,7,5,6,7,1,1,2,3,8,4,5,6,7,1,2,3,8,4,5,6,7,1,2,3,8,4,5,6,7,1,2,3,8,4,5,6,7,2,3,4,5,八数码难题的宽度优先搜索树,1,3,4,5,6,1,2,3,8,4,5,6,7,1,2,3,8,4,5,6,7,1,2,3,8,4,5,6,7,1,2,3,8,4,5,6,7,1,2,3,8,4,5,6,7,23,24,25,26,27,1,2,3,6,7,8,22,1,2,3,8,4,5,6,7,1,2,3,8,4,5,6,7,1,2,3,8,4,5,6,7,1,2,3,8,4,5,6,7,1,2,3,8,4,5,6,7,1,2,3,8,4,5,6,7,1,2,3,8,4,5,6,7,14,15,16,17,18,19,20,21,1,2,3,8,4,5,6,7,状态图搜索,图搜索,是指在状态图中寻找目标或路径的搜索。,所谓,搜索,，顾名思义，就是从初始节点出发，沿着与之相连的边试探地前进，寻找目标节点的过程(也可以反向进行)。,问题,状态图,搜索,解,解是由初始状态到目标状态的路径,状态图搜索相关问题,状态选择,解的性质：存在、分布、质量,搜索策略,图搜索策略,图搜索控制策略一种在状态图中寻找路径的方法。图中每个节点对应一个状态，每条连线对应一个操作符。,图搜索涉及两个主要数据结构：,op,en表,closed表,OPEN 表,OPEN表,是一种动态数据结构，专门登记当前待考查（待访问）的节点，也叫未扩展节点表。,节点,父节点编号,OPEN表,open表中，每个节点信息还包括指向父节点的返回指针（即父节点地址）,CLOSED 表,Closed表是一种动态数据结构，记录访问过的节点，也叫已扩展节点表，其初始为空表。,编号,节点,父节点编号,CLOSED表,开始,把S放入OPEN表,OPEN表为空表？,把第一个节点(n)从OPEN表移至CLOSED表,n为目标节点吗？,把n的后继节点放入OPEN表的末端，提供返回节点n的指针,修改指针方向,重排OPEN表,失败,成功,图搜索过程框图,是,是,否,否,搜索策略即体现在这里,按搜索轨迹分类,图式搜索,：搜索过程中，搜索路径允许形成回路。,树式搜索,：搜索过程中，搜索路径不允许形成回路。,线式搜索,：扩展节点每次只扩展一个节点。,S,G,S,G,搜索树的概念,一个可以搜索出某个可行解的问题，如“农夫、白菜、羊、狼”和“八数码难题”等，虽然从表面上看上去和“树”这种结构无关，但是整个搜索过程中的可能试探点所行成的搜索空间总可以对应到一颗,搜索树,上去。,将各类形式上不同的搜索问题抽象并统一成为搜索树的形式，为算法的设计与分析带来巨大的方便,。,（1，0，0，1）,（0，0，0，0）,（1，0，1，0）,（1，1，0，0）,（0，0，1，0）,（1，1，1，0）,（1，0，1，1）,（0，1，1，0）,（0，0，1，1）,（人，狼，羊，菜）,（0，0，0，1）,（1，1，0，1）,（0，1，0，1）,（1，1，1，1）,由于搜索具有探索性，所以要提高搜索效率(尽快地找到目标节点)，或要找,最佳路径,(最佳解)就必须注意搜索策略。,对于状态图搜索，已经提出了许多策略，它们大体可分为,盲目搜索,（bland search)和,启发式搜索,（heuristic search）两大类。,盲目搜索,是无向导搜索。,启发式搜索,是有向导搜索，即利用启发信息（函数）引导去寻找问题解。,搜索策略分类,盲目搜索,盲目搜索,又叫做无信息搜索，一般只适用于求解比较简单的问题。,种类：,宽度优先搜索,深度优先搜索,等代价搜索,图搜索策略,宽度优先,深度优先,启发式搜索,一种在图中寻找路径的方法。,宽度优先搜索策略,优先搜索状态空间中离初始状态近的节点(状态,特点:具有完备性,占用空间,搜索算法,数据结构:,OPEN表:,先进先出队列,存放待扩展的节点.,节点(状态)父节点编号(返回指针),CLOSED表:存放已被扩展过的节点.,编号 节点 父节点编号,开始,把S放入OPEN表,OPEN表为空表？,把第一个节点(n)从OPEN表移至CLOSED表,是否有后继节点,为目标节点？,扩展n，把n的后继节点放入OPEN表的,末端,，提供返回节点n的指针,失败,成功,宽度优先算法框图,是,否,是,否,算法,否,宽度优先搜索算法,Step1:把初始节点S0放入OPEN表中;,Step2:若OPEN表为空,则搜索失败,退出.,Step3:移出OPEN表中第一个节点N放入CLOSED表 中,并标以顺序号n;,Step4:若目标节点Sg=N,则搜索成功,结束.,Step5:若N不可扩展,则转Step2;,Step6:扩展N,将生成的一组子节点配上指向N的指针后,放入OPEN表尾部,转 Step2;,例子,八数码难题（8-puzzle problem,）,1,2,3,8,4,5,6,7,1,2,3,8,4,5,6,7,（目标状态）,（初始状态,）,规定：,将牌移入空格的顺序为：从空格左边开始顺时针旋转。不许斜向移动，也不返回先辈节点。,从图可见，要扩展26个节点，共生成26个节点之后才求得解（目标节点）,。,1,2,3,8,4,5,6,7,1,2,3,8,4,1,2,3,8,4,5,6,7,4,1,2,3,8,5,6,7,1,2,3,8,4,1,2,3,8,4,5,6,7,1,2,3,8,4,5,6,7,1,2,3,8,4,5,6,7,6,7,8,9,10,11,12,13,1,2,3,8,4,5,6,7,5,6,7,5,6,7,1,1,2,3,8,4,5,6,7,1,2,3,8,4,5,6,7,1,2,3,8,4,5,6,7,1,2,3,8,4,5,6,7,2,3,4,5,图 八数码难题的,宽度优先,搜索树,1,3,4,5,6,1,2,3,8,4,5,6,7,1,2,3,8,4,5,6,7,1,2,3,8,4,5,6,7,1,2,3,8,4,5,6,7,1,2,3,8,4,5,6,7,23,24,25,26,27,1,2,3,6,7,8,22,1,2,3,8,4,5,6,7,1,2,3,8,4,5,6,7,1,2,3,8,4,5,6,7,1,2,3,8,4,5,6,7,1,2,3,8,4,5,6,7,1,2,3,8,4,5,6,7,1,2,3,8,4,5,6,7,14,15,16,17,18,19,20,21,1,2,3,8,4,5,6,7,宽度优先搜索(,Breadth-First Strategy),新的节点被插入到栈OPEN的,后部,1,2,3,4,5,OPEN=(1),CLOSED=(),6,7,8,9,10,11,12,13,14,15,宽度优先搜索(,Breadth-First Strategy),新的节点被插入到栈OPEN的,后部,1,2,3,4,5,OPEN=(2,3),CLOSED=(1),6,7,8,9,10,11,12,13,14,15,宽度优先搜索(,Breadth-First Strategy),新的节点被插入到栈OPEN的,后部,1,2,3,4,5,OPEN=(3,4,5),CLOSED=(1,2),6,7,8,9,10,11,12,13,14,15,宽度优先搜索(,Breadth-First Strategy),新的节点被插入到栈OPEN的,后部,1,2,3,4,5,OPEN=(4,5,10,11),CLOSED=(1,2,3),6,7,8,9,10,11,12,13,14,15,宽度优先搜索(,Breadth-First Strategy),新的节点被插入到栈OPEN的,后部,1,2,3,4,5,OPEN=(5,10,11,6,7),CLOSED=(1,2,3,4),6,7,8,9,10,11,12,13,14,15,宽度优先搜索(,Breadth-First Strategy),新的节点被插入到栈OPEN的,后部,1,2,3,4,5,OPEN=(10,11,6,7,8,9),CLOSED=(1,2,3,4,5),6,7,8,9,10,11,12,13,14,15,宽度优先搜索(,Breadth-First Strategy),新的节点被插入到栈OPEN的,后部,1,2,3,4,5,OPEN=(11,6,7,8,9,12,13,),CLOSED=(1,2,3,4,5,10),6,7,8,9,10,11,12,13,14,15,深度优先搜索策略,新节点优先扩展,直到达到一定的深度限制.若找不到目标或无法在扩展时,回溯到另一节点继续扩展.,特点:需要深度限制,需要回溯控制,省空间,探索算法:,数据结构:,OPEN表:,后进先出队列,存放待扩展的节点.,CLOSED表:存放已被扩展过的节点.,除扩展后的子节点应放入到OPEN表的首部以外,与宽度优先算法一样.,深度优先算法框图,算法,开始,把S放入OPEN表,OPEN表为空表？,把第一个节点(n)从OPEN表移至CLOSED表,是否有后继节点,为目标节点？,扩展n，把n的后继节点放入OPEN表的,前端,，提供返回节点n的指针,失败,成功,是,否,是,否,深度优先搜索算法,Step1:把初始节点S0放入OPEN表中;,Step2:若OPEN表为空,则搜索失败,退出.,Step3:移出OPEN中第一个节点N放入CLOSED表 中,并标以顺序号n;,Step4:若目标节点Sg=N,则搜索成功,结束.,Step5:若N不可扩展,则转Step2;,Step6:扩展N,将生成的一组子节点配上指向N的指针后,放入OPEN表首部,转 Step2;,深度优先搜索(,Depth-First Strategy),新的节点被插入到栈OPEN的,前部,1,2,3,4,5,OPEN=(1),CLOSED=(),6,7,8,9,10,11,12,13,14,15,Depth-First Strategy,新的节点被插入到栈OPEN的,前部,1,2,3,4,5,OPEN=(2,3),CLOSED=(1),6,7,8,9,10,11,12,13,14,15,Depth-First Strategy,新的节点被插入到栈OPEN的,前部,1,2,3,4,5,OPEN=(4,5,3),CLOSED=(1,2),6,7,8,9,10,11,12,13,14,15,Depth-First Strategy,新的节点被插入到栈OPEN的,前部,1,2,3,4,5,CLOSED=(1,2,4),6,7,OPEN=(6,7,5,3),8,9,10,11,12,13,14,15,Depth-First Strategy,新的节点被插入到栈OPEN的,前部,1,2,3,4,5,6,7,8,9,10,11,CLOSED=(1,2,4,6),OPEN=(7,5,3),12,13,14,15,Depth-First Strategy,新的节点被插入到栈OPEN的,前部,1,2,3,4,5,6,7,8,9,10,11,CLOSED=(1,2,4,6,7),OPEN=(5,3),12,13,14,15,Depth-First Strategy,新的节点被插入到栈OPEN的,前部,1,2,3,4,5,6,7,8,9,10,11,CLOSED=(1,2,4,5,6,7,),OPEN=(8,9,3),12,13,14,15,Depth-First Strategy,新的节点被插入到栈OPEN的,前部,1,2,3,4,5,6,7,8,9,10,11,CLOSED=(1,2,4,5,6,7,8),OPEN=(9,3),12,13,14,15,Depth-First Strategy,新的节点被插入到栈OPEN的,前部,1,2,3,4,5,6,7,8,9,12,10,11,13,14,15,CLOSED=(1,2,4,5,6,7,8,9),OPEN=(3),Depth-First Strategy,新的节点被插入到栈OPEN的,前部,1,2,3,4,5,6,7,8,9,12,10,11,13,14,15,CLOSED=(1,2,4,5,6,7,8,9,3),OPEN=(10,11),Depth-First Strategy,新的节点被插入到栈OPEN的,前部,1,2,3,4,5,6,7,8,9,10,11,CLOSED=(1,2,4,5,6,7,8,9,3,10),12,13,14,15,OPEN=(12,13,11),代价树搜索,代价树,：搜索树中每条连接弧线上的有关代价,表示时间、距离等花费。,代价树搜索（等代价搜索）,：,是宽度优先搜索的一种推广，不是沿着等长度路径断层进行扩展，而是沿着等代价路径断层进行扩展。,*若所有连接弧线具有相等代价，则简化为宽度优先搜索算法。,算法使用符号,c(i,j)：,把从节点i到其后继节点j的连接弧线代价记为,c(i,j),g(i)：,把从起始节点S到任一节点i的路径代价记为,g(i).,在搜索树,（非循环路径）,上，假设g(i)是从起始节点S到节点i的最少路径上的代价。,等代价搜索方法以g(i)的递增顺序扩展其节点。,开始,把S放入OPEN表,OPEN,表为空表？,把具有最小,g(i),值的节点,i,从,OPEN,表移至,CLOSED,表,是否有后继节点,为目标节点？,失败,成功,等代价搜索算法框图,是,否,是,否,令,g(s)=0,S是否目标节点,？,是,成功,否,开始,把S放入OPEN表,OPEN,表为空表？,把具有最小,g(i),值的节点,i,从,OPEN,表移至,CLOSED,表,是否有后继节点,为目标节点？,失败,成功,是,是,否,令,g(s)=0,S是否目标节点,？,是,成功,开始,把S放入OPEN表,OPEN,表为空表？,把具有最小,g(i),值的节点,i,从,OPEN,表移至,CLOSED,表,是否有后继节点,为目标节点？,失败,成功,是,是,否,令,g(s)=0,S是否目标节点,？,是,成功,扩展i，计算其后继节点j的g(j)，并把后继节点放入OPEN表,开始,把S放入OPEN表,OPEN,表为空表？,把具有最小,g(i),值的节点,i,从,OPEN,表移至,CLOSED,表,是否有后继节点,为目标节点？,失败,成功,是,是,否,令,g(s)=0,S是否目标节点,？,是,成功,等代价搜索算法,（1）把起始节点放到未扩展节点表OPEN中。如果此起始节点为一目标节点，则求得一个解；否则令g（S）=0。,（2）如果OPEN是个空表，则没有解而失败退出。,（3）从OPEN 表中选择一个节点i，使其g（i）为最小。如果有几个节点都合格，那么就要选择一个目标节点作为节点 i（要是有目标节点的话）；否则，就从中选一个作为节点i。把节点i从OPEN表移至扩展节点表CLOSED中。,（4）如果节点i为目标节点，则求得一个解。,（5）扩展节点i。如果没有后继节点，则转向第（2）步。,（6）对于节点i的每个后继节点j，计算,g（j）=g（i）+c（i,j），,并把所有后继节点j放进OPEN表。提供回到节点i的指针。,（7）转向第（2）步。,宽度优先,d=1,d=2,d=3,d=4,宽度优先搜索：,沿着等长度,路径断层进行扩展,g1,g2,g3,g4,等代价,搜索,等代价搜索：沿,等代价路径,断层进行扩展,比较宽度优先搜索与等代价搜索,A,D,B,E,C,F,G,S,3,4,4,4,5,5,4,3,搜索树（非循环路径）,2,S,A,D,B,D,E,A,C,E,E,B,B,F,D,F,B,F,C,E,A,C,G,G,C,G,F,G,3,3,3,3,3,2,2,2,4,4,4,4,4,4,4,4,4,4,4,4,5,5,5,5,5,5,等代价搜索算法,S,A,D,B,D,A,E,E,B,B,F,B,F,C,E,A,C,G,G,G,F,C,3,4,4,5,5,5,2,5,4,3,3,4,7,8,9,6,10,11,C,E,D,F,G,4,5,11,12,13,13,13,4,在每一步,选择具有最低累计权值的点进行扩展,启发式搜索,盲目搜索的问题：,“组合爆炸”,利用问题的某些控制信息(如解的特征)来引导搜索.这种控制信息称为搜索的,启发信息,.,利用启发式信息定义节点的,启发函数,h(n),特点:深度优先,效率高,无回溯,但不能保证得到最佳解 。,探索算法:,全局择优搜索,(最好优先搜索),局部择优搜索,数据结构：OPEN表、,CLOSED表,启发信息,启发式搜索就是利用启发性信息进行制导的搜索。,启发性信息就是有利于尽快找到问题之解的信息。,按其用途划分，启发性信息一般可分为以下三类：,(1),用于扩展节点的选择,，即用于决定应先扩展哪一个节点，以免盲目扩展。,(2),用于生成节点的选择,，即用于决定应生成哪些后续节点，以免盲目地生成过多无用节点。,(3),用于删除节点的选择,，即用于决定应删除哪些无用节点，以免造成进一步的时空浪费。,重排OPEN表，使搜索沿某个被认为最有希望的路径扩展。,应用这种排序过程，需要某些估算节点“,希望,”的量度。,用来估算节点希望程度的量度，叫做,估价函数（evaluation function），有时也叫作启发函数,。,一个节点的“希望”（promise）有几种不同 的定义方法。,在状态空间问题中，一种方法是估算目标节点到此节点的距离；,估算全路径的长度或难度（包括此节点）。,我们用符号f来标记估价函数，用,f（n）,表示节点n的估价函数值。,启发函数,如何定义一个估价（启发）函数呢？估价（启发）函数并无固定的模式，需要具体问题具体分析。通常可以参考的思路有：,（1）一个节点到目标节点的距离或差异的度量；,（2）一个节点处在最佳路径上的概率；,（3）或者根据经验的主观打分。,启发函数,八数码难题（,8-puzzle）,f1(T)=恰好正确地处在目标状态的字码数目:,1,3,2,4,7,6,5,8,f1,=4,从实用角度，计算与目标的距离更有实际意义！,f2,=4,1,3,2,4,7,6,5,8,f2(T)=没有处在目标状态的字码数目（相当于粗略地给出了当前状态与目标的距离）,1,2,3,8,4,7,6,5,目标：,f3(T)=不在目标位置的字码距离目标位置水平距离和垂直距离之和。,该函数给出了一个更好的距离评估,f2,=1+1+2+2=6,1,3,2,4,7,6,5,8,1,2,3,8,4,7,6,5,目标：,启发式搜索算法,启发式搜索要用启发函数来导航，其搜索算法就要在状态图一般搜索算法基础上再增加启发函数值的计算与传播过程，并且由启发函数值来确定节点的扩展顺序。两种策略:,局部择优搜索,扩展节点N后仅对N的子节点按启发函数值大小以升序排序，再将它们依次放入OPEN表的,首部。,全局择优搜索,在OPEN表中保留所有已生成而未考察的节点，并用启发函数h(x)对它们全部进行估价，从中选出最优节点进行扩展，而不管这个节点出现在搜索树的什么地方。,全局择优搜索算法,Step1:把初始节点S0放入OPEN表中,计算h(S0);,Step2:若OPEN表为空,则搜索失败,退出.,Step3:移出OPEN中第一个节点N放入CLOSED表 中,并标以顺序编号n;,Step4:若目标节点Sg=N,则搜索成功,结束.,Step5:若N不可扩展,则转Step2;,Step6:扩展N,计算每个子节点的函数值h(x),将所有子节点配上指向N的返回指针后放入OPEN表中,再,按函数值的升序重新排序OPEN表中的节点,转 Step2;,全局择优搜索例子,九宫重排问题,定义评价函数;,h(n):目标格局与现格局(Sn)相比,位置不同的牌数,.,初始格局S0 目标格局Sg,2 8 3 1 2 3,1 4 =8 4,7 6 5 7 6 5,h(S0)=3,局部择优搜索算法,Step1:把初始节点S0放入OPEN表中,计算h(S0);,Step2:若OPEN表为空,则搜索失败,退出.,Step3:移出OPEN中第一个节点N放入CLOSED表 中,并标以顺序编号n;,Step4:若目标节点Sg=N,则搜索成功,结束.,Step5:若N不可扩展,则转Step2;,Step6:扩展N,计算每个子节点的函数值h(x),并将所有子节点按,函数值的升序排序后,配上指向N的返回指针放入OPEN表的首部,转 Step2;,局部搜索算法,特点：,从单独的一个当前状态出发，通常只移动到与之相邻的状态，并且不保留解的路径。,优点,：,需要很少的内存,经常能在很大或无限的状态空间中找到合理的解,爬山法（Hill climbing）,一种基本的局部启发式搜索方法,基本算法：扩展节点N后仅对N的子节点按启发函数值大小以升序排序，再将选择启发函数值,最小的节点,放入OPEN表的,首部。（,启发函数值越小离目标越近,）,相当于深度优先算法+启发式搜索,线式搜索,，不能回溯,向目标值增加的方向持续移动,启发式搜索:A算法,评价函数,f(x)=g(x)+h(x),，表示通过节点x的估计代价值。,n,m,S,G,g(n),g(m),h(n),h(m),比较f(n)和f(m)大小，决定节点搜索顺序，即在OPEN表中的顺序,启发式搜索:A算法,评价函数,f(x)=g(x)+h(x),当,f(x)=g(x)时，,为宽度优先搜索,当,f(x)=1/g(x)时，,为深度优先搜索,当,f(x)=h(x)时，,为全局优先搜索,n,m,S,G,g(n),g(m),h(n),h(m),启发式搜索:A算法,评价函数的一般形式:f(n)=g(n)+h(n),g(n):从S0到Sn的实际代价(搜索的横向因子),h(n):从N到目标节点的估计代价,称为,启发函数,(搜索的纵向因子);,特点:效率高,无回溯,搜索算法,OPEN表:存放待扩展的节点,.,CLOSED表:存放已被扩展过的节点.,启发式搜索:A算法,Step1:把附有计算f(S0)初始节点S0放入OPEN表中;,Step2:若OPEN表为空,则搜索失败,退出.,Step3:移出OPEN中第一个节点N放入CLOSED表中,并标以顺序编号n;,Step4:若目标节点Sg=N,则搜索成功,结束.,Step5:若N不可扩展,则转Step2;,Step6:扩展N,生成一组附有f(x)的子节点,作完以下处理后,将余下子节点配上指向N的返回指针后放入OPEN表中,再,按函数值的升序重新排序OPEN表中的节点,转 Step2;,删除重复节点和修改返回指针.,八数码难题（8-puzzle problem）,1,2,3,8,4,5,6,7,（目标状态）,1,2,3,8,4,5,6,7,（初始状态）,A算法的应用,八数码难题:,评价函数,简单的评价函数,h(n)=d(n)+W(n),其中：d(n)是搜索树中节点n的深度；W(n)用来计算对应于节点n的数据库中错放的棋子个数。,初始棋局f值等于0+4=4,1,2,3,8,4,5,6,7,（初始状态）,5,7,2,3,4,5,1,2,3,8,4,5,6,7,1,2,3,8,4,5,6,7,1,2,3,8,4,5,6,7,1+3,1+5,1+5,1,1,2,3,8,4,5,6,7,1,2,3,8,4,5,6,7,1,2,3,8,4,5,6,7,2+4,2+3,2+3,1,2,3,8,4,5,6,7,1,2,3,8,4,5,6,7,3+2,3+4,1,2,3,8,4,5,6,7,1,2,3,8,4,5,6,7,3+3,3+4,1,2,3,8,4,5,6,7,4+1,8,1,3,2,4,5,6,7,1,2,3,8,4,5,6,7,5+0,5+2,八数码难题的搜索树,1,2,3,8,4,6,0+4,7,5,启发式搜索:A*算法,评价函数的一般形式:,f(n)=g(n)+h(n)且 h(n)=h*(n),g(n),h(n):定义同,A算法,;,h*(n):从N到目标节点的最短路径;,称此时的A算法为,A*算法,.,A*算法的特征,:,A*是可采纳的:,只要最短路径存在,就一定能找出,.,如果有 h1(n)=h2(n)=h*(n),那么h2比h1展开更少的节点.,广度优先搜索是当h(n)=0时的A*算法的特例.,启发式搜索:A*算法,评价函数,f(x)=g(x)+h(x),(当h(n)=h*(n),n,S,G,g(n)=g*(n),h(n)=h*(n),A*算法要求保守估计：f(n)0。,4)：h(n)=h*(n),为什么A*算法低估h值,在A*算法中，对所有的x存在h(x)h*(x)（,低估),在A*算法中,只有对h值低估才能获得优化的搜索性能,为什么A*算法低估h值,举例：,S,A,D,F,B,E,H,C,G,I,1,1,1,1,1,1,1,1,1,1,1,红色值表示,真实的,剩余代价,3,2,1,2,1,3,2,1,3,2,1,5,4,4,3,2,多估,在多估情况下：,S,A,D,F,1+3,1+5,1+4,B,2+2,A,B,C,3+1,C,G,4,并不是优化路径,!,为什么A*算法低估h值,举例：,3,2,S,A,D,F,B,E,H,C,G,I,1,1,1,1,1,1,1,1,1,1,1,3,2,2,1,1,1,红色值表示,真实的,剩余代价,如果h被低估:,S,A,D,F,1+1,1+2,1+3,1,0,0,2,3,1,2,1,低估,A,B,2+0,C,3+0,B,G,4,G,C,D,E,E,3!,2+1,f1,f2,f3,f4,A*,A*算法沿f函数进行扩展,启发式搜索算法A*,Step1:把初始节点S0放入OPEN表中;,Step2:若OPEN表为空,则搜索失败,退出.,Step3:移出OPEN中第一个节点N放入CLOSED表 中,并标以顺序号n;,Step4:若目标节点Sg=N,则搜索成功,结束.,Step5:若N不可扩展,则转Step2;,Step6:扩展N,生成一组子节点,对这组子节点作如下处 理后,放入OPEN表,按评价函数的升序重新排序 OPEN表,转 Step2;,删除重复节点和修改返回指针处理.,八数码难题:,h1(T),0 启发函数为0,注意,:h3(T),h2(T),h1(T),h2,=4,1,3,2,4,7,6,5,8,h2(T)=,没有处在目标状态的字码数目,h3,=1+1+2+2=6,1,3,2,4,7,6,5,8,h3(T)=,不在目标位置的字码距离目标位置水平距离和垂直距离之和。,1,2,3,8,4,7,6,5,目标：,曼哈顿距离,八数码难题举例,2 8 3,1 6 4,7,5,2 8 3,1 6 4,7 5,2 8 3,1,4,7,6 5,2 8 3,1 6 4,7 5,2 8 3,6 4,1 7 5,2 8 3,1 4,7,6 5,2,3,1,8,4,7,6 5,2 8 3,1 4,7,6 5,2 8 3,1 6,7 5,4,8 3,2,6 4,1 7 5,2 8 3,6,4,1 7 5,8 3,2,1 4,7,6 5,2 8 3,7,1 4,6 5,2 3,1,8,4,7,6 5,2 8 3,1 4,5,7,6,2 8 3,1,6,7 5,4,2 3,1,8,4,7,6 5,2 8,1 4,3,7,6 5,2 8,1 6 3,7 5,4,h1=0,0,1,1,1,2,2,2,2,2,3,3,3,3,3,3,3,3,3,3,h2=错误数目,0+4,1+5,1+3,1+5,2+3,2+3,2+4,3+3,3+4,3+2,Not,selected,h3=,曼哈顿距离,0+5,1+6,1+4,1+6,2+5,2+3,2+5,Robot navigation,Cost of one horizontal/vertical step=1,Cost of one diagonal step=,2,f(N)=g(N)+h(N),with h(N)=,距离目标位置水平距离和垂直距离之和,Robot Navigation,Robot Navigation,0,2,1,1,5,8,7,7,3,4,7,6,7,6,3,2,8,6,4,5,2,3,3,3,6,5,2,4,4,3,5,5,4,6,5,6,4,5,f(N)=h(N),with h(N)=,距离目标位置水平距离和垂直距离之,Robot Navigation,0,2,1,1,5,8,7,7,3,4,7,6,7,6,3,2,8,6,4,5,2,3,3,3,6,5,2,4,4,3,5,5,4,6,5,6,4,5,f(N)=h(N),with h(N)=,距离目标位置水平距离和垂直距离之,7,0,Robot Navigation,f(N)=g(N)+h(N),with h(N)=,距离目标位置水平距离和垂直距离之和,0,2,1,1,5,8,7,7,3,4,7,6,7,6,3,2,8,6,4,5,2,3,3,3,6,5,2,4,4,3,5,5,4,6,5,6,4,5,7+0,6+1,6+1,8+1,7+0,7+2,6+1,7+2,6+1,8+1,7+2,8+3,7+2,6+3,6+3,5+4,5+4,4+5,4+5,3+6,3+6,2+7,8+3,7+4,7+4,6+5,5+6,6+3,5+6,2+7,3+8,4+7,5+6,4+7,3+8,4+7,3+8,3+8,2+9,2+9,3+10,2+9,3+8,2+9,1+10,1+10,0+11,搜索算法小结,树搜索-盲目搜索-广度优先搜索,-深度优先搜索-有界深度优先,-代价树搜索,-启发式搜索-全局择优搜索(最好优先),-局部择优搜索(爬山法),-A算法(基于:f(n)=g(n)+h(n),A*算法(最佳搜索:h(n)8 4,7 5 3 7 6 5,请针对TSP问题，提出启发式搜索策略，并对搜索效率进行分析？,4.3 问题归约法,问题归约的概念,问题归约的描述:三元组(S0,O,P)表示.,S0:初始问题;P:,本原问题,集合,O:操作算子集;将问题化成若干子问题.,问题归约的最终目标:原问题=本原问题,状态空间法是问题归约法的特例.,问题归约的与或图表示,与或图表示,A,A,C6,C5,C4,C3,C2,C1,C6,C5,C4,C3,C2,C1,m1,m2,或节点,与节点,叶节点(或称:端节点),3连接弧,节点的可解性判别,A,C6,C5,C4,C3,C2,C1,m1,m2,或节点,与节点,可解节点的判别条件,叶节点可解,或节点可解当且仅当至少有一个子节点可解.,与节点可解当且仅当所有子节点都可解,.,不可解节点的判别条件,没有子节点的非终止节点,或节点不可解当且仅当所有子节点不可解,.,与节点不可解当且仅当至少有一个子节点不可解,.,与或图的搜索,A,C6,C5,C4,C3,C2,C1,m1,m2,或节点,与节点,解图,求解与或图问题就是在与或图中搜索,解图,(或,解树,)的问题.,解图是原与或图的一个子图(与图),搜索策略:无信息搜索与启发式搜索,搜索过程:标记初始节点为可解节点(成功)或不可解节点(失败)的过程.,搜索算法:,与或树的搜索算法,1,Step1:S0=OPEN表,Step2:OPEN-N-CLOSED(n),Step3:如N可扩展:,扩展N=OPEN,标记可解节点,=CLOSED,如初始节点可解,搜索成功,结束.,删去OPEN中有可解先辈的节点.,Step4:N不可扩展:,标记不可解节点,.如初始节点不可解,搜索失败,退出.,删去OPEN中有不可解先辈的节点.,To Step2.,5,4,A,t2,t3,t4,2,t1,B,3,问题归约的例子,积分问题的与或树,三阶梵塔问题的与或树,几何定理证明的与或树,4.4 博弈树搜索,博弈树的概念,博弈:下棋,打牌等一类竞争性智力活动.最简单的是“,二人零和,全信息,非偶然,”博弈.,博弈树:描述博弈过程的与或树.,特点:或与节点分层交替出现;,搜索空间指数增长,只能前推几步,极大极小过程,剪枝技术,(7,min),(6,1,max)(5,2,max)(4,3,max),(5,1,1,min)(4,2,1min)(3,2,2,min)(3,3,1,min),(4,1,1,1,max)(3,2,1,1,mix)(2,2,2,1,max),max 失败,(3,1,1,1,1,min)(2,2,1,1,1,min),min失败,(2,1,1,1,1,1,max),max失败,分币原则:每次要将一堆分为币数不等的两堆,.,胜负标准:交替分钱币,谁不能再分谁输.,分钱币游戏的博弈树,结论:,?,(,7,min,),(,6,1,max,)(,5,2,max,)(,4,3,max),(,5,1,1,min,)(,4,2,1min,)(,3,2,2,min,)(,3,3,1,min,),(,4,1,1,1,max,)(,3,2,1,1,max,)(,2,2,2,1,max,),max失败,(,3,1,1,1,1,min,)(,2,2,1,1,1,min),min失败,(,2,1,1,1,1,1,max,),max失败,.,max 可解节点,min可解节点,分钱币游戏的博弈树,结论:,max必胜,钱币为8，9时，结论如何？,钱币为10 时，结论如何？,钱币为 x