第五章-搜索策略资料.ppt

第5章探索策略，5.1概要5.2状态空间探索5.3和树探索，2，探索分为盲目探索和启发式探索。 盲搜索可根据预定控制策略执行搜索，并且不使用在搜索期间获取的中间信息来改进控制策略。 启发式探索在探索中添加有关问题的启发性信息，指导探索向最有前途的方向前进，加快问题的解决过程，找到最佳解。 3、问题解决过程可视为探索过程。 状态空间表现是表现问题及其探索过程的方法。 这是人工智能中最基本的形式化方法。 状态空间用“状态”和“运算符”表示问题。 状态用于描述解决问题过程中不同时刻的情形，且具有数据结构，当每一分量的值确定时，通常SK=(Sk0，Sk1，)获得具体状态。 运算符称为运算符，它将状态的某些分量从一个状态改变为另一个状态。 在生成表达式系统中，生成表达式规则是运算符。 状态空间将问题的所有状态和所有可用运算符组成的集合称为问题的状态空间，通常以一个三维组来表示： (s，f，g )其中s是问题的所有初始状态的集合，f是运算符的集合，g是目标状态的集合。 状态空间的图示形式称为状态空间图。 4、SK=(Sk0，Sk1)表示问题的状态，SK0中金属片a所在的柱编号，Sk1中金属片b所在的柱编号，全部可能的状态为s0=(1，1，1 )、s1=(1，2，2 )、s2=(1，3 ) s3=(2，1 )、s4=(2，2，2 )、s5=(2，3 ) s6=(3，1 )、s7=(2，2，2 ) 运算符分别使用A(i，j )和B(i，j )。 A(i，j )表示将a金片从I号柱移至j号柱。 B(i，j )也是如此。 一共有12个运算符。 在状态空间图中，从初始节点(1，1 )至目标节点(2，2 )或(3，3 )的路径是问题的解决方案。 最短路径长度为3，它由三个运算符组成。 例如，要用： a (1，3，3 )、b (1，2 )、a (3，2 )、5，状态空间方法表示问题，首先必须定义状态的描述格式来表示问题的所有状态。 然后定义一组运算符。 问题的解决过程是运算符继续作用于状态的过程。 如果使用某个运算符得到的新状态是目标状态的话，就可以得到问题的解答。 该解是由从初始状态到目标状态使用的运算符构成的系列。 一次使用运算符可以将问题从一个状态转换为另一个状态。 运算符最少的解或者总成本最少的解称为最佳解。 在任何状态下，都可以使用多个运算符。 这可能会导致从单个状态生成多个后续状态。 在这种情况下，首先操作哪个状态取决于检索策略。 6、和或树是代表问题及其解决过程的另一种形式化方法，通常被用于表示相对复杂的问题的解决方案。 对于复杂的问题，直接解答往往很难。 在这种情况下，可以通过将一个复杂的问题分解为几个相对简单的子问题，并且继续逐个子问题的分解来简化这个过程。 重复此过程，直到不再需要或不再可拆卸为止。 以这种方式形成“与”树。 等效变换利用同源和同源的等效变换，变换成几个易于解决原始问题的新问题。 这样形成or树。 7、8、本原问题不能再分解或转换，而且是可以直接解决的子问题。 在末端节点和末端节点and/树中，将没有子节点的节点统称为末端节点的与本问题对应的节点称为结束节点。 解节点是and/树，满足称为解节点的条件之一的节点是or节点，其中至少一个子节点是可解析节点这是and节点，所有子节点都是可解析节点。 不可解节点由不满足全部可解节点的三个条件的节点、9、解树构成，从这些可解节点将初始节点为可解节点的子树称为解树。10、11、12、盲搜索的特征：以预定路由进行搜索并且将其应用于没有关于该问题的启发性信息的状态空间图是树结构的一个问题。 启发式搜索运用有关问题的启发性信息，用这些启发性信息指导搜索过程，高效地解决结构复杂的问题。 宽度优先搜索是以“先考虑扩展的节点”这一原则搜索的深度优先搜索，以“后考虑扩展的节点”这一原则搜索的有界深度优先搜索的原则与深度优先搜索相同，但由于规定了深度限制， 不能无限深度方向发展搜索的成本树的广度优先搜索是以“先考察哪个节点从哪个节点到根节点的成本小，哪个节点”这一原则搜索的成本树的深度优先搜索是“当前节点的哪个子节点对其父节点的成本小， 首先考察哪个子节点原则搜索的局部优先搜索是以由于当前节点的哪个子节点到达目标节点的估计成本小，所以先考察哪个子节点的原则搜索的全局优先搜索是从哪个节点到目标节点的估计成本小， 13、OPEN和CLOSE表OPEN表用于存储刚生成的节点，这些表按“先考虑哪个节点”原则搜索。 OPEN表中节点的排序顺序取决于搜索策略。 CLOSE表用于存储扩展的节点或扩展的节点。 将OPEN表CLOSE表、14、初始节点S0放入OPEN表中，制作仅包含当前S0的图，检查记为g的OPEN表是否为空，如果为空则不解决问题，将结束的OPEN表的第一个节点取出到CLOSE表中，将该节点设为n 如果是这样，求解问题，扩展退出的节点n，生成子节点集合。 其中，将不是节点n的前辈的子节点作为集合m，将这些子节点作为节点n的子节点加到g中，根据m子节点的状况，对于未出现在g中的m成员设定指向父节点(节点n )的指针，对于在列入OPEN表的处理之前出现在g中的m成员在确定是否需要更改指向父节点的指针之前出现在g中，对于已扩展的m个成员，按搜索策略对OPEN表中的节点进行排序，以确定后续节点是否需要修改指向父节点的指针。然后进行步骤2。 以上是共同的过程，各种检索策略的主要区别在于对OPEN表的节点进行排序的标准不同。 当一个节点由一个运算符操作时，通常只生成一个子节点。 但是，如果有多个运算符应用于一个节点，则会生成一组子节点。 虽然在这些子节点中，当前扩展节点的父节点、祖先节点等可能，但在这种情况下，它们不能是当前扩展节点的子节点。 新生成的节点可能是最初生成的节点，也可能以前生成为其他节点的继承节点，当前再次生成为其他节点的继承节点。 此时，不是哪个节点的后继节点？ 一般由从原始节点到该节点的成本来决定，成本较小的相应节点成为父节点。 在搜索过程中，如果被考察的节点是目标节点就可以得到解。 该解由从初始节点到目标节点的路径上的运算符组成。 如果在搜索中找不到目标节点，并且OPEN表中没有可扩展的节点，则搜索将失败。16、基本思想：从初始节点S0以层次方式扩展节点，并考虑它是否是目标节点。 在第n层的节点全部扩展考察之前，第n 1层的节点不扩展。 在OPEN表中，节点总是按条目的优先级排列，第一个条目的节点排在前面，下一个条目的节点排在后面。 还有，17、把初始节点S0放入OPEN表内。 如果OPEN表为空，则不解决问题并退出。 将OPEN表中的第一个节点(记为节点n )取出到CLOSE表中。 检查节点n是否为目标节点。 如果是这样的话，寻求问题的解答，退出。如果节点n无法扩展，请继续执行步骤2。 展开节点n，将其子节点放在OPEN表的末尾，配置指向每个子节点的父节点的指针，然后继续执行步骤2。 另外，18、19、优点：如果问题有解，可以通过广泛的优先搜索总是得到解，而且可以得到最短路径的解。 缺点：广优先搜索盲目性大，目标节点远离初始节点时，会产生许多不需要的节点，搜索效率低。20、基本思想：从初始节点S0中，从子节点中选择一个节点进行考察。 如果不是目标节点，则从该子节点的子节点中选择一个节点进行考察，这样进行向下搜索。 如果到达一个子节点且该子节点即使在目标节点中也不能被扩展，则选择其同级节点进行考察。 深度优先搜索和宽度优先搜索的唯一不同在于，宽度优先搜索是将节点n的子节点置于OPEN表的末尾，深度优先搜索是将节点n的子节点置于OPEN表的开头。 还有，21、把初始节点S0放入OPEN表内。 如果OPEN表为空，则不解决问题并退出。 将OPEN表中的第一个节点(记为节点n )取出到CLOSE表中。 检查节点n是否为目标节点。 如果是这样的话，寻求问题的解答，退出。 如果节点n无法扩展，请继续执行步骤2。 扩展节点n，将其子节点放入OPEN表的标题中，将指向父节点的指针放置在各个子节点中，进行至步骤2。22、23、在深度优先搜索中，进入某个分支，沿着该分支一直向下搜索。 如果目标节点恰好在此分支上，则可以更快地获得解。 但是，如果目标节点不在该分支上，该分支为无限分支，则不能得到解。 深度优先搜索不完整，即使问题有解，也不一定需要解。 以深度优先求得的解未必是路径最短的解。 24、基本思想：在深度优先探索中导入探索深度的界限(设为dm )，探索深度达到深度界限，目标节点尚未出现时，改变分支进行探索。 搜索过程：将初始节点S0置于OPEN表中，其中S0的深度为d(S0)=0。 如果OPEN表为空，则不解决问题并退出。 将OPEN表中的第一个节点(记为节点n )取出到CLOSE表中。 检查节点n是否为目标节点。 如果是这样的话，寻求问题的解答，退出。 如果节点n的深度d (节点n)=dm，则进行到步骤2。 如果节点n无法扩展，请继续执行步骤2。 扩展节点n，将其子节点放入OPEN表的标题中，将指向父节点的指针放置在各个子节点中，进行至步骤2。 25、若问题有解且其路径长度DM，则上述搜索过程必定能够求解。 但是，在解的路径长度dm中，在上述的探索过程中得不到解。 这表明在有界深度优先搜索中，深度边界的选择是重要的。 很难给出适当的dm值。 求解不一定是最佳解。 26、首先，将dm任意设定为小数，然后进行上述的有界深度优先搜索，如果搜索到达指定的深度界限dm后仍未发现目标节点，CLOSE表中仍有扩展节点，则将这些节点返回OPEN表，同时增大深度界限dm 如果这样加大dm的话，问题解决了的话一定能找到。 但是，此时发现的解未必是最佳解。 为了找到最佳解，增加表r并继续搜索，每当发现远程目标节点Sg时，表r将被放置在r之前且dm等于对应于目标节点的路径长度。 因为后面求得的解的路径长度不会超过先前求得的解的路径长度，所以后面求得的解必定是最佳解。 当27、深度极限DM=4、28时，盲搜索具有大的盲目性，产生的无用节点多，搜索空间大，效率差。 在启发式检索中，必须指导运用问题本身的特定特性信息，以最有希望的方向进行检索。 这样的检索对象很强，原则上只要检索问题的状态空间的一部分，效率就很高。29、可用于指导搜索过程的有关具体问题解决的控制性信息称为启发性信息。 评估节点重要性的函数称为评估函数。 其通常的格式是f(x)=g(x) h(x )，g(x )是从初始节点S0至目标节点Sg的实际支付的代价，h(x )是从节点x至目标节点Sg的最佳路径的估计成本，表示问题的开发性信息，其格式根据问题的特性来决定。 举例来说，从节点x至目标节点的距离可为节点x在最佳路径上的概率等。 h(x )称为启发函数。 g(x )表示检索的横向倾向。 有利于搜索的完整性，但会影响搜索的效率。 如果只关心到达目标节点的路径并且希望较高搜索效率，可以忽略g(x )，但是在那种情况下，会影响搜索的完整性。 有一款移动卡游戏，30、1张卡移动到相邻的可用位置时，费用为1单位。 一张卡至多能跳过两张卡进入空位，其费用等于跳过的卡数加1。 请求所有b移动到w的右侧，并设计评估函数中的h(x )。 解：根据要求，w左边的b越少，越接近目标，因此将w左边b的个数设为h(x )，即h(x)=3每个左边b的个数的总和)，在此乘以系数3是为了扩大h(x )在f(x )中的比重。 31、基本思想：一个节点扩展后，按f(x )计算每一个子节点的评估值，并选择最小值作为下一个考虑的节点。 搜索过程：将初始节点S0放入OPEN表中，使g(S0)=0。 如果OPEN表为空，则不解决问题并退出。 将OPEN表中的第一个节点(记为节点n )取出到CLOSE表中。 检查节点n是否为目标节点。 如果是这样的话，寻求问题的解答，退出。 如果节点n无法扩展，请继续执行步骤2。 扩展节点n，使用评价函数f(x )来计算各子节点的评价值，按照评价值由小到大的顺序将其配置在OPEN表的开头，将指向各子节点的指针配置于各父节点中，进行至步骤2。 深度优先搜索、成本树的深度优先搜索以及局部优先搜索都将子节点作为考察范围。 然而，前者和后者可以被视为局部选择优先搜索的特例。 32、基本思想：在成本树的广度优先搜索中，每次从OPEN表的所有节点中选择成本最小的节点发送到CLOSE表进行考察。 成本树的深度优先搜索从刚扩展的子节点中选择成本最小的节点发送到CLOSE表中进行考察。 搜索过程：将初始节点S0放入OPEN表中，使g(S0)=0。 如果OPEN表为空，则不解决问题并退出。 将OPEN表中的第一个节点(记为节点n )取出到CLOSE表中。 检查节点n是否为目标节点。 如果是这样的话，寻求问题的解答，退出。 如果节点n无法扩展，请继续执行步骤2。 扩展节点n，按照成本从小到大的顺序将其子节点置于OPEN表的开头，将指向父节点的指针置于各个子节点中，进行至步骤2。 代偿树深度有限的探索是不完整的。33、34、基本思想：每次选择一个节点进行考察，局部优先搜索只是从刚生成的子节点中进行选择，选择的范围很窄。 全局优先搜索部从OPEN表的所有节点中选择评价值总是最小的节点。 搜索过程：将初始节点S0放入OPEN表中，计算f(S0 )。 如果OPEN表为空，则不解决问题并退出。 将OPEN表中的第一个节点(记为节点n )取出到CLOSE表中。 检查节点n是否为目标节点。 如果是这样的话，寻求问题的解答，退出。 如果节点n无法扩展，请继续执行步骤2。 扩展节点n，利用评价函数f(x )来计算各子节点的评价值，在各子节点上构成指向父节点的