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

1、第第2 2章章 基于图的知识表示与图搜索技术基于图的知识表示与图搜索技术2021-7-20人工智能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-7-20人工智能32.1 2.1 概述概述2.1.1 2.1.1 知识与问题求解框架知识与问题求解框架2.1.2 2.1.2 知识表

2、示知识表示2.1.3 2.1.3 图搜索技术图搜索技术2021-7-20人工智能42.1.1 2.1.1 知识与问题求解框架知识与问题求解框架(1)(1) 1.知识的定义知识的定义心理学心理学：个体通过与环境相互作用后获得的信息及其组织。费根鲍姆费根鲍姆：知识是经过消减、塑造、解释和转换的信息。博恩斯坦博恩斯坦（Bernstein）：知识是由特定领域的描述、关系和过程组成的。 概括地说，知识是高度组织起来的信息集团，是人们在长期的生活和社会实践中、科学研究和科学实验中积累起来的经验或对客观世界规律的认识等。2.1.1 2.1.1 知识与问题求解框架知识与问题求解框架(2)(2)2.知识的分类知

3、识的分类（1）从应用领域来划分n常识性知识n领域（专业）性知识（2）从在问题求解中的作用来划分n叙述性知识n过程性知识n控制性知识（3）从确定性来划分n确定性知识n非确定性知识（4）从知识的表现形式来划分，可分为文字、符号、声音、图形、图像等。2021-7-20人工智能52.1.1 2.1.1 知识与问题求解框架知识与问题求解框架(3)(3)3.问题求解框架问题求解框架问题：问题：是指事件或事物的已知或当前状态当前状态与目标状态目标状态之间有差异差异。问题求解：问题求解：是指在一定的控制策略下，通过通过一系列的操作操作或运算运算来改变改变问题的状态状态，使之与目标状态接近或一致。例如，李明在北

4、京，他要去西安（办事）。又如，博弈问题。问题的求解框架问题的求解框架（1）叙述性知识：叙述性知识：描述问题的状态有关的各种知识。（2）过程性知识：过程性知识：描述状态之间的变换关系的各种知识。（3）控制性知识：控制性知识：描述如何在当前状态下选择合适操作的知识。2021-7-20人工智能62021-7-20人工智能72.1.2 2.1.2 知识表示知识表示(1)(1)知识表示：知识表示：就是研究在计算机中在计算机中如何用最合适的形式表示表示问题求解过程中所需要的各种知识，包括构成问题求解框架的全部知识。常用的知识表示形式常用的知识表示形式状态空间图与或图谓词逻辑产生式框架语义网络2.1.2 2

5、.1.2 知识表示知识表示(2)(2)2021-7-20人工智能8例例2.12.1麦卡赛问题麦卡赛问题。 在一个2n2n的方格棋盘中，去掉对角的两个方格，如图（a），问能否将它全部划成若干12的小长方块？目标状态目标状态初始状态初始状态可达状态可达状态同构问题同构问题同态问题同态问题2021-7-20人工智能92.1.3 2.1.3 图搜索技术图搜索技术(1)(1)1.搜索搜索 搜索，简单地说就是“寻找”，目的是找到问题的解。在问题求解过程中，待求解的问题被抽象成一定空间上的图，搜索过程就是从图中初始节点出发，沿着与之相连的边试探着前进，寻找目标节点或可解节点的过程。2.搜索树搜索树 搜索过程

6、中经过（考察过）的节点和边，按原图的连接关系，便会构成一个树型的有向图，称为搜索树。搜索树是一个搜索过程的搜索轨迹，或称之为搜索空间。2.1.3 2.1.3 图搜索技术图搜索技术(2)(2)2021-7-20人工智能10图 2-2搜索空间示意图问题的状态空间、搜索空间及解的示意图：2.1.3 2.1.3 图搜索技术图搜索技术(3)(3)3.搜索策略搜索策略 搜索策略将决定搜索过程按照什么样的顺序考察节点和经过状态空间图的哪些节点。盲目搜索盲目搜索：无向导的搜索，也称穷举搜索。启发式搜索启发式搜索：利用“启发性信息”作为导航的搜索过程。 对于较大或无限状态空间问题，盲目搜索效率太低，所以在实际当

