第2章基于状态空间图表示的搜索技术

1、2021-12-31人工智能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 博弈树及搜索技术博弈树及搜索技术2021-12-31人工智能32.1 2.1 概述概述2.1.1 2.1.1 知识与问题求解框架知识与问题求解框架2.1.2 2.1.2 知识表示知识表示2.1.3 2.1.3 图搜索技术图搜索技术2021-1

2、2-31人工智能42.1.1 2.1.1 知识与问题求解框架知识与问题求解框架(1)(1) 1. 1.知识的定义知识的定义n心理学心理学：个体通过与环境相互作用后获得的信息及：个体通过与环境相互作用后获得的信息及其组织。其组织。n费根鲍姆费根鲍姆：知识是经过消减、塑造、解释和转换的：知识是经过消减、塑造、解释和转换的信息。信息。n博恩斯坦博恩斯坦（BernsteinBernstein）：知识是由特定领域的描）：知识是由特定领域的描述、关系和过程组成的。述、关系和过程组成的。 概括地说，知识是高度组织起来的信息集团，概括地说，知识是高度组织起来的信息集团，是人们在长期的生活和社会实践中、科学研究

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

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

5、明在北京，他要去西安（办事）。又如，博弈问题。又如，博弈问题。2021-12-31人工智能6问题的求解框架问题的求解框架（1 1）叙述性知识：叙述性知识：描述问题的状态有关的各种描述问题的状态有关的各种知识。知识。（2 2）过程性知识：过程性知识：描述状态之间的变换关系的描述状态之间的变换关系的各种知识。各种知识。（3 3）控制性知识：控制性知识：描述如何在当前状态下选择描述如何在当前状态下选择合适操作的知识。合适操作的知识。2021-12-31人工智能82.1.2 2.1.2 知识表示知识表示(1)(1)知识表示：就是研究知识表示：就是研究在计算机中在计算机中如何用最合适的形式如何用最合适的

6、形式表示表示问题求解过程中所需要的各种知识，包括构成问题求解框问题求解过程中所需要的各种知识，包括构成问题求解框架的全部知识。架的全部知识。常用的知识表示形式常用的知识表示形式状态空间图状态空间图与或图与或图谓词逻辑谓词逻辑产生式产生式框架框架语义网络语义网络2.1.2 2.1.2 知识表示知识表示(2)(2)2021-12-31人工智能9例例2.12.1 麦卡赛问题麦卡赛问题。 在一个在一个2n2n 2n2n的方格棋盘中，去掉的方格棋盘中，去掉对角的两个方格，如图（对角的两个方格，如图（a a），问能否将它全部划成若干），问能否将它全部划成若干1 1 2 2的小长方块？的小长方块？目标状态目

7、标状态初始状态初始状态可达状态可达状态同构问题同构问题同态问题同态问题2021-12-31人工智能102.1.3 2.1.3 图搜索技术图搜索技术(1)(1)1.1.搜索搜索 搜索，简单地说就是搜索，简单地说就是“寻找寻找”，目的是找到问题的解。，目的是找到问题的解。在问题求解过程中，待求解的问题被抽象成一定空间上的图，在问题求解过程中，待求解的问题被抽象成一定空间上的图，搜索过程就是搜索过程就是从从图中图中初始节点初始节点出发，沿着与之相连的边出发，沿着与之相连的边试探试探着着前进，前进，寻找目标节点寻找目标节点或或可解节点可解节点的过程。的过程。2.2.搜索树搜索树 搜索过程中搜索过程中经

8、过经过（考察过）（考察过）的节点和边的节点和边，按原图的连接，按原图的连接关系，便会关系，便会构成构成一个一个树型树型的有的有向图向图，称为搜索树。搜索树是，称为搜索树。搜索树是一个搜索过程的搜索轨迹，或称之为一个搜索过程的搜索轨迹，或称之为搜索空间搜索空间。2.1.3 2.1.3 图搜索技术图搜索技术(2)(2)2021-12-31人工智能11图图 2-2 2-2 搜索空间示意图搜索空间示意图问题的状态空间、搜索空间及解的示意图：问题的状态空间、搜索空间及解的示意图：2.1.3 2.1.3 图搜索技术图搜索技术(3)(3)3.3.搜索策略搜索策略 搜索策略将决定搜索过程按照什么样的顺序考察节

9、点和搜索策略将决定搜索过程按照什么样的顺序考察节点和经过状态空间图的哪些节点。经过状态空间图的哪些节点。n盲目搜索：盲目搜索：无向导无向导的的搜索搜索，也称穷举搜索。，也称穷举搜索。n启发式搜索：利用启发式搜索：利用“启发性信息启发性信息”作为作为导航导航的搜索过程。的搜索过程。 对于较大或无限状态空间问题，盲目搜索效率太低，所对于较大或无限状态空间问题，盲目搜索效率太低，所以在实际当中往往是不可行的。以在实际当中往往是不可行的。 启发式搜索广泛地应用于实际问题求解中，如博弈、机启发式搜索广泛地应用于实际问题求解中，如博弈、机器学习、数据挖掘、智能检索等。器学习、数据挖掘、智能检索等。2021

