第3章+搜索推理技术.ppt

1、第3章搜索和推理技术，人工智能，3.1图形搜索策略，1。图搜索策略图搜索策略可以看作是在图中寻找路径的一种方法。初始节点和目标节点代表初始数据库和满足终止条件的数据库。找到将一个数据库转换成另一个数据库的规则序列问题相当于找到图中的路径问题。2.GRAPHSEARCH算法中的几个重要术语(1)OPEN表和CLOSE表(2)搜索图和搜索树(3.1图搜索策略，3 .图搜索的一般过程(1)建立一个只包含起始节点s的搜索图g，并将s放入一个未扩展的节点表OPEN中。(2)建立一个名为CLOSED的扩展节点表，它最初是一个空表。(3)循环：如果OPEN表为空，则无法退出。(4)选择打开表中的第一个节点，

2、将其从打开表中移除，并将其放入关闭表中。这个节点称为节点n。(5)如果n是目标节点，它有一个解决方案并成功退出。这个解决方案是通过在图G中跟踪从n到s的路径获得的(指针将在步骤7中设置)。3.1图搜索策略，(6)扩展节点N，同时生成不是N的祖先的M个后继节点的集合。将M的这些成员添加到图G中作为N的后继节点。(7)为那些从未出现在图G中的M个成员设置一个指向N的指针(既不在OPEN表上也不在CLOSED表上)。将m的这些成员添加到OPEN表中。对于OPEN或CLOSED表上的每个m成员，确定是否需要更改指向n的指针方向。对于已经在CLOSED表上的每个M成员，确定是否有必要改变图g(8)中通向

3、它的每个后代节点的指针方向。(9) GO LOOP .3.1图形搜索策略，思考：图形搜索是什么知识表示方法？3.1图形搜索策略，4。图搜索方法分析：在图搜索过程的第八步中，OPEN表上的节点被排序，以便在第四步中选择“最佳”节点进行扩展。这种排序可以是任意的或盲目的(属于盲目搜索)，或者它可以基于各种启发式思想或稍后讨论的其他标准(属于启发式搜索)。只要选择作为扩展的节点是目标节点，该过程就成功结束。此时，从起始节点到目标节点的成功路径可以通过根据指针将可追溯性从目标节点返回到S来再现。当搜索树中没有未扩展的结束节点时，该过程以失败告终(一些节点可能最终没有后续节点，因此OPEN表可能最终变成

4、空表)。在终止失败的情况下，从起始节点开始，无法到达目标节点。3.2盲搜索，3.2.1宽度优先搜索1。定义如果搜索依次扩展靠近起始节点的节点，则此搜索称为宽度优先搜索。2.该搜索是逐层进行的；在搜索下一层中的任何节点之前，必须搜索该层中的所有节点。3.2盲目搜索，3。宽度优先搜索算法(1)将起始节点放在OPEN表中(如果起始节点是目标节点，则得到一个解)。(2)如果OPEN是一个空表，则没有解决方案，并且无法退出；否则，继续。(3)将第一个节点(节点N)移出开放表，并将其放入封闭扩展节点表。(4)展开节点n。如果没有后续节点，转到上述步骤(2)。(5)将N的所有后继节点放在OPEN表的末尾，并

5、提供从这些后继节点回到N的指针。(6)如果N的任何后继节点是目标节点，则找到解决方案并成功退出；否则，转到步骤(2)。3.2盲目搜索，4。宽度优先搜索方法分析：宽度优先搜索是图形搜索一般过程中的特例，图形搜索一般过程中的第八步体现为该算法中的第六步，该算法实际上将OPEN表作为“先进先出”队列进行操作。宽度优先搜索方法可以保证在搜索树中找到到目标节点的最短路径；这个搜索树提供了所有现有的路径(如果没有路径，那么对于有限的图，我们说该方法不能退出；对于无限图，它永远不会终止)。3.2盲搜索，5。示例：绘制将宽度优先搜索应用于8位数字谜时生成的搜索树。初始游戏，目标游戏，3.2盲搜索，3.2.2深

6、度优先搜索1。定义在此搜索中，首先扩展新生成的(即最深的)节点。深度相等的节点可以任意排列。这种盲(无信息)搜索被称为深度优先搜索。2.首先，扩展最深节点的结果使得搜索从起始节点沿着状态空间中的单一路径向下进行；只有当搜索达到没有后代的状态时，它才会考虑另一条替代路径。3.2盲目搜索，3。深度限制为了避免考虑过长的路径(防止搜索过程沿着无用的路径扩展)，通常会给出节点扩展的最大深度限制。如果任何节点达到深度限制，它们将被视为没有后继的节点。4.具有深度限制的深度优先搜索算法(1)将起始节点放在OPEN表中(如果起始节点是目标节点，则得到一个解)。(2)如果OPEN是一个空表，它将无法退出。(3

7、)将第一个节点(节点N)从开放表移动到封闭扩展节点表。3.2盲搜索，(4)如果节点n的深度等于最大深度，转到步骤(2)。(5)展开节点N，生成它的所有后代，并将它们放在OPEN表的前面。如果没有后代，请转到步骤(2)。(6)如果N的任何后继节点是目标节点，则找到解决方案并成功退出；否则，转到步骤(2)。问题：有限深度优先搜索方法能确保在搜索树中找到到目标节点的最短路径吗？3.2盲搜索，5。示例：绘制深度优先搜索应用于8位数字谜时生成的搜索树，深度限制为4。初始状态，目标状态，3.2盲搜索，3.2.3等成本搜索。1.定义宽度优先搜索可以推广到解决从初始状态到目标状态寻找成本最低的路径的问题。这种

8、广义的宽度优先搜索算法称为等代价搜索算法。2.等代价搜索中若干标记的初始节点标记为S；从节点I到其后继节点j的连接的弧成本被记录为c(i，j)。从起始节点s到任何节点I的路径开销被记录为g(i)。3.2盲搜索，3.3等代价搜索算法(1)将起始节点放在OPEN表中。如果起始节点是目标节点，则获得解；否则，让g(S)=0。(2)如果OPEN是一个空表，则没有解决方案，并且无法退出；(3)从OPEN表中选择一个节点I，以最小化其g(i)。如果几个节点是合格的，那么应该选择目标节点1(如果有目标节点)；否则，选择其中一个作为节点I.将节点I从OPEN表移动到扩展节点表CLOSED。(4)如果节点1是目

9、标节点，则获得解。(5)展开节点I。如果没有后续节点，转到上述步骤(2)。(6)对于节点I的每个后继节点J，计算g(j)=g(i) c(i，J)，将所有后继节点放入OPEN表，并提供指向节点I的指针。(7)转到步骤(2)。3.2盲搜索，思维：等代价算法和宽度优先搜索算法的关系，3.3启发式搜索，3.3.1启发式搜索策略和评价函数1。定义搜索技术通常需要一些关于特定问题领域的特征的信息，这被称为启发式信息。使用启发式信息的搜索方法称为启发式搜索方法。2.启发式搜索策略关于特定问题区域的信息通常可以用来简化搜索。使用启发式信息的一种灵活(但代价昂贵)的方法是在每一步应用一些标准来重新排列OPEN表

10、中所有节点的顺序。然后，搜索可以沿着被认为是最有希望的某个边缘部分向外扩展。为了应用这种排序过程，我们需要一些度量来估计节点的“希望”，这被称为评估函数。3.3启发式搜索3 .评估功能提供了一种评估候选扩展节点的方法，以便获得一些节点“希望”的启发式信息，从而确定哪个节点最有可能在到达目标的最佳路径上。F(n)表示节点n的评价函数值。建立评价函数的一般方法是试图确定节点在最佳路径上的概率；提出任意节点与目标集之间的距离度量或差异度量；或者在棋盘式游戏问题中，根据象棋游戏的某些特征来确定象棋游戏的分数。这些特征被认为与进一步到达目标节点的希望程度相关。3.3启发式搜索，3.3.2有序搜索1。在G

11、RAPHSEARCH的步骤8中，定义使用评估函数f来排列OPEN表上的节点。应用一种算法(如等成本算法)选择OPEN表上f值最小的节点作为下一个要扩展的节点。这种搜索方法称为有序搜索或最佳优先搜索，其算法称为有序搜索算法或最佳优先搜索算法。尼尔森曾提出一个有序搜索的基本算法。评估函数f确定如下：节点的期望程序越大，其f值越小。选择作为扩展的节点是具有最小评估函数的节点。3.3启发式搜索，2 .本质上选择OPEN表上f值最小的节点作为下一个要扩展的节点，即总是选择最有希望的节点作为下一个要扩展的节点。3.3启发式搜索，3 .有序状态空间搜索算法(1)将起始节点S放入OPEN表中，计算f(S)并将

12、它的值与节点S相关联(2)如果OPEN是一个空表，它将无法在没有解的情况下退出。(3)从打开表中选择一个f值最小的节点I。因此，几个节点是合格的。如果其中一个是目标节点，选择这个目标节点；否则，选择它们中的任何一个作为节点I。(4)从OPEN表中删除节点I，并将其放入CLOSED扩展节点表。(5)如果我是目标节点，我会成功退出并获得解决方案。3.3启发式搜索，(6)扩展节点1以生成其所有后继节点。对于I的每个后继节点j:(a)计算f(j)。(b)如果j既不在开放表中，也不在封闭表中，用求值函数f将其添加到开放表中。添加一个从j到其父节点I的指针，以便在找到目标节点后记住解路径。(c)如果j已经

13、在OPEN表或CLOSED表中，将刚刚为j计算的f值与之前计算的表中节点的f值进行比较。如果新的f值很小，(I)用这个新值替换旧值。(ii)从j指向I，而不是指向其父节点。(iii)如果节点j在CLOSED表中，将其移回OPEN表。(7)转向(2)。3.3启发式搜索，思考：宽度优先搜索、等价搜索、深度优先搜索和有序搜索的关系。有序搜索的有效性直接取决于F的选择。如果F的选择不当，有序搜索可能会失去最佳解甚至所有解。如果没有适用的和准确的衡量希望的标准，f的选择将涉及两个方面：一方面，它是时间和空间之间的妥协；另一方面，有一个最优解或任意解。3.3启发式搜索，3.3.3 A*算法A*算法是一种有

14、序搜索算法，其特点是定义了评价函数。1.几个标记使得k(ni，nj)表示在任意两个节点ni和nj之间具有最低成本的路径的实际成本(对于在两个节点之间没有路径的节点，没有定义函数k)。因此，从节点n到特定目标节点ti，最小成本路径的成本可以由k(n，ti)给出。3.3启发式搜索，让h*(n)代表整个目标节点集合ti中所有k(n，ti)中最小的，所以h*(n)是从n到目标节点的最小成本路径的成本，并且从n到目标节点的能够获得h*(n)的任何路径是从n到目标节点的最佳路径(对于不能到达目标节点的任何节点n，3.3启发式搜索，2。评估函数g*的定义是g*(n)=k(S，N)，因此其函数值f* (n)是

15、从节点S到节点N的最佳路径的实际成本加上从节点N到目标节点的最佳路径的成本之和，即f*(n)=g*。h是h*的估计值。对于g(n)，一个显而易见的选择是搜索树中从s到n的路径的成本，这可以通过将寻找从n到s的指针时遇到的弧的成本相加来给出(该路径是迄今为止搜索算法找到的从s到n的最低成本路径)。h*(n) h(n)的估计依赖于相关问题领域的启发式信息。该信息可能类似于八位数字谜中的函数W(n)所使用的信息。h被称为启发式函数。3.3启发式搜索，3。A*算法定义定义1在GRAPHSEARCH过程中，如果在步骤8中OPEN表的重排是根据f(x)=g(x) h(x)进行的，那么这个过程称为算法。定义

16、2在一个算法中，如果所有x都有h(x)h*(x)，那么h(x)被称为h*(x)的下界，这表示某种保守估计。定义3:使用h*(x)的下限h(x)作为启发式函数的算法称为A*算法。思考：1 .从g*(n)和g(n)的定义中知道g*(n) g(n)吗？2.当h=0时，A*将成为哪种搜索算法？3.3启发式搜索，初始状态，目标状态，网格上有8个数字1-8加上一个空格，一次只有一个与空格相邻的数字可以移动到空格中，一次移动算一步，给出初始状态和目标状态，并寻找如何用最少的步数完成移动。请设计一个A*算法的启发式函数。3.3启发式搜索，当设计A*算法时，g(n)取目前已经移动的步数，h(n)取从每个数到目标状态中相应数的位置的最短距离之和。这种选择的原因是，对于每个移动，只有一个数字可以改变一个相邻的位置，所以至少需要h (n)步，所以它满足h(n)=h。A *的成功在于选择一个好的h(n)。如果没有办法使它为0，就可以得到问题的解。3.4消解原理，谓词公式即原子公式不能再分解。原子公式及其否定。p被称为正字符，p被称为负字符，p和p被称为互补字符(互补对)。由词的析取组成的公式。空子句不包含任何文本的子句被表示为NIL。空子句总是假的(不可满足)。3.4决议原则，条款集是由条款组成的集合。当解析可用时，将解析过程应用于