第2章_基于状态空间图表示的搜索搜索技术(新)XXXX1013

1、第第2 2章章 基于图的知识表示与图搜索技术基于图的知识表示与图搜索技术2022-6-1人工智能2第第2 2章章基于图的知识表示与图搜索技术基于图的知识表示与图搜索技术2.1 2.1 概述概述2.2 2.2 状态空间图表示状态空间图表示2.3 2.3 状态空间图的盲目搜索状态空间图的盲目搜索2.4 2.4 状态空间图的启发式搜索状态空间图的启发式搜索2.5 2.5 与或图表示及搜索技术与或图表示及搜索技术2.6 2.6 博弈树及搜索技术博弈树及搜索技术2022-6-1人工智能32.1 2.1 概述概述2.1.1 2.1.1 知识与问题求解框架知识与问题求解框架2.1.2 2.1.2 知识表示知

2、识表示2.1.3 2.1.3 图搜索技术图搜索技术2022-6-1人工智能42.1.1 2.1.1 知识与问题求解框架知识与问题求解框架(1)(1) 1.知识的定义知识的定义心理学：个体通过与环境相互作用后获得的信息及其组心理学：个体通过与环境相互作用后获得的信息及其组织。织。费根鲍姆：知识是经过消减、塑造、解释和转换的信息。费根鲍姆：知识是经过消减、塑造、解释和转换的信息。博恩斯坦博恩斯坦Bernstein：知识是由特定领域的描述、关：知识是由特定领域的描述、关系和过程组成的。系和过程组成的。 概括地说，知识是高度组织起来的信息集团，概括地说，知识是高度组织起来的信息集团，是人们在长期的生活

3、和社会实践中、科学研究和科是人们在长期的生活和社会实践中、科学研究和科学实验中积累起来的经验或对客观世界规律的认识学实验中积累起来的经验或对客观世界规律的认识等。等。2.1.1 2.1.1 知识与问题求解框架知识与问题求解框架(2)(2)2.知识的分类知识的分类1从应用领域来划分从应用领域来划分常识性知识常识性知识领域专业性知识领域专业性知识2从在问题求解中的作用来划分从在问题求解中的作用来划分表达性知识表达性知识过程性知识过程性知识控制性知识控制性知识3从确定性来划分从确定性来划分确定性知识确定性知识非确定性知识非确定性知识4从知识的表现形式来划分，可分为文字、符号、声从知识的表现形式来划分

4、，可分为文字、符号、声音、图形、图像等。音、图形、图像等。2022-6-1人工智能52.1.1 2.1.1 知识与问题求解框架知识与问题求解框架(3)(3)3.问题求解框架问题求解框架问题：是指事件或事物的或当前状态与目标状态之间有问题：是指事件或事物的或当前状态与目标状态之间有差异。差异。问题求解：是指在一定的控制策略下，通过一系列的操问题求解：是指在一定的控制策略下，通过一系列的操作或运算来改变问题的状态，使之与目标状态接近或一作或运算来改变问题的状态，使之与目标状态接近或一致。致。例如，李明在北京，他要去西安办事。例如，李明在北京，他要去西安办事。又如，博弈问题。又如，博弈问题。问题的求

5、解框架问题的求解框架1表达性知识：描述问题的状态有关的各种知识。表达性知识：描述问题的状态有关的各种知识。2过程性知识：描述状态之间的变换关系的各种知过程性知识：描述状态之间的变换关系的各种知识。识。3控制性知识：描述如何在当前状态下选择适宜操控制性知识：描述如何在当前状态下选择适宜操作的知识。作的知识。2022-6-1人工智能62022-6-1人工智能72.1.2 2.1.2 知识表示知识表示(1)(1)知识表示：就是研究在计算机中如何用最适宜知识表示：就是研究在计算机中如何用最适宜的形式表示问题求解过程中所需要的各种知识，的形式表示问题求解过程中所需要的各种知识，包括构成问题求解框架的全部

6、知识。包括构成问题求解框架的全部知识。常用的知识表示形式常用的知识表示形式状态空间图状态空间图与或图与或图谓词逻辑谓词逻辑产生式产生式框架框架语义网络语义网络2.1.2 2.1.2 知识表示知识表示(2)(2)2022-6-1人工智能8例例2.12.1麦卡赛问题。麦卡赛问题。 在一个在一个2n2n2n2n的方格棋盘中，去掉对角的两个的方格棋盘中，去掉对角的两个方格，如图方格，如图a a，问能否将它全部划成假设干，问能否将它全部划成假设干1 12 2的小长方块？的小长方块？目标状态目标状态初始状态初始状态可达状态可达状态同构问题同构问题同态问题同态问题2022-6-1人工智能92.1.3 2.1

7、.3 图搜索技术图搜索技术(1)(1)1.搜索搜索 搜索，简单地说就是搜索，简单地说就是“寻找，目的是找到问题的解。寻找，目的是找到问题的解。在问题求解过程中，待求解的问题被抽象成一定空间上在问题求解过程中，待求解的问题被抽象成一定空间上的图，搜索过程就是从图中初始节点出发，沿着与之相的图，搜索过程就是从图中初始节点出发，沿着与之相连的边试探着前进，寻找目标节点或可解节点的过程。连的边试探着前进，寻找目标节点或可解节点的过程。2.搜索树搜索树 搜索过程中经过考察过的节点和边，按原图的搜索过程中经过考察过的节点和边，按原图的连接关系，便会构成一个树型的有向图，称为搜索树。连接关系，便会构成一个树