7、中往往是不可行的。启发式搜索广泛地应用于实际问题求解中，如博弈、机器学习、数据挖掘、智能检索等。2021-7-20人工智能112021-7-20人工智能122.2 2.2 状态空间图表示状态空间图表示2.2.1 2.2.1 状态空间图状态空间图2.2.2 2.2.2 隐式状态空间图隐式状态空间图2021-7-20人工智能132.2.1 2.2.1 状态空间图（状态空间图（1 1）1.状态状态 状态对应叙述性知识状态对应叙述性知识，描述一个问题在开始、结束或中间的某一时刻所处的状况或状态。通常引进一组变量 ，表示与问题状态相关的各种要素，并用这组变量所构成的多元组 来表示状态。 状态在状态图中表

8、示为节点节点。12nqqq， ， ，12()nqqq， ，2021-7-20人工智能142.2.1 2.2.1 状态空间图（状态空间图（2 2）2.2.操作操作 操作对应过程性知识操作对应过程性知识，即状态转换规则，描述状态之间的关系。描述一个操作要包含两个部分条件条件:指明被作用的状态要满足的约束条件动作动作:指明一个操作对状态的分量所做的改变。操作的表示形式可以是一个机械性的步骤、过程、规则或算子。操作在状态图中表示为边边。在程序中，状态转换规则可用数据对、条件语句、规则、函数、过程等表示。 如：如果室内温度低于26度，则关闭空调。 2021-7-20人工智能152.2.1 2.2.1 状

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

10、寻找操作序列的问题。n状态空间的解为三元组状态空间的解为三元组 Q nQ Qs s ：某个初始状态：某个初始状态nQ Qg g ：某个目标状态：某个目标状态na a：把：把Q Qs s变换成变换成Q Qg g的有限的操作序列的有限的操作序列n状态转换图状态转换图S1S3S2f1f2f3f4QsQgfn2021-7-20人工智能162021-7-20人工智能17例例2.2 翻转钱币问题（翻转钱币问题（1） 三枚钱币处于反、正、反状态，每次只许翻动一枚钱币，问连续翻动三次后，能否出现全正或全反状态。 初始状态Qs目标状态集合Q0, Q7例例2.2 翻转钱币问题（翻转钱币问题（2）引入一个三元组引入

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翻转一次翻转一次 问题的状态空间为问题的状态空间为 2021-7-20人工智能18例例2.2 翻转钱币问题（翻转钱币问题（4）3.状态空间图状态空间图 问题的状态空间为： 2021-7-20人工智能19 构造状态空间图： 507QabcQQ， ， ， ，aabababaabbbbcccbcccb例例2.2 翻转钱币问题（翻转钱币问题（5）2021-7-20人工智

13、能20图2-5 翻动三次后三枚钱币问题的状态变化翻转钱币问题状态空间图的另一种表示：2021-7-20人工智能21例例2.3修道士和野人问题（修道士和野人问题（1） 在河的左岸有三个修道士、三个野人和一条船，修在河的左岸有三个修道士、三个野人和一条船，修道士们想用这条船将所有的人都运过河去，但受到以下道士们想用这条船将所有的人都运过河去，但受到以下条件的限制：条件的限制： （1 1）修道士和野人都会划船，但船一次）修道士和野人都会划船，但船一次最多最多只能只能运运两个人两个人； （2 2）在任何岸边）在任何岸边野人数目野人数目都都不得超过修道士不得超过修道士，否则，否则修道士就会被野人吃掉。修

14、道士就会被野人吃掉。 假定野人会服从任何一种过河安排，试规划出一种确假定野人会服从任何一种过河安排，试规划出一种确保修道士安全过河方案。保修道士安全过河方案。2021-7-20人工智能22例例2.3修道士和野人问题（修道士和野人问题（2）1 1、问题的状态、问题的状态可以用一个三元数组来描述：可以用一个三元数组来描述： S S(m, c, b)(m, c, b) m m：左岸的修道士数：左岸的修道士数 c c：左岸的野人数：左岸的野人数 b b：左岸的船数：左岸的船数 右岸的状态不必标出，因为：右岸的状态不必标出，因为： 右岸的修道士数右岸的修道士数 m m 3 3m m 右岸的野人数右岸的野

