问题求解的基本原理

问题求解的基本原理第一页，共七十九页，编辑于2023年，星期二2.1概述人工智能解决问题的过程可以抽象为一个问题的求解过程。问题求解就是通过在某个可能的解空间内搜索，在有限的步长内寻找到一个能解决某类问题的解。第二页，共七十九页，编辑于2023年，星期二什么是搜索1、搜索引起：人工智能所要解决的问题大部分是结构不良或非结构化的问题，对这样的问题一般不存在成熟的求解算法可供利用，而只能是利用已有的知识一步步地摸索着前进。在此过程中，存在着如何寻找可用知识的问题，即如何确定推理路线，使其付出的代价尽可能的少，而问题又能得到较好的解决。2、搜索：根据问题的实际情况不断寻找可利用的知识，从而构造一条代价较少的推理路线，使问题得到圆满解决的过程称为搜索。第三页，共七十九页，编辑于2023年，星期二求解问题的步骤

目标的表示搜索（工作过程的动作表示）执行（执行动作）问题的形式化的定义（问题的表示）初始状态集合：所处的环境。操作符集合：把一个问题从一个状态变换为另一个状态的动作集合。目标测试函数：确定一个状态是否是目标。路径费用函数例子：书33的8数码游戏第四页，共七十九页，编辑于2023年，星期二搜索分类：分为盲目搜索和启发式搜索。A、盲目搜索：是按预定的控制策略进行搜索，在搜索过程中获得的中间信息不用来改进控制策略。由于搜索总是按预先规定的路线进行，没有考虑到问题本身的特性，所以这种搜索具有盲目性，效率不高，不便于复杂问题的求解。B、启发式搜索：是在搜索中加入了与问题有关的启发性信息，用以指导搜索朝着最有希望的方向前进，加速问题的求解过程并找到最优解。（显然，启发式搜索优于盲目搜索。但由于启发式搜索需要具有与问题本身特性有关的信息，而这并非对每一类问题都可方便地抽取出来，因此盲目搜索仍不失为一种应用较多的搜索策略。）第五页，共七十九页，编辑于2023年，星期二问题求解的性能完备性：是否能找到解最优性：找到最优解时间复杂度：找到一个解花费时间空间复杂度：需多少存储空间第六页，共七十九页，编辑于2023年，星期二1、状态空间表示法状态空间表示法是人工智能中最基本的形式化方法，也是讨论问题求解技术的基础。状态空间表示法是用“状态”和“算符”来表示问题的一种方法。2.2盲目搜索策略第七页，共七十九页，编辑于2023年，星期二1、状态：状态是描述问题求解过程中任一时刻状况的数据结构，一般用一组变量的有序组合表示：SK=（SK0,SK1，…）当给每一个分量以确定的值时，就得到了一个具体的状态。2、算符：算符引起状态中某些分量发生变化，从而使问题由一个状态变为另一个状态的操作称为算符。当到达目标状态时，由初始状态到目标状态所用算符的序列就是问题的一个解。第八页，共七十九页，编辑于2023年，星期二3、状态空间：由问题的全部状态及一切可用算符所构成的集合称为问题的状态空间。状态空间是一个四元组：（S，O，S0，G），其中S为状态集合，O为算符集合，S0为初始状态集合，G为目标状态集合。4、状态空间的图示形式称为状态空间图。其中，节点表示状态；有向边（弧）表示算符。第九页，共七十九页，编辑于2023年，星期二例1