10、-12-31人工智能122021-12-31人工智能132.2 2.2 状态空间图表示状态空间图表示2.2.1 2.2.1 状态空间图状态空间图2.2.2 2.2.2 隐式状态空间图隐式状态空间图2021-12-31人工智能142.2.1 2.2.1 状态空间图（状态空间图（1 1）1.1.状态状态 状态对应叙述性知识状态对应叙述性知识，描述一个问题在，描述一个问题在开始、结束或中间的某一时刻所处的开始、结束或中间的某一时刻所处的状况状况或或状态状态。通常引进一组变量。通常引进一组变量 ，表，表示与问题状态相关的各种要素，并用这组变示与问题状态相关的各种要素，并用这组变量所构成的多元组量所构成

11、的多元组 来表示状来表示状态。态。 状态在状态图中表示为状态在状态图中表示为节点节点。12nqqq， ， ，12()nqqq， ，2021-12-31人工智能152.2.1 2.2.1 状态空间图（状态空间图（2 2）2.2.操作操作 操作对应过程性知识操作对应过程性知识，即状态转换规则，描述状态，即状态转换规则，描述状态之间的关系。之间的关系。描述一个操作要包含两个部分描述一个操作要包含两个部分条件条件: :指明被作用的状态要满足的约束条件指明被作用的状态要满足的约束条件动作动作: :指明一个操作对状态的分量所做的改变。指明一个操作对状态的分量所做的改变。操作的表示形式可以是一个机械性的步骤

12、、过程、规则操作的表示形式可以是一个机械性的步骤、过程、规则或算子。或算子。操作在状态图中表示为操作在状态图中表示为边边。在程序中，状态转换规则可。在程序中，状态转换规则可用数据对、条件语句、规则、函数、过程等表示。用数据对、条件语句、规则、函数、过程等表示。 如：如果室内温度低于如：如果室内温度低于2626度，则关闭空调。度，则关闭空调。 2021-12-31人工智能162.2.1 2.2.1 状态空间图（状态空间图（3 3）3.3.状态空间图状态空间图n问题的问题的状态空间图状态空间图是一个描述该问题全部可能的是一个描述该问题全部可能的状态状态及及相互相互关系关系的的图图，如考虑操作的代价

13、，状态空间图就是一，如考虑操作的代价，状态空间图就是一个个赋值有向图赋值有向图。n状态空间常记为三元组：状态空间常记为三元组： S：初始状态的集合初始状态的集合 F：操作的集合操作的集合 G：目标状态的集合。目标状态的集合。 n由问题的状态空间表示就可以构造出状态空间图。由问题的状态空间表示就可以构造出状态空间图。SFG， ，2.2.1 2.2.1 状态空间图（状态空间图（4 4）4.4.求解求解n在状态空间表示法中，问题求解过程转化为在图中在状态空间表示法中，问题求解过程转化为在图中寻找寻找从初始状态从初始状态Qs出发出发到达到达目标状态目标状态Qg的的路径路径问题问题，也就是寻找操作序列的

14、问题。，也就是寻找操作序列的问题。n状态空间的解为三元组状态空间的解为三元组 nQs ：某个初始状态：某个初始状态nQg ：某个目标状态：某个目标状态na：把把Qs变换成变换成Qg的有限的操作序列的有限的操作序列n状态转换图状态转换图Q1Q3Q2f1f2f3f4QsQgfn2021-12-31人工智能172021-12-31人工智能18例例2.22.2 翻转钱币问题（翻转钱币问题（1 1） 三三枚钱币处于反、正、反状态，每次只许翻动一枚枚钱币处于反、正、反状态，每次只许翻动一枚钱币，问连续翻动三次后，能否出现全正或全反状态。钱币，问连续翻动三次后，能否出现全正或全反状态。 初始状态初始状态目标

15、状态集合目标状态集合例例2.22.2 翻转钱币问题（翻转钱币问题（2 2）1.1.状态状态引入一个三元组引入一个三元组(q0,q1,q2)来描述总状态，钱币正面来描述总状态，钱币正面为为0 0，反面为，反面为1 1，全部可能的状态为：，全部可能的状态为： Q0=(0,0,0) ; Q1=(0,0,1); Q2=(0,1,0) Q3=(0,1,1) ; Q4=(1,0,0); Q5=(1,0,1) Q6=(1,1,0) ; Q7=(1,1,1)。2021-12-31人工智能192.2.操作操作翻动钱币的操作抽象为改变上述状态的算子，翻动钱币的操作抽象为改变上述状态的算子， 即即Fa, b, c

