新人工智能课件

一个智能系统搜索策略的优劣直接影响到系统的性能语推理效率。

本章主要内容：搜索的基本概念；状态空间的盲目搜索；状态空间的启发式搜索；与或树的盲目搜索；与或树的启发式搜索；博奕树的启发式搜索；第5章搜索测略1一个智能系统搜索策略的优劣直接影响到系5.1搜索策略的基本概念

5.1.1搜索的含义1.搜索定义:根据问题的实际情况，不断寻找可利用的知识，从而构造一条代价最小的推理路线，使问题得以解决的过程称为搜索。2.组合爆炸问题：结构良好，理论上有算法可依的问题，如果问题或算法的复杂性较高（按指数形式增长），由于受计算机在时间和空间上的限制，无法付诸实用。25.1搜索策略的基本概念5.1.1搜索的含义25.1搜索策略的基本概念3.搜索类型：(1)根据是否使用启发信息分类：盲目搜索：按预定的控制策略进行，在搜索过程中获得的中间信息不改变控制策略。启发式搜索：在搜索过程中加入了与问题有关的启发性信息，用于指导搜索朝着最有希望的方向前进，加速问题的求解过程并找到最优解。35.1搜索策略的基本概念3.搜索类型：35.1搜索策略的基本概念(2)根据问题的表示方式分类：状态空间搜索：用状态空间法来求解问题所进行的搜索。与/或树搜索：用问题归约法来求解问题时所进行的搜索。45.1搜索策略的基本概念(2)根据问题的表示方式分类：45.1搜索策略的基本概念5.1.2状态空间法1.状态空间表示法（1）状态(state):表示问题求解过程中每一步问题状况的数据结构，形式的表示为：

Sk={Sk0,Sk1,…)当对每一个分量都予以确定的值时，就得到了一个具体的状态。55.1搜索策略的基本概念5.1.2状态空间法55.1搜索策略的基本概念（2）操作（operator)（算符）把问题从一种状态转换为另一种状态的手段。可以是一个机械步骤、一个运算、一条规则或一个过程。可理解为状态集合上的一个函数，描述了状态之间的关系。65.1搜索策略的基本概念（2）操作（operator)（算符5.1搜索策略的基本概念（3）状态空间（statespace）描述一个问题的全部状态以及这些状态之间的相互关系。常用三元组表示:(S,F,G)S:为问题所有初始状态的集合。

F:为操作的集合。

G:为目标状态的集合。75.1搜索策略的基本概念（3）状态空间（statespac5.1搜索策略的基本概念状态空间图：赋值的有向图。节点表示问题的状态，有向边表示操作.2.状态空间问题求解任何以状态和操作为基础的问题求解方法都称为状态空间问题求解。简称为状态空间法。状态空间法的基本过程为：（1）为问题选择适当的“状态”及“操作”的形式化描述方法。85.1搜索策略的基本概念状态空间图：赋值的有向图。节点表示5.1搜索策略的基本概念（2）从某个初始状态出发，每次使用一个“操作”，递增地建立起操作序列，直到达到目标状态为止。（3）从初始状态到目标状态所使用的算符序列就是问题的一个解。95.1搜索策略的基本概念（2）从某个初始状态出发，每次使用一5.1搜索策略的基本概念3.状态空间的例子例5.1:二阶梵塔问题：设有三根钢针，它们的编号分别是1，2，3。在初始情况下，1号钢针上穿有A、B两个金片，A比B小，A位于B的上面。要求把这两个金片全部移到另一根钢针上，而且规定每次只能移动一个金片，任何时刻都不能使大片位于小片的上面。105.1搜索策略的基本概念3.状态空间的例子105.1搜索策略的基本概念解：设用Sk={Sk0,Sk1}表示问题的状态，其中，Sk0表示金片A所在的钢针号，Sk1表示金片B所在的钢针号。全部可能的问题状态共有以下9种：S0=(1,1)S1=(1,2)S2=(1,3)S3=(2,1)S4=(2,2)S5=(2,3)S6=(3,1)S7=(3,2)S8=(3,3)其中S0为初始状态，S4和S8为目标状态。115.1搜索策略的基本概念解：设用Sk={Sk0,Sk1}表5.1搜索策略的基本概念任何以状态和操作为基础的问题求解方法都称为状态空间问题求解。简称为状态空间法。状态空间法的基本过程为：（1）为问题选择适当的“状态”及“操作”的形式化描述方法。（2）从某个初始状态出发，每次使用一个“操作”，递增地建立起操作序列，直到达到目标状态为止。（3）从初始状态到目标状态所使用的算符序列就是问题的一个解。125.1搜索策略的基本概念任何以状态和操5.1搜索策略的基本概念例5.2修道士和野人问题.首先选取描述问题状态的方法。用一个三元组表示状态：S=(m,c,b)其中：m表示左岸的修道士数；c表示左岸的野人数；b表示左岸的船数；135.1搜索策略的基本概念例5.2修道士和野人问题.135.1搜索策略的基本概念右岸的状态由下式确定：右岸的修道士数m’=3-m；右岸的野人数c’=3-c；

右岸的船数b’=1-b；

m和c的取值分别为0，1，2，3之一；b的取值分别为0，1;