8、型的有向图，称为搜索树。搜索树是一个搜索过程的搜索轨迹，或称之为搜索空间。搜索树是一个搜索过程的搜索轨迹，或称之为搜索空间。2.1.3 2.1.3 图搜索技术图搜索技术(2)(2)2022-6-1人工智能10图 2-2搜索空间示意图问题的状态空间、搜索空间及解的示意图：2.1.3 2.1.3 图搜索技术图搜索技术(3)(3)3.搜索策略搜索策略 搜索策略将决定搜索过程按照什么样的顺序考察节搜索策略将决定搜索过程按照什么样的顺序考察节点和经过状态空间图的哪些节点。点和经过状态空间图的哪些节点。盲目搜索：无向导的搜索，也称穷举搜索。盲目搜索：无向导的搜索，也称穷举搜索。启发式搜索：利用启发式搜索：

9、利用“启发性信息作为导航的搜索过程。启发性信息作为导航的搜索过程。 对于较大或无限状态空间问题，盲目搜索效率太低，对于较大或无限状态空间问题，盲目搜索效率太低，所以在实际当中往往是不可行的。启发式搜索广泛地应所以在实际当中往往是不可行的。启发式搜索广泛地应用于实际问题求解中，如博弈、机器学习、数据挖掘、用于实际问题求解中，如博弈、机器学习、数据挖掘、智能检索等。智能检索等。2022-6-1人工智能112022-6-1人工智能122.2 2.2 状态空间图表示状态空间图表示2.2.1 2.2.1 状态空间图状态空间图2.2.2 2.2.2 隐式状态空间图隐式状态空间图2022-6-1人工智能13

10、2.2.1 2.2.1 状态空间图状态空间图1 11.状态状态 状态对应表达性知识，描述一个问题在开始、状态对应表达性知识，描述一个问题在开始、结束或中间的某一时刻所处的状况或状态。通常引结束或中间的某一时刻所处的状况或状态。通常引进一组变量进一组变量 ，表示与问题状态相关的各种，表示与问题状态相关的各种要素，并用这组变量所构成的多元组要素，并用这组变量所构成的多元组 来来表示状态。表示状态。 状态在状态图中表示为节点。状态在状态图中表示为节点。12nqqq， ， ，12()nqqq， ，2022-6-1人工智能142.2.1 2.2.1 状态空间图状态空间图2 22.2.操作操作 操作对应过

11、程性知识，即状态转换规那么，描述操作对应过程性知识，即状态转换规那么，描述状态之间的关系。状态之间的关系。描述一个操作要包含两个局部描述一个操作要包含两个局部条件条件: :指明被作用的状态要满足的约束条件指明被作用的状态要满足的约束条件动作动作: :指明一个操作对状态的分量所做的改变。指明一个操作对状态的分量所做的改变。操作的表示形式可以是一个机械性的步骤、过程、规那操作的表示形式可以是一个机械性的步骤、过程、规那么或算子。么或算子。操作在状态图中表示为边。在程序中，状态转换规那么操作在状态图中表示为边。在程序中，状态转换规那么可用数据对、条件语句、规那么、函数、过程等表示。可用数据对、条件语

12、句、规那么、函数、过程等表示。 如：如果室内温度低于如：如果室内温度低于2626度，那么关闭空调。度，那么关闭空调。 2022-6-1人工智能152.2.1 2.2.1 状态空间图状态空间图3 33.状态空间图状态空间图n问题的状态空间图是一个描述该问题全部可能的状态及相互关系的图，如考虑操作的代价，状态空间图就是一个赋值有向图。n状态空间常记为三元组： S：初始状态的集合 F：操作的集合 G：目标状态的集合。 n由问题的状态空间表示就可以构造出状态空间图。SFG， ，2.2.1 2.2.1 状态空间图状态空间图4 44.求解求解n在状态空间表示法中，问题求解过程转化为在图中在状态空间表示法中

13、，问题求解过程转化为在图中寻找寻找从初始状态从初始状态Q Qs s出发出发到达到达目标状态目标状态Q Qg g的的路径路径问题问题，也就是寻找操作序列的问题。，也就是寻找操作序列的问题。n状态空间的解为三元组状态空间的解为三元组 Q nQ Qs s ：某个初始状态：某个初始状态nQ Qg g ：某个目标状态：某个目标状态na a：把：把Q Qs s变换成变换成Q Qg g的有限的操作序列的有限的操作序列n状态转换图状态转换图S1S3S2f1f2f3f4QsQgfn2022-6-1人工智能162022-6-1人工智能17例例2.2 翻转钱币问题翻转钱币问题1 三枚钱币处于反、正、反状态，每次只许

14、翻动一枚钱币，问连续翻动三次后，能否出现全正或全反状态。 初始状态Qs目标状态集合Q0, Q7例例2.2 翻转钱币问题翻转钱币问题2引入一个三元组引入一个三元组(q(q0 0,q,q1 1,q,q2 2) )来描述总状态，钱币正面为来描述总状态，钱币正面为0 0，反面，反面为为1 1，全部可能的状态为：，全部可能的状态为： Q Q0 0=(0,0,0)=(0,0,0) ; Q ; Q1 1=(0,0,1); Q=(0,0,1); Q2 2=(0,1,0)=(0,1,0) Q Q3 3=(0,1,1) ; Q=(0,1,1) ; Q4 4=(1,0,0); =(1,0,0); Q Q5 5=(1

15、,0,1)=(1,0,1) Q Q6 6=(1,1,0) ; =(1,1,0) ; Q Q7 7=(1,1,1)=(1,1,1)。翻动钱币的操作抽象为改变上述状态的算子，翻动钱币的操作抽象为改变上述状态的算子， 即即F Fa, b, ca, b, c a: a:把钱币把钱币q q0 0翻转一次翻转一次 b:b:把钱币把钱币q q1 1翻转一次翻转一次 c:c:把钱币把钱币q q2 2翻转一次翻转一次 问题的状态空间为问题的状态空间为 2022-6-1人工智能18例例2.2 翻转钱币问题翻转钱币问题43.状态空间图状态空间图 问题的状态空间为： 2022-6-1人工智能19 构造状态空间图： 5