16、a: a:把钱币把钱币q0翻转一次翻转一次 b:b:把钱币把钱币q1翻转一次翻转一次 c:c:把钱币把钱币q2翻转一次翻转一次问题的状态空间为问题的状态空间为 例例2.22.2 翻转钱币问题（翻转钱币问题（3 3）例例2.22.2 翻转钱币问题（翻转钱币问题（4 4）3.3.状态空间图状态空间图 问题的状态空间为：问题的状态空间为： 2021-12-31人工智能21 构造状态空间图：构造状态空间图：507QabcQQ， ， ， ，aabababaabbbbcccbcccb例例2.22.2 翻转钱币问题（翻转钱币问题（5 5）2021-12-31人工智能22翻转钱币问题状态空间图的翻转钱币问题状

17、态空间图的另一种表示另一种表示：引入分量引入分量n表示已经翻过的次数表示已经翻过的次数即即Q50表示经过表示经过0次翻转到次翻转到达达Q5； Q41表示经过表示经过1次翻转到达次翻转到达Q4； 。例例2.22.2 翻转钱币问题（翻转钱币问题（6 6）2021-12-31人工智能23aabababaabbbbcccbcccb2021-12-31人工智能24例例2.32.3 修道士和野人问题（修道士和野人问题（1 1） 在河的左岸有三个修道士、三个野人和一条船，在河的左岸有三个修道士、三个野人和一条船，修道士们想用这条船将所有的人都运过河去，但受修道士们想用这条船将所有的人都运过河去，但受到以下条

18、件的限制：到以下条件的限制： （1 1）修道士和野人都会划船，但船一次）修道士和野人都会划船，但船一次最多最多只只能能运两个人运两个人； （2 2）在任何岸边）在任何岸边野人数目野人数目都都不得超过修道士不得超过修道士，否则修道士就会被野人吃掉。否则修道士就会被野人吃掉。 假定野人会服从任何一种过河安排，试规划出假定野人会服从任何一种过河安排，试规划出一种确保修道士安全过河方案。一种确保修道士安全过河方案。2021-12-31人工智能25例例2.32.3 修道士和野人问题（修道士和野人问题（2 2）1 1、问题的状态、问题的状态可以用一个三元数组来描述：可以用一个三元数组来描述： S(m, c

19、, b) m：左岸的修道士人数左岸的修道士人数 m0,1,2,3 c： 左岸的野人数左岸的野人数 c c 0,1,2,3 b： 左岸的船数左岸的船数 b0,1右岸的状态不必标出，因为：右岸的状态不必标出，因为： 右岸的修道士人数右岸的修道士人数 m 3m 右岸的野人数右岸的野人数 c 3c 右岸的船数右岸的船数 b 1b2021-12-31人工智能26例例2.32.3 修道士和野人问题（修道士和野人问题（3 3）状态m, c, b状态m, c, b状态m, c, b状态m, c, bS03 3 1S81 3 1 S163 3 0S241 3 0S13 2 1S91 2 1 S173 2 0S2

20、51 2 0S23 1 1 S101 1 1 S183 1 0S261 1 0S33 0 1 S111 0 1 S193 0 0S271 0 0S42 3 1 S120 3 1 S202 3 0S28 0 3 0不可能状态不可能状态不合法状态不合法状态合法状态合法状态1616例例2.32.3 修道士和野人问题（修道士和野人问题（4 4）2 2、操作操作 pij 操作：左岸到右岸操作：左岸到右岸 qij 操作：右岸到左岸操作：右岸到左岸 船上修道士人数船上修道士人数i，野人人数，野人人数j满足：满足： 1 i+j 2可实施的操作集为：可实施的操作集为：F p01, p10,p11,p02,p20