共有4x4x2=32种状态。145.1搜索策略的基本概念右岸的状态由下式确定：145.1搜索策略的基本概念3,32,12,31,21,3A(3,2)2,23,23,11,1B(1,2)A(1,3)二阶樊塔状态空间图155.1搜索策略的基本概念3,32,12,31,21,3A(35.1搜索策略的基本概念除去不合法的状态和修道士被野人吃掉的状态，余下的状态由16种：S0=(3,3,1),S1=(3,2,1),S2=(3,1,1),S3=(2,2,1),S4=(1,1,1),S5=(0,3,1),S6=(0,2,1),S7=(0,1,1),S8=(3,2,0),S9=(3,1,0),S10=(3,0,0),S11=(2,2,0),S12=(1,1,0),S13=(0,2,0),S14=(0,1,0),S15=(0,0,0),165.1搜索策略的基本概念除去不合法的状态和修道士被野人吃掉的5.1搜索策略的基本概念需要考虑的操作有：（1）船至少有一个人（m或c）操作，离开岸边的m和c的减少数目应该等于到达岸边的m和c的增加数目；（2）每次操作船上的人数不得超过2个；（3）操作应保证不产生非法状态。操作由两部分组成：条件部分和动作部分。175.1搜索策略的基本概念需要考虑的操作有：175.1搜索策略的基本概念用Qij表示从右岸到左岸的运人操作，可供选择的操作由10种，操作集为：F={P01,P10,P11,P02,P20,Q01,Q10,Q11,Q02,Q20,}以P01和Q01为例说明操作的条件和动作：操作符号条件动作P01b=1,m=0或3,c≥1b=0,c=c-1Q01b=1,m=0或3,c≤2b=1,c=c+1185.1搜索策略的基本概念用Qij表示从5.1搜索策略的基本概念例5.3猴子摘香蕉问题.

首先选取描述问题状态的方法。用一个四元组表示状态：S=(w,x,y,z)

其中：w表示猴子的水平位置；x表示箱子的水平位置；

y表示猴子是否在箱子上，当猴子在箱子上时y=1否则y=0；

z表示猴子是否拿到香蕉，当拿到香蕉时z=1否则z=0；195.1搜索策略的基本概念例5.3猴子摘香蕉问题.195.1搜索策略的基本概念所有可能的状态有：S0=(a,b,0,0),初始状态S1=(b,b,0,0),S2=(c,c,1,0),S3=(c,c,1,1),目标状态205.1搜索策略的基本概念所有可能的状态有：205.1搜索策略的基本概念允许的操作为：Goto(u):猴子走到位置u，即:(w,x,0,0)→(u,x,0,0)Pushbox(v):猴子推着箱子到水平位置v，即:(x,x,0,0)→(v,v,0,0)Climbbox:猴子爬上箱子，即:(x,x,0,0)→(x,x,1,0)Grasp:猴子拿到香蕉，即:(c,c,1,0)→(c,c,1,1)215.1搜索策略的基本概念允许的操作为：215.1搜索策略的基本概念问题的状态空间图见书P172,图5-3.由初始状态变为目标状态的操作序列为：{Goto(b),Pushbox©,Climbbox,Grasp}225.1搜索策略的基本概念问题的状态空间图见书P172,图5-5.1搜索策略的基本概念5.1.3问题归约

问题是不同于状态空间方法的另外一种形式化方法，基本思想是对问题进行分解或变换。当一个问题比较复杂时，直接求解比较困难，可以通过分解或变换，将其转化为一系列较简单的问题，然后通过对较简单的球接来实现对原问题的求解。1.问题的分解与等价变换

当把一个问题归约为子问题时，可采用对原问题的分解或变换方法。235.1搜索策略的基本概念5.1.3问题归约235.1搜索策略的基本概念（1）分解如果一个问题P可以归约为一组子问题P1,P2,…,Pn，并且只有当所有子问题Pi(I=1,2,…,n)都有解时，原问题P才有解，任何一个子问题Pi(I=1,2,…,n)无解都会导致原问题P无解。称这种归约为问题的分解。分解所得到的子问题的“与”与原问题P等价。245.1搜索策略的基本概念（1）分解245.1搜索策略的基本概念（2）等价变换如果一个问题P可以归约为一组子问题P1,P2,…,Pn，并且这些子问题Pi(I=1,2,…,n)中只要有一个有解则原问题P就有解，只有当所有的子问题都无解时，原问题P才无解，称这种归约为问题的等价变换。简称变换。即变换所得的子问题的“或”与原问题P等价。255.1搜索策略的基本概念（2）等价变换255.1搜索策略的基本概念在实际问题的归约过程中，有可能需要同时采用变换和分解的方法。无论是分解还是变换，都是要将原问题归约为一系列本原问题。所谓本原问题是指那种不能分解（或不需要分解）或变换，且可以直接解答的子问题。本原问题可以作为终止归约的限制条件。265.1搜索策略的基本概念在实际问题的归5.1搜索策略的基本概念2.问题归约的“与或树”表示

当把一个原问题归约为一系列本原问题的过程可以很方便的用一个“与或树”来表示。（1）与树（2）或树275.1搜索策略的基本概念2.问题归约的“与或树”表示275.1搜索策略的基本概念（3）与/或树285.1搜索策略的基本概念（3）与/或树285.1搜索策略的基本概念（4）端节点与终止节点端节点：没有子节点的节点。终止节点：本原问题所对应的节点。（5）可解节点与不可解节点满足以下三个条件的为可解节点:任何终止节点都是可解节点；对“或”节点，当其子节点中至少有一个可解节点时，则该或节点就是可解节点；对“与”节点，只有当其子节点全部为可解节点时，则该与节点才是可解节点。295.1搜索策略的基本概念（4）端节点与终止节点295.1搜索策略的基本概念满足以下三个条件的为不可解节点:不为终止节点的端节点是不可解节点；对“或”节点，若其全部子节点中为不可解节点时，则该或节点就是不可解节点；对“与”节点，只要其子节点中有一个为不可解节点时，则该与节点才是不可解节点。305.1搜索策略的基本概念满足以下三个条件的为不可解节点:305.1搜索策略的基本概念（6）解树由可解节点构成，并且由这些可解节点可以推出初始节点（对应着原始问题）为可解节点的子树为解树。在解树中一定包含初始节点。315.1搜索策略的基本概念（6）解树315.1搜索策略的基本概念325.1搜索策略的基本概念325.1搜索策略的基本概念3.问题归约的例子例5.4:三阶梵塔问题：设有三根钢针，它们的编号分别是1，2，3。在初始情况下，1号钢针上穿有A、B、C三个金片，自上而下，有小到大，。要求把这两个金片全部移到另一根钢针上，而且规定每次只能移动一个金片，任何时刻都不能使大片位于小片的上面。用归约法求解。335.1搜索策略的基本概念3.问题归约的例子335.1搜索策略的基本概念解：为了能够解决这一问题，首先需要定义该问题的形式化表示方法。用三元组（i,j,k)表示问题任何时刻的状态；用“→”表示状态的转换；i表示金片C的针号;j表示金片B的针号;k表示金片A的针号;345.1搜索策略的基本概念解：为了能够解决这一问题，首先需要定5.1搜索策略的基本概念利用问题归约方法，原问题可分解为以下三个子问题:(1)把金片A及B移到2号钢针上的双金片移动问题：(1,1,1)→(1,2,2)(2)把金片C移到3号钢针上的单金片移动问题：(1,2,2)→(3,2,2)(1)把金片A及B移到3号钢针上的双金片移动问题：(3,2,2)→(3,3,3)355.1搜索策略的基本概念利用问题归约方法，原问题可分解为以下5.1搜索策略的基本概念(1,1,1)→(3,3,3)(1,1,1)→(1,2,2)(3,2,2)→(3,3,3)(1,2,2)→(3,2,2)(3,3,1)→(3,3,3)(3,2,1)→(3,3,1)(3,2,2)→(3,2,1)(1,2,3)→(1,2,2)(1,1,3)→(1,2,3)(1,1,1)→(1,1,3)365.1搜索策略的基本概念(1,1,1)→(3,3,3)(15.1搜索策略的基本概念原始问题的解：(1,1,1)→(1,1,3)(1,1,3)→(1,2,3)(1,2,3)→(1,2,2)(1,2,2)→(3,2,2)

(3,2,2)→(3,2,1)(3,2,1)→(3,3,1)(3,3,1)→(3,3,3)375.1搜索策略的基本概念原始问题的解：375.2状态空间的盲目搜索状态空间的搜索策略可分为盲目搜索和启发式搜索。启发式搜索需要抽取与问题本身有关的特征信息，而信息抽取比较困难，所以盲目搜索仍不失为一种有效的搜索策略。385.2状态空间的盲目搜索状态空间的搜索策略可分为盲目搜5.2状态空间的盲目搜索5.2.1一般图搜索过程当用状态空间法解决问题时，需要考虑：（1）对于很大问题，计算机无法保存其全部状态空间；（2）对于具体问题，与解有关的状态空间一般仅是全部状态空间的一部分。因此在问题求解过程中，没有必要生成和保存该问题的全部状态空间，只要能够生成和保存与解有关的那部分状态空间即可。解决问题的方法是采用状态空间搜索技术。395.2状态空间的盲目搜索5.2.1一般图搜索过程395.2状态空间的盲目搜索对状态空间的搜索，由于问题的状态空间可用一个有向图来表示，因此状态空间搜索实际上就是对有向图的搜索。405.2状态空间的盲目搜索对状态空间的搜5.2状态空间的盲目搜索状态空间搜索的基本思想是：先把问题的初始状态作为当前扩展节点对其进行扩展，生成一组子节点，然后检查问题的目标状态是否出现在这些子节点中。若出现，则搜索成功，找到了问题的解；若没有出现，则按照某种搜索策略从已生成的子节点中选择一个节点作为扩展节点，重复上述过程，指导目标状态出现在子节点中或者没有可供扩展的节点为止。415.2状态空间的盲目搜索状态空间搜索的基本思想是：415.2状态空间的盲目搜索状态空间算法：需要设立数据结构Open和Closed表。Open表（未扩展节点表）：用于存放刚生成没有扩展的节点；Closed表（已扩展节点表）：用于存放已经扩展或将要扩展的节点。425.2状态空间的盲目搜索状态空间算法：425.2状态空间的盲目搜索状态空间的一般图搜索过程为：（1）把初始节点S0放入Open表并建立目前仅包含S0的图G;（2）检查Open表是否为空，若为空，则问题无解，失败退出；（3）把Open表的第一个节点取出放入Closed表，并记该节点为节点n;（4）考察节点n是否为目标节点。若是则得到了问题的解，成功退出；435.2状态空间的盲目搜索状态空间的一般图搜索过程为：435.2状态空间的盲目搜索（5）扩展节点n，生成一组子节点。把这些子节点中不是节点n先辈的那部分子节点记入集合M，并把这些子节点作为节点n的子节点加入G中。（6）针对M中子节点的不同情况，分别作如下处理：对那些没有在G中出现过的M成员设置一个指向其父节点（即节点n）的指针，并把它放入Open表；对那些原来已在G中出现过，但还没有被扩展的M成员，确定是否需要修改它指向父节点的指针；445.2状态空间的盲目搜索（5）扩展节点n，生成一组子节点。把5.2状态空间的盲目搜索对于先前已在G中出现过，并已经扩展了的M成员，确定是否需要修改其后继节点指向父节点的指针。（7）按某种策略对Open表中的节点进行排序；（8）转(2)步。455.2状态空间的盲目搜索对于先前已在G中出现过，并已经扩展了5.2状态空间的盲目搜索搜索过程说明：（1）状态空间图搜索算法具有通用性，其它的各种状态空间搜索策略都是上述的一个特例。各种搜索策略的主要区别在于对Open表中节点的排列顺序不同。如广度优先搜索把先生成的子节点排在前面；深度优先搜索把后生成的子节点排在前面。465.2状态空间的盲目搜索搜索过程说明：465.2状态空间的盲目搜索（2）在第(5)步对节点n扩展后，生成并记入M的子节点有以下三种情况：该子节点从未被任何节点生成过，由n第一次生成；该子节点原来被其它节点生成过，但还没有被扩展，这一次又被n再次生成；该子节点原来被其它节点生成过，并且已经被扩展过，这一次又被n再次生成。475.2状态空间的盲目搜索（2）在第(5)步对节点n扩展后，生5.2状态空间的盲目搜索对于一般图搜索算法，具有以上三种情况；对于盲目搜索，由于其状态空间是树状结构，因此不会出现后两种情况，每个节点扩展后生成的子节点都是第一次出现的节点，不必检查并修改指向父节点的指针。（3）在第（6）步针对M中子节点的不同情况进行处理时，如果发生上面第2种情况，一般是由原时节点到该节点路径上所付出的代价来决定。485.2状态空间的盲目搜索对于一般图搜索5.2状态空间的盲目搜索例题见书P1775.2.2广度优先搜索广度优先搜索也成为宽度优先搜索，是一种先生成的节点限扩展的策略。

495.2状态空间的盲目搜索例题见书P177495.2状态空间的盲目搜索广度优先搜索策略搜索过程为：从初始节点S0开始逐层向下扩展，在第n曾节点还没有全部搜索完之前，不进入第n+1层节点的搜索。Open表中的节点总是按进入的先后排序，先进入Open表的节点排在前面，后进入的节点排在后面。505.2状态空间的盲目搜索广度优先搜索策略搜索过程为：5.2状态空间的盲目搜索广度优先搜索算法如下：（1）把初始节点S0放入Open表中；（2）如果Open表为空，则问题无解，失败退出。（3）把Open表的第一个节点取出放入Closed表，并记该节点为节点n;（4）考察节点n是否为目标节点。若是则得到了问题的解，成功退出；（5）若节点n不可扩展，则转第（2）步。515.2状态空间的盲目搜索广度优先搜索算法如下：515.2状态空间的盲目搜索（6）扩展节点n，将其子节点放入Open表的尾部。并为每个子节点设置指向父节点指针，然后转第（2）步。例5.5八数码难题。见书P178525.2状态空间的盲目搜索（6）扩展节点n，将其子节点放入Op5.2状态空间的盲目搜索5.2.3深度优先搜索深度优先搜索是一种后生成的节点先扩展的策略。深度优先搜索策略搜索过程为：从初始节点S0开始，在其子节点中选择一个最新生成的节点进行考察，如果该子解不是目标节点而且可以扩展，则扩展该子节点，然后再在此子节点的子节点中选择一个最新生成的节点进行考察，依次向下搜索，直到某个子节点即不是目标节点，又不能继续扩展时，才选择其兄弟节点进行考察。535.2状态空间的盲目搜索5.2.3深度优先搜索535.2状态空间的盲目搜索Open表示一种栈结构，最先进入的节点排在最后面，最后进入的节点排在最前面。

深度优先搜索算法如下：（1）把初始节点S0放入Open表中；（2）如果Open表为空，则问题无解，失败退出。（3）把Open表的第一个节点取出放入Closed表，并记该节点为节点n;545.2状态空间的盲目搜索Open表示一5.2状态空间的盲目搜索（4）考察节点n是否为目标节点。若是则得到了问题的解，成功退出；（5）若节点n不可扩展，则转第（2）步。（6）扩展节点n，将其子节点放入Open表的首部。并为每个子节点设置指向父节点指针，然后转第（2）步。例5.6八数码难题。见书P179555.2状态空间的盲目搜索（4）考察节点n是否为目标节点。若是5.2状态空间的盲目搜索5.2.4有界深度优先搜索深度优先搜索如果目标不在搜索的分支上，且该分支又是一个无限分支，则搜索过程就不可能找到解。即使能够找到节，按深度优先找到的解也不一定是最优解。有界深度优先搜索过程总体上按深度优先策略进行，但对搜索深度需要给出一个深度限制dm，当搜索深度达到了dm，但还没有找到目标时，就停止该分支的搜索，换到另外一个分支进行搜索。565.2状态空间的盲目搜索5.2.4有界深度优先搜索565.2状态空间的盲目搜索有界深度优先搜索算法如下：（1）把初始节点S0放入Open表中；（2）如果Open表为空，则问题无解，失败退出。（3）把Open表的第一个节点取出放入Closed表，并记该节点为节点n;（4）考察节点n是否为目标节点。若是则得到了问题的解，成功退出；575.2状态空间的盲目搜索有界深度优先搜索算法如下：575.2状态空间的盲目搜索（5）若节点n的深度d(n)=dm，则转第（2）步。(6)若节点n不可扩展，则转第（2）步。（7）扩展节点n，将其子节点放入Open表的首部。并为每个子节点设置指向父节点指针，然后转第（2）步。例5.7八数码难题。见书P180585.2状态空间的盲目搜索（5）若节点n的深度d(n)=dm，5.2状态空间的盲目搜索5.2.5代价树搜索需要在搜索树的每条边标上其代价。这种有代价的树称为代价树。在代价树中，用g(n)表示从初始节点S0到节点n的代价，用c(n1,n2)表从父节点n1到其子节点n2的代价，对节点n2的代价有：

g(n2)=g(n1)+c(n1,n2)595.2状态空间的盲目搜索5.2.5代价树搜索595.2状态空间的盲目搜索在代价树中，最小代价的路径和最短路径（即路径长度最短）是有可能的。最短路径不一定是代价最小的路径；代价最小的路径不一定是最短路径。1.代价树的广度优先搜索代价树的广度优先搜索也称为分枝界限法。每次从Open表中选择节点或往closed表中存放节点时，总是选择代价小的节点排在前面，代价大的排在后面，与节点在树中的位置无关。605.2状态空间的盲目搜索在代价树中，最5.2状态空间的盲目搜索代价树的广度优先搜索算法如下：（1）把初始节点S0放入Open表中，置S0的代价g(s0)=0；（2）如果Open表为空，则问题无解，失败退出。（3）把Open表的第一个节点取出放入Closed表，并记该节点为节点n;（4）考察节点n是否为目标节点。若是则得到了问题的解，成功退出；615.2状态空间的盲目搜索代价树的广度优先搜索算法如下：615.2状态空间的盲目搜索(5)若节点n不可扩展，则转第（2）步。(6）扩展节点n，生成子节点ni(I=1,2,…),将这些子节点放入Open表中，并为每个子节点设置指向父节点指针；按如下公式：

g(ni)=g(n)+c(n,ni)(i=1,2,…)计算各自节点的代价，并根据各节点的代价对Open表中的全部按照从小到大顺序重新进行排序，然后转第（2）步。625.2状态空间的盲目搜索(5)若节点n不可扩展，则转第（5.2状态空间的盲目搜索代价树的广度优先搜索是完备的，如果问题有解，上述算法一定能够找到，并且找到的是最优解。例5.8城市交通问题。P181635.2状态空间的盲目搜索代价树的广度5.2状态空间的盲目搜索2.代价树的深度优先搜索代价树的深度优先搜索每次从Open表中选择节点或往closed表中存放节点时，总是从刚扩展的子节点中选择一个代价最小的节点。645.2状态空间的盲目搜索2.代价树的深度优先搜索645.2状态空间的盲目搜索代价树的深度优先搜索算法如下：（1）把初始节点S0放入Open表中，置S0的代价g(s0)=0；（2）如果Open表为空，则问题无解，失败退出。（3）把Open表的第一个节点取出放入Closed表，并记该节点为节点n;（4）考察节点n是否为目标节点。若是则得到了问题的解，成功退出；655.2状态空间的盲目搜索代价树的深度优先搜索算法如下：655.2状态空间的盲目搜索(5)若节点n不可扩展，则转第（2）步。(6）扩展节点n，生成子节点ni(I=1,2,…),将这些子节点按边代价由小到大放入Open表的首部，并为每个子节点设置指向父节点指针。然后转第（2）步。例5.8城市交通问题。665.2状态空间的盲目搜索(5)若节点n不可扩展，则转第（5.3状态空间的启发式搜索5.3.1启发性信息和估价函数启发式搜索方法所依据的是问题自身的启发性信息，启发性信息又是通过估价函数作用到搜索过程中。1.启发性信息启发性信息是至于具体问题求解过程无关的，并可指导搜索过程朝着最有希望方向前进的控制信息。675.3状态空间的启发式搜索5.3.1启发性信息和估价函数5.3状态空间的启发式搜索启发性信息一般有三种:(1)有效地帮助确定扩展节点的信息。(2)有效地帮助决定哪些后继节点应被生成的信息。(3)能决定在扩展一个节点时哪些节点应从搜索树上删除的信息。搜索过程的启发性信息的启发能力越强，扩展的无用节点就越少。685.3状态空间的启发式搜索启发性信息一般有三种:685.3状态空间的启发式搜索2.估价函数用来估计节点重要性的函数称为估价函数。估价函数f(n)被定义为从初始节点S0出发到，约束经过节点n到达目标节点Sg的所有路径中最小路径代价的估计值。其一般形式为：

F(n)=g(n)+h(n)其中：g(n)是从初始节点S0到节点n的实际代价；h(n)是从节点n到目标节点Sg的最优路径的估计代价。695.3状态空间的启发式搜索2.估价函数695.3状态空间的启发式搜索例5.9八数码难题P1835.3.2A算法在图搜索算法中，如果能在搜索的每一步都利用估价函数F(n)=g(n)+h(n)对Open表中的节点进行排序，则该搜索算法为A算法，由于估价函数中带有自身的启发性信息，A算法又称为启发式搜索算法。705.3状态空间的启发式搜索例5.9八数码难题P183705.3状态空间的启发式搜索1.全局择优搜索在全局择优搜索中，每当需要扩展节点时总是从Open表的所有节点中选择一个估计函数值最小的节点进行扩展，其搜索过程可描述如下：（1）把初始节点S0放入Open表中，f(S0)=g(S0)+h(S0);（2）如果Open表为空，则问题无解，失败退出。715.3状态空间的启发式搜索1.全局择优搜索715.3状态空间的启发式搜索（3）把Open表的第一个节点取出放入Closed表，并记该节点为节点n;（4）考察节点n是否为目标节点。若是则得到了问题的解，成功退出；(5)若节点n不可扩展，则转第（2）步。(6）扩展节点n，生成子节点ni(i=1,2,…),计算每一个子节点的估价值f(ni)(I=1,2,…),并为每个子节点设置指向父节点指针。然后将这些子节点放入Open表中。

725.3状态空间的启发式搜索（3）把Open表的第一个节点取5.3状态空间的启发式搜索（7）根据各节点的估价函数值，对Open表中的全部节点按从小到大的顺序重新进行排序。（8）转第（2）步。如果估价函数F(n)=g(n),则退化为代价树的广度优先搜索；如果估价函数F(n)=d(n),则退化为广度优先搜索；可见，广度优先搜索和代价树的广度优先搜索是全局择优搜索的两个特例。例5.10八数码难题P184735.3状态空间的启发式搜索（7）根据各节点的估价函数值，对5.3状态空间的启发式搜索2.局部择优搜索在局部择优搜索中，每当需要扩展节点时总是从刚生成的子节点中选择一个估价函数值最小的节点进行扩展。其搜索过程可描述如下：（1）把初始节点S0放入Open表中，f(S0)=g(S0)+h(S0);（2）如果Open表为空，则问题无解，失败退出。745.3状态空间的启发式搜索2.局部择优搜索745.3状态空间的启发式搜索（3）把Open表的第一个节点取出放入Closed表，并记该节点为节点n;（4）考察节点n是否为目标节点。若是则得到了问题的解，成功退出；(5)若节点n不可扩展，则转第（2）步。(6）扩展节点n，生成子节点ni(i=1,2,…),计算每一个子节点的估价值f(ni)(i=1,2,…),并按股价值从小到大的顺序依次放入Open表的首部，并为每个子节点设置指向父节点指针。然后转(2)步。755.3状态空间的启发式搜索（3）把Open表的第一个节点取5.3状态空间的启发式搜索可见，深度优先搜索和代价树的深度优先搜索是局部择优搜索的两个特例。5.3.3A*算法在启发式搜索中没有对估价函数f(n)做任何限制。实际上，估价函数对搜索过程是十分重要的，如果选择不当，则有可能找不到问题的界，为此，需要对估价函数进行适当的限制。A*算嘎就是对估价寒暑加上一些先之后的到的一种启发式搜索算法。765.3状态空间的启发式搜索可见，深度5.3状态空间的启发式搜索1.A*算法的可纳性2.A*算法的最优性3.h(n)的单调限制5.3.4A*算法应用举例例5.11八树码难题P190例5.12修道士和野人问题P190775.3状态空间的启发式搜索1.A*算法的可纳性775.4与/或树的盲目搜索5.4.1与/或树的一般搜索

与/或树的搜索过程实际上是一个不断搜索寻找解树的过程，其一般搜索过程为：（1）（2）（3)（4）见书P191785.4与/或树的盲目搜索5.4.1与/或树的一般搜索785.4与/或树的盲目搜索5.4.2与/或树的广度优先搜索P1925.4.3与/或树的深度优先搜索P193795.4与/或树的盲目搜索5.4.2与/或树的广度优先搜索5.5与/或树的启发式搜索5.5.1解树的代价与希望树5.5.2与或树的启发式搜索过程805.5与/或树的启发式搜索5.5.1解树的代价与希望树85.6博奕树的启发式搜索5.6.1概述5.5.2极大极小过程815.6博奕树的启发式搜索5.6.1概述81本章小结：82本章小结：82谢谢！83谢谢！83一个智能系统搜索策略的优劣直接影响到系统的性能语推理效率。

本章主要内容：搜索的基本概念；状态空间的盲目搜索；状态空间的启发式搜索；与或树的盲目搜索；与或树的启发式搜索；博奕树的启发式搜索；第5章搜索测略84一个智能系统搜索策略的优劣直接影响到系5.1搜索策略的基本概念

5.1.1搜索的含义1.搜索定义:根据问题的实际情况，不断寻找可利用的知识，从而构造一条代价最小的推理路线，使问题得以解决的过程称为搜索。2.组合爆炸问题：结构良好，理论上有算法可依的问题，如果问题或算法的复杂性较高（按指数形式增长），由于受计算机在时间和空间上的限制，无法付诸实用。855.1搜索策略的基本概念5.1.1搜索的含义25.1搜索策略的基本概念3.搜索类型：(1)根据是否使用启发信息分类：盲目搜索：按预定的控制策略进行，在搜索过程中获得的中间信息不改变控制策略。启发式搜索：在搜索过程中加入了与问题有关的启发性信息，用于指导搜索朝着最有希望的方向前进，加速问题的求解过程并找到最优解。865.1搜索策略的基本概念3.搜索类型：35.1搜索策略的基本概念(2)根据问题的表示方式分类：状态空间搜索：用状态空间法来求解问题所进行的搜索。与/或树搜索：用问题归约法来求解问题时所进行的搜索。875.1搜索策略的基本概念(2)根据问题的表示方式分类：45.1搜索策略的基本概念5.1.2状态空间法1.状态空间表示法（1）状态(state):表示问题求解过程中每一步问题状况的数据结构，形式的表示为：

Sk={Sk0,Sk1,…)当对每一个分量都予以确定的值时，就得到了一个具体的状态。885.1搜索策略的基本概念5.1.2状态空间法55.1搜索策略的基本概念（2）操作（operator)（算符）把问题从一种状态转换为另一种状态的手段。可以是一个机械步骤、一个运算、一条规则或一个过程。可理解为状态集合上的一个函数，描述了状态之间的关系。895.1搜索策略的基本概念（2）操作（operator)（算符5.1搜索策略的基本概念（3）状态空间（statespace）描述一个问题的全部状态以及这些状态之间的相互关系。常用三元组表示:(S,F,G)S:为问题所有初始状态的集合。

F:为操作的集合。

G:为目标状态的集合。905.1搜索策略的基本概念（3）状态空间（statespac5.1搜索策略的基本概念状态空间图：赋值的有向图。节点表示问题的状态，有向边表示操作.2.状态空间问题求解任何以状态和操作为基础的问题求解方法都称为状态空间问题求解。简称为状态空间法。状态空间法的基本过程为：（1）为问题选择适当的“状态”及“操作”的形式化描述方法。915.1搜索策略的基本概念状态空间图：赋值的有向图。节点表示5.1搜索策略的基本概念（2）从某个初始状态出发，每次使用一个“操作”，递增地建立起操作序列，直到达到目标状态为止。（3）从初始状态到目标状态所使用的算符序列就是问题的一个解。925.1搜索策略的基本概念（2）从某个初始状态出发，每次使用一5.1搜索策略的基本概念3.状态空间的例子例5.1:二阶梵塔问题：设有三根钢针，它们的编号分别是1，2，3。在初始情况下，1号钢针上穿有A、B两个金片，A比B小，A位于B的上面。要求把这两个金片全部移到另一根钢针上，而且规定每次只能移动一个金片，任何时刻都不能使大片位于小片的上面。935.1搜索策略的基本概念3.状态空间的例子105.1搜索策略的基本概念解：设用Sk={Sk0,Sk1}表示问题的状态，其中，Sk0表示金片A所在的钢针号，Sk1表示金片B所在的钢针号。全部可能的问题状态共有以下9种：S0=(1,1)S1=(1,2)S2=(1,3)S3=(2,1)S4=(2,2)S5=(2,3)S6=(3,1)S7=(3,2)S8=(3,3)其中S0为初始状态，S4和S8为目标状态。945.1搜索策略的基本概念解：设用Sk={Sk0,Sk1}表5.1搜索策略的基本概念任何以状态和操作为基础的问题求解方法都称为状态空间问题求解。简称为状态空间法。状态空间法的基本过程为：（1）为问题选择适当的“状态”及“操作”的形式化描述方法。（2）从某个初始状态出发，每次使用一个“操作”，递增地建立起操作序列，直到达到目标状态为止。（3）从初始状态到目标状态所使用的算符序列就是问题的一个解。955.1搜索策略的基本概念任何以状态和操5.1搜索策略的基本概念例5.2修道士和野人问题.首先选取描述问题状态的方法。用一个三元组表示状态：S=(m,c,b)其中：m表示左岸的修道士数；c表示左岸的野人数；b表示左岸的船数；965.1搜索策略的基本概念例5.2修道士和野人问题.135.1搜索策略的基本概念右岸的状态由下式确定：右岸的修道士数m’=3-m；右岸的野人数c’=3-c；

右岸的船数b’=1-b；

m和c的取值分别为0，1，2，3之一；b的取值分别为0，1;

共有4x4x2=32种状态。975.1搜索策略的基本概念右岸的状态由下式确定：145.1搜索策略的基本概念3,32,12,31,21,3A(3,2)2,23,23,11,1B(1,2)A(1,3)二阶樊塔状态空间图985.1搜索策略的基本概念3,32,12,31,21,3A(35.1搜索策略的基本概念除去不合法的状态和修道士被野人吃掉的状态，余下的状态由16种：S0=(3,3,1),S1=(3,2,1),S2=(3,1,1),S3=(2,2,1),S4=(1,1,1),S5=(0,3,1),S6=(0,2,1),S7=(0,1,1),S8=(3,2,0),S9=(3,1,0),S10=(3,0,0),S11=(2,2,0),S12=(1,1,0),S13=(0,2,0),S14=(0,1,0),S15=(0,0,0),995.1搜索策略的基本概念除去不合法的状态和修道士被野人吃掉的5.1搜索策略的基本概念需要考虑的操作有：（1）船至少有一个人（m或c）操作，离开岸边的m和c的减少数目应该等于到达岸边的m和c的增加数目；（2）每次操作船上的人数不得超过2个；（3）操作应保证不产生非法状态。操作由两部分组成：条件部分和动作部分。1005.1搜索策略的基本概念需要考虑的操作有：175.1搜索策略的基本概念用Qij表示从右岸到左岸的运人操作，可供选择的操作由10种，操作集为：F={P01,P10,P11,P02,P20,Q01,Q10,Q11,Q02,Q20,}以P01和Q01为例说明操作的条件和动作：操作符号条件动作P01b=1,m=0或3,c≥1b=0,c=c-1Q01b=1,m=0或3,c≤2b=1,c=c+11015.1搜索策略的基本概念用Qij表示从5.1搜索策略的基本概念例5.3猴子摘香蕉问题.

首先选取描述问题状态的方法。用一个四元组表示状态：S=(w,x,y,z)

其中：w表示猴子的水平位置；x表示箱子的水平位置；

y表示猴子是否在箱子上，当猴子在箱子上时y=1否则y=0；

z表示猴子是否拿到香蕉，当拿到香蕉时z=1否则z=0；1025.1搜索策略的基本概念例5.3猴子摘香蕉问题.195.1搜索策略的基本概念所有可能的状态有：S0=(a,b,0,0),初始状态S1=(b,b,0,0),S2=(c,c,1,0),S3=(c,c,1,1),目标状态1035.1搜索策略的基本概念所有可能的状态有：205.1搜索策略的基本概念允许的操作为：Goto(u):猴子走到位置u，即:(w,x,0,0)→(u,x,0,0)Pushbox(v):猴子推着箱子到水平位置v，即:(x,x,0,0)→(v,v,0,0)Climbbox:猴子爬上箱子，即:(x,x,0,0)→(x,x,1,0)Grasp:猴子拿到香蕉，即:(c,c,1,0)→(c,c,1,1)1045.1搜索策略的基本概念允许的操作为：215.1搜索策略的基本概念问题的状态空间图见书P172,图5-3.由初始状态变为目标状态的操作序列为：{Goto(b),Pushbox©,Climbbox,Grasp}1055.1搜索策略的基本概念问题的状态空间图见书P172,图5-5.1搜索策略的基本概念5.1.3问题归约

问题是不同于状态空间方法的另外一种形式化方法，基本思想是对问题进行分解或变换。当一个问题比较复杂时，直接求解比较困难，可以通过分解或变换，将其转化为一系列较简单的问题，然后通过对较简单的球接来实现对原问题的求解。1.问题的分解与等价变换

当把一个问题归约为子问题时，可采用对原问题的分解或变换方法。1065.1搜索策略的基本概念5.1.3问题归约235.1搜索策略的基本概念（1）分解如果一个问题P可以归约为一组子问题P1,P2,…,Pn，并且只有当所有子问题Pi(I=1,2,…,n)都有解时，原问题P才有解，任何一个子问题Pi(I=1,2,…,n)无解都会导致原问题P无解。称这种归约为问题的分解。分解所得到的子问题的“与”与原问题P等价。1075.1搜索策略的基本概念（1）分解245.1搜索策略的基本概念（2）等价变换如果一个问题P可以归约为一组子问题P1,P2,…,Pn，并且这些子问题Pi(I=1,2,…,n)中只要有一个有解则原问题P就有解，只有当所有的子问题都无解时，原问题P才无解，称这种归约为问题的等价变换。简称变换。即变换所得的子问题的“或”与原问题P等价。1085.1搜索策略的基本概念（2）等价变换255.1搜索策略的基本概念在实际问题的归约过程中，有可能需要同时采用变换和分解的方法。无论是分解还是变换，都是要将原问题归约为一系列本原问题。所谓本原问题是指那种不能分解（或不需要分解）或变换，且可以直接解答的子问题。本原问题可以作为终止归约的限制条件。1095.1搜索策略的基本概念在实际问题的归5.1搜索策略的基本概念2.问题归约的“与或树”表示

当把一个原问题归约为一系列本原问题的过程可以很方便的用一个“与或树”来表示。（1）与树（2）或树1105.1搜索策略的基本概念2.问题归约的“与或树”表示275.1搜索策略的基本概念（3）与/或树1115.1搜索策略的基本概念（3）与/或树285.1搜索策略的基本概念（4）端节点与终止节点端节点：没有子节点的节点。终止节点：本原问题所对应的节点。（5）可解节点与不可解节点满足以下三个条件的为可解节点:任何终止节点都是可解节点；对“或”节点，当其子节点中至少有一个可解节点时，则该或节点就是可解节点；对“与”节点，只有当其子节点全部为可解节点时，则该与节点才是可解节点。1125.1搜索策略的基本概念（4）端节点与终止节点295.1搜索策略的基本概念满足以下三个条件的为不可解节点:不为终止节点的端节点是不可解节点；对“或”节点，若其全部子节点中为不可解节点时，则该或节点就是不可解节点；对“与”节点，只要其子节点中有一个为不可解节点时，则该与节点才是不可解节点。1135.1搜索策略的基本概念满足以下三个条件的为不可解节点:305.1搜索策略的基本概念（6）解树由可解节点构成，并且由这些可解节点可以推出初始节点（对应着原始问题）为可解节点的子树为解树。在解树中一定包含初始节点。1145.1搜索策略的基本概念（6）解树315.1搜索策略的基本概念1155.1搜索策略的基本概念325.1搜索策略的基本概念3.问题归约的例子例5.4:三阶梵塔问题：设有三根钢针，它们的编号分别是1，2，3。在初始情况下，1号钢针上穿有A、B、C三个金片，自上而下，有小到大，。要求把这两个金片全部移到另一根钢针上，而且规定每次只能移动一个金片，任何时刻都不能使大片位于小片的上面。用归约法求解。1165.1搜索策略的基本概念3.问题归约的例子335.1搜索策略的基本概念解：为了能够解决这一问题，首先需要定义该问题的形式化表示方法。用三元组（i,j,k)表示问题任何时刻的状态；用“→”表示状态的转换；i表示金片C的针号;j表示金片B的针号;k表示金片A的针号;1175.1搜索策略的基本概念解：为了能够解决这一问题，首先需要定5.1搜索策略的基本概念利用问题归约方法，原问题可分解为以下三个子问题:(1)把金片A及B移到2号钢针上的双金片移动问题：(1,1,1)→(1,2,2)(2)把金片C移到3号钢针上的单金片移动问题：(1,2,2)→(3,2,2)(1)把金片A及B移到3号钢针上的双金片移动问题：(3,2,2)→(3,3,3)1185.1搜索策略的基本概念利用问题归约方法，原问题可分解为以下5.1搜索策略的基本概念(1,1,1)→(3,3,3)(1,1,1)→(1,2,2)(3,2,2)→(3,3,3)(1,2,2)→(3,2,2)(3,3,1)→(3,3,3)(3,2,1)→(3,3,1)(3,2,2)→(3,2,1)(1,2,3)→(1,2,2)(1,1,3)→(1,2,3)(1,1,1)→(1,1,3)1195.1搜索策略的基本概念(1,1,1)→(3,3,3)(15.1搜索策略的基本概念原始问题的解：(1,1,1)→(1,1,3)(1,1,3)→(1,2,3)(1,2,3)→(1,2,2)(1,2,2)→(3,2,2)

(3,2,2)→(3,2,1)(3,2,1)→(3,3,1)(3,3,1)→(3,3,3)1205.1搜索策略的基本概念原始问题的解：375.2状态空间的盲目搜索状态空间的搜索策略可分为盲目搜索和启发式搜索。启发式搜索需要抽取与问题本身有关的特征信息，而信息抽取比较困难，所以盲目搜索仍不失为一种有效的搜索策略。1215.2状态空间的盲目搜索状态空间的搜索策略可分为盲目搜5.2状态空间的盲目搜索5.2.1一般图搜索过程当用状态空间法解决问题时，需要考虑：（1）对于很大问题，计算机无法保存其全部状态空间；（2）对于具体问题，与解有关的状态空间一般仅是全部状态空间的一部分。因此在问题求解过程中，没有必要生成和保存该问题的全部状态空间，只要能够生成和保存与解有关的那部分状态空间即可。解决问题的方法是采用状态空间搜索技术。1225.2状态空间的盲目搜索5.2.1一般图搜索过程395.2状态空间的盲目搜索对状态空间的搜索，由于问题的状态空间可用一个有向图来表示，因此状态空间搜索实际上就是对有向图的搜索。1235.2状态空间的盲目搜索对状态空间的搜5.2状态空间的盲目搜索状态空间搜索的基本思想是：先把问题的初始状态作为当前扩展节点对其进行扩展，生成一组子节点，然后检查问题的目标状态是否出现在这些子节点中。若出现，则搜索成功，找到了问题的解；若没有出现，则按照某种搜索策略从已生成的子节点中选择一个节点作为扩展节点，重复上述过程，指导目标状态出现在子节点中或者没有可供扩展的节点为止。1245.2状态空间的盲目搜索状态空间搜索的基本思想是：415.2状态空间的盲目搜索状态空间算法：需要设立数据结构Open和Closed表。Open表（未扩展节点表）：用于存放刚生成没有扩展的节点；Closed表（已扩展节点表）：用于存放已经扩展或将要扩展的节点。1255.2状态空间的盲目搜索状态空间算法：425.2状态空间的盲目搜索状态空间的一般图搜索过程为：（1）把初始节点S0放入Open表并建立目前仅包含S0的图G;（2）检查Open表是否为空，若为空，则问题无解，失败退出；（3）把Open表的第一个节点取出放入Closed表，并记该节点为节点n;（4）考察节点n是否为目标节点。若是则得到了问题的解，成功退出；1265.2状态空间的盲目搜索状态空间的一般图搜索过程为：435.2状态空间的盲目搜索（5）扩展节点n，生成一组子节点。把这些子节点中不是节点n先辈的那部分子节点记入集合M，并把这些子节点作为节点n的子节点加入G中。（6）针对M中子节点的不同情况，分别作如下处理：对那些没有在G中出现过的M成员设置一个指向其父节点（即节点n）的指针，并把它放入Open表；对那些原来已在G中出现过，但还没有被扩展的M成员，确定是否需要修改它指向父节点的指针；1275.2状态空间的盲目搜索（5）扩展节点n，生成一组子节点。把5.2状态空间的盲目搜索对于先前已在G中出现过，并已经扩展了的M成员，确定是否需要修改其后继节点指向父节点的指针。（7）按某种策略对Open表中的节点进行排序；（8）转(2)步。1285.2状态空间的盲目搜索对于先前已在G中出现过，并已经扩展了5.2状态空间的盲目搜索搜索过程说明：（1）状态空间图搜索算法具有通用性，其它的各种状态空间搜索策略都是上述的一个特例。各种搜索策略的主要区别在于对Open表中节点的排列顺序不同。如广度优先搜索把先生成的子节点排在前面；深度优先搜索把后生成的子节点排在前面。1295.2状态空间的盲目搜索搜索过程说明：465.2状态空间的盲目搜索（2）在第(5)步对节点n扩展后，生成并记入M的子节点有以下三种情况：该子节点从未被任何节点生成过，由n第一次生成；该子节点原来被其它节点生成过，但还没有被扩展，这一次又被n再次生成；该子节点原来被其它节点生成过，并且已经被扩展过，这一次又被n再次生成。1305.2状态空间的盲目搜索（2）在第(5)步对节点n扩展后，生5.2状态空间的盲目搜索对于一般图搜索算法，具有以上三种情况；对于盲目搜索，由于其状态空间是树状结构，因此不会出现后两种情况，每个节点扩展后生成的子节点都是第一次出现的节点，不必检查并修改指向父节点的指针。（3）在第（6）步针对M中子节点的不同情况进行处理时，如果发生上面第2种情况，一般是由原时节点到该节点路径上所付出的代价来决定。1315.2状态空间的盲目搜索对于一般图搜索5.2状态空间的盲目搜索例题见书P1775.2.2广度优先搜索广度优先搜索也成为宽度优先搜索，是一种先生成的节点限扩展的策略。

1325.2状态空间的盲目搜索例题见书P177495.2状态空间的盲目搜索广度优先搜索策略搜索过程为：从初始节点S0开始逐层向下扩展，在第n曾节点还没有全部搜索完之前，不进入第n+1层节点的搜索。Open表中的节点总是按进入的先后排序，先进入Open表的节点排在前面，后进入的节点排在后面。1335.2状态空间的盲目搜索广度优先搜索策略搜索过程为：5.2状态空间的盲目搜索广度优先搜索算法如下：（1）把初始节点S0放入Open表中；（2）如果Open表为空，则问题无解，失败退出。（3）把Open表的第一个节点取出放入Closed表，并记该节点为节点n;（4）考察节点n是否为目标节点。若是则得到了问题的解，成功退出；（5）若节点n不可扩展，则转第（2）步。1345.2状态空间的盲目搜索广度优先搜索算法如下：515.2状态空间的盲目搜索（6）扩展节点n，将其子节点放入Open表的尾部。并为每个子节点设置指向父节点指针，然后转第（2）步。例5.5八数码难题。见书P1781355.2状态空间的盲目搜索（6）扩展节点n，将其子节点放入Op5.2状态空间的盲目搜索5.2.3深度优先搜索深度优先搜索是一种后生成的节点先扩展的策略。深度优先搜索策略搜索过程为：从初始节点S0开始，在其子节点中选择一个最新生成的节点进行考察，如果该子解不是目标节点而且可以扩展，则扩展该子节点，然后再在此子节点的子节点中选择一个最新生成的节点进行考察，依次向下搜索，直到某个子节点即不是目标节点，又不能继续扩展时，才选择其兄弟节点进行考察。1365.2状态空间的盲目搜索5.2.3深度优先搜索535.2状态空间的盲目搜索Open表示一种栈结构，最先进入的节点排在最后面，最后进入的节点排在最前面。

深度优先搜索算法如下：（1）把初始节点S0放入Open表中；（2）如果Open表为空，则问题无解，失败退出。（3）把Open表的第一个节点取出放入Closed表，并记该节点为节点n;1375.2状态空间的盲目搜索Open表示一5.2状态空间的盲目搜索（4）考察节点n是否为目标节点。若是则得到了问题的解，成功退出；（5）若节点n不可扩展，则转第（2）步。（6）扩展节点n，将其子节点放入Open表的首部。并为每个子节点设置指向父节点指针，然后转第（2）步。例5.6八数码难题。见书P1791385.2状态空间的盲目搜索（4）考察节点n是否为目标节点。若是5.2状态空间的盲目搜索5.2.4有界深度优先搜索深度优先搜索如果目标不在搜索的分支上，且该分支又是一个无限分支，则搜索过程就不可能找到解。即使能够找到节，按深度优先找到的解也不一定是最优解。有界深度优先搜索过程总体上按深度优先策略进行，但对搜索深度需要给出一个深度限制dm，当搜索深度达到了dm，但还没有找到目标时，就停止该分支的搜索，换到另外一个分支进行搜索。1395.2状态空间的盲目搜索5.2.4有界深度优先搜索565.2状态空间的盲目搜索有界深度优先搜索算法如下：（1）把初始节点S0放入Open表中；（2）如果Open表为空，则问题无解，失败退出。（3）把Open表的第一个节点取出放入Closed表，并记该节点为节点n;（4）考察节点n是否为目标节点。若是则得到了问题的解，成功退出；1405.2状态空间的盲目搜索有界深度优先搜索算法如下：575.2状态空间的盲目搜索（5）若节点n的深度d(n)=dm，则转第（2）步。(6)若节点n不可扩展，则转第（2）步。（7）扩展节点n，将其子节点放入Open表的首部。并为每个子节点设置指向父节点指针，然后转第（2）步。例5.7八数码难题。见书P1801415.2状态空间的盲目搜索（5）若节点n的深度d(n)=dm，5.2状态空间的盲目搜索5.2.5代价树搜索需要在搜索树的每条边标上其代价。这种有代价的树称为代价树。在代价树中，用g(n)表示从初始节点S0到节点n的代价，用c(n1,n2)表从父节点n1到其子节点n2的代价，对节点n2的代价有：

g(n2)=g(n1)+c(n1,n2)1425.2状态空间的盲目搜索5.2.5代价树搜索595.2状态空间的盲目搜索在代价树中，最小代价的路径和最短路径（即路径长度最短）是有可能的。最短路径不一定是代价最小的路径；代价最小的路径不一定是最短路径。1.代价树的广度优先搜索代价树的广度优先搜索也称为分枝界限法。每次从Open表中选择节点或往closed表中存放节点时，总是选择代价小的节点排在前面，代价大的排在后面，与节点在树中的位置无关。1435.2状态空间的盲目搜索在代价树中，最5.2状态空间的盲目搜索代价树的广度优先搜索算法如下：（1）把初始节点S0放入Open表中，置S0的代价g(s0)=0；（2）如果Open表为空，则问题无解，失败退出。（3）把Open表的第一个节点取出放入Closed表，并记该节点为节点n;（4）考察节点n是否为目标节点。若是则得到了问题的解，成功退出；1445.2状态空间的盲目搜索代价树的广度优先搜索算法如下：615.2状态空间的盲目搜索(5)若节点n不可扩展，则转第（2）步。(6）扩展节点n，生成子节点ni(I=1,2,…),将这些子节点放入Open表中，并为每个子节点设置指向父节点指针；按如下公式：

g(ni)=g(n)+c(n,ni)(i=1,2,…)计算各自节点的代价，并根据各节点的代价对Open表中的全部按照从小到大顺序重新进行排序，然后转第（2）步。1455.2状态空间的盲目搜索(5)若节点n不可扩展，则转第（5.2状态空间的盲目搜索代价树的广度优先搜索是完备的，如果问题有解，上述算法一定能够找到，并且找到的是最优解。例5.8城市交通问题。P1811465.2状态空间的盲目搜索代价树的广度5.2状态空间的盲目搜索2.代价树的深度优先搜索代价树的深度优先搜索每次从Open表中选择节点或往closed表中存放节点时，总是从刚扩展的子节点中选择一个代价最小的节点。1475.2状态空间的盲目搜索2.代价树的深度优先搜索645.2状态空间的盲目搜索代价树的深度优先搜索算法如下：（1）把初始节点S0放入Open表中，置S0的代价g(s0)=0；（2）如果Open表为空，则问题无解，失败退出。（3）把Open表的第一个节点取出放入Closed表，并记该节点为节点n;（4）考察节点n是否为目标节点。若是则得到了问题的解，