16、07QabcQQ， ， ， ，aabababaabbbbcccbcccb2022-6-1人工智能20例例2.3修道士和野人问题修道士和野人问题1 在河的左岸有三个修道士、三个野人和一条船，修在河的左岸有三个修道士、三个野人和一条船，修道士们想用这条船将所有的人都运过河去，但受到以下道士们想用这条船将所有的人都运过河去，但受到以下条件的限制：条件的限制： 1修道士和野人都会划船，但船一次最多只能运两修道士和野人都会划船，但船一次最多只能运两个人；个人； 2在任何岸边野人数目都不得超过修道士，否那么在任何岸边野人数目都不得超过修道士，否那么修道士就会被野人吃掉。修道士就会被野人吃掉。 假定野人会服

17、从任何一种过河安排，试规划出一种确假定野人会服从任何一种过河安排，试规划出一种确保修道士平安过河方案。保修道士平安过河方案。2022-6-1人工智能21例例2.3修道士和野人问题修道士和野人问题21 1、问题的状态、问题的状态可以用一个三元数组来描述：可以用一个三元数组来描述： S S(m, c, b)(m, c, b) m m：左岸的修道士数：左岸的修道士数 c c：左岸的野人数：左岸的野人数 b b：左岸的船数：左岸的船数 右岸的状态不必标出，因为：右岸的状态不必标出，因为： 右岸的修道士数右岸的修道士数 m m 3 3m m 右岸的野人数右岸的野人数 c c 3 3c c 右岸的船数右岸

18、的船数 b b 1 1b b2022-6-1人工智能22例例2.3修道士和野人问题修道士和野人问题3状态m, c, b状态m, c, b状态m, c, b状态m, c, bS03 3 1S81 3 1S163 3 0S241 3 0S13 2 1S91 2 1S173 2 0S251 2 0S23 1 1S101 1 1S183 1 0S261 1 0S33 0 1S111 0 1S193 0 0S271 0 0S42 3 1S120 3 1S202 3 0S28 0 3 0S52 2 1S130 2 1S212 2 0S290 2 0S62 1 1S140 1 1S222 1 0S300 1

19、 0S72 0 1S150 0 1S232 0 0S310 0 02022-6-1人工智能23例例2.3修道士和野人问题修道士和野人问题42.2.操作集操作集Fp01, p10,p11,p02,p20,q01,q10,q11, q02,q20q20b=0, (m=0,c=2)或(m=1,c=1)b=1, m=m+2q02b=0, m=0或3, c2b=1, c=c+2q11b=0, m=c, c2b=1, m=m+1, c=c+1q10b=0, (m=0,c=1)或(m=2,c=2)b=1, m=m+1q01b=0, m=0或3, c2b=1, c=c+1p20b=1, (m=3,c=1)或(

20、m=2,c=2)b=0, m=m-2p02b=1, m=0或3, c2b=0, c=c-2p11b=1, m=c, c1b=0, m=m-1, c=c-1p10b=1, (m=3,c=2)或(m=1,c=1)b=0, m=m-1p01b=1, m=0或3, c1b=0, c=c-1操作符条 件动 作例例2.3修道士和野人问题修道士和野人问题53.状态空间状态空间给出状态和操作的描述之后，该问题的状态空间是：S0， P 01，P 10，P 11，P 02，P 20，Q01，Q 10，Q 11，Q 02，Q 20，S31。2022-6-1人工智能25例例2.3修道士和野人问题修道士和野人问题6S0

21、(3,3,1)S18(3,1,0)p02q02S17(3,2,0)p01q01S21(2,2,0)p11q11S1(3,2,1)q01p01p10q10S19(3,0,0)q02p02S2(3,1,1)q01p01S26(1,1,0)q20p20S31(0,0,0)q11p11S14(0,1,1)p01q01p02q02S10(1,1,1)p10q10S13(0,2,1)q01p01S30(0,1,0) p02q02S12(0,3,1)p01q01S29(0,2,0)p20q20S5(2,2,1)q11p114.4.状态空间图：状态空间图：四条S0到S31长度相等的最短路径，对应的操作序列就是

22、该问题的四个最优解2022-6-1人工智能262.2.2 2.2.2 隐式状态空间图隐式状态空间图显式状态空间图：表示了问题所有可能的状态及显式状态空间图：表示了问题所有可能的状态及状态之间的关系，这种表示方式称为显式状态空间状态之间的关系，这种表示方式称为显式状态空间图，或称为状态空间图的显示表示。图，或称为状态空间图的显示表示。隐式状态空间图：利用有关状态描述和状态转换隐式状态空间图：利用有关状态描述和状态转换操作的知识定义的状态空间图。在计算机中仅操作的知识定义的状态空间图。在计算机中仅存储描述问题状态及操作的有关知识，包括该问题存储描述问题状态及操作的有关知识，包括该问题的各状态分量的

23、取值情况、分量之间的约束条件、的各状态分量的取值情况、分量之间的约束条件、开始状态、终止状态，以及全部操作的条件和动作开始状态、终止状态，以及全部操作的条件和动作等。隐式状态空间图也称为是状态空间图的隐式表等。隐式状态空间图也称为是状态空间图的隐式表示或隐式图。示或隐式图。重排九宫问题的隐式图描述为： 1有关状态的知识：状态S的定义：S(X0，X1，X2，X3，X4 ，X5， X6 ，X7 ，X8) 其中， Xi0，1，2，3，4，5，6，7，8， ，且 。初始状态： S0 0，1，2，3，5，6，4，7，8 目标状态： Sg 0，1，2，3，4，5，6，7，8 重排九宫问题的状态表示80 i

