图搜索与问题求解

1、第第3 3章章 图搜索与问题求解图搜索与问题求解2022-3-6人工智能2推理与搜索推理与搜索n图搜索技术是人工智能的核心技术之一。图搜索技术是人工智能的核心技术之一。n任一搜索过程也都是一个推理过程。任一搜索过程也都是一个推理过程。n隐式图的搜索过程是一种利用局部性知识构隐式图的搜索过程是一种利用局部性知识构造全局性答案的过程。造全局性答案的过程。n在各种搜索过程中，人工智能最感兴趣的是在各种搜索过程中，人工智能最感兴趣的是那些具有很强选择性的启发式方法，即那些那些具有很强选择性的启发式方法，即那些利用很局部的状态空间可以有效地找到问题利用很局部的状态空间可以有效地找到问题的解的方法。的解的

2、方法。n机器学习等很多过程都是在假设空间中搜索机器学习等很多过程都是在假设空间中搜索目标的过程。目标的过程。2022-3-6人工智能3第第3 3章章 图搜索与问题求解图搜索与问题求解3.1 3.1 状态图知识表示状态图知识表示（状态图搜索问题求解）（状态图搜索问题求解）3.2 3.2 状态图搜索状态图搜索3.3 3.3 与或图知识表示与或图知识表示（与或图搜索问题求解（与或图搜索问题求解 ）3.4 3.4 与或图搜索与或图搜索3.5 3.5 博弈树搜索博弈树搜索2022-3-6人工智能43.1 3.1 状态图知识表示状态图知识表示3.1.1 3.1.1 状态、操作和状态空间状态、操作和状态空间

3、3.1.2 3.1.2 修道士和野人的状态空间修道士和野人的状态空间3.1.3 3.1.3 梵塔问题的状态空间梵塔问题的状态空间3.1.4 3.1.4 重排九宫问题和隐式图重排九宫问题和隐式图3.1.5 3.1.5 问题求解的基本框架问题求解的基本框架2022-3-6人工智能53.1.13.1.1状态、操作和状态空间（状态、操作和状态空间（1 1）例例3.13.1走迷宫走迷宫走迷宫问题就是从该有向图的初始节点出发，走迷宫问题就是从该有向图的初始节点出发，寻找目寻找目标节点标节点的问题，或者是的问题，或者是寻找寻找通向目标节点的通向目标节点的路径路径问题。问题。2022-3-6人工智能63.1.

4、1 3.1.1 状态、操作和状态空间（状态、操作和状态空间（2 2）例例3.23.2八数码难题八数码难题( (重排九宫问题重排九宫问题) ) 2 83147 6512384765初始棋局目标棋局以上两个问题抽象来看，都是某个有向图中寻找目标以上两个问题抽象来看，都是某个有向图中寻找目标或路径的问题，在人工智能技术中，把这种描述问题或路径的问题，在人工智能技术中，把这种描述问题的有向图称为的有向图称为状态空间图，状态空间图，简称简称状态图状态图。棋局作为节点，相邻节点通过移动数码一个一个产生棋局作为节点，相邻节点通过移动数码一个一个产生出来，所有节点由它们的相邻关系连成一个有向图。出来，所有节点

5、由它们的相邻关系连成一个有向图。2022-3-6人工智能73.1.1 3.1.1 状态、操作和状态空间（状态、操作和状态空间（3 3）n状态状态（StateState）p62p62n为了描述某一类事物中各个不同事物之间为了描述某一类事物中各个不同事物之间的差异而引入的最少的一组变量的差异而引入的最少的一组变量q q的有序的有序组合，表征了问题的特征和结构。组合，表征了问题的特征和结构。n表示成矢量形式：表示成矢量形式：n状态在状态图中表示为状态在状态图中表示为节点节点。T210210Q，qqqqqq2022-3-6人工智能83.1.1 3.1.1 状态、操作和状态空间（状态、操作和状态空间（4

6、 4）n状态转换规则（操作状态转换规则（操作 operatoroperator）n引起状态中某些分量发生改变，从而使一个引起状态中某些分量发生改变，从而使一个具体状态变化到另一个具体状态的作用。具体状态变化到另一个具体状态的作用。n它可以是一个机械性的步骤、过程、规则或它可以是一个机械性的步骤、过程、规则或算子。算子。n操作描述了状态之间的关系。操作描述了状态之间的关系。n状态转换规则在状态图中表示为状态转换规则在状态图中表示为边边。在程序。在程序中状态转换规则可用数据对、条件语句、规中状态转换规则可用数据对、条件语句、规则、函数、过程等表示。则、函数、过程等表示。2022-3-6人工智能93

7、.1.1 3.1.1 状态、操作和状态空间（状态、操作和状态空间（5 5）n状态空间（状态空间（State SpaceState Space）n问题的状态空间是一个表示该问题全部的可问题的状态空间是一个表示该问题全部的可能状态及相互关系的图。能状态及相互关系的图。n状态空间一般用赋值有向图表示，记为：状态空间一般用赋值有向图表示，记为： （S S，F F，G G）nS S：问题的可能有的初始状态的集合；：问题的可能有的初始状态的集合；nF F：操作的集合；：操作的集合；nG G：目标状态的集合。：目标状态的集合。2022-3-6人工智能103.1.1 3.1.1 状态、操作和状态空间（状态、操