21、,q01,q10,q11, q02,q20 2021-12-31人工智能28例例2.32.3 修道士和野人问题（修道士和野人问题（5 5）操作集操作集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)或(m=2,

22、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.32.3 修道士和野人问题（修道士和野人问题（6 6）3.3.状态空间状态空间给出状态和操作的描述之后，该问题的状态空间是：给出状态和操作的描述之后，该问题的状态空间是：S0， P 01，P 10，P 11，P 02，P 20，Q01，Q 10，Q 11，Q 02，Q 20，S31。 以全部合法状态

23、为节点，按照操作要求的条件，在节点之以全部合法状态为节点，按照操作要求的条件，在节点之间构造有向边。间构造有向边。2021-12-31人工智能30例例2.32.3 修道士和野人问题（修道士和野人问题（7 7）S0(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)q01p01S

24、30(0,1,0) p02q02S12(0,3,1)p01q01S29(0,2,0)p20q20S5(2,2,1)q11p114.4.状态空间图：状态空间图：四条四条S S0 0到到S S3131长度相等的最短路径，对应的操作长度相等的最短路径，对应的操作序列就是该问题的四个最优解序列就是该问题的四个最优解 P 01，P 10，P 11，P 02，P 20，Q01，Q 10，Q 11，Q 02，Q 20 2021-12-31人工智能312.2.2 隐式状态空间图隐式状态空间图显式状态空间显式状态空间图：图： 表表示了问题所有可能的状态及状态之间的关系，示了问题所有可能的状态及状态之间的关系，这

25、种这种 表表示方式称为示方式称为显式状态空间图显式状态空间图，或称为，或称为状态空间状态空间图的图的 显式表示显式表示。隐式状态空间隐式状态空间图：图： 利利用有关状态描述和状态转换（操作）的知识定用有关状态描述和状态转换（操作）的知识定义的义的 状状态空间图。在计算机中仅存储描述问题状态及态空间图。在计算机中仅存储描述问题状态及操作操作 的的有关知识，包括该问题的各状态分量的取值情有关知识，包括该问题的各状态分量的取值情况、况、 分分量之间的约束条件、开始状态、终止状态，以量之间的约束条件、开始状态、终止状态，以及全及全 部部操作的条件和动作等。隐式状态空间图也称为操作的条件和动作等。隐式状

26、态空间图也称为是是状状 态态空间图的隐式表示或隐式图。空间图的隐式表示或隐式图。重排九宫问题的隐式图描述为：重排九宫问题的隐式图描述为： （1 1）有关状态的知识：）有关状态的知识：状态状态S的定义：的定义：S(X0，X1，X2，X3，X4 ，X5， X6 ，X7 ，X8) 其中，其中， Xi 0，1，2，3，4，5，6，7，8， ，且，且 。初始状态：初始状态： S S0 0 （0 0，1 1，2 2，3 3，5 5，6 6，4 4，7 7，8 8） 目标状态：目标状态： S Sg g （0 0，1 1，2 2，3 3，4 4，5 5，6 6，7 7，8 8） 重排九宫问题的状态表示80 i

27、ijijXX时，例例2.42.4 重排九宫问题重排九宫问题（八数码问题）（八数码问题） 例例2.42.4 重排九宫问题（重排九宫问题（2 2）（2 2）有关操作的知识（规则）：）有关操作的知识（规则）：0 0组规则组规则 R1(X0=0 ) (X2=n ) X0 = n X2 =0； R2(X0=0 ) (X4=n ) X0 = n X4 =0； R3(X0=0 ) (X6=n ) X0 = n X6 =0； R4(X0=0 ) (X8=n ) X0 = n X8 =0；1 1组规则组规则 R5(X1=0 ) (X2=n ) X1 = n X2 =0； R6(X1=0 ) (X8=n ) X1

28、 = n X8 =0；8 8组规则组规则: : R22(X8=0 ) (X1=n ) X8 = n X1 =0； R23(X8=0 ) (X0=n ) X8 = n X0=0； R24(X8=0 ) (X7=n ) X8 = n X7 =0；例例2.42.4 重排九宫问题（重排九宫问题（3 3） 八数码的状态图可表示为八数码的状态图可表示为 （S0, R1 , R2 , , R24 , Sg） 八数码问题状态图仅给出了初始节点和八数码问题状态图仅给出了初始节点和目标节点，其余节点需用状态转换规则来产目标节点，其余节点需用状态转换规则来产生。类似于这样表示的状态图称为生。类似于这样表示的状态图称

29、为隐式状态隐式状态图图，或者说，或者说状态图状态图的的隐式表示隐式表示。例例2.42.4 重排九宫问题（重排九宫问题（4 4）（3 3）隐式图搜索）隐式图搜索 初始状态初始状态S（ 0，1，2，3，5，6，4，7，8 ）满足条件满足条件X0 =0，故可以使用第，故可以使用第0 0组的四条规则：组的四条规则： 如果选择规则如果选择规则R1，则状态转换为：，则状态转换为：S1（ 2，1，0，3，5，6，4，7，8)2021-12-31人工智能36例例2.52.5 旅行商问题旅行商问题(TSP)(1)(TSP)(1) 设有设有n个互相可直达的城市，某推销商准备从其中的个互相可直达的城市，某推销商准备

30、从其中的A A城城出发，周游各城市一遍，最后又回到出发，周游各城市一遍，最后又回到A A城。要求为该推销商规城。要求为该推销商规划一条最短的旅行路线。划一条最短的旅行路线。（1 1）状态描述：该问题的状态为以）状态描述：该问题的状态为以A A打头城市序列：打头城市序列： = AA1Ai AjA 其中：其中：A、Ai、Aj、A为城市名，为城市名， 1 i、j n-1，Aj A，Ai A； 1 | | n+1；当当i j 时，时，Ai Aj； 当且仅当当且仅当| |=n+1时时，A=A。初始状态初始状态： = A，| | = 1终止状态终止状态： = AA1A2A，| | = n+1例例2.52.