15、人数 c c 3 3c c 右岸的船数右岸的船数 b b 1 1b b2021-7-20人工智能23例例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

16、1 1S140 1 1S222 1 0S300 1 0S72 0 1S150 0 1S232 0 0S310 0 02021-7-20人工智能24例例2.3修道士和野人问题（修道士和野人问题（4）2.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, c2

17、b=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操作符条 件动 作例例2.3修道士和野人问题（修道士和野人问题（5）3.状态空间状态空间给出状态和操作的描述之后，该问题的状态空间是：S0， P 01，P 10，P 11，P 02，P 20，Q01，Q 10，Q 11，Q 02，Q 20，S31。2021-7

18、-20人工智能26例例2.3修道士和野人问题（修道士和野人问题（6）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)q20p20S0(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.状态空间

19、图：状态空间图：四条S0到S31长度相等的最短路径，对应的操作序列就是该问题的四个最优解2021-7-20人工智能272.2.2 2.2.2 隐式状态空间图隐式状态空间图显式状态空间图：显式状态空间图：表示了问题所有可能的状态及状态之间的关系，这种表示方式称为显式状态空间显式状态空间图图，或称为状态空间图的显示表示状态空间图的显示表示。隐式状态空间图隐式状态空间图：利用有关状态描述和状态转换（操作）的知识定义的状态空间图。在计算机中仅存储描述问题状态及操作的有关知识，包括该问题的各状态分量的取值情况、分量之间的约束条件、开始状态、终止状态，以及全部操作的条件和动作等。隐式状态空间图也称为是状态

20、空间图的隐式表状态空间图的隐式表示或隐式图示或隐式图。重排九宫问题的隐式图描述为： （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 iijijXX时，例例2.42.4重排九宫问题重排九宫问题（八数码问题）（八数码问题） 例例2.42.4重排九宫问题（重排九宫问题（2 2）（2 2）有关操作的知识（规则）：）有关操作的知识（

21、规则）：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 ) ) (X(X8 8=n=n ) ) X X0 0 = n = n X X8 8 =0 =0；1 1组规则组规则 R R5 5(X(

22、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(X0 0=n=n ) ) X X8 8 = n = n X X0 0=0=0； R R2424(X(X8 8=0=0 ) ) (X(X7

23、7=n=n ) ) X X8 8 = n = n X X7 7 =0 =0；例例2.42.4重排九宫问题（重排九宫问题（3 3）八数码的状态图可表示为八数码的状态图可表示为 （SS0 0, r, r1 1 , r , r2 2 , , r , , r2424 , S , Sg g ） 八数码问题状态图仅给出了初始节点八数码问题状态图仅给出了初始节点和目标节点，其余节点需用状态转换规则和目标节点，其余节点需用状态转换规则来产生。类似于这样表示的状态图称为来产生。类似于这样表示的状态图称为隐隐式状态图式状态图，或者说，或者说状态图状态图的的隐式表示隐式表示。例例2.42.4重排九宫问题（重排九宫问

24、题（4 4）（3 3）隐式图搜索）隐式图搜索 初始状态S（ 0，1，2，3，5，6，4，7，8 ）满足条件X0 =0，故可以使用第0组的四条规则： 如果选择规则R1，则状态转换为：S1（ 2，1，0，3，5，6，4，7，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 5 7 6 1 2 3 8 8 5 7 4 62021-7-20人工智能32例例2.5 2.5 旅行商问题旅行商问题(TSP)(1)(TSP)(1) 设有n个互相可直达的城市，某推销商准备从其中的A城出发，周游各城市一遍，最后又回到A城。要求

25、为该推销商规划一条最短的旅行路线。（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)(TSP)(2)（2）操作描述）操作描述（状态转换规则）：规则规则1 ：如果=AA1Ai Aj，且| n，但A，则置= A。即没遍历完时，在城市序列中添加一个没有到过的城市。规则规则2 ：如果|= n，置= A，即从当