8、作和状态空间（6 6）n状态空间中问题求解状态空间中问题求解n在状态空间表示法中，问题求解过程转化为在图中在状态空间表示法中，问题求解过程转化为在图中寻找从初始状态寻找从初始状态Q Qs s出发到达目标状态出发到达目标状态Q Qg g的路径问题，的路径问题，也就是寻找操作序列的问题。也就是寻找操作序列的问题。n状态空间的解为三元组状态空间的解为三元组 Q nQ Qs s ：某个初始状态：某个初始状态nQ Qg g ：某个目标状态：某个目标状态na a：把：把Q Qs s变换成变换成Q Qg g的有限的操作序列的有限的操作序列n状态转换图状态转换图S1S3S2O1O2O3O4QsQgOn2022

9、-3-6人工智能113.1.1 3.1.1 状态、操作和状态空间（状态、操作和状态空间（7 7）例例 3.7 3.7 迷宫问题的状态图表示。迷宫问题的状态图表示。 S：SoF：(So, S4), (S4, So), (S4, S1), (S1, S4), (S1,S2), (S2, S1), (S2, S3), (S3, S2), (S4, S7), (S7, S4), (S4, S5), (S5, S4), (S5, S6), (S6, S5), (S5, S8), (S8, S5), (S8, S9), (S9, S8), (S9, Sg)G：Sg 迷宫问题规则集描述了图中所有节点和边。类

10、似于迷宫问题规则集描述了图中所有节点和边。类似于这样罗列出全部节点和边的状态图称为这样罗列出全部节点和边的状态图称为显式状态图显式状态图，或者说或者说状态图状态图的的显式显式表示。表示。2022-3-6人工智能123.1.1 3.1.1 状态、操作和状态空间（状态、操作和状态空间（8 8）补充例补充例1 1 三枚钱币，能否从下面状态翻动三次后三枚钱币，能否从下面状态翻动三次后出现全正或全反状态。出现全正或全反状态。反正反正正正反反反初始状态s目标状态集合0, 72022-3-6人工智能133.1.1 3.1.1 状态、操作和状态空间（状态、操作和状态空间（9 9）引入一个三元组引入一个三元组(

11、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,0,1)=(1,0,1) Q Q6 6=(1,1,0) ; =(1,1,0) ; Q Q7 7=(1,1,1)=(1,1,1)。翻动钱币的操作抽象为改变上述状态

12、的算子，翻动钱币的操作抽象为改变上述状态的算子， 即即F Fa, b, ca, b, c a: a:把钱币把钱币q q0 0翻转一次翻转一次 b:b:把钱币把钱币q q1 1翻转一次翻转一次 c:c:把钱币把钱币q q2 2翻转一次翻转一次 问题的状态空间为问题的状态空间为 2022-3-6人工智能143.1.1 3.1.1 状态、操作和状态空间（状态、操作和状态空间（1010）状态空间图（0，0，0）（1，0，1）（0，0，1）（0，1，0）（1，1，0）（1，0，0）（0，1，0）（1，1，1）acabacabcbbc2022-3-6人工智能153.1.2 3.1.2 修道士和野人问题的状

13、态空间（修道士和野人问题的状态空间（1 1）补充例补充例2 2 修道士和野人问题。在河的左岸有三个修道士和野人问题。在河的左岸有三个修道士、三个野人和一条船，修道士们想用这修道士、三个野人和一条船，修道士们想用这条船将所有的人都运过河去，但受到以下条件条船将所有的人都运过河去，但受到以下条件的限制：的限制： （1 1）修道士和野人都会划船，但船一次）修道士和野人都会划船，但船一次最最多多只能只能运两个人运两个人； （2 2）在任何岸边）在任何岸边野人数目野人数目都都不得超过修道不得超过修道士士，否则修道士就会被野人吃掉。，否则修道士就会被野人吃掉。 假定野人会服从任何一种过河安排，试规划假定野

14、人会服从任何一种过河安排，试规划出一种确保修道士安全过河方案。出一种确保修道士安全过河方案。2022-3-6人工智能163.1.2 3.1.2 修道士和野人问题的状态空间（修道士和野人问题的状态空间（2 2）解：先建立问题的状态空间。问题的状态可以用解：先建立问题的状态空间。问题的状态可以用一个三元数组来描述：一个三元数组来描述： S S(m, c, b)(m, c, b) m m：左岸的修道士数：左岸的修道士数 c c：左岸的野人数：左岸的野人数 b b：左岸的船数：左岸的船数 右岸的状态不必标出，因为：右岸的状态不必标出，因为： 右岸的修道士数右岸的修道士数mm3 3m m 右岸的野人数右

15、岸的野人数cc3 3c c 右岸的船数右岸的船数b=1-bb=1-b2022-3-6人工智能173.1.2 3.1.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 1S21

16、2 2 0S290 2 0S62 1 1S140 1 1S222 1 0S300 1 0S72 0 1S150 0 1S232 0 0S310 0 02022-3-6人工智能183.1.2 3.1.2 修道士和野人问题的状态空间（修道士和野人问题的状态空间（4 4）操作集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