24、ijijXX时，例例2.42.4重排九宫问题八数码问题重排九宫问题八数码问题 例例2.42.4重排九宫问题重排九宫问题2 22 2有关操作的知识规那么：有关操作的知识规那么：0 0组规那么组规那么 R1(X0=0 ) R1(X0=0 ) (X2=n ) (X2=n ) X0 = n X0 = n X2 X2 =0=0； R2(X0=0 ) R2(X0=0 ) (X4=n ) (X4=n ) X0 = n X0 = n X4 X4 =0=0； R3(X0=0 ) R3(X0=0 ) (X6=n ) (X6=n ) X0 = n X0 = n X6 X6 =0=0； R4(X0=0 ) R4(X0

25、=0 ) (X8=n ) (X8=n ) X0 = n X0 = n X8 X8 =0=0；1 1组规那么组规那么 R5(X1=0 ) R5(X1=0 ) (X2=n ) (X2=n ) X1 = n X1 = n X2 X2 =0=0； R6(X1=0 ) R6(X1=0 ) (X8=n ) (X8=n ) X1 = n X1 = n X8 X8 =0=0；8 8组规那么组规那么: : R22(X8=0 ) R22(X8=0 ) (X1=n ) (X1=n ) X8 = n X8 = n X1 X1 =0=0； R23(X8=0 ) R23(X8=0 ) (X0=n ) (X0=n ) X8

26、 = n X8 = n X0=0X0=0； R24(X8=0 ) R24(X8=0 ) (X7=n ) (X7=n ) X8 = n X8 = n X7 X7 =0=0；例例2.42.4重排九宫问题重排九宫问题3 3八数码的状态图可表示为八数码的状态图可表示为 S0, r1 , r2 , , r24 , SgS0, r1 , r2 , , r24 , Sg 八数码问题状态图仅给出了初始节点八数码问题状态图仅给出了初始节点和目标节点，其余节点需用状态转换规那和目标节点，其余节点需用状态转换规那么来产生。类似于这样表示的状态图称为么来产生。类似于这样表示的状态图称为隐式状态图，或者说状态图的隐式表

27、示。隐式状态图，或者说状态图的隐式表示。例例2.42.4重排九宫问题重排九宫问题4 43 3隐式图搜索隐式图搜索 初始状态初始状态S S 0 0，1 1，2 2，3 3，5 5，6 6，4 4，7 7，8 8 满满足条件足条件X0 =0X0 =0，故可以使用第，故可以使用第0 0组的四条规那么：组的四条规那么： 如果选择规那么如果选择规那么R1R1，那么状态转换为：，那么状态转换为：S1S1 2 2，1 1，0 0，3 3，5 5，6 6，4 4，7 7，8)8)R2R4R1R3 1 2 3 8 5 7 4 6 1 3 8 2 5 7 4 6 1 2 3 8 5 7 4 6 1 2 3 8 4

28、 5 7 6 1 2 3 8 8 5 7 4 62022-6-1人工智能31例例2.5 2.5 旅行商问题旅行商问题(TSP)(1)(TSP)(1) 设有n个互相可直达的城市，某推销商准备从其中的A城出发，周游各城市一遍，最后又回到A城。要求为该推销商规划一条最短的旅行路线。1状态描述：该问题的状态为以A打头城市序列： =AA1Ai AjA其中：A、Ai、Aj、A为城市名， 1i、jn-1，AjA，AiA； 1|n+1；当i j 时，Ai Aj； 当且仅当|=n+1时，A=A。初始状态：=A，|=1终止状态：=AA1A2A，|=n+1例例2.5 2.5 旅行商问题旅行商问题(TSP)(2)(T

29、SP)(2)2操作描述状态转换规那么：操作描述状态转换规那么：规那么规那么1 ：如果：如果=AA1Ai Aj，且，且| n，但，但A，那么置，那么置= A。即没遍历完时，在城市序列中。即没遍历完时，在城市序列中添加一个没有到过的城市。添加一个没有到过的城市。规那么规那么2 ：如果：如果|= n，置，置= A，即从当前城市返，即从当前城市返回回A城。城。 3隐式图搜索隐式图搜索对于有对于有A、B、C、D四个城市所组成的连通城市网，四个城市所组成的连通城市网，初始状态：初始状态：=A，|=1，满足规那么，满足规那么1 ，那么操作的结果为：那么操作的结果为：=AB 、或、或=AC、或、或=AD，继续

30、使用规那么继续使用规那么1 ，直到生成包含四个城市的序列出现，直到生成包含四个城市的序列出现，再使用规那么再使用规那么2。2022-6-1人工智能32补充例补充例 二阶梵塔问题二阶梵塔问题1 1 有三个杆，一号杆有有三个杆，一号杆有A A、B B两个金盘，两个金盘，A A小于小于B B。要求将。要求将A A、B B移至三号杆，每次只可移动一个盘子，任何时刻移至三号杆，每次只可移动一个盘子，任何时刻B B不不能在能在A A上。上。 1 1有关状态的知识：有关状态的知识：用二元组用二元组SASA，SBSB表示状态，表示状态，SASA表示表示A A所在杆号，所在杆号，SBSB表表示示B B所在杆号。