31、5 旅行商问题旅行商问题(TSP)(2)(TSP)(2)（2 2）操作描述（状态转换规则）：）操作描述（状态转换规则）：规则规则1 1 ：如果：如果 =AA1Ai Aj，且且| | n，但但A，则置，则置 = A。即没遍历完时，在城市序列中添加一个没即没遍历完时，在城市序列中添加一个没 有到过的城市。有到过的城市。规则规则2 2 ：如果：如果| | |= |= n n，置，置 = = A A，即从当前城市返回，即从当前城市返回A A城。城。 （3 3）隐式图搜索）隐式图搜索对于有对于有A、B、C、D四个四个城市所组成的连通城市网，城市所组成的连通城市网，初始状态：初始状态： =A，| |=1，

32、满足规则满足规则1 1 ，则操作的结果为则操作的结果为： =AB 、或或 =AC、或或 =AD，继续使用规则继续使用规则1 1 ，直到生成包含四个城市的序列出现，再使用，直到生成包含四个城市的序列出现，再使用规则规则2 2。2021-12-31人工智能37补充例补充例 二阶梵塔问题（二阶梵塔问题（1 1） 一号杆有一号杆有A、B两个金盘，两个金盘，A小于小于B。要求将。要求将A、B移至三号杆移至三号杆，每次只可移动一个盘子，任何时刻，每次只可移动一个盘子，任何时刻B不能在不能在A上。上。 （1 1）有关状态的知识：）有关状态的知识：用二元组用二元组（SA，SB）表示状态，表示状态，SA表示表示

33、A所在杆号，所在杆号，SB表表示示B所在杆号。其中所在杆号。其中: : SA ,SB 1,2,3 , , 则则全部状态如下：全部状态如下： （1，1），（），（1，2），（），（1，3） （2，1），（），（2，2），（），（2，3） （3，1），（），（3，2），（），（3，3）初始状态为初始状态为（1，1），），终止状态为终止状态为：（3，3） 。2021-12-31人工智能38AB123S0：（：（1，1）123S1：（：（1，2）123S2：（：（1，3）AA123S5：（：（2，3）123S4：（：（2，2）123S3：（：（2，1）123S8：（：（3，3）123S7：（：（3，2

34、）123S6：（：（3，1）AAAAABABBBBB补充例补充例 二阶梵塔问题（二阶梵塔问题（2 2）2021-12-31人工智能39（2 2）有关操作的知识（规则）：）有关操作的知识（规则）： A（i，j）表示金盘表示金盘A从第从第i号杆移到号杆移到j号杆，号杆，B（i，j）表示金盘表示金盘B从第从第i号杆移到号杆移到j号杆，其中：号杆，其中：i,j 1,2,3，但，但i j ，全部操作为：，全部操作为： A（1，2），），A（1，3），）， A（2，1） A（2，3），），A（3，1），）， A（3，2） B（1，2），），B（1，3），）， B（2，1） B（2，3），），B（3，1），

35、）， B（3，2）分析每个操作的条件和动作，得到下表：分析每个操作的条件和动作，得到下表：补充例补充例 二阶梵塔问题（二阶梵塔问题（3 3）2021-12-31人工智能40补充例补充例 二阶梵塔问题（二阶梵塔问题（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 1,2 或或SA=3SB=2B B（1 1，3 3）SB=1， SA 1,

36、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=22021-12-31人工智能41补充例补充例 二阶梵塔问题（二阶梵塔问题（5 5）（3 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,2)A(3,1)B(1,3)A(2,3)2021-12-31

37、人工智能422.3 2.3 状态空间图的盲目搜索状态空间图的盲目搜索n盲目搜索盲目搜索: :搜索时搜索时不参考不参考与具体待求解问题相关的任何信息，与具体待求解问题相关的任何信息，只是按预先设定的顺序逐个考察节点只是按预先设定的顺序逐个考察节点。盲目搜索与问题无关，。盲目搜索与问题无关，具有通用性。具有通用性。n算法中使用的数据结构算法中使用的数据结构: :OPEN表：表：专门登记已经生成但还没有考察的节点，即待考专门登记已经生成但还没有考察的节点，即待考察节点。察节点。CLOSED表：表：用来记录考察过的节点以及节点之间的关系，用来记录考察过的节点以及节点之间的关系，如每个节点指向父节点的编

38、号（返回指针）。如每个节点指向父节点的编号（返回指针）。C CLOSEDLOSED表中存表中存放的就是一定搜索策略下的搜索树。放的就是一定搜索策略下的搜索树。节点节点父节点编号父节点编号编号编号节点节点父节点编号父节点编号OPENOPEN表表CLOSEDCLOSED表表2021-12-31人工智能442.3 状态空间图的盲目搜索状态空间图的盲目搜索2.3.1 广度优先搜索广度优先搜索2.3.2 深度优先搜索深度优先搜索2021-12-31人工智能452.3.1 广度优先搜索（广度优先搜索（1 1） 广度优先搜索（广度优先搜索（A A?eded）基本思想：）基本思想： 广度优先搜索是严格按节点在