17、)b=1, m=m+1q01b=0, m=0或3, c2b=1, c=c+1p20b=1, (m=3,c=1)或(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操作符条 件动 作2022-3-6人工智能193.1.2 3.1.2 修道士和野人问题的状态空间（修道士和野人问题的状态空间（5 5）S0(3,3,1)S18(3,1,0)p02q02S17(3,2,0)

18、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)q11p112022-3-6人工智能203.1.3 3.1.3 梵塔问题的状态空间（梵塔问题的状态空间（1 1） 例例3.9 3.9 二阶梵塔问题二阶梵塔问题 一号

19、杆有一号杆有A A、B B两个金盘，两个金盘，A A小于小于B B。要求将。要求将ABAB移至三号杆，每次只可移动移至三号杆，每次只可移动一个盘子，任何时刻一个盘子，任何时刻B B不能在不能在A A上。上。 用二元组用二元组（S SA A，S SB B）表示状态，表示状态，S SA A表示表示A A所在所在杆号，杆号，S SB B表示表示B B所在杆号，全部状态如下：所在杆号，全部状态如下： （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

20、，3 3）2022-3-6人工智能213.1.3 3.1.3 梵塔问题的状态空间（梵塔问题的状态空间（2 2）AB123S0：（：（1，1）123S1：（：（1，2）123S2：（：（1，3）AA123S5：（：（2，3）123S4：（：（2，2）123S3：（：（2，1）123S8：（：（3，3）123S7：（：（3，2）123S6：（：（3，1）AAAAABABBBBB2022-3-6人工智能223.1.3 3.1.3 梵塔问题的状态空间（梵塔问题的状态空间（3 3）转换规则：转换规则：A A（i i，j j）表示金盘）表示金盘A A从第从第i i号杆移到号杆移到j j号杆号杆 B B（i

21、 i，j j）表示金盘）表示金盘B B从第从第i i号杆移到号杆移到j j号杆号杆 A A（1 1，2 2），），A A（1 1，3 3），）， A A（2 2，1 1） A A（2 2，3 3），），A A（3 3，1 1），）， A A（3 3，2 2） B（1 1，2 2），），B B（1 1，3 3），）， B B（2 2，1 1） B B（2 2，3 3），），B B（3 3，1 1），）， B B（3 3，2 2）初始状态初始状态（1 1，1 1），目标状态，目标状态（3 3，3 3）梵塔问题用状态图表示为梵塔问题用状态图表示为： (1,1),A(1,2),B(3,2),(3,3)

22、2022-3-6人工智能233.1.3 3.1.3 梵塔问题的状态空间（梵塔问题的状态空间（4 4）1,12,13,12,33,31,33,21,22,2A(1,3)A(2,1)B(3,1)A(3,2)A(1,3)B(1,3)A(2,1)B(1,2)A(3,2)2022-3-6人工智能24n n（n3n3）阶梵塔问题）阶梵塔问题n假设金片假设金片PkPk从小片到大片按下标从小片到大片按下标k k顺序编号，顺序编号，即即k=1k=1，2 2，3 3，n n，n n阶梵塔问题状态空间阶梵塔问题状态空间可用矢量表示为：可用矢量表示为： (P(P1 1, P, P2 2, P, P3 3, P, Pk

23、 k, P, Pn n) ) P Pk k表示第表示第k k个金片穿在编号为个金片穿在编号为P Pk k的宝石针上，的宝石针上， P Pk k=1=1，2 2，33n初始状态初始状态 S S0 0=(1,1,1,1,1)=(1,1,1,1,1)n目标状态目标状态 S Sg1g1 =(2,2,2,2,2) =(2,2,2,2,2) S Sg2g2 =(3,3,3,3,3) =(3,3,3,3,3)2022-3-6人工智能25n n（n3n3）阶梵塔问题）阶梵塔问题nn阶梵塔问题的操作集合表示为：阶梵塔问题的操作集合表示为： F=RF=Rk k(i,j) | i,j(i,j) | i,j=1,2,

24、3=1,2,3，k=1k=1，2 2，nnn全部可能状态数为全部可能状态数为3n个，最佳解长度为个，最佳解长度为2n-1。n三阶梵塔问题状态图三阶梵塔问题状态图S S0 0=(1,1,1)=(1,1,1)S Sg2g2=(3,3,3)=(3,3,3)S Sg1g1=(2,2,2)=(2,2,2)2022-3-6人工智能263.1.4 3.1.4 重排九宫问题和隐式图（重排九宫问题和隐式图（1 1）例例3.83.8重排九宫问题（八数码难题）重排九宫问题（八数码难题）X1X2X3X8X0X4X7X6X5将棋局用向量将棋局用向量A A(X(X0 0，X X1 1 ， X X2 2 ， X X3 3

25、， X X4 4 ， X X5 5 ， X X6 6 ， X X7 7 ， X X8 8) )表示，其中表示，其中X Xi i为变量，值表示方格为变量，值表示方格X Xi i内的数字。内的数字。 初始状态初始状态 S S0 0 （0 0，2 2，8 8，3 3，4 4，5 5，6 6，7 7，1 1） 目标状态目标状态 S Sg g （0 0，1 1，2 2，3 3，4 4，5 5，6 6，7 7，8 8）数码的移动规则就是该问题的状态变化规则。经分析，该问题共有数码的移动规则就是该问题的状态变化规则。经分析，该问题共有2424条规则，分为条规则，分为9 9组。组。2 83147 651238