26、前城市返回A城。 （3 3）隐式图搜索）隐式图搜索对于有A、B、C、D四个城市所组成的连通城市网，初始状态：=A，|=1，满足规则1 ，则操作的结果为：=AB 、或=AC、或=AD，继续使用规则1 ，直到生成包含四个城市的序列出现，再使用规则2。2021-7-20人工智能33补充例补充例 二阶梵塔问题（二阶梵塔问题（1 1） 一号杆有一号杆有A A、B B两个金盘，两个金盘，A A小于小于B B。要求将。要求将A A、B B移至三号移至三号杆，每次只可移动一个盘子，任何时刻杆，每次只可移动一个盘子，任何时刻B B不能在不能在A A上。上。 （1 1）有关状态的知识：）有关状态的知识：用二元组用

27、二元组（S SA A，S SB B）表示状态，表示状态，S SA A表示表示A A所在杆号，所在杆号，S SB B表示表示B B所在杆号。其中所在杆号。其中: : S SA A ,S SB B 1,2,31,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） 。2021-7-20人工智能34AB1

28、23S0：（：（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）AAAAABABBBBB补充例补充例 二阶梵塔问题（二阶梵塔问题（2 2）2021-7-20人工智能35（2 2）有关操作的知识（规则）：）有关操作的知识（规则）： A A（i i，j j）表示金盘）表示金盘A A从第从第I I号杆移到号杆移到j j号杆，号杆，B B（i i，j j）表示金盘）表示金盘B B从第从第i i号杆移到号杆移到j j号杆，其中：号杆，

29、其中：i,j i,j 1,2,31,2,3，但，但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）分析每个操作的条件和动作，得到下表：分析每个操作的条件和动作，得到下表：补充例补充例 二阶梵塔问题（二阶梵塔问题（3 3）2021-7-20人工智能36补充例

30、补充例 二阶梵塔问题（二阶梵塔问题（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,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

31、，1 1）SB=3， SA 1,3 或或SA=2SB=1B B（3 3，2 2）SB=3， SA 2,3 或或SA=1SB=22021-7-20人工智能37补充例补充例 二阶梵塔问题（二阶梵塔问题（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-7-20人工智能382.3 状态空间图的盲目搜索状态空间图的盲目搜索n盲目搜索盲目搜索:搜索时不参考与具体待求解问题相关的任何信息，只是按预先设定的顺序逐个考察节点。盲目搜索与问题无关，具有

32、通用性。n算法中使用的数据结构算法中使用的数据结构:OPEN表表：专门登记已经生成但还没有考察的节点，即待考察节点。CLOSED表：表：用来记录考察过的节点以及节点之间的关系，如每个节点指向父节点的编号（返回指针）。CLOSED表中存放的就是一定搜索策略下的搜索树。2021-7-20人工智能39节点父节点编号编号节点父节点编号OPEN表表CLOSED表表2021-7-20人工智能402.3 状态空间图的盲目搜索状态空间图的盲目搜索2.3.1 广度优先搜索广度优先搜索2.3.2 深度优先搜索深度优先搜索2021-7-20人工智能412.3.1 广度优先搜索（广度优先搜索（1）广度优先搜索（广度优

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

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

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

36、 523八数码广度优先搜索八数码广度优先搜索1 28 5 37 4 69161 2 38 5 67 42021-7-20人工智能442.3.1 广度优先搜索广度优先搜索广度优先搜索的特点：广度优先搜索的特点：广度优先中OPEN表是一个队列，CLOSED表是一个顺序表，表中各节点按顺序编号，正被考察的节点在表中编号最大。广度优先搜索又称为宽度优先或横向搜索。广度优先策略是完备的，即如果问题的解存在，则它一定可以找到解，并且找到的解还是最优解。广度优先搜索策略与问题无关，具有通用性。缺点搜索效率低。2021-7-20人工智能452.3.2 深度优先搜索深度优先搜索(1)深度优先搜索的基本思想：深度