二阶梵塔问题。设有1、2、3三根钢针，在1号钢针上穿有A、B两个金片，A小于B，A位于B的上面。要求把这两个金片全部移到另一根钢针上，而且规定每次只能移动一片，任何时刻都不能使B位于A的上面。第十页，共七十九页，编辑于2023年，星期二第十一页，共七十九页，编辑于2023年，星期二第十二页，共七十九页，编辑于2023年，星期二解1：A、B都搬到3上：A(1,2)B(1,3)A(2,3)第十三页，共七十九页，编辑于2023年，星期二解2：A、B都搬到2上：A(1,3)B(1,2)A(3,2)第十四页，共七十九页，编辑于2023年，星期二6、状态空间方法求解问题特点：（a）用状态空间方法表示问题时，首先必须定义状态的描述形式，通过使用这种描述形式可把问题的一切状态都表示出来。其次，还要定义一组算符，通过使用算符可把问题由一种状态转变为另一种状态。（b）问题的求解过程是一个不断把算符作用于状态的过程。5、状态空间图搜索求解步骤（书37）第十五页，共七十九页，编辑于2023年，星期二（c）算符的一次使用，就使问题由一种状态转变为另一种状态。可能有多个算符序列都可使问题从初始状态变到目标状态，这就得到了多个解。（d）对任何一个状态，可使用的算符可能不止一个，这样由一个状态所生成的后继状态就可能有多个。当对这些后继状态使用算符生成更进一步的状态时，首先应对哪一个状态进行操作呢？这取决于搜索策略，不同搜索策略的操作顺序是不相同的，这正是本章要讨论的问题。第十六页，共七十九页，编辑于2023年，星期二2、与／或树表示法（与／或树是用于表示问题及其求解过程的又一种形式化方法，通常用于表示比较复杂问题的求解）。对于一个复杂问题，直接求解往往比较困难。此时，可通过下述方法进行简化：1、分解：把一个复杂问题分解为若干个较为简单的子问题，每个子问题又可继续分解为若干个更为简单的子问题，重复此过程，直到不需要再分解或者不能再分解为止。然后对每个子问题分别进行求解，最后把各子问题的解复合起来就得到了原问题的解。问题的这一分解过程可用一个图表示出来。第十七页，共七十九页，编辑于2023年，星期二例如，把问题P分解为三个子问题P1，P2，P3，可用图表示。如图：P1，P2，P3是问题P的三个子问题，只有当这三个子问题都可解时，问题P才可解，称P1，P2，P3之间存在“与”关系；称节点P为“与”节点；由P，P1，P2，P3所构成的图称为“与”树。在图中，为了标明某个节点是“与”节点，通常用一条弧把各条边连接起来。第十八页，共七十九页，编辑于2023年，星期二2、等价变换：对于一个复杂问题，除了可用“分解”方法进行求解外，还可利用同构或同态的等价变换，把它变换为若干个较容易求解的新问题。若新问题中有一个可求解，则就得到了原问题的解。问题的等价变换过程，也可用一个图表示出来，称为“或”树。第十九页，共七十九页，编辑于2023年，星期二例如，问题P被等价变换为新问题P1，P2，P3。如左图所示。其中，新问题P1，P2，P3中只要有一个可解，则原问题就可解，称P1,P2，P3之间存在“或”关系；节点P称为“或”节点；由P，P1，P2，P3所构成的图是一个“或”树。上述两种方法也可结合起来使用，此时的图称为“与／或”树。其中既有“与”节点，也有“或”节点。如右图所示。第二十页，共七十九页，编辑于2023年，星期二3、基本概念：A、本原问题：不能再分解或变换，而且直接可解的子问题称为本原问题。B、端节点与终止节点：在与／或树中，没有子节点的节点称为端节点；本原问题所对应的节点称为终止节点。显然，终止节点一定是端节点，但端节点不一定是终止节点。C、可解节点：在与／或树中，满足下列条件之一者，称为可解节点：(1）它是一个终止节点。(2）它是一个“或”节点，且其子节点中至少有一个是可解节点。(3）它是一个“与”节点，且其子节点全部是可解节点。第二十一页，共七十九页，编辑于2023年，星期二D、不可解节点：关于可解节点的三个条件全部不满足的节点称为不可解节点。E、解树：由可解节点所构成，并且由这些可解节点可推出初始节点（原始问题）为可解节点的子树称为解树。在解树中一定包含初始节点。第二十二页，共七十九页，编辑于2023年，星期二例如，图(a)的解树如图(b)所示。在图中，节点p为原始问题节点，用t标出的节点是终止节点。根据可解节点的定义，很容易推出原始问题p是可解的。第二十三页，共七十九页，编辑于2023年，星期二第二十四页，共七十九页，编辑于2023年，星期二第二十五页，共七十九页，编辑于2023年，星期二第二十六页，共七十九页，编辑于2023年，星期二第二十七页，共七十九页，编辑于2023年，星期二第二十八页，共七十九页，编辑于2023年，星期二S(3,3,1)S(3,3,3)第二十九页，共七十九页，编辑于2023年，星期二2.3状态空间的搜索策略第三十页，共七十九页，编辑于2023年，星期二一、状态空间的一般搜索过程

一个复杂问题的状态空间一般都是十分宠大的。若把它们都存储到计算机中去，需占用巨大的存储空间。另一方面，对一个确定的具体问题来说，与解题有关的状态空间往往只是整个状态空间的一部分，因此只要能生成并存储这部分状态空间就可求得问题的解。对一个具体问题，如何生成它所需要的部分状态空间从而实现对问题的求解呢？第三十一页，共七十九页，编辑于2023年，星期二1、基本思想：A、把问题的初始状态（即初始节点）作为当前状态；B、选择适用的算符对其进行操作，生成一组子状态（或称后继状态、后继节点、子节点）；C、然后检查目标状态是否在其中出现。若出现，则搜索成功，找到了问题的解；若不出现，则按某种搜索策略从已生成的状态中再选一个状态作为当前状态；D、重复B、C，直到目标状态出现或者不再有可供操作的状态及算符时为止。第三十二页，共七十九页，编辑于2023年，星期二2、状态空间的一般搜索过程：OPEN表：用于存放刚生成的节点。对于不同的搜索策略，节点在OPEN表中的排列顺序是不同的。CLOSED表：用于存放将要扩展或者已扩展的节点。所谓对一个节点进行“扩展”是指：用合适的算符对该节点进行操作，生成一组子节点。第三十三页，共七十九页，编辑于2023年，星期二第三十四页，共七十九页，编辑于2023年，星期二搜索的一般过程如下：①把初始节点S0放入OPEN表，并建立目前只包含S0的图，记为G。②检查OPEN表是否为空，若为空则问题无解，退出。③把OPEN表的第一个节点取出放入CLOSED表，并记该节点为节点n。④考察节点n是否为目标节点。若是，则求得了问题的解，退出。⑤扩展节点n，生成一组子节点。把其中不是节点n先辈的那些子节点记作集合M，并把这些子节点作为节点n的子节点加入G中。第三十五页，共七十九页，编辑于2023年，星期二⑥针对M中子节点的不同情况，分别进行如下处理：A、对于那些未曾在G中出现过的M成员设置一个指向父节点（即节点n）的指针，并把它们放入OPEN表。B、对于那些先前已在G中出现过的M成员，确定是否需要修改它指向父节点的指针。C、对于那些先前已在G中出现并且已经扩展了的M成员，确定是否需要修改其后继节点指向父节点的指针。⑦按某种搜索策略对OPEN表中的节点进行排序。⑧转第（2）步。第三十六页，共七十九页，编辑于2023年，星期二第三十七页，共七十九页，编辑于2023年，星期二例1：实心黑点代表已扩展了的节点，它们位于CLOSED表上；空心圆圈代表未扩展的节点，它们位于OPEN表上；有向边旁的箭头是指向父节点的指针。每边代价为1。第三十八页，共七十九页，编辑于2023年，星期二扩展节点1：假设现在要扩展节点1，并且只生成单一的后继节点2。但是目前节点2已有父节点3，即节点2在先前扩节点3时已被生成了，现在又作为节点1的后继节点被再次生成。此时，为确定哪一个节点作为节点2的父节点，需要计算路径代价。从S0经节点1到节点2的代价为2，而从S0经节点3到节点2的代价为4，显然经节点1到节点2的代价较小，因此应修改节点2指向父节点的指针，让它指向节点1，即把节点1作为节点2的父节点，不再以节点3作为它的父节点。第三十九页，共七十九页，编辑于2023年，星期二另外，节点4既是节点2的后继节点又是节点6的后继节点，当节点2以节点3为父节点时，由于从S0经节点2到节点4的代价大于从S0经节点6到节点4的代价，所以节点4以节点6为父节点。但是，经扩展节点1之后，从S0经节点2到节点4的代价为3，而从S0经节点6到节点4的代价为4，所以节点4不能再以节点6为父节点，而需要改为以节点2为父节点。第四十页，共七十九页，编辑于2023年，星期二第四十一页，共七十九页，编辑于2023年，星期二第四十二页，共七十九页，编辑于2023年，星期二二、广度优先搜索——宽度优先搜索1、基本思想：

从初始节点S0开始，逐层地对节点进行扩展并考察它是否为目标节点，在第n层的节点没有全部扩展并考察之前，不对第n+1层的节点进行扩展。OPEN表中的节点总是按进入的先后顺序排列，先进入的节点排在前面，后进入的排在后面。第四十三页，共七十九页，编辑于2023年，星期二2、搜索过程：①把初始节点S0放入OPEN表。②如果OPEN表为空，则问题无解，退出。③把OPEN表的第一个节点（记为节点n）取出放入CLOSED表。④考察节点n是否为目标节点。若是，则求得了问题的解，退出。⑤若节点n不可扩展，则转第②步。⑥扩展节点n，将其子节点(不含先辈节点)放入OPEN表的尾部，并为每一个子节点都配置指向父节点的指针，然后转第②步。第四十四页，共七十九页，编辑于2023年，星期二例：重排九宫问题。在3×3的方格棋盘上放置分别标有数字1,2,3,4,5,6,7,8的八张牌，初始状态为S0，目标状态为Sg，如图所示。可使用的算符有：空格左移，空格上移，空格右移，空格下移。即，它们只允许把位于空格左，上，右，下边的牌移入空格。要求寻找从初始状态到目标状态的路径。第四十五页，共七十九页，编辑于2023年，星期二由图3可以看出，解的路径是S0——3——8——16——26。第四十六页，共七十九页，编辑于2023年，星期二

广度优先搜索的优劣：①缺点：盲目性较大，当目标节点距离初始节点较远时将会产生许多无用节点，搜索效率低。②优点：只要问题有解，用广度优先搜索总可以得到解，而且得到的是路径最短的解。第四十七页，共七十九页，编辑于2023年，星期二三、深度优先搜索：1、基本思想：

从初始节点S0开始扩展，若没有得到目标节点，则选择最后产生的子节点进行扩展，若还是不能到达目标节点，则再对刚才最后产生的子节点进行扩展，一直如此向下搜索。当到达某个子节点，且该子节点既不是目标节点又不能继续扩展时，才选择其兄弟节点进行考察。第四十八页，共七十九页，编辑于2023年，星期二2、其搜索过程如下：

①把初始节点S0放入OPEN表。②如果OPEN表为空，则问题无解，退出。③把OPEN表的第一个节点（记为节点n）取出放入CLOSED表。④考察节点n是否为目标节点。若是，则求得了问题的解，退出。⑤若节点n不可扩展，则转第②步。⑥扩展节点n，将其子节点放入到OPEN表的首部，并为其配置指向父节点的指针，然后转第②步。

该过程与广度优先搜索的唯一区别是：广度优先搜索是将节点n的子节点放入到OPEN表的尾部，而深度优先搜索是把节点n的子节点放入到OPEN表的首部。第四十九页，共七十九页，编辑于2023年，星期二例3：重排九宫问题进行深度优先搜索。（图中只是搜索树的一部分，尚未到达目标节点，仍可继续往下搜索。）第五十页，共七十九页，编辑于2023年，星期二深度优先搜索的特点：

在深度优先搜索中，搜索一旦进入某个分支，就将沿着该分支一直向下搜索。如果目标节点恰好在此分支上，则可较快地得到解。但是，如果目标节点不在此分支上，而该分支又是一个无穷分支，则就不可能得到解。所以深度优先搜索是不完备的，即使问题有解，它也不一定能求得解。另外，用深度优先搜索求得的解，不一定是路径最短的解。

第五十一页，共七十九页，编辑于2023年，星期二四、有界深度优先搜索：1、提出：为了解决深度优先搜索不完备的问题，避免搜索过程陷入无穷分支的死循环，提出了有界深度优先搜索方法。2、基本思想：对深度优先搜索引入搜索深度的界限（设为dm)，当搜索深度达到了深度界限，而尚未出现目标节点时，就换一个分支进行搜索。第五十二页，共七十九页，编辑于2023年，星期二3、搜索过程：①把初始节点S0放入OPEN表中，置S0的深度d（S0)=0。②如果OPEN表为空，则问题无解，退出。③把OPEN表中的第一个节点（记为节点n）取出放入CLOSED表。④考察节点n是否为目标节点。若是，则求得了问题的解，退出。⑤如果节点n的深度d（节点n）=dm，则转第②步。⑥若节点n不可扩展，则转第②步。⑦扩展节点n，将其子节点放入OPEN表的首部，并为其配置指向父节点的指针。然后转第②步。第五十三页，共七十九页，编辑于2023年，星期二关于dm的讨论：①如果问题有解，且其路径长度<=dm，则上述搜索过程一定能求得解。但是，若解的路径长度＞dm，则上述搜索过程就得不到解。②当dm太大时，搜索时将产生许多无用的子节点，既浪费了计算机的存储空间与时间，又降低了搜索效率。③dm的选择：先任意给定一个较小的数作为dm，然后进行上述的有界深度优先搜索，当搜索达到了指定的深度界限dm仍未发现目标节点，并且CLOSED表中仍有待扩展节点时，就将这些节点送回OPEN表，同时增大深度界限dm，继续向下搜索。如此不断地增大dm，只要问题有解，就一定可以找到它。但此时找到的解不一定是最优解。第五十四页，共七十九页，编辑于2023年，星期二④为找到最优解，可增设一个表（R)，每找到一个目标节点后，就把它放入到R的前面，并令dm等于该目标节点所对应的路径长度，然后继续搜索。由于后求得的解的路径长度不会超过先求得的解的路径长度，所以最后求得的解一定是最优解。第五十五页，共七十九页，编辑于2023年，星期二例4：设深度界度dm=4，用有界深度优先搜索方法求解重排九宫问题。）解的路径是S0—20—25—26—28。第五十六页，共七十九页，编辑于2023年，星期二五、代价树的广度优先搜索