26、4765初始棋局初始棋局目标棋局目标棋局2022-3-6人工智能273.1.4 3.1.4 重排九宫问题和隐式图（重排九宫问题和隐式图（2 2）0 0组规则组规则 r r1 1(X(X0 0=0=0 ) ) (X(X2 2=n=n ) ) X X0 0 = n = n X X2 2 =0 =0； r r2 2(X(X0 0=0=0 ) ) (X(X4 4=n=n ) ) X X0 0 = n = n X X4 4 =0 =0； r r3 3(X(X0 0=0=0 ) ) (X(X6 6=n=n ) ) X X0 0 = n = n X X6 6 =0 =0； r r4 4(X(X0 0=0=0

27、 ) ) (X(X8 8=n=n ) ) X X0 0 = n = n X X8 8 =0 =0；1 1组规则组规则 r r5 5(X(X1 1=0=0 ) ) (X(X2 2=n=n ) ) X X1 1 = n = n X X2 2 =0 =0； r r6 6(X(X1 1=0=0 ) ) (X(X8 8=n=n ) ) X X1 1 = n = n X X8 8 =0 =0；8 8组规则组规则: : r r2222(X(X8 8=0=0 ) ) (X(X1 1=n=n ) ) X X8 8 = n = n X X1 1 =0 =0； r r2323(X(X8 8=0=0 ) ) (X(X

28、0 0=n=n ) ) X X8 8 = n = n X X0 0=0=0； r r2424(X(X8 8=0=0 ) ) (X(X7 7=n=n ) ) X X8 8 = n = n X X7 7 =0 =0；2022-3-6人工智能283.1.4 3.1.4 重排九宫问题和隐式图（重排九宫问题和隐式图（3 3）八数码的状态图可表示为八数码的状态图可表示为 （SS0 0, r, r1 1 , r , r2 2 , , r , , r2424 , S , Sg g ） 八数码问题状态图仅给出了初始节点八数码问题状态图仅给出了初始节点和目标节点，其余节点需用状态转换规则和目标节点，其余节点需用状

29、态转换规则来产生。类似于这样表示的状态图称为来产生。类似于这样表示的状态图称为隐隐式状态图式状态图，或者说，或者说状态图状态图的的隐式表示隐式表示。2022-3-6人工智能293.1.4 3.1.4 重排九宫问题和隐式图（重排九宫问题和隐式图（4 4）n如何隐式的描述一个状态空间如何隐式的描述一个状态空间n有描述问题状态的有关知识，包括该问题的有描述问题状态的有关知识，包括该问题的各状态分量的取值情况，开始条件、结束条各状态分量的取值情况，开始条件、结束条件、各种约束条件等等。件、各种约束条件等等。n需要由任何一个状态生成其所有直接后继节需要由任何一个状态生成其所有直接后继节点的的有关知识。点

30、的的有关知识。2022-3-6人工智能303.1.4 3.1.4 重排九宫问题和隐式图（重排九宫问题和隐式图（5 5）例例3.10 旅行商问题旅行商问题(Traveling(TravelingSalesmanProblemSalesmanProblem，简，简称称TSP)TSP)。设有。设有n n个互相可直达的城市，某推销商准备从个互相可直达的城市，某推销商准备从其中的其中的A A城出发，周游各城市一遍，最后又回到城出发，周游各城市一遍，最后又回到A A城。城。要求为该推销商规划一条最短的旅行路线。要求为该推销商规划一条最短的旅行路线。 该问题的状态为以该问题的状态为以A A打头的已访问过的城

31、市序打头的已访问过的城市序列列:A:A S S0 0:A:A。 S Sg g:A:A, ,A,A。其中。其中“”为其余为其余n-1n-1个城市的一个序列。个城市的一个序列。状态转换规则：状态转换规则： 规则规则1 1 如果当前城市的下一个城市还未去过，则去该如果当前城市的下一个城市还未去过，则去该城市，并把该城市名排在已去过的城市名序列后端。城市，并把该城市名排在已去过的城市名序列后端。 规则规则2 2 如果所有城市都去过一次，则从当前城市返回如果所有城市都去过一次，则从当前城市返回A A城，把城，把A A也添在去过的城市名序列后端。也添在去过的城市名序列后端。2022-3-6人工智能313.

32、1.5 3.1.5 问题求解的基本框架（问题求解的基本框架（1 1）n问题求解所需要的知识问题求解所需要的知识n与描述问题的状态有关的各种与描述问题的状态有关的各种叙述性知识叙述性知识。n描述状态之间的变换关系的各种描述状态之间的变换关系的各种过程性知识过程性知识。n一般以一组一般以一组操作操作的形式出现的。任何一个操作都含有的形式出现的。任何一个操作都含有条件和动作两部分，条件和动作两部分，条件条件给定了操作的适用范围，给定了操作的适用范围，动作动作描述了由于操作而引起的状态中某些分量的变化情形。描述了由于操作而引起的状态中某些分量的变化情形。n描述如何根据当前状态和目标状态选择合适的操描述