37、优先搜索的基本思想： 深度优先搜索是一种一直向下的搜索过程，它优先在自己的子结点集合中选择下一个被考察的结点，不断向纵深方向前进，直到到达叶子结点或受到深度限制时，才返回到上一级结点沿另一方向继续前进。深度优先搜索算法：深度优先搜索算法： 与广度优先搜索策略的唯一不同点就是OPENOPEN表表被设计成后进先出的栈后进先出的栈，新生成的子结点放在OPEN表的前面，后生成的结点优先被考察。深度优先搜索算法只需将宽将宽度优先搜索算法步度优先搜索算法步6 6修改为修改为：步步6 6 否则，扩展否则，扩展N N，将其所有子结点配上指向，将其所有子结点配上指向N N的指针的指针放入放入OPENOPEN表的

38、表的首部首部，转步，转步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 552021-7-20人工智能472.3.2 深度优先搜索深度优先搜索深度优先搜索的特点深度优先搜索的特点：OPEN表为一个堆栈。深度优先又称纵向搜索。一般不能保证找到最优解。如下图所示：图2-13 深度优先

39、搜索不具有完备性示意图2021-7-20人工智能481.1.有界深度优先搜索（有界深度优先搜索（A Acdcd ）为克服深度优先搜索的不足，可以对其深度进行为克服深度优先搜索的不足，可以对其深度进行限制限制n深度界限的选择很重要深度界限的选择很重要 d dm m 若太小，则达不到解的深度，得不到解；若太若太小，则达不到解的深度，得不到解；若太大，既浪费了计算机的存储空间与时间，又降低了搜索大，既浪费了计算机的存储空间与时间，又降低了搜索效率。由于解的路径长度事先难以预料，所以要恰当地效率。由于解的路径长度事先难以预料，所以要恰当地给出给出d dm m的值是比较困难的。的值是比较困难的。n即使能

40、求出解，它也不一定是最优解。即使能求出解，它也不一定是最优解。2.2.可变界深度优先搜索算法可变界深度优先搜索算法(1)(1) 当在dm界限之内找不到解时，可以将深度界限dm不断扩大，每次增加一个深度增量d，直到找到解，或者搜索完整棵树。这样算法的完备性得到了保证，称为可变界深度优先搜索算法(或迭代加深搜索)。 当d =1时，算法开始蜕变为广度优先搜索算法。 2.2.可变界深度优先搜索算法可变界深度优先搜索算法(2)(2)n迭代加深搜索过程：迭代加深搜索过程：步步1 把初始节点把初始节点S0放入放入OPEN表中，置表中，置S0的深度的深度d（ S0 ）0，dm为任意初值。为任意初值。步步2 若

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

42、待扩展节点，则转步则转步2； 步步6 N无子节点，则转步无子节点，则转步2； 步步7 扩展扩展N，将其所有子节点，将其所有子节点Ni配上指向配上指向N的指针放入的指针放入OPEN首部首部， 置置 d（ Ni ）d（N）1，转步，转步2。3.3.可采纳的有界深度优先搜索算法可采纳的有界深度优先搜索算法(1)(1)问题：问题：当d d 1 时， 是否能保证找到最优解？2021-7-20人工智能543.3.可采纳的有界深度优先搜索算法可采纳的有界深度优先搜索算法(2)(2)步步1 1 把初始结点把初始结点S S0 0放入放入OPENOPEN表中，置表中，置d(Sd(S0 0)=0)=0，d dm m

43、=d=dm0m0，G=NULLG=NULL。步步2 2 若若OPENOPEN表为空，则考察表为空，则考察CLOSEDCLOSED表是否有待扩展结点：表是否有待扩展结点： （1 1）若无待扩展结点，则判断）若无待扩展结点，则判断G G表是否为空：表是否为空： 若为空，搜索失败，退出；若为空，搜索失败，退出； 否则，取出否则，取出G G表最后面的结点表最后面的结点S Sg g， S Sg g即为所求最优解，搜即为所求最优解，搜索成功，退出；索成功，退出； （2 2）若有待扩展结点，则取出）若有待扩展结点，则取出CLOSEDCLOSED表中待扩展结点放入到表中待扩展结点放入到OPENOPEN表中，令