39、树中的出现位广度优先搜索是严格按节点在树中的出现位置置一层一层一层一层向下的搜索过程。通过将向下的搜索过程。通过将OPEN表设表设计为一个计为一个队列队列来实现，将新生成的子节点放在来实现，将新生成的子节点放在OPEN表的表的后面后面，保证先生成的节点先考察保证先生成的节点先考察。广度优先搜索算法：广度优先搜索算法：步步1 1 把初始结点把初始结点S S0 0放入放入OPEN表中；表中；步步2 2 若若OPEN表为空，则搜索失败，退出；表为空，则搜索失败，退出；步步3 3 否则，取否则，取OPEN表中第一个结点表中第一个结点N N 放在放在CLOSED 表中；并冠以顺序编号表中；并冠以顺序编号

40、n；步步4 4 若结点若结点N为目标结点，则搜索成功。利用为目标结点，则搜索成功。利用 CLOSED表中的返回指针找出表中的返回指针找出S0到到N的路径即的路径即 为所求解，退出；为所求解，退出；步步5 5 若若N不可扩展，转步不可扩展，转步2 2；步步6 6 否则，扩展否则，扩展N，将其所有子结点配上指向，将其所有子结点配上指向N 的返回指针放入的返回指针放入OPEN表表的的尾部尾部，转步，转步2 2。2.3.1 广度优先搜索（广度优先搜索（2 2）2021-12-31人工智能48例例2.6 使用使用广度优先广度优先搜索算法求解重排九宫问题搜索算法求解重排九宫问题1 2 38 57 4 61

41、1 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 38 2 57 4 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 37 6 5221 2 3 8 57 4 651 2 38 47 6

42、523八数码广度优先搜索八数码广度优先搜索1 28 5 37 4 69161 2 38 5 67 42021-12-31人工智能492.3.1 广度优先搜索广度优先搜索广度优先搜索的特点：广度优先搜索的特点：广度优先中广度优先中OPEN表表是一个是一个队列队列，CLOSED表表是一个是一个顺序表顺序表， 表中各节点按顺序编号，正被考察的节点在表中编号最大。表中各节点按顺序编号，正被考察的节点在表中编号最大。广度优先搜索又称为广度优先搜索又称为宽度优先宽度优先或或横向搜索横向搜索。广度优先策略是广度优先策略是完备完备的，即如果问题的解存在，则它一定可的，即如果问题的解存在，则它一定可 以找到解，

43、并且找到的解还是最优解。以找到解，并且找到的解还是最优解。广度优先搜索策略与问题无关，具有通用性。广度优先搜索策略与问题无关，具有通用性。缺点搜索缺点搜索效率低效率低。2021-12-31人工智能502.3.2 深度优先搜索深度优先搜索(1)(1)深度优先搜索的基本思想：深度优先搜索的基本思想： 深度优先搜索是一种深度优先搜索是一种一直向下一直向下的搜索过程，它的搜索过程，它优先在自己的子结点集合中选择下一个被考察的结优先在自己的子结点集合中选择下一个被考察的结点点，不断向纵深方向前进，直到到达叶子结点或受，不断向纵深方向前进，直到到达叶子结点或受到深度限制时，才返回到上一级结点沿另一方向继到

44、深度限制时，才返回到上一级结点沿另一方向继续前进。续前进。n深度优先搜索算法：深度优先搜索算法：n 与广度优先搜索策略的唯一不同点就是与广度优先搜索策略的唯一不同点就是OPEN表表被设计成被设计成后进先出的栈后进先出的栈，新生成的子结点放在，新生成的子结点放在OPEN表的前面，表的前面，后生成的结点优先被考察后生成的结点优先被考察。深度优先搜索。深度优先搜索算法只需算法只需将宽度优先搜索算法将宽度优先搜索算法步步6 6修改为修改为：n步步6 6 否则，扩展否则，扩展N N，将其所有子结点配上指向，将其所有子结点配上指向N N 的的指针放入指针放入OPENOPEN表的表的首部首部，转步，转步2

45、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 552021-12-31人工智能532.3.2 深度优先搜索深度优先搜索深度优先搜索的特点：深度优先搜索的特点：nOPENOPEN表为一个表为一个堆栈堆栈。n深度优先又称深度优先又称纵向搜索纵向搜索。n一般一般不能保证找到最优解不能保