33、如何根据当前状态和目标状态选择合适的操作的作的控制性知识控制性知识。n根据叙述性和过程性知识可以构造问题的状态空根据叙述性和过程性知识可以构造问题的状态空间。一般讲间。一般讲状态空间状态空间是一个赋值有向图，节点对应是一个赋值有向图，节点对应着问题的状态，边对应操作。着问题的状态，边对应操作。2022-3-6人工智能323.1.5 3.1.5 问题求解的基本框架（问题求解的基本框架（2 2）n问题求解问题求解就是在图中寻找一条从初始节点到就是在图中寻找一条从初始节点到达目标节点的通路或操作序列。达目标节点的通路或操作序列。n首先从操作集中选择可作用在当前状态上首先从操作集中选择可作用在当前状态

34、上的操作；的操作；n如果符合条件的操作有许多个，则要从挑如果符合条件的操作有许多个，则要从挑选出最有希望导致目标状态的操作施加到当选出最有希望导致目标状态的操作施加到当前状态上，以便克服组合爆炸；前状态上，以便克服组合爆炸；n如果解的长度很大，还需要更为复杂的克如果解的长度很大，还需要更为复杂的克服组合爆炸的技术。服组合爆炸的技术。2022-3-6人工智能333.2 3.2 状态图搜索状态图搜索3.2.13.2.1状态图搜索状态图搜索3.2.23.2.2穷举式搜索穷举式搜索3.2.33.2.3启发式搜索启发式搜索3.2.43.2.4加权状态图搜索加权状态图搜索3.2.53.2.5启发式图搜索的

35、启发式图搜索的A A算法和算法和A A* *算法算法3.2.63.2.6状态图搜索策略小结状态图搜索策略小结2022-3-6人工智能343.2.1 3.2.1 状态图搜索（状态图搜索（1 1）n搜索搜索：从初始节点出发，沿着与之相连的边试：从初始节点出发，沿着与之相连的边试探地前进，寻找目标节点的过程。探地前进，寻找目标节点的过程。n搜索过程中经过的节点和边，按原图的连接关搜索过程中经过的节点和边，按原图的连接关系，便会构成一个树型的有向图，这种树型有系，便会构成一个树型的有向图，这种树型有向图称为向图称为搜索树搜索树。n搜索进行中，搜索树会不断增长，直到当搜索搜索进行中，搜索树会不断增长，直

36、到当搜索树中出现目标节点，搜索便停止。这时从搜索树中出现目标节点，搜索便停止。这时从搜索树中就可很容易地找出从初始节点到目标节点树中就可很容易地找出从初始节点到目标节点的路径（的路径（解解）来。）来。 2022-3-6人工智能353.2.1 3.2.1 状态图搜索（状态图搜索（2 2）1 1 搜索方式搜索方式n树式搜索树式搜索 在搜索过程中记录所经过的在搜索过程中记录所经过的所有节点和边所有节点和边。树式。树式搜索所记录的搜索所记录的轨迹轨迹始终是一棵始终是一棵树树，这棵树也就是搜，这棵树也就是搜索过程中所产生的搜索树。索过程中所产生的搜索树。n线式搜索线式搜索 在搜索过程中只记录那些在搜索过

37、程中只记录那些当前当前认为在所找路径上认为在所找路径上的的节点和边节点和边。n不回溯线式搜索不回溯线式搜索n可回溯线式搜索可回溯线式搜索 2022-3-6人工智能363.2.1 3.2.1 状态图搜索（状态图搜索（3 3）2 2 搜索策略搜索策略n盲目搜索盲目搜索 无向导的搜索，树式盲目搜索就是穷举搜索，不无向导的搜索，树式盲目搜索就是穷举搜索，不回溯的线式搜索是随机碰撞式搜索，回溯的线式搜回溯的线式搜索是随机碰撞式搜索，回溯的线式搜索也是穷举式搜索。索也是穷举式搜索。n启发式搜索启发式搜索 是利用是利用“启发性信息启发性信息”引导的搜索策略。引导的搜索策略。“启发启发性信息性信息”就是与问题

38、有关的有利于尽快找到问题解就是与问题有关的有利于尽快找到问题解的信息或知识。启发式搜索分为不同的策略，如全的信息或知识。启发式搜索分为不同的策略，如全局择优，局部择优，最佳图搜索。局择优，局部择优，最佳图搜索。n按按扩展顺序扩展顺序不同分为不同分为广度优先广度优先和和深度优先深度优先。2022-3-6人工智能373.2.1 3.2.1 状态图搜索（状态图搜索（4 4）3 3 搜索算法搜索算法n搜索的目的是为了寻找初始节点到目标节点的路径，搜索的目的是为了寻找初始节点到目标节点的路径，搜索过程中就得随时记录搜索轨迹。搜索过程中就得随时记录搜索轨迹。nClOSEDClOSED表表动态数据结构来记录

39、考察过的节点。动态数据结构来记录考察过的节点。nOPENOPEN表表的动态数据结构来专门登记当前待考查的节的动态数据结构来专门登记当前待考查的节点。点。节点父节点编号编号节点父节点编号OPEN表表CLOSED表表2022-3-6人工智能383.2.1 3.2.1 状态图搜索（状态图搜索（5 5）n树式搜索算法 步步1 把初始节点把初始节点S0放入放入OPEN表中。表中。 步步2 若若OPEN表为空，则搜索失败，退出。表为空，则搜索失败，退出。 步步3 取取OPEN表中表中第一个节点第一个节点N放在放在CLOSED表中；表中；并冠以顺序编号并冠以顺序编号n； 步步4 若目标节点若目标节点Sg=N