31、其中所在杆号。其中: SA ,SB: SA ,SB1,2,3 , 1,2,3 , 那么全部状态那么全部状态如下：如下： 1 1，1 1，1 1，2 2，1 1，3 3 2 2，1 1，2 2，2 2，2 2，3 3 3 3，1 1，3 3，2 2，3 3，3 3初始状态为初始状态为1 1，1 1，终止状态为：，终止状态为：3 3，3 3 。2022-6-1人工智能33AB123S0：（：（1，1）123S1：（：（1，2）123S2：（：（1，3）AA123S5：（：（2，3）123S4：（：（2，2）123S3：（：（2，1）123S8：（：（3，3）123S7：（：（3，2）123S6：（

32、：（3，1）AAAAABABBBBB补充例补充例 二阶梵塔问题二阶梵塔问题2 22022-6-1人工智能342 2有关操作的知识规那么：有关操作的知识规那么： A Ai i，j j表示金盘表示金盘A A从第从第i i号杆移到号杆移到j j号杆，号杆，B Bi i，j j表示金盘表示金盘B B从第从第i i号杆移到号杆移到j j号杆，其中号杆，其中：i,j i,j 1,2,31,2,3，但，但i i j j ，全部操作为：，全部操作为： A A1 1，2 2，A A1 1，3 3， A A2 2，1 1 A A2 2，3 3，A A3 3，1 1， A A3 3，2 2 B B1 1，2 2，B

33、 B1 1，3 3， B B2 2，1 1 B B2 2，3 3，B B3 3，1 1， B B3 3，2 2分析每个操作的条件和动作，得到下表：分析每个操作的条件和动作，得到下表：补充例补充例 二阶梵塔问题二阶梵塔问题3 32022-6-1人工智能35补充例补充例 二阶梵塔问题二阶梵塔问题4 4操作符操作符条件动作A A（1 1，2 2）SA=1SA=2A A（1 1，3 3）SA=1SA=3A A（2 2，1 1）SA=2SA=1A A（2 2，3 3）SA=2 SA=3A A（3 3，1 1）SA=3 SA=1A A（3 3，2 2）SA=3 SA=2B（1 1，2 2）SB=1， SA

34、 1,2 或或SA=3SB=2B B（1 1，3 3）SB=1， SA 1,3 或或SA=2SB=3B B（2 2，1 1）SB=2， SA 1,2 或或SA=3SB=1B B（2 2，3 3）SB=2， SA 2,3 或或SA=1SB=3B B（3 3，1 1）SB=3， SA 1,3 或或SA=2SB=1B B（3 3，2 2）SB=3， SA 2,3 或或SA=1SB=22022-6-1人工智能36补充例补充例 二阶梵塔问题二阶梵塔问题5 53 3状态空间图状态空间图1,12,13,12,33,31,33,21,22,2A(1,2)A(1,3)B(1,2)A(3,2)A(1,2)B(3,

35、2)A(3,1)B(1,3)A(2,3)2022-6-1人工智能372.3 状态空间图的盲目搜索状态空间图的盲目搜索n盲目搜索盲目搜索:搜索时不参考与具体待求解问题相关的任何搜索时不参考与具体待求解问题相关的任何信息，只是按预先设定的顺序逐个考察节点。盲目搜索信息，只是按预先设定的顺序逐个考察节点。盲目搜索与问题无关，具有通用性。与问题无关，具有通用性。n算法中使用的数据结构算法中使用的数据结构:nOPEN表：专门登记已经生成但还没有考察的节点，即表：专门登记已经生成但还没有考察的节点，即待考察节点。待考察节点。nCLOSED表：用来记录考察过的节点以及节点之间的关表：用来记录考察过的节点以及

36、节点之间的关系，如每个节点指向父节点的编号返回指针。系，如每个节点指向父节点的编号返回指针。CLOSED表中存放的就是一定搜索策略下的搜索树。表中存放的就是一定搜索策略下的搜索树。2022-6-1人工智能38节点父节点编号编号节点父节点编号OPEN表表CLOSED表表2022-6-1人工智能392.3 状态空间图的盲目搜索状态空间图的盲目搜索2.3.1 广度优先搜索广度优先搜索2.3.2 深度优先搜索深度优先搜索2022-6-1人工智能402.3.1 广度优先搜索广度优先搜索1广度优先搜索广度优先搜索A A?eded根本思想：根本思想： 广度优先搜索是严格按节点在树中的出现位置一层一层向广度优

37、先搜索是严格按节点在树中的出现位置一层一层向下的搜索过程。通过将下的搜索过程。通过将OPENOPEN表设计为一个队列来实现，将新生表设计为一个队列来实现，将新生成的子节点放在成的子节点放在OPENOPEN表的后面，保证先生成的节点先考察。表的后面，保证先生成的节点先考察。广度优先搜索算法：广度优先搜索算法：步步1 1 把初始节点把初始节点S0S0放入放入OPENOPEN表中；表中；步步2 2 假设假设OPENOPEN表为空，那么搜索失败，退出；表为空，那么搜索失败，退出；步步3 3 否那么，取否那么，取OPENOPEN表中第一个节点表中第一个节点N N放在放在CLOSEDCLOSED表中；并冠

38、表中；并冠以顺序编号以顺序编号n n；步步4 4 假设节点假设节点N N为目标节点，那么搜索成功。利用为目标节点，那么搜索成功。利用CLOSEDCLOSED表中表中的返回指针找出的返回指针找出S0S0到到N N的路径即为所求解，退出；的路径即为所求解，退出；步步5 5 假设假设N N不可扩展，转步不可扩展，转步2 2；步步6 6 否那么，扩展否那么，扩展N N，将其所有子节点配上指向，将其所有子节点配上指向N N的返回指针放的返回指针放入入OPENOPEN表的尾部，转步表的尾部，转步2 2。2.3.1 广度优先搜索广度优先搜索22022-6-1人工智能42例例2.6使用广度优先搜索算法求解重排