44、表中，令dm=dm+d，转步，转步2 2；3.3.可采纳的有界深度优先搜索算法可采纳的有界深度优先搜索算法(3)(3)步步3 3 取取OPENOPEN表中首部的结点表中首部的结点N N放在放在CLOSEDCLOSED表中；并冠以顺序编号表中；并冠以顺序编号n n； 步步4 4 若若d（N N）dm m，则标，则标N N为待扩展结点，转步为待扩展结点，转步2 2；步步5 5 若若N N是目标结点是目标结点S Sg g ，则令，则令dm md（ S Sg g ）-1 ，把，把S Sg g放到放到G G 表的尾表的尾部，转步部，转步2 2。步步6 6 若若N N不可扩展，则转步不可扩展，则转步2 2

45、； 步步7 7 否则，扩展否则，扩展N N，将其所有子结点，将其所有子结点N Ni i配上指向配上指向N N的返回指针放入的返回指针放入OPENOPEN表首部，表首部， 置置d（ Ni ）d（N）1 ，转步，转步2 2。 2021-7-20人工智能552.4 2.4 状态空间图的启发式搜索状态空间图的启发式搜索(1)(1)1.启发性知识与启发函数启发性知识与启发函数启发性知识启发性知识 就是与被求解问题自身特性相关的知识，包括被求解问题的解的特性、解的分布规律和在实际当中求解此类问题的经验、技巧等，对应于问题求解框架中的控制性知识。 启发函数启发函数 要实现启发式搜索，需要把启发性知识形式化，

46、即用一定的函数表示出来，通过函数计算来评价每种选择的价值大小，用以指导搜索过程，这样的函数称为启发函数。 2021-7-20人工智能562021-7-20人工智能572.4 2.4 状态空间图的启发式搜索状态空间图的启发式搜索(2)(2)2.启发函数的设计启发函数的设计 在实际设计过程中，启发函数是用来估计搜索树节点x与目标节点接近程度的一种函数，通常记为h（x）。启发函数可以是：（1）一个结点到目标结点的某种距离或差异的量度；（2）一个结点处在最佳路径上的概率；（3）根据主观经验的主观打分等。2021-7-20人工智能582.4 2.4 状态空间图的启发式搜索状态空间图的启发式搜索(3)(3

47、)2.4.1 启发式搜索算法启发式搜索算法2.4.2 启发式搜索的启发式搜索的A算法和算法和A*算法算法2.4.3 A*算法在游戏中的应用算法在游戏中的应用2021-7-20人工智能592.4.1 启发式搜索算法启发式搜索算法（1 1）启发式搜索启发式搜索用启发函数来导航，其搜索算法就要在状态图一般搜索算法基础上再增加启发函数值的计算与传播过程，并且由启发函数值来确定节点的扩展顺序。按选择范围不同，启发式搜索分为按选择范围不同，启发式搜索分为：全局择优搜索全局择优搜索局部择优搜索局部择优搜索2021-7-20人工智能602.4.1 启发式搜索算法启发式搜索算法（2 2）1.全局择优搜索全局择优

48、搜索基本思想：基本思想：在OPEN表中保留所有已生成而未考察的节点，并用启发函数h(x)对它们全部进行估价，从中选出最优节点进行扩展，而不管这个节点出现在搜索树的什么地方。2.4.1 启发式搜索算法启发式搜索算法（3 3）全局择优搜索算法：全局择优搜索算法：步步1 1 把初始结点把初始结点S S0 0放入放入OPENOPEN表中，计算表中，计算h(Sh(S0 0) )；步步2 2 若若OPENOPEN表为空，则搜索失败，退出；表为空，则搜索失败，退出；步步3 3 否则，移出否则，移出OPENOPEN表中第一个结点表中第一个结点N N放入放入CLOSEDCLOSED表中，表中，并冠以序号并冠以序

49、号n n ；步步4 4 若目标结点若目标结点Sg Sg N N，则搜索成功，利用，则搜索成功，利用CLOSEDCLOSED表中表中的返回指针找出的返回指针找出S S0 0到到N N的路径即为所求解，退出；的路径即为所求解，退出；步步5 5 若若N N不可扩展，则转步不可扩展，则转步2 2 ；步步6 6 否则，扩展否则，扩展N N，计算，计算N N的每个子结点的每个子结点x x的函数值，并将的函数值，并将N N所有子结点所有子结点x x配以指向配以指向N N的返回指针后放入的返回指针后放入OPENOPEN表中表中，依据启发函数对结点的计算，再对，依据启发函数对结点的计算，再对OPENOPEN表中