40、，成功退出。，成功退出。 步步5 若若N不可扩展，转步不可扩展，转步2。 步步6 扩展扩展N，生成一组节点，对这组子节点作如下处，生成一组节点，对这组子节点作如下处理：理：2022-3-6人工智能393.2.1 3.2.1 状态图搜索（状态图搜索（6 6）（1）删除）删除N的先辈节点的先辈节点（如果有的话）。（如果有的话）。（2）对）对已存在于已存在于OPEN表中的节点表中的节点（如果有的话）也删（如果有的话）也删除之；删除之前要比较其返回初始节点的新路径与原除之；删除之前要比较其返回初始节点的新路径与原路径，如果新路径路径，如果新路径“短短”，则修改这些节点在，则修改这些节点在OPEN表中的

41、原返回指针，使其沿新路径返回。表中的原返回指针，使其沿新路径返回。（3）对）对已存在于已存在于CLOSED表的节点表的节点，作与（，作与（2）同样的）同样的处理，并且将其移出处理，并且将其移出CLOSED表，放入表，放入OPEN表中重表中重新扩展。新扩展。（4）对）对其余子节点其余子节点配上指向配上指向N的返回指针后放入的返回指针后放入OPEN表中表中某处某处，或对，或对OPEN表进行表进行重新排序重新排序，转步，转步2。2022-3-6人工智能403.2.1 3.2.1 状态图搜索（状态图搜索（7 7）n树式算法的几点说明树式算法的几点说明n返回指针返回指针指的是父节点在指的是父节点在CLO

42、SEDCLOSED表中的编号。表中的编号。n步步6 6中中修改指针修改指针的原因是返回初始节点的路径有两的原因是返回初始节点的路径有两条，要选择条，要选择“短短”的那条路径。的那条路径。n这里这里路径长短路径长短以节点数来衡量，在后面将会看到以以节点数来衡量，在后面将会看到以代价来衡量。按代价衡量修改返回指针的同时还要代价来衡量。按代价衡量修改返回指针的同时还要修改相应的代价值。修改相应的代价值。2022-3-6人工智能413.2.1 3.2.1 状态图搜索（状态图搜索（8 8）图 3-5 修改返回指针示例 2022-3-6人工智能423.2.1 3.2.1 状态图搜索（状态图搜索（9 9）n

43、树式搜索例树式搜索例n对于对于已存在于已存在于OPENOPEN表中的节点表中的节点（如果有的话）也删除之；删（如果有的话）也删除之；删除之前要比较其返回初始节点的新路径与原路径，如果新路除之前要比较其返回初始节点的新路径与原路径，如果新路径短，则修改这些节点在径短，则修改这些节点在OPENOPEN表中的原返回指针，使其沿原表中的原返回指针，使其沿原路径返回。路径返回。Path1Path2S0mnP先扩展后扩展P P在在n n之前已是某一节点之前已是某一节点m m的后继的后继如图所示：说明从如图所示：说明从S S0 0PP至至少有两条路，这时有两少有两条路，这时有两种情况：种情况：f f（Pat

44、h2Path2） f f（Path1Path1），），当前路径较好，要修改当前路径较好，要修改P P的指针，使其指向的指针，使其指向n n，即，即搜索之后的最佳路径。搜索之后的最佳路径。否则，原路径好。否则，原路径好。2022-3-6人工智能433.2.1 3.2.1 状态图搜索（状态图搜索（1010）n对对已存在于已存在于CLOSEDCLOSED表的节点表的节点，作与（，作与（2 2）同样的处理，并将其）同样的处理，并将其移出移出CLOSEDCLOSED表，放入表，放入OPENOPEN表中重新扩展。表中重新扩展。S0过去生成P的路径现在生成P的路径过去对Ps的最优路径PsPmnka.Pa.P

45、在在n n之前已是某一节点之前已是某一节点m m的的后继，所以需要做如同（后继，所以需要做如同（2 2）同样的处理，如图右部所示。同样的处理，如图右部所示。b.Pb.P在在ClosedClosed表中，说明表中，说明P P的后的后继也在继也在n n之前已经生成，称为之前已经生成，称为PsPs。对。对PsPs而言同样可能而言同样可能 由于由于nPnP这一路径的加入，又必须这一路径的加入，又必须比较多条路径之后而取代价小比较多条路径之后而取代价小的一条，如图左部所示。的一条，如图左部所示。2022-3-6人工智能443.2.1 3.2.1 状态图搜索（状态图搜索（1111）例：设当前搜索图和搜索树

46、如图所示例：设当前搜索图和搜索树如图所示S0nPmPsPsS0nPmPsPsFF2022-3-6人工智能453.2.1 3.2.1 状态图搜索（状态图搜索（1212）n若启发函数若启发函数f(n)f(n)为从为从S0S0到节点到节点n n的最短路径的长度，用的最短路径的长度，用边的数目来考察，当前扩展的节点是搜索图中的边的数目来考察，当前扩展的节点是搜索图中的n,Pn,P是是n n的后继的后继S0nPmPsPsnPPsPsS0mFF2022-3-6人工智能463.2.1 3.2.1 状态图搜索（状态图搜索（1313）nP P的指针改变后，修改搜索树结果如下：的指针改变后，修改搜索树结果如下：n