39、九宫问题使用广度优先搜索算法求解重排九宫问题1 2 38 57 4 611 2 38 5 67 481 38 2 57 4 6101 2 38 4 5 7 671 2 38 4 57 6 6 1 38 2 57 4 6111 2 38 4 57 621 2 38 5 7 4 631 2 38 4 57 641 2 37 8 5 4 612 2 31 8 57 4 6131 2 38 47 6 5141 2 3 4 58 7 6151 28 5 37 4 6171 3 58 27 4 6188 1 3 2 57 4 6191 2 37 8 54 6202 31 8 5 7 4 6211 28 4

40、 37 6 5221 2 3 8 57 4 651 2 38 47 6 523八数码广度优先搜索八数码广度优先搜索1 28 5 37 4 69161 2 38 5 67 42022-6-1人工智能432.3.1 广度优先搜索广度优先搜索广度优先搜索的特点：广度优先搜索的特点：广度优先中广度优先中OPENOPEN表是一个队列，表是一个队列，CLOSEDCLOSED表是一个顺序表，表是一个顺序表，表中各节点按顺序编号，正被考察的节点在表中编号最表中各节点按顺序编号，正被考察的节点在表中编号最大。大。广度优先搜索又称为宽度优先或横向搜索。广度优先搜索又称为宽度优先或横向搜索。广度优先策略是完备的，即

41、如果问题的解存在，那么它广度优先策略是完备的，即如果问题的解存在，那么它一定可以找到解，并且找到的解还是最优解。一定可以找到解，并且找到的解还是最优解。广度优先搜索策略与问题无关，具有通用性。广度优先搜索策略与问题无关，具有通用性。缺点搜索效率低。缺点搜索效率低。2022-6-1人工智能442.3.2 深度优先搜索深度优先搜索(1)深度优先搜索的根本思想：深度优先搜索的根本思想： 深度优先搜索是一种一直向下的搜索过程，它优深度优先搜索是一种一直向下的搜索过程，它优先在自己的子节点集合中选择下一个被考察的节点，不先在自己的子节点集合中选择下一个被考察的节点，不断向纵深方向前进，直到到达叶子节点或

42、受到深度限制断向纵深方向前进，直到到达叶子节点或受到深度限制时，才返回到上一级节点沿另一方向继续前进。时，才返回到上一级节点沿另一方向继续前进。深度优先搜索算法：深度优先搜索算法： 与广度优先搜索策略的唯一不同点就是与广度优先搜索策略的唯一不同点就是OPENOPEN表被表被设计成后进先出的栈，新生成的子节点放在设计成后进先出的栈，新生成的子节点放在OPENOPEN表的前表的前面，后生成的节点优先被考察。深度优先搜索算法只需面，后生成的节点优先被考察。深度优先搜索算法只需将宽度优先搜索算法步将宽度优先搜索算法步6 6修改为：修改为：步步6 6 否那么，扩展否那么，扩展N N，将其所有子节点配上指

43、向，将其所有子节点配上指向N N的的指针放入指针放入OPENOPEN表的首部，转步表的首部，转步2 2。 例例2.7使用深度优先搜索算法求解重排九宫问题使用深度优先搜索算法求解重排九宫问题 1 2 38 57 4 611 2 38 4 5 7 631 2 38 4 57 6 1 2 38 4 57 61 2 38 5 7 4 61 2 38 4 57 61 2 38 47 6 541 28 4 37 6 51 2 3 8 57 4 621 2 38 47 6 552022-6-1人工智能462.3.2 深度优先搜索深度优先搜索深度优先搜索的特点：深度优先搜索的特点：OPENOPEN表为一个堆栈

44、。表为一个堆栈。深度优先又称纵向搜索。深度优先又称纵向搜索。一般不能保证找到最优解。如以下图所示：一般不能保证找到最优解。如以下图所示：图2-13 深度优先搜索不具有完备性示意图2022-6-1人工智能471.1.有界深度优先搜索有界深度优先搜索Acd Acd 为克服深度优先搜索的缺乏，可以对其深度进行为克服深度优先搜索的缺乏，可以对其深度进行限制限制深度界限的选择很重要深度界限的选择很重要 dm 假设太小，那么达不到解的深度，得不假设太小，那么达不到解的深度，得不到解；假设太大，既浪费了计算机的存储空间与到解；假设太大，既浪费了计算机的存储空间与时间，又降低了搜索效率。由于解的路径长度事时间

45、，又降低了搜索效率。由于解的路径长度事先难以预料，所以要恰当地给出先难以预料，所以要恰当地给出dm的值是比较的值是比较困难的。困难的。即使能求出解，它也不一定是最优解。即使能求出解，它也不一定是最优解。2.2.可变界深度优先搜索算法可变界深度优先搜索算法(1)(1) 当在dm界限之内找不到解时，可以将深度界限dm不断扩大，每次增加一个深度增量d，直到找到解，或者搜索完整棵树。这样算法的完备性得到了保证，称为可变界深度优先搜索算法(或迭代加深搜索)。 当d =1时，算法开始蜕变为广度优先搜索算法。 2.2.可变界深度优先搜索算法可变界深度优先搜索算法(2)(2)n迭代加深搜索过程：迭代加深搜索过