46、证找到最优解。如下图所示：。如下图所示：图图2-13 2-13 深度优先搜索不具有完备性示意图深度优先搜索不具有完备性示意图2.3.2 深度优先搜索深度优先搜索1.1.有界深度优先搜索有界深度优先搜索2.2.可变界深度优先搜索算法可变界深度优先搜索算法3.3.可采纳的有界深度优先搜索算法可采纳的有界深度优先搜索算法2021-12-31人工智能551.1.有界深度优先搜索（有界深度优先搜索（A Acdcd ）为克服深度优先搜索的不足，可以对其深度进行为克服深度优先搜索的不足，可以对其深度进行限制限制n深度界限深度界限dm的选择很重要的选择很重要 dm 若太小，则达不到解的深度，得不到解；若太大若

47、太小，则达不到解的深度，得不到解；若太大，既浪费了计算机的存储空间与时间，又降低了搜索效，既浪费了计算机的存储空间与时间，又降低了搜索效率。由于解的路径长度事先难以预料，所以要恰当地给率。由于解的路径长度事先难以预料，所以要恰当地给出出dm的值是比较困难的。的值是比较困难的。n即使能求出解，它也不一定是最优解。即使能求出解，它也不一定是最优解。2.2.可变界深度优先搜索算法可变界深度优先搜索算法(1)(1) 当在当在dm界限之内找不到解时，可以将深度界限界限之内找不到解时，可以将深度界限dm不断扩大，每次增加一个深度增量不断扩大，每次增加一个深度增量 d，直到找到解，直到找到解，或者搜索完整棵

48、树。这样算法的完备性得到了保证，或者搜索完整棵树。这样算法的完备性得到了保证，称为称为可变界深度优先搜索算法可变界深度优先搜索算法( (或迭代加深搜索或迭代加深搜索) )。 当当d =1时，算法开始蜕变为时，算法开始蜕变为广度优先搜索广度优先搜索算法。算法。 2.2.可变界深度优先搜索算法可变界深度优先搜索算法(2)(2)n迭代加深搜索过程：迭代加深搜索过程：步步1 1 把初始节点把初始节点S0放入放入OPEN表中，置表中，置S0的深度的深度d (S0)=0， dm为任意初值。为任意初值。步步2 2 若若OPEN表为空，表为空，则考查则考查CLOSED表是否有待扩展节点：表是否有待扩展节点：

49、若无，则问题无解，退出。若无，则问题无解，退出。 若有，则取出若有，则取出CLOSED表中待扩展节点放入到表中待扩展节点放入到OPEN表表 中，令中，令 dm=dm+d。 2.2.可变界深度优先搜索算法可变界深度优先搜索算法(3)(3) 步步3 3 取取OPEN表中第一个节点表中第一个节点N放在放在CLOSED表中；并冠以编号表中；并冠以编号 n； 步步4 4 若节点若节点N为目标节点，成功退出。为目标节点，成功退出。 步步5 5 若若N的深度的深度d（N）dm（深度限制值），（深度限制值），则标则标N为待扩展节为待扩展节 点，点，则转步则转步2； 步步6 6 N无子节点，则转步无子节点，则转

50、步2； 步步7 7 扩展扩展N，将其所有子节点，将其所有子节点Ni配上指向配上指向N的指针放入的指针放入OPEN首首 部部，置，置 d(Ni) d(N)1，转步，转步2。3.3.可采纳的有界深度优先搜索算法可采纳的有界深度优先搜索算法(1)(1)问题：当问题：当d d 11 时，是否能保证找到最优解？时，是否能保证找到最优解？2021-12-31人工智能613.3.可采纳的有界深度优先搜索算法可采纳的有界深度优先搜索算法(2)(2)步步1 1 把初始结点把初始结点S0放入放入OPEN表中，置表中，置d(S0)=0，dm=dm0，G=NULL。步步2 2 若若OPEN表为空，则考察表为空，则考察

51、CLOSED表是否有待扩展结点：表是否有待扩展结点： （1 1）若无待扩展结点，则判断）若无待扩展结点，则判断G表是否为空：表是否为空： 若为空，搜索失败，退出；若为空，搜索失败，退出； 否则，取出否则，取出G表最后面的结点表最后面的结点Sg， Sg即为所求最优解，搜索成功即为所求最优解，搜索成功，退出；，退出； （2 2）若有待扩展结点，则取出）若有待扩展结点，则取出CLOSED表中待扩展结点放入到表中待扩展结点放入到OPEN表中，令表中，令dm=dm+d，转步，转步2 2；3.3.可采纳的有界深度优先搜索算法可采纳的有界深度优先搜索算法(3)(3)步步3 3 取取OPEN表中首部的结点表中

52、首部的结点N放在放在CLOSED表中；并冠以顺序表中；并冠以顺序编号编号n； 步步4 4 若若d（N）dm，则标，则标N为待扩展结点，转步为待扩展结点，转步2 2；步步5 5 若若N是目标结点是目标结点S Sg g ，则令，则令dm md（ S Sg g ）-1 ，把，把S Sg g放到放到G 表表的尾部，转步的尾部，转步2 2。步步6 6 若若N不可扩展，则转步不可扩展，则转步2 2； 步步7 7 否则，扩展否则，扩展N，将其所有子结点，将其所有子结点Ni配上指向配上指向N的返回指针放的返回指针放入入OPEN表首部，表首部， 置置d（ Ni ）d（N）1 ，转步，转步2 2。 2021-12