47、PPsS0FmPs2022-3-6人工智能473.2.1 3.2.1 状态图搜索（状态图搜索（1414）n不回溯线式搜索算法不回溯线式搜索算法 步步1 把初始节点把初始节点S0放入放入CLOSED表中；表中； 步步2 令令N S0 ； 步步3 若若N是目标节点，则搜索成功，结束。是目标节点，则搜索成功，结束。 步步4 若若N不可扩展，则搜索失败，退出。不可扩展，则搜索失败，退出。 步步5 扩展扩展N，选取其一个未在，选取其一个未在CLOSED表中出现过的表中出现过的 子节点子节点N1放入放入 CLOSED表中，令表中，令NN1，转步，转步3。2022-3-6人工智能483.2.1 3.2.1

48、状态图搜索（状态图搜索（1515）n可回溯的线式搜索可回溯的线式搜索步步1 把初始节点把初始节点S0放入放入CLOSED表中；表中；步步2 令令N S0 ；步步3 若若N是目标节点，则搜索成功，结束。是目标节点，则搜索成功，结束。步步4 若若N不可扩展，则移出不可扩展，则移出CLOSED表中的末端节点表中的末端节点Ne ，若，若NeS0， 则搜索失败，退出。否则以则搜索失败，退出。否则以CLOSED表新的末端节点表新的末端节点Ne作为作为 N，即令，即令N Ne，转步，转步4；步步5 扩展扩展N，选取其一个未在，选取其一个未在CLOSED表中出现过的子节点表中出现过的子节点N1放入放入 CLO

49、SED表中，令表中，令N N1 ，转步，转步3。2022-3-6人工智能493.2.2 3.2.2 穷举式搜索（穷举式搜索（1 1）n广度优先搜索（算法广度优先搜索（算法A A?eded）n策略策略 始终在始终在同一级节点同一级节点中考查，当同一级节点考查完了之后，才中考查，当同一级节点考查完了之后，才 考查下一级节点。搜索树考查下一级节点。搜索树自顶向下一层一层自顶向下一层一层逐渐生成。逐渐生成。n算法算法 步步1 把初始节点把初始节点S0S0放入放入OPENOPEN表中；表中； 步步2 2 若若OPENOPEN表为空，则搜索失败，退出。表为空，则搜索失败，退出。 步步3 3 取取OPENO

50、PEN表中第一个节点表中第一个节点N N放在放在CLOSEDCLOSED表中；并冠以顺序编号表中；并冠以顺序编号n n； 步步4 4 若节点若节点N N为目标节点，成功退出。为目标节点，成功退出。 步步5 5 若若N N不可扩展，转步不可扩展，转步2 2； 步步6 6 扩展扩展N N，将其所有子节点配上指向，将其所有子节点配上指向N N的指针放入的指针放入OPENOPEN尾部尾部，转步，转步2 2。2022-3-6人工智能503.2.2 3.2.2 穷举式搜索（穷举式搜索（2 2）2022-3-6人工智能513.2.2 3.2.2 穷举式搜索（穷举式搜索（3 3）n广度优先搜索的特点广度优先搜

51、索的特点n广度优先中广度优先中OPENOPEN表表是一个是一个队列队列，CLOSEDCLOSED表表是一个是一个顺顺序表序表，表中各节点按顺序编号，正被考察的节点在，表中各节点按顺序编号，正被考察的节点在表中编号最大。表中编号最大。n广度优先搜索又称为广度优先搜索又称为宽度优先宽度优先或或横向搜索横向搜索。n广度优先策略是广度优先策略是完备完备的，即如果问题的解存在，则的，即如果问题的解存在，则它一定可以找到解，并且找到的解还是最优解。它一定可以找到解，并且找到的解还是最优解。n广度优先搜索策略与问题无关，具有通用性。广度优先搜索策略与问题无关，具有通用性。n缺点搜索缺点搜索效率低效率低。20

52、22-3-6人工智能523.2.2 3.2.2 穷举式搜索（穷举式搜索（4 4）n八数码问题2 8 31 47 6 5初始状态8 1 32 47 6 5目标状态2022-3-6人工智能533.2.2 3.2.2 穷举式搜索（穷举式搜索（5 5）2 8 31 47 6 51 2 3 1 8 47 6 592 31 8 47 6 582 81 4 37 6 5102 8 37 1 4 6 57 8 32 1 47 6 562 8 31 4 57 6112 8 3 1 47 6 522 31 8 47 6 532 8 31 47 6 542 8 31 6 4 7 5122 8 31 6 47 513

53、8 32 1 47 6 5142 8 37 1 46 5152 3 41 87 6 5161 2 3 8 47 6 5172 81 4 37 6 5182 8 31 4 57 6192 8 3 6 41 7 5202 8 31 6 7 5 4218 32 1 47 6 5222 8 31 6 47 558 1 32 47 6 523八数码广度优先搜索八数码广度优先搜索2022-3-6人工智能543.2.2 3.2.2 穷举式搜索（穷举式搜索（6 6）n深度优先搜索（过程深度优先搜索（过程A Apdpd ）n搜索策略搜索策略 在搜索树的每一层始终先扩展一个子节点，不断地向纵深前在搜索树的每一层始