46、程：n步步1 把初始节点把初始节点S0放入放入OPEN表中，置表中，置S0的深度的深度d S0 0，dm为任意初值。为任意初值。n步步2 假设假设OPEN表为空，那么考查表为空，那么考查CLOSED表是否有表是否有待扩展节点：待扩展节点：n 假设无，那么问题无解，退出。假设无，那么问题无解，退出。n 假设有，那么取出假设有，那么取出CLOSED表中待扩展节表中待扩展节点放入到点放入到OPEN表中，令表中，令 dm=dm+d。n n 2.2.可变界深度优先搜索算法可变界深度优先搜索算法(3)(3) 步步3 取取OPEN表中第一个节点表中第一个节点N放在放在CLOSED表中；并冠以编号表中；并冠以

47、编号n； 步步4 假设节点假设节点N为目标节点，成功退出。为目标节点，成功退出。 步步5 假设假设N的深度的深度dNdm深度限制值，那么标深度限制值，那么标N为待扩展为待扩展节点，那么转步节点，那么转步2； 步步6 N无子节点，那么转步无子节点，那么转步2； 步步7 扩展扩展N，将其所有子节点，将其所有子节点Ni配上指向配上指向N的指针放入的指针放入OPEN首部首部， 置置 d Ni dN1，转步，转步2。3.3.可采纳的有界深度优先搜索算法可采纳的有界深度优先搜索算法(1)(1)问题：问题：当d d 1 时， 是否能保证找到最优解？2022-6-1人工智能533.3.可采纳的有界深度优先搜索

48、算法可采纳的有界深度优先搜索算法(2)(2)步步1 1 把初始节点把初始节点S0S0放入放入OPENOPEN表中，置表中，置d(S0)=0d(S0)=0，dm=dm0dm=dm0，G=NULLG=NULL。步步2 2 假设假设OPENOPEN表为空，那么考察表为空，那么考察CLOSEDCLOSED表是否有待扩展节点：表是否有待扩展节点： 1 1假设无待扩展节点，那么判断假设无待扩展节点，那么判断G G表是否为空：表是否为空： 假设为空，搜索失败，退出；假设为空，搜索失败，退出； 否那么，取出否那么，取出G G表最后面的节点表最后面的节点SgSg， Sg Sg即为所求最优解，即为所求最优解，搜索

49、成功，退出；搜索成功，退出； 2 2假设有待扩展节点，那么取出假设有待扩展节点，那么取出CLOSEDCLOSED表中待扩展节点放入表中待扩展节点放入到到OPENOPEN表中，令表中，令dm=dm+dm=dm+d d，转步，转步2 2；3.3.可采纳的有界深度优先搜索算法可采纳的有界深度优先搜索算法(3)(3)步步3 3 取取OPENOPEN表中首部的节点表中首部的节点N N放在放在CLOSEDCLOSED表中；并冠以顺序编号表中；并冠以顺序编号n n； 步步4 4 假设假设d dN Ndmdm，那么标，那么标N N为待扩展节点，转步为待扩展节点，转步2 2；步步5 5 假设假设N N是目标节点

50、是目标节点Sg Sg ，那么令，那么令dmdmd d Sg Sg -1 -1 ，把，把SgSg放到放到G G 表的尾部，转步表的尾部，转步2 2。步步6 6 假设假设N N不可扩展，那么转步不可扩展，那么转步2 2； 步步7 7 否那么，扩展否那么，扩展N N，将其所有子节点，将其所有子节点NiNi配上指向配上指向N N的返回指针放入的返回指针放入OPENOPEN表首部，表首部， 置置d d Ni Ni d dN N1 1 ，转步，转步2 2。 2022-6-1人工智能542.4 2.4 状态空间图的启发式搜索状态空间图的启发式搜索(1)(1)1.启发性知识与启发函数启发性知识与启发函数n启发

51、性知识启发性知识 就是与被求解问题自身特性相关的知识，包括被求解问题的解的特性、解的分布规律和在实际当中求解此类问题的经验、技巧等，对应于问题求解框架中的控制性知识。 n启发函数启发函数 要实现启发式搜索，需要把启发性知识形式化，即用一定的函数表示出来，通过函数计算来评价每种选择的价值大小，用以指导搜索过程，这样的函数称为启发函数。 2022-6-1人工智能552022-6-1人工智能562.4 2.4 状态空间图的启发式搜索状态空间图的启发式搜索(2)(2)2.启发函数的设计启发函数的设计 在实际设计过程中，启发函数是用来估计搜索树节点在实际设计过程中，启发函数是用来估计搜索树节点x与目标节

52、点接近程度的一种函数，通常记为与目标节点接近程度的一种函数，通常记为hx。启发函数可以是：启发函数可以是：1一个节点到目标节点的某种距离或差异的量度；一个节点到目标节点的某种距离或差异的量度；2一个节点处在最正确路径上的概率；一个节点处在最正确路径上的概率；3根据主观经验的主观打分等。根据主观经验的主观打分等。2022-6-1人工智能572.4 2.4 状态空间图的启发式搜索状态空间图的启发式搜索(3)(3)2.4.1 启发式搜索算法启发式搜索算法2.4.2 启发式搜索的启发式搜索的A算法和算法和A*算法算法 A*算法在游戏中的应用算法在游戏中的应用2022-6-1人工智能582.4.1 启发

53、式搜索算法启发式搜索算法1启发式搜索启发式搜索用启发函数来导航，其搜索算法就要在状态图一般搜索用启发函数来导航，其搜索算法就要在状态图一般搜索算法根底上再增加启发函数值的计算与传播过程，并且算法根底上再增加启发函数值的计算与传播过程，并且由启发函数值来确定节点的扩展顺序。由启发函数值来确定节点的扩展顺序。按选择范围不同，启发式搜索分为：按选择范围不同，启发式搜索分为：全局择优搜索全局择优搜索局部择优搜索局部择优搜索2022-6-1人工智能592.4.1 启发式搜索算法启发式搜索算法21.全局择优搜索全局择优搜索根本思想：在根本思想：在OPEN表中保存所有已生成而未考察的节表中保存所有已生成而未

