一般搜索原理.ppt

1、第三章问题解决、问题推论：基于知识表现，进行机械思考，解决问题。 是知识利用的基础。 推论技术：解决问题(从初始状态到目标状态)的方法和方法。 与知识表现技术密切相关。 图检索方法：基于图的知识表示。 从相当于图中初始状态的起点到相当于目标状态的结束节点为止的路径搜索过程。 广度优先搜索、深度优先搜索.逻辑论证法：基于谓语逻辑和其他形式逻辑方法的知识表现。 不确定性推理非单调推理，推理方法：是否完善：推理算法：推理过程完善，可以找到解。 推论步骤：推论过程不完整，不一定能解决问题。 是否引进启发性知识：启发性推论：在推论过程中，利用关于问题的启发性知识，即解决问题的战略、技巧、技巧、解的特性和

2、规律的推断等实践经验和知识，加快推论过程，提高探索效率的非启发性推论：在解决问题的推论过程中，不使用启发性知识3.1一般的搜索原理、一般的图搜索策略1图搜索：求图中从初始状态到目标状态的路径。 2盲目检索：无信息检索，非启发性检索。 3检索策略： (1)相关数据结构和概念： OPEN表：用于存储刚生成的节点的CLOSED表：用于存储要扩展或扩展的节点的扩展：用定义的运算符或运算符操作节点，生成子节点的指针：子节点反向指向母节点的检索图：通过检索得到的图检索树：由检索图中的所有节点和反向指针构成的集合。 (2)一般图的搜索策略、不同的搜索方法是后续节点对应不同的扩展方式、OPEN表对应不同的排序

3、顺序。 宽度优先搜索是逐层进行的，在搜索下一层的节点之前，必须搜索本层的所有节点。 另外，扩展后的子节点被放置在OPEN表的末尾，OPEN表CLOSED表(1)、(2)、(3)、(4)、(5)、(7)、(1)、(2)、(3)进行深度优先搜索，首先新生成的节点被扩展。 OPEN表CLOSED表(1)、(2)、(3)、(1)、(4)、(3)、(3)、(1)、(2)、(4)、1、2、3、4、5、6、扩展的子节点位于OPEN表的开头，有界深度优先搜索：的深度优先搜索不完全，陷入无限分支4成本树搜索1成本树：把搜索扩展的成本视为输入。 2成本树的广度优先搜索：成本最小的节点选择扩展的节点。 3成本树的深

4、度优先搜索：从刚扩展的子节点中选择成本最小的节点。 例如：图5城市间的交通路线图，a是出发地，e是目的地，两城市间的交通费(成本)用图中的数字表示。 求a到e最小费用的交通路线。a、b、c、d、e、4、3、2、4、5、3、a、C1、B1、D1、E2、B2、D2、E1、C2、E3、E4、3、4、2、3、4、5、5、2、3、3.2启发式搜索有信息检索。 有序搜索：选择最想要的节点作为扩展的节点。 定义某个测量标准来决定希望的程度。 (1)决定扩展的下一个节点(2)生成哪个后续节点，或者生成哪个后续节点(3)从搜索树中决定舍弃或修剪的节点。 的双曲正切值。 典型的形式是f (x)=g (x) h (

5、x) f表示评估函数，f (x )表示节点x的评估函数值。 g (x )表示从初始节点实际支付给x的成本，h(x )是从节点x到目标节点的估计成本，利用问题本身的信息进行估计。按f值对OPEN表中的节点进行排序，然后选择具有最小/最大f值的节点作为下一个扩展节点。 秩序检索也称为优先检索。盲目搜索的一些方法也可以认为是有序搜索的特例。 宽度优先：深度小者优先；深度优先：深度深者优先；成本优先：成本小者优先。 局部优先搜索(深度):按成本大小对新扩展的节点进行排序全局优先搜索(范围):按成本大小对OPEN表中的所有节点进行排序。 对于f的选择，没有适当的期望测量，确保(1)在时间和空间上有权衡(

6、2)最佳解或任意解。 解的三种情况： (1)求最佳(最小成本)解(2)恰当的检索，找到不最佳的，好的检索。 但是，优先和最佳很难定义。 (3)只要找到解就行了。 例如，定义八数字象棋、评价函数： f (n)=d(n) w(n) d(n )是搜索树中的节点n的深度w(n )，用于计算节点n对应于目标状态而被偏移了的棋子的数量。 二、八、三、六、七、s(4)、A(6)、B(4)、C(6)、D(5)、E(5)、F(6)、G(6)、H(7)、I(5)、J(7)、K(5)、L(5)、M(7)、目标、1、2、3、4、5、6、1、2 首先，定义f *(n)=g *(n) h *(n )。 其中g *(n )