代价树：边上标有代价（或费用）的树称为代价树。代价树中，用c（x1，x2）表示从父节点x1到子节点x2的代价。用g（x）表示从初始节点S0到节点x的代价。代价计算公式：g（x2)=g（x1)+c（x1，x2)第五十七页，共七十九页，编辑于2023年，星期二1、代价树广度优先搜索的基本思想：

每次从OPEN表中选择节点往CLOSED表传送时，总是选择其代价为最小的节点。（也就是说，OPEN表中的节点在任一时刻都是按其代价从小至大排序的，代价小的节点排在前面，代价大的节点排在后面，而不管节点在代价树中处于什么位置上。）第五十八页，共七十九页，编辑于2023年，星期二

2、代价树广度优先搜索的搜索过程：(1）把初始节点S0放入OPEN表，令g(S0)=0。(2）如果OPEN表为空，则问题无解，退出。(3）把OPEN表的第一个节点（记为节点n）取出放入CLOSED表。(4）考察节点n是否为目标节点。若是，则求得了问题的解，退出。(5）若节点n不可扩展，则转第（2）步。(6）扩展节点n，将其子节点放入OPEN表中，且为其配置指向父节点的指针；计算各子节点的代价，并按各节点的代价对OPEN表中的全部节点进行排序（按从小到大的顺序），然后转第（2）步。如果问题有解，该搜索过程一定能求得，并且求出的是最优解。第五十九页，共七十九页，编辑于2023年，星期二例1：如图1为五城市间的交通路线图，A城市是出发地，E城市是目的地，两城市间的交通费用（代价）如图中数字所示。求从A到E的最小费用交通路线。第六十页，共七十九页，编辑于2023年，星期二为了应用代价树的广度优先搜索方法求解此问题，需先将交通图转换为代价树，如图2所示。转换的方法是：①从起始节点A开始，把与它直接相邻的节点作为它的子节点。对其它节点也做相同的处理。②若一个节点已作为某节点的直系先辈节点时，就不能再作为这个节点的子节点。③图中的节点除起始节点A外，其它节点都可能要在代价树中出现多次，为区分它的多次出现，分别用下标1,2，…标出，其实它们都是图中的同一节点。例如El,E2,E3,E4都是图中的节点E。对此代价树进行代价树的广度优先搜索，可得到最优解为A一Cl一Dl一E2代价为8。由此可知从A城市到E城市的最小费用路线为A一C一D一E。第六十一页，共七十九页，编辑于2023年，星期二八、代价树的深度优先搜索1、基本思想：

代价树的深度优先搜索是从刚扩展出的子节点中选一个代价最小的节点送入CLOSED表进行考察。（而在代价树的广度优先搜索中，每次都是从OPEN表的全体节点中选择一个代价最小的节点送入CLOSED表进行考察。）

第六十二页，共七十九页，编辑于2023年，星期二2、代价树深度优先搜索的过程：(1）把初始节点S0放入OPEN表中。(2）如果OPEN表为空，则问题无解，退出。(3）把OPEN表的第一个节点（记为节点n）取出放入CLOSED表。(4）考察节点n是否为目标节点。若是，则求得了问题的解，退出。(5）若节点n不可扩展，则转第(2)步。(6）扩展节点n，将其子节点按边代价从小到大的顺序放到OPEN表的首部，并为各子节点配置指向父节点的指针，然后转第(2)步。第六十三页，共七十九页，编辑于2023年，星期二例如，在上图所示的代价树中，首先对A进行扩展，得到Cl及Bl，由于Cl的代价小于Bl的代价，所以首先把Cl送入CLOSED表进行考察。此时代价树的广度优先搜索与代价树的深度优先搜索是一致的。但往下继续进行时，两者就不一样了。对Cl进行扩展得到Dl，Dl的代价为5。此时OPEN表中有Bl与Dl,Bl的代价为4。若按代价树的广度优先搜索方法进行搜索，应选Bl送入CLOSED表，但按代价树的深度优先搜索方法，则应选Dl送入CLOSED表。Dl扩展后，再选E2，到达了目标节点。所以，按代价树的深度优先搜索方法，得到的解是A一Cl一Dl一E2代价为8。第六十四页，共七十九页，编辑于2023年，星期二5.3与／或树的搜索策略第六十五页，共七十九页，编辑于2023年，星期二一、与／或树的一般搜索过程：1、概念对于一个“与”节点，只有当其子节点全部为可解节点时，它才为可解节点，只要子节点中有一个为不可解节点，它就是不可解节点。对与一个“或”节点，只要子节点中有一个是可解节点，它就是可解节点，只有当全部子节点都是不可解节点时，它才是不可解节点。可解标示过程：由可解子节点来确定父节点、祖父节点等为可解节点的过程称为可解标示过程。不可解标示过程：由不可解子节点来确定其父节点、祖父节点等为不可解节点的过程称为不可解标示过程。第六十六页，共七十九页，编辑于2023年，星期二2、与／或树的一般搜索过程：(a）把原始问题作为初始节点S0，并把它作为当前节点。(b）应用分解或等价变换算符对当前节点进行扩展。(c）为每个子节点设置指向父节点的指针。(d）选择合适的子节点作为当前节点，反复执行第（b）步和第（c）步，在此期间要多次调用可解标示过程和不可解标示过程，直到初始节点被标示为可解节点或不可解节点为止。可解与不可解标示过程都是由下而上进行的。第六十七页，共七十九页，编辑于2023年，星期二由这个搜索过程所形成的节点和指针结构称为搜索树。与／或树搜索的目标是寻找解树，从而求得原始问题的解。如果在搜索的某一时刻，通过可解标示过程可确定初始节点是可解的，则由此初始节点及其下属的可解节点就构成了解树。如果已确定某个节点为可解节点，则其不可解的后裔节点就不再有用，可从搜索树中删去；同样，如果已确定某个节点是不可解节点，则其全部后裔节点都不再有用，可从搜索树中删去，但当前这个不可解节点还不能删去，因为在判断其先辈节点的可解性时还要用到它。第六十八页，共七十九页，编辑于2023年，星期二二、与／或树的广度优先搜索：

搜索过程如下：(1）把初始节点S0放入OPEN表。(2）把OPEN表中的第一个节点（记为节点n）取出放入CLOSED表。(3）如果节点n可扩展，则做下列工作。①扩展节点n，将其子节点放入OPEN表的尾部，并为每个子节点配置指向父节点的指针，以备标示过程使用。

第六十九页，共七十九页，编辑于2023年，星期二②考察这些子节点中有否终止节点。若有，则标示这些终止节点为可解节点，并将它们也放入CLOSED表，然后应用可解标示过程对其父节点、祖父节点等先辈节点中的可解节点进行标示。如果初始节点S0也被标示为可解节点，就得到了解树，搜索成功，退出搜索过程；如果不能确定S0为可解节点，则从OPEN表中删去具有可解先辈的节点。(因为其先辈节点已可解，故已无再考察节点的必要)③转第（2）步。第七十页，共七十九页，编辑于2023年，星期二(4）如果节点n不可扩展，则做下列工作：①标示节点n为不可解节点。②应用不可解标示过程对节点n的先辈节点中不可解的节点进行标示。如果初始节点S0也被标示为不可解节点，则搜索失败，表明原始问题无解，退出搜索过程；如果不能确定S0为不可解节点，则从OPEN表中删去具有不可解先辈的节点。(因为其先辈节点已不可解，故已无再考察这些节点的必要)③转第(2)步。第七十一页，共七十九页，编辑于2023年，星期二例:设有如图所示的与／或树。其中标有t1，t2，t3，t4的节点均为终止节点，A和B为不可解的端节点。第七十二页，共七十九页，编辑于2023年，星期二搜索过程为：

(l）首先扩展1号节点，得到2号节点和3号节点，由于这两个子节点均不是终止节点，所以接着扩展2号节点。此时OPEN表中只剩下3号节点。

(2）扩展2号节点后，得到4号节点和t1节点。此时OPEN表中的节点有：3号节点、4号节点及t1节点。由于t1是终止节点，则标示它为可解节点，并应用可解标示过程，对其先辈节点中的可解节点进行标示。在此例中，t1的父节点是一个“与”节点，因此仅由t1可解尚不能确定2号节点是否为可解节点。将t1放入closed表中，继续搜索，下一步扩展的是3号节点。第七十三页，共七十九页，编辑于2023年，星期二(3）扩展3号节点得到5号节点与B节点，两者均不是终止节点，所以接着扩展4号节点。(4）扩展4号节点后得到节点A和t2。由于t2是终止节点，所以标示它为可解节点，放入closed中，并应用可解标示过程标示出4号节点、2号节点均为可解节点，但1号节点目前还不能确定它是否为可解节点。删除2的后继