50、表中所有结所有结点点按其启发函数值的大小以升序排列，转步按其启发函数值的大小以升序排列，转步2 2。2021-7-20人工智能612.4.1 启发式搜索算法启发式搜索算法（4 4）2.局部择优搜索局部择优搜索基本思想：基本思想：局部择优搜索是在启发性知识导航下的深度优先搜索，在OPEN表中保留所有已生成而未考察的结点，对其中新生成的每个子结点x计算启发函数，从全部子结点中选出最优结点进行扩展，其选择下一个要考察结点的范围是刚刚生成的全部子结点，局部择优搜索算法：局部择优搜索算法： 与全局择优搜索算法的区别仅在步步6： 步步6 6 否则，扩展否则，扩展N N，计算，计算N N的每个子结点的每个子

51、结点x x的函数值，并将的函数值，并将N N的所有子结点的所有子结点x x配以指向结点配以指向结点N N的指针后，将的指针后，将全部子结点全部子结点按按启发函数值升序排列后放入启发函数值升序排列后放入OPENOPEN表的首部，转步表的首部，转步2 2。2021-7-20人工智能622.4.2 启发式搜索的启发式搜索的A算法和算法和A*算法（算法（1） 启发函数是对当前结点到达目标结点未来可能要付出的代价的估计。 在全局择优和局部择优搜索算法中，都没有考虑从初始结点到当前结点已经付出的实际代价。 在很多实际问题中，已经付出的实际代价是必须考虑的，如TSP问题等。将两者同时考虑，用于指导搜索的算法

52、称为A算法和算法和A*算法算法。2021-7-20人工智能642.4.2 启发式搜索的启发式搜索的A算法和算法和A*算法（算法（2）1. 1. A算法算法估价函数估价函数f（x） : :为了防止在单独利用启发函数的时候误入歧途，将启发函数h（x）与代价函数g（x）相结合，即初始节点S0到达节点x处已付出的代价与节点x 到达目标节点Sg的接近程度估计值总和。 f（x） g（x）h（x） g（x）代价函数）代价函数：初始节点S0到达节点x处已付出的代价，有利于搜索纵向发展，提高搜索效率，但影响完备性。 h（x）启发函数）启发函数：节点x 到达目标节点Sg的接近程度估计值有利于搜索横向发展，提高搜索

53、的完备性，但影响搜索效率。2.4.2 启发式搜索的启发式搜索的A算法和算法和A*算法（算法（3）代价代价g（x）的计算的计算 g（x）表示从初始节点S0到节点x的代价： g（ S0 0 ）0 0 g（ xj j ）g（ xi i ） c（xi i，xj j） 其中，其中，c（xi i，xj j）表示父节点xi到子节点xj的代价ADCEB464332323462344632C1B1D1D2E1C2E2D3C3B2E4E36B32021-7-20人工智能652.4.2 启发式搜索的启发式搜索的A算法和算法和A*算法（算法（4）对估价函数 f（x） g（x）h（x） 令其中的h（x）=0=0时，这时

54、得到的是代价树代价树的非启发式搜索算法非启发式搜索算法。按对节点的考察范围不同，可分为两种搜索策略：n分支界限法分支界限法将全局择优搜索算法中的h（x）替换为g（x） ，即可得到分支界限搜索算法。n瞎子爬山法瞎子爬山法将局部择优搜索算法中的h（x）替换为g（x） ，即可得到瞎子爬山搜索算法。2021-7-20人工智能662021-7-20人工智能672.4.2 启发式搜索的启发式搜索的A算法和算法和A*算法（算法（5）步步1 1 把附有把附有f（ S0 0 ）的初始结点的初始结点S0 0放入放入OPEN表中；表中；步步2 2 若若OPEN表为空，则搜索失败，退出；表为空，则搜索失败，退出；步步