7、是从初始节点到节点n的最佳路径的成本，h *(n )是从n到目标节点的最小成本路径的成本。 定义评估函数。 f (n)=g (n) h (n )其中g是g*的估计值，h是h*的估计值。 g(n )可以是实际值，其中h(n )取决于关于问题区域的启发信息，并且h被称为启发函数。 A*算法的定义： (1)评价函数由f (x)=g (x) h (x )进行，(2)h(x)=h*(x )，h(x )是以h*(x )的下界(h*(x )的下界h(x )为启发函数的a算法，A*算法。 A*算法的特征： (1) A*算法以有限的步骤结束，能够找到最佳解(在满足h(x)=h*(x )的前提下，h(x )的值越

8、大越好。 f1(x )=g1(x ) h1(x ) f2(x )=g2(x ) h2(x ) a1*、A2*是分别以f1(x )、f2(x )为评价函数的A*算法，在所有非对象节点上都有h 1(x) h 2(x )时，进行A2*扩展3.3和树的搜索策略，1和树的一般搜索策略1中可识别的进程：决定父节点、祖节点是否可以解析。 2不可解决的标识过程(由可解决的节点定义) :确定不可解决的子节点是否可解决父节点、祖节点。 3解树：由识别初期节点和初期节点的可解的子节点构成。 4一般搜索过程：将开始、S0发送到OPEN表，将OPEN表的第一个节点nCLOSED表、扩展节点n及其子节点放在OPEN表中，

9、对每个子节点配置指向节点n的指针，将这些叶节点表示为可分解节点将这些叶节点表示为不可分解节点，应用不可分解的显示过程：n，n，y，y，(1)，(2)，(3)，成功退出，从OPEN表中删除具有可以释放的前辈的节点，失败退出，从OPEN表中删除具有不可释放的前辈的节点，(2) (3)、n，n，y，(1)，(1)，两个删除过程：2和或树的宽度优先搜索扩展节点n，将其子节点置于OPEN表的末尾，按每个子节点配置指向节点n的指针。 三和树的深度优先搜索扩展节点n，将其子节点放入OPEN表的标头中，按每个子节点构成指向节点n的指针。 有界深度优先搜索：如果节点n的深度=深度边界，则表示节点n是不可解的节点

10、。 四和或树的秩序检索是根据成本来确定检索路径的。 1成本计算(1)x是最终叶节点，h(x)=0； (2)假设x不能扩展，且非最终叶节点h(x)=(3)x的后续节点(y1，y2，yn )是逻辑，则设h(x)=minc (x，yi) h(yi) (4)x的后续节点(y1，y2，yn )是逻辑yi) h(yi ) )或h(x)=maxc (x，yi) h(yi) a，b，c，d，e，f，g，h，j，l，n，m，2，2，4，3，1，1，最大法： h左(A)=6 h右(a希望树t :在扩展搜索求解中，有可能成为最佳解树的一部分的扩展等待树，现在的成本最小的解树。 t是(1)包含初始节点的(2)节点x在

11、t中，或者后续节点中世代价值最小的节点也在t中的(3)节点x在t中，其全部和后续节点也在t中，找到3秩序搜索过程(1)希望树t (2)。h左(A)=9 *h右(A)=8 h(A)=8、h(F)=7 h(C)=11 *h左(A)=9 *h右(A)=12 h(A)=9、5游戏树的启发式搜索1游戏：智能竞争活动。 “两人零和，不是偶然，全部信息”两人零和：得分函数之和为零，三个结尾，我赢了，我输了，不是平局偶然：双方根据全部信息进行分析，赢数最大的方案全部信息：现在的结构和过去，双方都知道。 2游戏树：描述这样的过程的and或树(总是站在某一方的立场) (1)初始结构：初始节点(2)与或节点交替出现

12、(3)我方的扩展节点-或关系(可以选择值大的一方)与敌人的扩展节点-关系(对方对我方来说选择对自己最有利的方案。 3极大极小分析法的基本思想：预老师定义成为一定深度的博弈树的评价函数，计算末端节点的值(分数)，计算静态评价，并根据(逆推)父节点的逆推值的值选择适当的分支扩展的深度。 /一字象棋。 a、b比赛，以把自己的棋子放在第一线者为胜。 a方：这边先走。 定义评价函数： e(p)=在局面p上a侧有可能成为一线的局面p上b侧有可能成为一线的数量a获胜的局面p，e(p)=； a必负局面p，e (P)=各扩展两步。 b，1，4 -剪枝技术的基本思想：根据背推值的计算方法，或者中取大、中取小，在扩

13、张和计算过程中，可以切除不必要的分支，提高效率。 定义：值：有效或后续节点将当前子节点中的最大偏移值作为其下限，称为值。 节点偏移=； 值：有后续节点，以当前子节点的最小偏移值为上限，称为值。 节点偏移=；-剪枝： (1)剪枝：节点x的值不能降低其父节点的值，x以下的分支可以停止搜索，且x的逆算值为(2)剪枝：节点x的值不能提高其父节点的值，x以下的分支可以停止搜索，并且x的逆算值为，2 3.4归纳/消除演绎推理，逻辑推理1方式： (1)演绎推理：从一般到个别最典型的：三段论(2)归纳推理：从个别到一般，从多个特例归纳一般的结论(3)默认推理：知识不完全时，某个条件/事实/情况默认成立，推论变

14、得容易的2控制前向推理： (2)反向推理，混合推理双向推理3模式匹配：两个(知识)模式(谓语式、框架、语义网络)进行比较，完全一致或近似一致，是被称为可匹配的推理的重要过程。 2置换和1置换：项对变量的置换以变量、常数或函数进行置换，以使两个式匹配。 示例： P(x，f(y )，b )，S1=z/x，w/y P(x，f(y )，B) S1=P (z，f(w )，b )，替换复合：=t1/x1，t2/x2，tn /xn=u1/y1，u2/y2，un/yn=t1 /x1 在un/yn中，ti /xi是ti=xi ui/yi，x2，xn *替换是可合成的，不可交换： (PS1 ) S2=p (S1

15、S2 ) (S2 ) S3=S1 (S2 S3 ) s2s 1示例：=f(y)/x z/y=a/x，b/y，y/z=f (b例如，F=P (x，y，z )、P(x，f (a )、h(b) y、f (a )、z、h(b )、(1)定义：表达式集合F=F1、F2、Fn，如果存在一个替换，则称为F1=F2=Fn、f的一个合并，F1、F2、Fn 例如，F=P (x，y，f(y ) )，P (a，g(x，z)=g (a)/y，a/x，f (g(a)/z，(2)最常见的整合： s是f的任一整合，g是其一整合，对任何s都存在取代s，S=g S或fs=。 (4)求最常见的整合算法：思想：从最初的差异集，求项的变量的置换。 (a) k=0，Fk=F，gk=； 如果(b)f的表达式匹配，则该算法停止，找到(c)fk的最常见集合Dk，其中Dk是元素ak，tk，tk是项，ak是参数，并且ak没有出现在tk中，则g k 1=g