54、终先扩展一个子节点，不断地向纵深前进，直到不能再前进，才从当前节点返回到上一级节点，从另一进，直到不能再前进，才从当前节点返回到上一级节点，从另一方向继续前进。方向继续前进。n算法 步步1 把初始节点把初始节点S0放入放入OPEN表中；表中； 步步2 若若OPEN表为空，则搜索失败，退出。表为空，则搜索失败，退出。 步步3 取取OPEN表中第一个节点表中第一个节点N放在放在CLOSED表中；并冠以编号表中；并冠以编号n； 步步4 节点节点N为目标节点，成功退出。为目标节点，成功退出。 步步5 若若N不可扩展，转步不可扩展，转步2； 步步6 扩展扩展N，将其所有子节点配上指向，将其所有子节点配上

55、指向N的指针放入的指针放入OPEN首部首部，转，转 步步2。2022-3-6人工智能553.2.2 3.2.2 穷举式搜索（穷举式搜索（7 7）2022-3-6人工智能563.2.2 3.2.2 穷举式搜索（穷举式搜索（8 8）n深度优先搜索的特点深度优先搜索的特点nOPENOPEN表为一个表为一个堆栈堆栈。n深度优先又称深度优先又称纵向搜索纵向搜索。n一般一般不能保证找到最优解不能保证找到最优解。n当深度限制不合理时，可能找不到解，可以将算当深度限制不合理时，可能找不到解，可以将算法改为可变深度限制，即有界深度优先搜索。法改为可变深度限制，即有界深度优先搜索。n最坏情况时，搜索空间等同于穷举

56、。最坏情况时，搜索空间等同于穷举。2022-3-6人工智能573.2.2 3.2.2 穷举式搜索（穷举式搜索（9 9）2 31 8 47 6 52 8 31 47 6 52 8 3 1 47 6 52 8 31 6 47 52 8 31 47 6 512 8 31 6 47 532 8 31 6 7 5 442 8 31 6 47 522 8 31 6 7 5 42 81 6 37 5 45八数码深度优先搜索2022-3-6人工智能583.2.2 3.2.2 穷举式搜索（穷举式搜索（1010）n有界深度优先搜索（过程有界深度优先搜索（过程A Acdcd ）n搜索策略搜索策略 给出搜索树给出搜索

57、树深度深度的的限制限制，当从初始节点出发沿某一分支扩展到一定，当从初始节点出发沿某一分支扩展到一定深度限制时，就不能再继续往下扩展，而只能改变方向继续搜索深度限制时，就不能再继续往下扩展，而只能改变方向继续搜索。n算法算法 步步1 把初始节点把初始节点S0放入放入OPEN表中，置表中，置S0的深度的深度d（ S0 ）0； 步步2 若若OPEN表为空，则搜索失败，退出。表为空，则搜索失败，退出。 步步3 取取OPEN表中第一个节点表中第一个节点N放在放在CLOSED表中；并冠以编号表中；并冠以编号n； 步步4 若节点若节点N为目标节点，成功退出。为目标节点，成功退出。 步步5 若若N的深度的深度

58、d（N）dm（深度限制值），或者若（深度限制值），或者若N无子节点，无子节点， 则转步则转步2； 步步6 扩展扩展N，将其所有子节点，将其所有子节点Ni配上指向配上指向N的指针放入的指针放入OPEN首部首部， 置的置的d（ Ni ）d（N）1，转步，转步2。2022-3-6人工智能593.2.2 3.2.2 穷举式搜索（穷举式搜索（1111）a1a2a3a6b1b2b4b3b5S2022-3-6人工智能603.2.2 3.2.2 穷举式搜索（穷举式搜索（1212）n有界深度优先搜索存在的问题有界深度优先搜索存在的问题n深度界限的选择很重要深度界限的选择很重要 d dm m 若太小，则达不到解的

59、深度，得不到解；若太若太小，则达不到解的深度，得不到解；若太大，既浪费了计算机的存储空间与时间，又降低了搜大，既浪费了计算机的存储空间与时间，又降低了搜索效率。由于解的路径长度事先难以预料，所以要恰索效率。由于解的路径长度事先难以预料，所以要恰当地给出当地给出d dm m的值是比较困难的。的值是比较困难的。n即使能求出解，它也不一定是最优解。即使能求出解，它也不一定是最优解。2022-3-6人工智能613.2.2 3.2.2 穷举式搜索（穷举式搜索（1313）n有界深度优先搜索改进有界深度优先搜索改进nd dm m随搜索深度不断加大（随搜索深度不断加大（迭代加深搜索迭代加深搜索） 先任意给定一

60、个较小的数作为先任意给定一个较小的数作为d dm m，然后进行上述的有界深，然后进行上述的有界深 度优先搜索，当搜索达到了指定的深度界限度优先搜索，当搜索达到了指定的深度界限d dm m仍未发现目标节点，仍未发现目标节点，并且并且CLOSEDCLOSED表中仍有待扩展节点时就将这些节点送回表中仍有待扩展节点时就将这些节点送回OPENOPEN表，表，同时增大深度界限同时增大深度界限d dm m，继续向下搜索。如此不断地增大，继续向下搜索。如此不断地增大d dm m，只要，只要问题有解，就一定可以找到它。问题有解，就一定可以找到它。n增加一个增加一个R R表表 此时找到的解不一定是最优解。为找到最