55、3 3 否则，移出否则，移出OPEN表中第一个结点表中第一个结点N放入放入CLOSED表中，并冠以顺序编号表中，并冠以顺序编号n；步步4 4 若目标结点若目标结点Sg gN，则搜索成功，利用，则搜索成功，利用CLOSED表表中的返回指针找出中的返回指针找出S0 0到到N的路径即为所求解，退出。的路径即为所求解，退出。步步5 5 若若N不可扩展，则转步不可扩展，则转步2 2；2.4.2 启发式搜索的启发式搜索的A算法和算法和A*算法（算法（6）步步6 6 否则，扩展否则，扩展N，生成一组子结点，生成一组子结点xi i，计算，计算f（ xi i ） ，并对这组结点并对这组结点xi作如下处理：作如下

56、处理： 1 1）若）若xi是是N的的先辈结点先辈结点，则，则删除删除之。之。 2 2）若）若xi存在于存在于OPEN或或CLOSED表中，也表中，也删除删除之，但表之，但表明此时存在两条初始结点明此时存在两条初始结点S0 0到到xi的路径；如果的路径；如果新路径新路径较较短短，则，则修改修改xi i结点的结点的返回指针返回指针（指向（指向N），并修改），并修改x xi i及及其后裔结点和其后裔结点和f值；同时若值；同时若xi存在存在于于CLOSED表中，则表中，则将其将其移出放入移出放入OPEN表表重新考察重新考察。 3 3）对其余子结点配上指向）对其余子结点配上指向N的返回指针放入的返回指针

57、放入OPEN表。表。步步7 7 对对OPEN表中所有结点按表中所有结点按f值以升序排列，转步值以升序排列，转步2 2。2021-7-20人工智能682021-7-20人工智能692.4.2 启发式搜索的启发式搜索的A算法和算法和A*算法（算法（7）对步步6 6的1）的说明：2.4.2 启发式搜索的启发式搜索的A算法和算法和A*算法（算法（8）对步6的 2）的说明：2021-7-20人工智能702.4.2 启发式搜索的启发式搜索的A算法和算法和A*算法（算法（9）n树式搜索例树式搜索例n对于对于已存在于已存在于OPENOPEN表中的节点表中的节点（如果有的话）也删除之；删（如果有的话）也删除之；

58、删除之前要比较其返回初始节点的新路径与原路径，如果新路除之前要比较其返回初始节点的新路径与原路径，如果新路径短，则修改这些节点在径短，则修改这些节点在OPENOPEN表中的原返回指针，使其沿原表中的原返回指针，使其沿原路径返回。路径返回。Path1Path2S0mnP先扩展后扩展P P在在n n之前已是某一节点之前已是某一节点m m的后继的后继如图所示：说明从如图所示：说明从S S0 0PP至至少有两条路，这时有两少有两条路，这时有两种情况：种情况：f f（Path2Path2） f(3,3,3)(1,1,1)=(3,3,3)(1,1,1)=(1,1,3)(1,1,1)=(1,1,3)(1,2

59、,3)=(1,2,2)(1,2,3)=(1,2,2) (3,2,2)=(3,2,1)(3,2,2)=(3,2,1)(3,3,1)=(3,3,3)(3,3,1)=(3,3,3)(1,1,3)=(1,2,3)(1,1,3)=(1,2,3)(3,2,1)=(3,3,1)(3,2,1)=(3,3,1)(1,1,1)=(1,2,2)(1,1,1)=(1,2,2)(1,2,2)=(3,2,2)(1,2,2)=(3,2,2)(3,2,2)=(3,3,3)(3,2,2)=(3,3,3)三阶梵塔问题的与或树三阶梵塔问题的与或树2021-7-20人工智能1042.5.1 与或图表示（与或图表示（7）与或图的几个概

60、念：与或图的几个概念：n直接可解的问题称为本原问题。n本原问题对应的节点称为终止节点。n无子节点的节点称为端节点。n子节点为与关系，则该节点为与节点。n子节点为或关系，则该节点为或节点。 与或图一般表示问题的变换过程，就是从原问题出发，运用某些规则不断的进行问题的分解（得到与分支）和变换（得到或分支），而得到一个与或图，与或图的节点一般代表问题，整个图就表示问题空间。2021-7-20人工智能1052.5.1 与或图表示（与或图表示（8）与或图也可以用三元组表示：与或图也可以用三元组表示： （Q Q0 0 , F , Q , F , Qn n） Q Q0 0表示初始问题表示初始问题 F F表示