1、西安电子科技大学西安电子科技大学Artificial Intelligence(AI)人工智能人工智能主讲：戚玉涛Email：qi_第三章：确定第三章：确定性推理性推理西安电子科技大学西安电子科技大学内容提要1.1.推理的基本概念推理的基本概念2.2.搜索策略搜索策略3.3.自然演绎推理自然演绎推理4.4.归结演绎推理归结演绎推理5.5.基于规则的演绎推理基于规则的演绎推理西安电子科技大学西安电子科技大学搜索策略v搜索策略搜索策略搜索的基本概念搜索的基本概念状态空间的搜索策略状态空间的搜索策略与与/或树的搜索策略或树的搜索策略搜索的完备性与效率搜索的完备性与效率西安电子科技大学西安电子科技大学
2、状态空间的搜索策略v状态空间的搜索策略状态空间的搜索策略状态空间搜索的基本思想状态空间搜索的基本思想图搜索的一般过程图搜索的一般过程状态空间的盲目搜索状态空间的盲目搜索p广度优先搜索广度优先搜索p深度优先搜索深度优先搜索p代价树搜索代价树搜索状态空间的启发式搜索状态空间的启发式搜索p启发性信息和估价函数启发性信息和估价函数pA算法和算法和A*算法算法西安电子科技大学西安电子科技大学状态空间的搜索策略v状态空间的搜索策略状态空间的搜索策略状态空间搜索的基本思想状态空间搜索的基本思想图搜索的一般过程图搜索的一般过程状态空间的盲目搜索状态空间的盲目搜索p广度优先搜索广度优先搜索p深度优先搜索深度优先
3、搜索p代价树搜索代价树搜索状态空间的启发式搜索状态空间的启发式搜索p启发性信息和估价函数启发性信息和估价函数pA算法和算法和A*算法算法西安电子科技大学西安电子科技大学A算法vA算法：算法：在图搜索算法中，如果能在搜索的每一步都利在图搜索算法中，如果能在搜索的每一步都利用估价函数用估价函数f(n)=g(n)+h(n)对对OPEN表中的节点进行排序，表中的节点进行排序，则该搜索算法为则该搜索算法为A算法算法。由于估价函数中带有问题自身的由于估价函数中带有问题自身的启发性信息，因此，启发性信息，因此，A算法也被称为算法也被称为启发式搜索算法启发式搜索算法。vA算法的类型：算法的类型：可根据搜索过程
4、中选择扩展节点的范围，可根据搜索过程中选择扩展节点的范围，将启发式搜索算法分为将启发式搜索算法分为全局择优搜索算法全局择优搜索算法：从从OPEN表的表的所有节点所有节点中选择一中选择一个估价函数值最小的一个进行扩展。个估价函数值最小的一个进行扩展。局部择优搜索算法：局部择优搜索算法：仅从刚生成的子节点仅从刚生成的子节点中选择一个中选择一个估价函数值最小的一个进行扩展。估价函数值最小的一个进行扩展。西安电子科技大学西安电子科技大学A算法v 全局择优搜索算法流程全局择优搜索算法流程(1)把初始节点把初始节点S0放入放入OPEN表，计算表，计算f(S0)。(2)如果如果OPEN表为空，则问题无解，退
5、出。表为空，则问题无解，退出。(3)把把OPEN表的第一个节点（记为节点表的第一个节点（记为节点n）取出放入）取出放入CLOSED表。表。(4)考察节点考察节点n是否为目标节点。若是，则求得了问题的解，是否为目标节点。若是，则求得了问题的解，退出。退出。(5)若节点若节点n不可扩展，则转第不可扩展，则转第2步。步。(6)扩展节点扩展节点n，用估价函数，用估价函数f(x)计算每个子节点的估价值，计算每个子节点的估价值，并为每一个子节点都配置指向父节点的指针。并为每一个子节点都配置指向父节点的指针。把这些子节把这些子节点都送入点都送入OPEN表中，然后对表中，然后对OPEN表中的全部节点按估价表中
6、的全部节点按估价值从小至大的顺序进行排序值从小至大的顺序进行排序，然后转第，然后转第2步。步。西安电子科技大学西安电子科技大学A算法v 局部择优搜索算法流程局部择优搜索算法流程(1)把初始节点把初始节点S0放入放入OPEN表，计算表，计算f(S0)。(2)如果如果OPEN表为空，则问题无解，退出。表为空，则问题无解，退出。(3)把把OPEN表的第一个节点（记为节点表的第一个节点（记为节点n）取出放入）取出放入CLOSED表。表。(4)考察节点考察节点n是否为目标节点。若是，则求得了问题的解，是否为目标节点。若是，则求得了问题的解，退出。退出。(5)若节点若节点n不可扩展，则转第不可扩展，则转第
7、2步。步。(6)扩展节点扩展节点n，用估价函数，用估价函数f(x)计算每个子节点的估价值，计算每个子节点的估价值，并按估价值从小到大的顺序放到并按估价值从小到大的顺序放到OPEN表中的首部表中的首部，并为，并为每一个子节点都配置指向父节点的指针，然后转第每一个子节点都配置指向父节点的指针，然后转第2步。步。西安电子科技大学西安电子科技大学A*算法vA*算法：算法：A*算法是对算法是对A算法的估价函数算法的估价函数f(n)=g(n)+h(n)加上某些限制后得到的一种启发式搜索算法。加上某些限制后得到的一种启发式搜索算法。v假设假设f*(n)是从初始节点出发经过节点是从初始节点出发经过节点n达到目
8、标节点达到目标节点的最小代价，估价函数的最小代价，估价函数f(n)是对是对f*(n)的的估计值估计值。且。且 f*(n)=g*(n)+h*(n)g*(n)是从初始节点是从初始节点S0到节点到节点n的最小代价。的最小代价。h*(n)是从节点是从节点n到目标节点的最小代价，若有多个到目标节点的最小代价，若有多个目标节点，则为其中最小的一个。目标节点，则为其中最小的一个。西安电子科技大学西安电子科技大学A*算法vA*算法：算法：A*算法对算法对A算法（全局择优的启发式搜算法（全局择优的启发式搜索算法）中的索算法）中的g(n)和和h(n)分别提出如下限制：分别提出如下限制：第一，第一，g(n)是对最小
9、代价是对最小代价g*(n)的估计，且的估计，且g(n)0；第二，第二，h(n)是最小代价是最小代价h*(n)的的下界下界，即对任意，即对任意节点节点n均有均有h(n)h*(n)。v即：满足上述两条限制的即：满足上述两条限制的A算法称为算法称为A*算法算法。西安电子科技大学西安电子科技大学A*算法v在在A*算法中，算法中，g(n)比较容易得到，它比较容易得到，它实际上就是从初始节点实际上就是从初始节点S0到节点到节点n的路的路径代价，恒有：径代价，恒有：g(n)g*(n)v在算法执行过程中，随着更多搜索信在算法执行过程中，随着更多搜索信息的获得，息的获得，g(n)呈下降的趋势。呈下降的趋势。v如
10、右图的例子：如右图的例子：p对对S0扩展后扩展后g(n1)=3，g(n2)=7p对对n1扩展后扩展后g(n2)=6，g(n3)=5S0n137n2n332西安电子科技大学西安电子科技大学A*算法vA*算法的可纳性：算法的可纳性：可纳性的含义：可纳性的含义：对任一状态空间图，当从初始对任一状态空间图，当从初始节点到目标节点有路经存在时，如果搜索算法节点到目标节点有路经存在时，如果搜索算法总能在总能在有限步骤内有限步骤内找到一条从初始节点到目标找到一条从初始节点到目标节点的节点的最佳路径最佳路径，并在此路径上结束，则称该，并在此路径上结束，则称该搜索算法是搜索算法是可纳的可纳的。A*算法是可纳的，
11、即它能在有限步内终止，并算法是可纳的，即它能在有限步内终止，并找到问题的最优解。找到问题的最优解。证明：证明：西安电子科技大学西安电子科技大学A*算法A*算法的可纳性证明：算法的可纳性证明：第一步：第一步：对于有限图，对于有限图，A*算法一定会在有算法一定会在有限步骤内终止。限步骤内终止。第二步：第二步：对于无限图，如果从初始节点对于无限图，如果从初始节点S0到到目标节点目标节点Sg有路径存在，则有路径存在，则A*算法也必然会算法也必然会终止。终止。第三步：第三步：A*算法一定终止在最优路径上算法一定终止在最优路径上。西安电子科技大学西安电子科技大学A*算法v证明：证明：A*算法一定终止在最优
12、路径上。算法一定终止在最优路径上。假设最优路径存在，记为假设最优路径存在，记为S0,x1,x2,.,xm,Sg*由于由于A*算法中的算法中的h(n)满足满足 h(n)h*(n)，则：，则：f(S0),f(x1),f(x2),.,f(xm)均不大于均不大于,f(Sg*)，f(Sg*)=f*(S0)在在A*算法结束之前，算法结束之前，OPEN表中必然存在最优路径表中必然存在最优路径S0,x1,x2,.,xm,Sg*中的一些节点，记中的一些节点，记x为其中最前面一个，为其中最前面一个，则则f(x)f*(S0)。假设：假设：A*算法不是终止在最优路径上，而是在某个目算法不是终止在最优路径上，而是在某个
13、目标节点标节点t处终止，则有处终止，则有f(t)=g(t)f*(S0)。此时有此时有f(x)f(t)，按照，按照A*算法的规则，应该选择算法的规则，应该选择x进进行扩展，而不会选择行扩展，而不会选择t。与假设矛盾与假设矛盾西安电子科技大学西安电子科技大学A*算法vA*算法的最优性：算法的最优性：h(n)的确定依赖于具体问题领域的启发性信息，的确定依赖于具体问题领域的启发性信息，其中其中h(n)h*(n)的限制是十分重要的，的限制是十分重要的，它可以它可以保证保证A*算法能找到问题的最优解算法能找到问题的最优解。A*算法的搜索效率很大程度上取决于估价函数算法的搜索效率很大程度上取决于估价函数h(
14、n)。一般来说，。一般来说，在满足在满足h(n)h*(n)的前提下，的前提下，h(n)的值越大越好的值越大越好。h(n)的值越大，说明它携的值越大，说明它携带的启发性信息越多，带的启发性信息越多，A*算法搜索时扩展的节算法搜索时扩展的节点就越少，搜索效率就越高。点就越少，搜索效率就越高。西安电子科技大学西安电子科技大学A*算法vh(n)的单调限制的单调限制在在A*算法中，每当扩展一个节点算法中，每当扩展一个节点n时，都需要检查其子时，都需要检查其子节点是否已在节点是否已在OPEN表或表或CLOSED表中。表中。p对已在对已在OPEN表中的子节点，需要决定是否调整指表中的子节点，需要决定是否调整
15、指向其父节点的指针；向其父节点的指针；p对已在对已在CLOSED表中的子节点，除需要决定是否调表中的子节点，除需要决定是否调整其指向父节点的指针外，还需要决定是否调整其整其指向父节点的指针外，还需要决定是否调整其子节点的后继节点的父指针。子节点的后继节点的父指针。如果能够保证，每当扩展一个节点时就已经找到了通如果能够保证，每当扩展一个节点时就已经找到了通往这个节点的最佳路径，就没有必要再去作上述检查。往这个节点的最佳路径，就没有必要再去作上述检查。西安电子科技大学西安电子科技大学A*算法vh(n)的单调限制的单调限制为能够保证，每当扩展一个节点时就已经找到了通为能够保证，每当扩展一个节点时就已
16、经找到了通往这个节点的最佳路径，我们需要对启发函数往这个节点的最佳路径，我们需要对启发函数h(n)增加单调性限制。增加单调性限制。如果启发函数满足以下两个条件如果启发函数满足以下两个条件:p(1)h(Sg)=0;p(2)对任意节点对任意节点ni及其任一子节点及其任一子节点nj，都有，都有 0h(ni)-h(nj)c(ni,nj)其中其中c(ni,nj)是是ni到其子节点到其子节点nj的边代价，则称的边代价，则称h(n)满足单调限制。满足单调限制。西安电子科技大学西安电子科技大学A*算法v 如果如果h(n)满足单调条件，则当满足单调条件，则当A*算法扩展节点算法扩展节点n时，该节点时，该节点就已
17、经找到了通往它的最佳路径，即就已经找到了通往它的最佳路径，即g(n)=g*(n)。v 证明：证明：设设A*正要扩展节点正要扩展节点n，而节点序列，而节点序列S0=n0,n1,nk=n是由初始是由初始节点节点S0到节点到节点n的的最佳路径最佳路径。其中，。其中，ni是这个序列中最后一个位于是这个序列中最后一个位于CLOSED表中的节点，则上述节点序列中的表中的节点，则上述节点序列中的ni+1节点必定在节点必定在OPEN表中，表中，由由h(n)的单调条件可知：的单调条件可知：g*(ni)+h(ni)g*(ni)+c(ni,ni+1)+h(ni+1)所以：所以：g*(ni)+h(ni)g*(ni+1
18、)+h(ni+1)依此类推可得：依此类推可得：g*(ni+1)+h(ni+1)g*(nk)+h(nk)=g*(n)+h(n)由于节点由于节点ni+1在最佳路径上，故有在最佳路径上，故有 f(ni+1)g*(n)+h(n)因为这时因为这时A*扩展节点扩展节点n而不扩展节点而不扩展节点ni+1，则有：，则有：f(n)=g(n)+h(n)f(ni+1)g*(n)+h(n)即即g(n)g*(n)。g*(n)是最小代价值，所以有是最小代价值，所以有g(n)=g*(n)最佳路径上最佳路径上的节点的节点西安电子科技大学西安电子科技大学A*算法v 如果如果h(n)满足单调限制，则满足单调限制，则A*算法扩展的
19、节点序列的算法扩展的节点序列的f 值值是非递减的，即是非递减的，即f(ni)f(ni+1)。v 证明：证明：假设节点假设节点ni+1在节点在节点ni之后立即扩展，由单调限制条之后立即扩展，由单调限制条件可知：件可知：h(ni)-h(ni+1)c(ni,ni+1)即即：(f(ni)-g(ni)-(f(ni+1)-g(ni+1)c(ni,ni+1)亦即：亦即：f(ni)-g(ni)-f(ni+1)+g(ni)+c(ni,ni+1)c(ni,ni+1)所以：所以：f(ni)-f(ni+1)0 即：即：f(ni)f(ni+1)v 以上两个定理都是在以上两个定理都是在h(n)满足单调性限制的前提下才成立
20、满足单调性限制的前提下才成立的。的。如果如果h(n)不满足单调性限制，则它们不一定成立不满足单调性限制，则它们不一定成立。西安电子科技大学西安电子科技大学A*算法vA*算法应用：算法应用：八数码难题八数码难题 f(n)=g(n)+h(n)g(n)深度深度 h(n)与目标距离与目标距离 f*=g*+h*f(n)=g(n)+h(n)g(n)深度深度h(n)与目标距离与目标距离f*=g*+h*西安电子科技大学西安电子科技大学搜索策略v搜索策略搜索策略搜索的基本概念搜索的基本概念状态空间的搜索策略状态空间的搜索策略与与/或树的搜索策略或树的搜索策略搜索的完备性与效率搜索的完备性与效率西安电子科技大学西
21、安电子科技大学与/或树的搜索策略v与与/或树的搜索策略或树的搜索策略与与/或树的一般搜索过程或树的一般搜索过程与与/或树的广度优先搜索或树的广度优先搜索与与/或树的深度优先搜索或树的深度优先搜索与与/或树的启发式搜索或树的启发式搜索博弈树的启发式搜索博弈树的启发式搜索-剪枝技术剪枝技术西安电子科技大学西安电子科技大学与/或树的搜索策略v与与/或树的搜索策略或树的搜索策略与与/或树的一般搜索过程或树的一般搜索过程与与/或树的广度优先搜索或树的广度优先搜索与与/或树的深度优先搜索或树的深度优先搜索与与/或树的启发式搜索或树的启发式搜索博弈树的启发式搜索博弈树的启发式搜索-剪枝技术剪枝技术西安电子科
22、技大学西安电子科技大学与/或树的一般搜索过程v与与/或树的搜索策略：或树的搜索策略：用与用与/或树方法求解问题时，首先要或树方法求解问题时，首先要定义问题的描述方定义问题的描述方法法，及分解或变换问题的算符及分解或变换问题的算符，然后就用它们通过搜，然后就用它们通过搜索生成与索生成与/或树，从而或树，从而求得原始问题的解求得原始问题的解。在与在与/或树中，一个节点是否为可解节点是由它的子节或树中，一个节点是否为可解节点是由它的子节点确定的。由可解点确定的。由可解/不可解子节点来确定父节点、祖父不可解子节点来确定父节点、祖父节点等为可解节点等为可解/不可解节点的过程成为不可解节点的过程成为可解可
23、解/不可解标不可解标记过程记过程。与与/或树的搜索过程是或树的搜索过程是反复调用可解反复调用可解/不可解标记过程，不可解标记过程，直到初始节点（原始问题）被标记为可解直到初始节点（原始问题）被标记为可解/不可解节点不可解节点为止为止。西安电子科技大学西安电子科技大学与/或树的一般搜索过程v与与/或树的一般搜索过程如下：或树的一般搜索过程如下：(1)把原始问题作为初始节点把原始问题作为初始节点S0，并把它作为当前节点；，并把它作为当前节点；(2)应用分解或等价变换操作对当前节点进行扩展；应用分解或等价变换操作对当前节点进行扩展；(3)为每个子节点设置指向父节点的指针；为每个子节点设置指向父节点的
24、指针；(4)选择选择合适的子节点作为当前节点合适的子节点作为当前节点，反复执行第，反复执行第(2)步步和第和第(3)步，在此期间需要多次调用可解标记过程或不可步，在此期间需要多次调用可解标记过程或不可解标记过程，直到初始节点被标记为可解节点或不可解解标记过程，直到初始节点被标记为可解节点或不可解节点为止。节点为止。v上述搜索过程将形成一棵与上述搜索过程将形成一棵与/或树，这种由搜索过或树，这种由搜索过程所形成的与程所形成的与/或树称为或树称为搜索树搜索树。西安电子科技大学西安电子科技大学与/或树的搜索策略v与与/或树的搜索策略或树的搜索策略与与/或树的一般搜索过程或树的一般搜索过程与与/或树的
25、广度优先搜索或树的广度优先搜索与与/或树的深度优先搜索或树的深度优先搜索与与/或树的启发式搜索或树的启发式搜索博弈树的启发式搜索博弈树的启发式搜索-剪枝技术剪枝技术西安电子科技大学西安电子科技大学与/或树的广度优先搜索v与与/或树的广度优先搜索：或树的广度优先搜索：与与/或树的广度优先搜索与状态空间的广度优先或树的广度优先搜索与状态空间的广度优先搜索的主要差别是，搜索的主要差别是，需要在搜索过程中需要多需要在搜索过程中需要多次调用可解标识过程或不可解标识过程次调用可解标识过程或不可解标识过程。v与与/或树的广度优先搜索算法如下：或树的广度优先搜索算法如下：(1)把初始节点把初始节点S0放入放入
26、OPEN表中；表中；(2)把把OPEN表的表的第一个节点第一个节点取出放入取出放入CLOSED表，并表，并记该节点为记该节点为n；(3)如果节点如果节点n可扩展，则做下列工作：可扩展，则做下列工作：西安电子科技大学西安电子科技大学与/或树的广度优先搜索p 扩展节点扩展节点n，将其子节点放入，将其子节点放入OPEN表的表的尾部尾部，并为每一个子节点设置指向父节点的指针；并为每一个子节点设置指向父节点的指针；p 考察这些考察这些子节点子节点中有否中有否终止节点终止节点。若有，则标记若有，则标记这些终止节点为可解节点，并用可解标记过程对其这些终止节点为可解节点，并用可解标记过程对其父节点及先辈节点中
27、的可解解节点进行标记。父节点及先辈节点中的可解解节点进行标记。如果如果初始解节点初始解节点S0能够被标记为可解节点，就得到了解能够被标记为可解节点，就得到了解树，搜索成功，退出搜索过程；如果不能确定树，搜索成功，退出搜索过程；如果不能确定S0为为可解节点，则从可解节点，则从OPEN表中表中删去具有可解先辈的节删去具有可解先辈的节点点。p 转第转第(2)步。步。西安电子科技大学西安电子科技大学与/或树的广度优先搜索(4)如果节点如果节点n不可扩展，则作下列工作：不可扩展，则作下列工作：p 标记节点标记节点n为不可解节点；为不可解节点；p 应用不可解标记过程对节点应用不可解标记过程对节点n的先辈中
28、不可解解的先辈中不可解解的节点进行标记的节点进行标记。如果初始解节点。如果初始解节点S0也被标记为不也被标记为不可解节点，则搜索失败，表明原始问题无解，退出可解节点，则搜索失败，表明原始问题无解，退出搜索过程；如果不能确定搜索过程；如果不能确定S0为不可解节点，则从为不可解节点，则从Open表中表中删去具有不可解先辈的节点删去具有不可解先辈的节点。p 转第转第(2)步。步。西安电子科技大学西安电子科技大学与/或树的广度优先搜索v与与/或树的广度优先搜索的例子或树的广度优先搜索的例子:设有下图所示的与设有下图所示的与/或树，节点按标注顺序进行扩展，或树，节点按标注顺序进行扩展，其中表有其中表有t
29、1、t2、t3的节点是终止节点，的节点是终止节点，A、B、C为不为不可解的端节点。可解的端节点。12 3A 4 t1 5 t2 B t3 C西安电子科技大学西安电子科技大学与/或树的广度优先搜索v广度优先搜索过程：广度优先搜索过程：(1)先扩展先扩展1号节点，生成号节点，生成2号号节点和节点和3号节点。号节点。(2)扩展扩展2号节点，生成号节点，生成A节节点和点和4号节点。号节点。(3)扩展扩展3号节点，生成号节点，生成t1节点和节点和5号节点。号节点。由于由于t1为终止为终止节点，则标记它为可解节点节点，则标记它为可解节点，并应用可解标记过程，不，并应用可解标记过程，不能确定能确定3号节点是
30、否可节。号节点是否可节。(4)扩展节点扩展节点A，由于，由于A是端节点，因此不可扩展。调是端节点，因此不可扩展。调用不可解标记过程。用不可解标记过程。西安电子科技大学西安电子科技大学与/或树的广度优先搜索v广度优先搜索过程：广度优先搜索过程：(5)扩展扩展4号节点，生成号节点，生成t2节点和节点和B节点。节点。由于由于t2为终止节点为终止节点，标，标记为可解节点，应用可解标记记为可解节点，应用可解标记过程，可标记过程，可标记2号节点为可解，号节点为可解，但不能标记但不能标记1号节点为可解。号节点为可解。(6)扩展扩展5号节点，生成号节点，生成t3节点和节点和C节点。节点。由于由于t3为终止节为
31、终止节点点，标记它为可解节点，应用可解标记过程，可标记，标记它为可解节点，应用可解标记过程，可标记1号节点为可解节点。号节点为可解节点。(7)搜索成功，得到由搜索成功，得到由1、2、3、4、5号节点和号节点和t1、t2、t3节点构成的解树。节点构成的解树。西安电子科技大学西安电子科技大学与/或树的搜索策略v与与/或树的搜索策略或树的搜索策略与与/或树的一般搜索过程或树的一般搜索过程与与/或树的广度优先搜索或树的广度优先搜索与与/或树的深度优先搜索或树的深度优先搜索与与/或树的启发式搜索或树的启发式搜索博弈树的启发式搜索博弈树的启发式搜索-剪枝技术剪枝技术西安电子科技大学西安电子科技大学与/或树
32、的深度优先搜索v与与/或树的深度优先搜索：或树的深度优先搜索：与与/或树的深度优先搜索和与或树的深度优先搜索和与/或树的广度优先搜索过程或树的广度优先搜索过程基本相同，其主要区别在于基本相同，其主要区别在于OPEN表中节点的排列顺序表中节点的排列顺序不同。在扩展节点时，与不同。在扩展节点时，与/或树的深度优先搜索过程总或树的深度优先搜索过程总是把刚生成的节点放在是把刚生成的节点放在OPEN表的表的首部首部。与与/或树的深度优先搜索也可以带有深度限制或树的深度优先搜索也可以带有深度限制dmv与与/或树的深度优先搜索或树的深度优先搜索算法如下：算法如下：(1)把初始节点把初始节点S0放入放入OPE
33、N表中；表中；(2)把把OPEN表第一个节点取出放入表第一个节点取出放入CLOSED表，并记表，并记该节点为该节点为n；西安电子科技大学西安电子科技大学与/或树的深度优先搜索v与与/或树的深度优先搜索或树的深度优先搜索算法如下：算法如下：(3)如果节点如果节点n的深度等于的深度等于dm，则转第，则转第(5)步的第点；步的第点；(4)如果节点如果节点n可扩展，则做下列工作：可扩展，则做下列工作：p 扩展节点扩展节点n，将其子节点放入，将其子节点放入OPEN表的表的首部首部，并为每一个子节点设置指向父节点的指针；并为每一个子节点设置指向父节点的指针；p 考察这些考察这些子节点中子节点中是否有是否有
34、终止节点终止节点。若有，则标。若有，则标记这些终止节点为可解节点，并用可解标记过程对记这些终止节点为可解节点，并用可解标记过程对其父节点及先辈节点中的可解解节点进行标记。如其父节点及先辈节点中的可解解节点进行标记。如果初始解节点果初始解节点S0能够被标记为可解节点，就得到了能够被标记为可解节点，就得到了解树，搜索成功；如果不能确定解树，搜索成功；如果不能确定S0为可解节点，则为可解节点，则从从OPEN表中删去具有可解先辈的节点。表中删去具有可解先辈的节点。西安电子科技大学西安电子科技大学与/或树的深度优先搜索v与与/或树的深度优先搜索或树的深度优先搜索算法如下：算法如下：p 转第转第(2)步。
35、步。(5)如果节点如果节点n不可扩展，则作下列工作：不可扩展，则作下列工作：p 标记节点标记节点n为不可解节点；为不可解节点；p 应用不可解标记过程对节点应用不可解标记过程对节点n的先辈中不可解解的先辈中不可解解的节点进行标记。如果初始解节点的节点进行标记。如果初始解节点S0也被标记为不也被标记为不可解节点，则搜索失败，表明原始问题无解，退出可解节点，则搜索失败，表明原始问题无解，退出搜索过程；如果不能确定搜索过程；如果不能确定S0为不可解节点，则从为不可解节点，则从Open表中删去具有不可解先辈的节点。表中删去具有不可解先辈的节点。p 转第转第(2)步。步。西安电子科技大学西安电子科技大学与
36、/或树的广度优先搜索v与与/或树的深度优先搜索的例子或树的深度优先搜索的例子:设有下图所示的与设有下图所示的与/或树，其中表有或树，其中表有t1、t2、t3的节点是的节点是终止节点，终止节点，A、B、C为不可解的端节点。若按有界深为不可解的端节点。若按有界深度优先搜索，设度优先搜索，设dm=4，则其节点扩展顺序为：，则其节点扩展顺序为：1，3，5，2，4。12 3A 4 t1 5 t2 B t3 C西安电子科技大学西安电子科技大学与/或树的广度优先搜索v深度优先搜索过程：深度优先搜索过程：(1)先扩展先扩展1号节点，生成号节点，生成2号号节点和节点和3号节点。号节点。(2)扩展扩展3号节点，生
37、成号节点，生成t1节点节点和和5号节点。由于号节点。由于t1为终止节为终止节点，则标记它为可解节点，点，则标记它为可解节点，并应用可解标记过程，不能并应用可解标记过程，不能确定确定3号节点是否可解。号节点是否可解。(3)扩展扩展5号节点，生成号节点，生成t3节点和节点和C节点。由于节点。由于t3为终止节为终止节点，则标记它为可解节点，并应用可解标记过程，可标点，则标记它为可解节点，并应用可解标记过程，可标记记3号节点为可解节点，但不能标记号节点为可解节点，但不能标记1号为可解。号为可解。西安电子科技大学西安电子科技大学与/或树的广度优先搜索v深度优先搜索过程：深度优先搜索过程：(4)扩展扩展2
38、号节点，生成号节点，生成A节节点和点和4号节点。号节点。(5)扩展扩展4号节点，生成号节点，生成t2节节点和点和B节点。由于节点。由于t2为终止节为终止节点，则标记它为可解节点，点，则标记它为可解节点，并应用可解标记过程，可标并应用可解标记过程，可标记记2号节点为可解，再往上号节点为可解，再往上又可标记又可标记1号节点为可解。号节点为可解。(6)搜索成功，得到由搜索成功，得到由1、3、5、2、4号节点即号节点即t1、t2、t3节点构成的解树。节点构成的解树。西安电子科技大学西安电子科技大学与/或树的搜索策略v与与/或树的搜索策略或树的搜索策略与与/或树的一般搜索过程或树的一般搜索过程与与/或树的广度优先搜索或树的广度优先搜索与与/或树的深度优先搜索或树的深度优先搜索与与/或树的启发式搜索或树的启发式搜索博弈树的启发式搜索博弈树的启发式搜索-剪枝技术剪枝技术西安电子科技大学西安电子科技大学