54、考察的节点，并用启发函数点，并用启发函数h(x)对它们全部进行估价，从中选出对它们全部进行估价，从中选出最优节点进行扩展，而不管这个节点出现在搜索树的什最优节点进行扩展，而不管这个节点出现在搜索树的什么地方。么地方。2.4.1 启发式搜索算法启发式搜索算法3全局择优搜索算法：全局择优搜索算法：步步1 把初始节点把初始节点S0放入放入OPEN表中，计算表中，计算h(S0)；步步2 假设假设OPEN表为空，那么搜索失败，退出；表为空，那么搜索失败，退出；步步3 否那么，移出否那么，移出OPEN表中第一个节点表中第一个节点N放入放入CLOSED表中，并冠以序号表中，并冠以序号n ；步步4 假设目标节

55、点假设目标节点Sg N，那么搜索成功，利用，那么搜索成功，利用CLOSED表中的返回指针找出表中的返回指针找出S0到到N的路径即为所求的路径即为所求解，退出；解，退出；步步5 假设假设N不可扩展，那么转步不可扩展，那么转步2 ；步步6 否那么，扩展否那么，扩展N，计算，计算N的每个子节点的每个子节点x的函数值，并的函数值，并将将N所有子节点所有子节点x配以指向配以指向N的返回指针后放入的返回指针后放入OPEN表中，依据启发函数对节点的计算，再对表中，依据启发函数对节点的计算，再对OPEN表中表中所有节点按其启发函数值的大小以升序排列，转步所有节点按其启发函数值的大小以升序排列，转步2。2022

56、-6-1人工智能602.4.1 启发式搜索算法启发式搜索算法42.局部择优搜索局部择优搜索根本思想：局部择优搜索是在启发性知识导航下的深度优根本思想：局部择优搜索是在启发性知识导航下的深度优先搜索，在先搜索，在OPEN表中保存所有已生成而未考察的节点，表中保存所有已生成而未考察的节点，对其中新生成的每个子节点对其中新生成的每个子节点x计算启发函数，从全部子节点计算启发函数，从全部子节点中选出最优节点进行扩展，其选择下一个要考察节点的范中选出最优节点进行扩展，其选择下一个要考察节点的范围是刚刚生成的全部子节点，围是刚刚生成的全部子节点，局部择优搜索算法：局部择优搜索算法： 与全局择优搜索算法的区

57、别仅在步与全局择优搜索算法的区别仅在步6： 步步6 否那么，扩展否那么，扩展N，计算，计算N的每个子节点的每个子节点x的函数值，并的函数值，并将将N的所有子节点的所有子节点x配以指向节点配以指向节点N的指针后，将全部子节的指针后，将全部子节点按启发函数值升序排列后放入点按启发函数值升序排列后放入OPEN表的首部，转步表的首部，转步2。2022-6-1人工智能612.4.2 启发式搜索的启发式搜索的A算法和算法和A*算法算法1 启发函数是对当前节点到达目标节点未来可能要付出的代价的估计。 在全局择优和局部择优搜索算法中，都没有考虑从初始节点到当前节点已经付出的实际代价。 在很多实际问题中，已经付

58、出的实际代价是必须考虑的，如TSP问题等。将两者同时考虑，用于指导搜索的算法称为A算法和算法和A*算法算法。2022-6-1人工智能63 启发式搜索的启发式搜索的A算法和算法和A*算法算法21. A1. A算法算法估价函数估价函数f fx x : :为了防止在单独利用启发函数的时候为了防止在单独利用启发函数的时候误入歧途，将启发函数误入歧途，将启发函数h hx x与代价函数与代价函数g gx x相结合，相结合，即初始节点即初始节点S0S0到达节点到达节点x x处已付出的代价与节点处已付出的代价与节点x x 到达目到达目标节点标节点SgSg的接近程度估计值总和。的接近程度估计值总和。 f fx

59、x g gx xh hx x g gx x代价函数：初始节点代价函数：初始节点S0S0到达节点到达节点x x处已付出的代处已付出的代价，有利于搜索纵向开展，提高搜索效率，但影响完备价，有利于搜索纵向开展，提高搜索效率，但影响完备性。性。 h hx x启发函数：节点启发函数：节点x x 到达目标节点到达目标节点SgSg的接近程度估的接近程度估计值有利于搜索横向开展，提高搜索的完备性，但影响计值有利于搜索横向开展，提高搜索的完备性，但影响搜索效率。搜索效率。 启发式搜索的启发式搜索的A算法和算法和A*算法算法3代价代价gx的计算的计算 gx表示从初始节点表示从初始节点S0到节点到节点x的代价：的代

60、价： g S0 0 g xj g xi cxi，xj 其中，其中，cxi，xj表示父节点表示父节点xi到子节点到子节点xj的代价的代价ADCEB464332323462344632C1B1D1D2E1C2E2D3C3B2E4E36B32022-6-1人工智能64 启发式搜索的启发式搜索的A算法和算法和A*算法算法4对估价函数 fx gxhx 令其中的hx=0时，这时得到的是代价树的非启发式搜索算法。按对节点的考察范围不同，可分为两种搜索策略：分支界限法将全局择优搜索算法中的hx替换为gx ，即可得到分支界限搜索算法。瞎子爬山法将局部择优搜索算法中的hx替换为gx ，即可得到瞎子爬山搜索算法。2