53、-31人工智能622.4 2.4 状态空间图的启发式搜索状态空间图的启发式搜索(1)(1)1.1.启发性知识与启发函数启发性知识与启发函数n启发性知识启发性知识 就是与被求解问题自身特性相关的知识，包括被就是与被求解问题自身特性相关的知识，包括被求解问题的解的特性、解的分布规律和在实际当中求解问题的解的特性、解的分布规律和在实际当中求解此类问题的经验、技巧等，对应于问题求解框求解此类问题的经验、技巧等，对应于问题求解框架中的架中的控制性知识控制性知识。 n启发函数启发函数 要实现启发式搜索，需要把启发性知识形式化，要实现启发式搜索，需要把启发性知识形式化，即用一定的函数表示出来，通过函数计算来

54、评价每即用一定的函数表示出来，通过函数计算来评价每种选择的价值大小，用以种选择的价值大小，用以指导搜索过程指导搜索过程，这样的函，这样的函数称为数称为启发函数启发函数。 2021-12-31人工智能632021-12-31人工智能642.4 2.4 状态空间图的启发式搜索状态空间图的启发式搜索(2)(2)2.2.启发函数的设计启发函数的设计 在实际设计过程中，在实际设计过程中，启发函数启发函数是用来估计搜索树节是用来估计搜索树节点点x与目标节点接近程度的一种函数，通常记为与目标节点接近程度的一种函数，通常记为h(x)。启启发函数可以是：发函数可以是：（1 1）一个结点到目标结点的某种距离或差异

55、的）一个结点到目标结点的某种距离或差异的量度量度；（2 2）一个结点处在最佳路径上的）一个结点处在最佳路径上的概率概率；（3 3）根据主观经验的主观）根据主观经验的主观打分打分等。等。2021-12-31人工智能652.4 2.4 状态空间图的启发式搜索状态空间图的启发式搜索(3)(3)2.4.1 2.4.1 启发式搜索算法启发式搜索算法2.4.2 2.4.2 启发式搜索的启发式搜索的A A算法和算法和A A* *算法算法2.4.32.4.3 A A* *算法在游戏中的应用算法在游戏中的应用2021-12-31人工智能662.4.1 启发式搜索算法启发式搜索算法（1 1）启发式搜索启发式搜索用

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

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

58、搜索成功，利用，则搜索成功，利用CLOSED表中的表中的返回指针找出返回指针找出S0到到N N 的路径即为所求解，退出；的路径即为所求解，退出；步步5 5 若若N N不可扩展，则转步不可扩展，则转步2 2 ；步步6 6 否则，扩展否则，扩展N，计算，计算N的每个子结点的每个子结点x的函数值，并将的函数值，并将N所有子结点所有子结点x配以指向配以指向N的返回指针后放入的返回指针后放入OPEN表中，表中，依据启发函数对结点的计算，再对依据启发函数对结点的计算，再对OPEN表中表中所有结点所有结点按按其启发函数值的大小以升序排列，转步其启发函数值的大小以升序排列，转步2 2。2021-12-31人工

59、智能682.4.1 启发式搜索算法（启发式搜索算法（4 4）2.2.局部择优搜索局部择优搜索基本思想：局部择优搜索是在启发性知识导航下的深度优基本思想：局部择优搜索是在启发性知识导航下的深度优先搜索，在先搜索，在OPEN表中保留所有已生成而未考察的结点，表中保留所有已生成而未考察的结点，对其中对其中新生成的每个子结点新生成的每个子结点x计算启发函数计算启发函数，从，从全部子结点全部子结点中选出中选出最优结点最优结点进行扩展，其选择下一个要考察结点的范进行扩展，其选择下一个要考察结点的范围是刚刚生成的全部子结点，围是刚刚生成的全部子结点，局部择优搜索算法：局部择优搜索算法： 与全局择优搜索算法的

60、区别仅在与全局择优搜索算法的区别仅在步步6 6： 步步6 6 否则，扩展否则，扩展N N，计算，计算N N的每个子结点的每个子结点x x的函数值，并将的函数值，并将N N的所有子结点的所有子结点x x配以指向结点配以指向结点N N的指针后，将的指针后，将全部子结点全部子结点按按启发函数值升序排列后放入启发函数值升序排列后放入OPEN表的首部，转步表的首部，转步2 2。2021-12-31人工智能692.4.2 启发式搜索的启发式搜索的A算法和算法和A*算法（算法（1） 启发函数是对当前结点到达目标结点未来启发函数是对当前结点到达目标结点未来可能要付出的代价的估计。可能要付出的代价的估计。 在全