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

第2章基于图的知识表示与图搜索技术2023/2/5人工智能2第2章基于图的知识表示与图搜索技术2.1概述2.2状态空间图表示2.3状态空间图的盲目搜索2.4状态空间图的启发式搜索2.5与或图表示及搜索技术2.6博弈树及搜索技术2023/2/5人工智能32.1概述2.1.1知识与问题求解框架2.1.2知识表示2.1.3图搜索技术2023/2/5人工智能42.1.1知识与问题求解框架(1)1.知识的定义心理学：个体通过与环境相互作用后获得的信息及其组织。费根鲍姆：知识是经过消减、塑造、解释和转换的信息。博恩斯坦（Bernstein）：知识是由特定领域的描述、关系和过程组成的。概括地说，知识是高度组织起来的信息集团，是人们在长期的生活和社会实践中、科学研究和科学实验中积累起来的经验或对客观世界规律的认识等。2.1.1知识与问题求解框架(2)2.知识的分类（1）从应用领域来划分常识性知识领域（专业）性知识（2）从在问题求解中的作用来划分叙述性知识过程性知识控制性知识（3）从确定性来划分确定性知识非确定性知识（4）从知识的表现形式来划分，可分为文字、符号、声音、图形、图像等。2023/2/5人工智能52.1.1知识与问题求解框架(3)3.问题求解框架问题：是指事件或事物的已知或当前状态与目标状态之间有差异。问题求解：是指在一定的控制策略下，通过一系列的操作或运算来改变问题的状态，使之与目标状态接近或一致。例如，李明在北京，他要去西安（办事）。又如，博弈问题。问题的求解框架（1）叙述性知识：描述问题的状态有关的各种知识。（2）过程性知识：描述状态之间的变换关系的各种知识。（3）控制性知识：描述如何在当前状态下选择合适操作的知识。2023/2/5人工智能62023/2/5人工智能72.1.2知识表示(1)知识表示：就是研究在计算机中如何用最合适的形式表示问题求解过程中所需要的各种知识，包括构成问题求解框架的全部知识。常用的知识表示形式状态空间图与或图谓词逻辑产生式框架语义网络……2.1.2知识表示(2)2023/2/5人工智能8例2.1麦卡赛问题。在一个2n2n的方格棋盘中，去掉对角的两个方格，如图（a），问能否将它全部划成若干12的小长方块？目标状态初始状态可达状态同构问题同态问题2023/2/5人工智能92.1.3图搜索技术(1)1.搜索搜索，简单地说就是“寻找”，目的是找到问题的解。在问题求解过程中，待求解的问题被抽象成一定空间上的图，搜索过程就是从图中初始节点出发，沿着与之相连的边试探着前进，寻找目标节点或可解节点的过程。2.搜索树搜索过程中经过（考察过）的节点和边，按原图的连接关系，便会构成一个树型的有向图，称为搜索树。搜索树是一个搜索过程的搜索轨迹，或称之为搜索空间。2.1.3图搜索技术(2)2023/2/5人工智能10图2-2搜索空间示意图问题的状态空间、搜索空间及解的示意图：2.1.3图搜索技术(3)3.搜索策略搜索策略将决定搜索过程按照什么样的顺序考察节点和经过状态空间图的哪些节点。盲目搜索：无向导的搜索，也称穷举搜索。启发式搜索：利用“启发性信息”作为导航的搜索过程。对于较大或无限状态空间问题，盲目搜索效率太低，所以在实际当中往往是不可行的。启发式搜索广泛地应用于实际问题求解中，如博弈、机器学习、数据挖掘、智能检索等。2023/2/5人工智能112023/2/5人工智能122.2状态空间图表示2.2.1状态空间图2.2.2隐式状态空间图2023/2/5人工智能132.2.1状态空间图（1）1.状态

状态对应叙述性知识，描述一个问题在开始、结束或中间的某一时刻所处的状况或状态。通常引进一组变量，表示与问题状态相关的各种要素，并用这组变量所构成的多元组来表示状态。状态在状态图中表示为节点。2023/2/5人工智能142.2.1状态空间图（2）2.操作

操作对应过程性知识，即状态转换规则，描述状态之间的关系。描述一个操作要包含两个部分条件:指明被作用的状态要满足的约束条件动作:指明一个操作对状态的分量所做的改变。操作的表示形式可以是一个机械性的步骤、过程、规则或算子。操作在状态图中表示为边。在程序中，状态转换规则可用数据对、条件语句、规则、函数、过程等表示。如：如果室内温度低于26度，则关闭空调。2023/2/5人工智能152.2.1状态空间图（3）3.状态空间图问题的状态空间图是一个描述该问题全部可能的状态及相互关系的图，如考虑操作的代价，状态空间图就是一个赋值有向图。状态空间常记为三元组：

S：初始状态的集合

F：操作的集合

G：目标状态的集合。由问题的状态空间表示就可以构造出状态空间图。2.2.1状态空间图（4）4.求解在状态空间表示法中，问题求解过程转化为在图中寻找从初始状态Qs出发到达目标状态Qg的路径问题，也就是寻找操作序列的问题。状态空间的解为三元组<Qs,a,Qg>Qs：某个初始状态Qg：某个目标状态a：把Qs变换成Qg的有限的操作序列状态转换图S1S3S2…f1f2f3f4QsQgfn2023/2/5人工智能162023/2/5人工智能17例2.2翻转钱币问题（1）三枚钱币处于反、正、反状态，每次只许翻动一枚钱币，问连续翻动三次后，能否出现全正或全反状态。初始状态Qs目标状态集合{Q0,Q7}例2.2翻转钱币问题（2）引入一个三元组(q0,q1,q2)来描述总状态，钱币正面为0，反面为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)。翻动钱币的操作抽象为改变上述状态的算子，即F＝{a,b,c}a:把钱币q0翻转一次

b:把钱币q1翻转一次

c:把钱币q2翻转一次问题的状态空间为<{Q5},{a,b,c}，{Q0Q7}>2023/2/5人工智能18例2.2翻转钱币问题（4）3.状态空间图问题的状态空间为：2023/2/5人工智能19构造状态空间图：

aabababaabbbbcccbcccb2023/2/5人工智能20例2.3修道士和野人问题（1）

在河的左岸有三个修道士、三个野人和一条船，修道士们想用这条船将所有的人都运过河去，但受到以下条件的限制：（1）修道士和野人都会划船，但船一次最多只能运两个人；（2）在任何岸边野人数目都不得超过修道士，否则修道士就会被野人吃掉。假定野人会服从任何一种过河安排，试规划出一种确保修道士安全过河方案。2023/2/5人工智能21例2.3修道士和野人问题（2）1、问题的状态可以用一个三元数组来描述：

S＝(m,c,b)

m：左岸的修道士数c：左岸的野人数b：左岸的船数右岸的状态不必标出，因为：

右岸的修道士数m’＝3－m右岸的野人数c’＝3－c右岸的船数b’＝1－b2023/2/5人工智能22例2.3修道士和野人问题（3）状态m,c,b状态m,c,b状态m,c,b状态m,c,bS0331S8131S16330S24130S1321S9121S17320S25120S2311S10111S18310S26110S3301S11101S19300S27100S4231S12031S20230S28

030S5221S13021S21220S29020S6211S14011S22210S30010S7201S15001S23200S310002023/2/5人工智能23例2.3修道士和野人问题（4）2.操作集F＝{p01,p10,p11,p02,p20,q01,q10,q11,q02,q20}q20b=0,(m=0,c=2)或(m=1,c=1)b=1,m=m+2q02b=0,m=0或3,c≤2b=1,c=c+2q11b=0,m=c,c≤2b=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,c≤2b=1,c=c+1p20b=1,(m=3,c=1)或(m=2,c=2)b=0,m=m-2p02b=1,m=0或3,c≥2b=0,c=c-2p11b=1,m=c,c≥1b=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,c≥1b=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}}。2023/2/5人工智能25例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)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.状态空间图：四条S0到S31长度相等的最短路径，对应的操作序列就是该问题的四个最优解2023/2/5人工智能262.2.2隐式状态空间图显式状态空间图：表示了问题所有可能的状态及状态之间的关系，这种表示方式称为显式状态空间图，或称为状态空间图的显示表示。隐式状态空间图：利用有关状态描述和状态转换（操作）的知识定义的状态空间图。在计算机中仅存储描述问题状态及操作的有关知识，包括该问题的各状态分量的取值情况、分量之间的约束条件、开始状态、终止状态，以及全部操作的条件和动作等。隐式状态空间图也称为是状态空间图的隐式表示或隐式图。重排九宫问题的隐式图描述为：（1）有关状态的知识：状态S的定义：S＝(X0，X1，X2，X3，X4

，X5，X6

，X7，X8)其中，Xi｛0，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）重排九宫问题的状态表示例2.4重排九宫问题（八数码问题）

例2.4重排九宫问题（2）（2）有关操作的知识（规则）：0组规则

R1(X0=0

)(X2=n

)X0=nX2=0；R2(X0=0

)(X4=n

)X0=nX4=0；R3(X0=0

)(X6=n

)X0=nX6=0；R4(X0=0

)(X8=n

)X0=nX8=0；1组规则

R5(X1=0

)(X2=n

)X1=nX2=0；R6(X1=0

)(X8=n

)X1=nX8=0；8组规则:

R22(X8=0

)(X1=n

)X8=nX1=0；R23(X8=0

)(X0=n

)X8=nX0=0；R24(X8=0

)(X7=n

)X8=nX7=0；……例2.4重排九宫问题（3）八数码的状态图可表示为（{S0},{r1,r2,…,r24},{Sg}）八数码问题状态图仅给出了初始节点和目标节点，其余节点需用状态转换规则来产生。类似于这样表示的状态图称为隐式状态图，或者说状态图的隐式表示。例2.4重排九宫问题（4）（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)2023/2/5人工智能31例2.5旅行商问题(TSP)(1)设有n个互相可直达的城市，某推销商准备从其中的A城出发，周游各城市一遍，最后又回到A城。要求为该推销商规划一条最短的旅行路线。（1）状态描述：该问题的状态为以A打头城市序列：

=AA1…Ai…Aj…A’其中：A、Ai、Aj、A’为城市名，1i、jn-1，AjA，AiA；

1||n+1；当i

j时，AiAj；当且仅当||=n+1时，A’=A。初始状态：=A，||=1终止状态：=AA1A2…A，||=n+1例2.5旅行商问题(TSP)(2)（2）操作描述（状态转换规则）：规则1：如果=AA1…Ai…Aj…，且||

n，但A’，则置=A。即没遍历完时，在城市序列中添加一个没有到过的城市。规则2：如果||=n，置=

A，即从当前城市返回A城。

（3）隐式图搜索对于有A、B、C、D四个城市所组成的连通城市网，初始状态：=A，||=1，满足规则1，则操作的结果为：=AB、或=AC、或=AD，继续使用规则1，直到生成包含四个城市的序列出现，再使用规则2。2023/2/5人工智能32补充例二阶梵塔问题（1）

有三个杆，一号杆有A、B两个金盘，A小于B。要求将A、B移至三号杆，每次只可移动一个盘子，任何时刻B不能在A上。（1）有关状态的知识：用二元组（SA，SB）表示状态，SA表示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）。2023/2/5人工智能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：（3，1）AAAAABABBBBB补充例二阶梵塔问题（2）2023/2/5人工智能34（2）有关操作的知识（规则）：A（i，j）表示金盘A从第i号杆移到j号杆，B（i，j）表示金盘B从第i号杆移到j号杆，其中：i,j{1,2,3}，但ij，全部操作为：

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），B（3，2）分析每个操作的条件和动作，得到下表：补充例二阶梵塔问题（3）2023/2/5人工智能35补充例二阶梵塔问题（4）操作符条件动作A（1，2）SA=1SA=2A（1，3）SA=1SA=3A（2，1）SA=2SA=1A（2，3）SA=2SA=3A（3，1）SA=3SA=1A（3，2）SA=3SA=2B（1，2）SB=1，SA1,2或SA=3SB=2B（1，3）SB=1，SA1,3或SA=2SB=3B（2，1）SB=2，SA1,2或SA=3SB=1B（2，3）SB=2，SA2,3或SA=1SB=3B（3，1）SB=3，SA1,3或SA=2SB=1B（3，2）SB=3，SA2,3或SA=1SB=22023/2/5人工智能36补充例二阶梵塔问题（5）（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)2023/2/5人工智能372.3状态空间图的盲目搜索盲目搜索:搜索时不参考与具体待求解问题相关的任何信息，只是按预先设定的顺序逐个考察节点。盲目搜索与问题无关，具有通用性。算法中使用的数据结构:OPEN表：专门登记已经生成但还没有考察的节点，即待考察节点。CLOSED表：用来记录考察过的节点以及节点之间的关系，如每个节点指向父节点的编号（返回指针）。CLOSED表中存放的就是一定搜索策略下的搜索树。2023/2/5人工智能38节点父节点编号编号节点父节点编号OPEN表CLOSED表2023/2/5人工智能392.3状态空间图的盲目搜索2.3.1广度优先搜索2.3.2深度优先搜索2023/2/5人工智能402.3.1广度优先搜索（1）广度优先搜索（A٭ed）基本思想：广度优先搜索是严格按节点在树中的出现位置一层一层向下的搜索过程。通过将OPEN表设计为一个队列来实现，将新生成的子节点放在OPEN表的后面，保证先生成的节点先考察。广度优先搜索算法：步1把初始节点S0放入OPEN表中；步2若OPEN表为空，则搜索失败，退出；步3否则，取OPEN表中第一个节点N放在CLOSED表中；并冠以顺序编号n；步4若节点N为目标节点，则搜索成功。利用CLOSED表中的返回指针找出S0到N的路径即为所求解，退出；步5若N不可扩展，转步2；步6

否则，扩展N，将其所有子节点配上指向N的返回指针放入OPEN表的尾部，转步2。2.3.1广度优先搜索（2）2023/2/5人工智能42例2.6使用广度优先搜索算法求解重排九宫问题1238574611238567481382574610123845767123845766138257461112384576212385746312384576412378546122318574613123847651412345876151285374617135827461881325746191237854620231857462112843765221238574651238476523八数码广度优先搜索12853746916123856742023/2/5人工智能432.3.1广度优先搜索广度优先搜索的特点：广度优先中OPEN表是一个队列，CLOSED表是一个顺序表，表中各节点按顺序编号，正被考察的节点在表中编号最大。广度优先搜索又称为宽度优先或横向搜索。广度优先策略是完备的，即如果问题的解存在，则它一定可以找到解，并且找到的解还是最优解。广度优先搜索策略与问题无关，具有通用性。缺点搜索效率低。2023/2/5人工智能442.3.2深度优先搜索(1)深度优先搜索的基本思想：

深度优先搜索是一种一直向下的搜索过程，它优先在自己的子节点集合中选择下一个被考察的节点，不断向纵深方向前进，直到到达叶子节点或受到深度限制时，才返回到上一级节点沿另一方向继续前进。深度优先搜索算法：

与广度优先搜索策略的唯一不同点就是OPEN表被设计成后进先出的栈，新生成的子节点放在OPEN表的前面，后生成的节点优先被考察。深度优先搜索算法只需将宽度优先搜索算法步6修改为：步6否则，扩展N，将其所有子节点配上指向N的指针放入OPEN表的首部，转步2。

例2.7使用深度优先搜索算法求解重排九宫问题

12385746112384576312384576

123845761238574612384576123847654128437651238574621238476552023/2/5人工智能462.3.2深度优先搜索深度优先搜索的特点：OPEN表为一个堆栈。深度优先又称纵向搜索。一般不能保证找到最优解。如下图所示：图2-13深度优先搜索不具有完备性示意图2023/2/5人工智能471.有界深度优先搜索（Acd）为克服深度优先搜索的不足，可以对其深度进行限制深度界限的选择很重要

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

=1时，算法开始蜕变为广度优先搜索算法。

2.可变界深度优先搜索算法(2)迭代加深搜索过程：步1把初始节点S0放入OPEN表中，置S0的深度d（S0）＝0，dm为任意初值。步2若OPEN表为空，则考查CLOSED表是否有待扩展节点：

①若无，则问题无解，退出。②若有，则取出CLOSED表中待扩展节点放入到OPEN表中，令dm=dm+⊿d。

2.可变界深度优先搜索算法(3)

步3取OPEN表中第一个节点N放在CLOSED表中；并冠以编号n；步4若节点N为目标节点，成功退出。步5若N的深度d（N）＞dm（深度限制值），则标N为待扩展节点，则转步2；

步6N无子节点，则转步2；步7扩展N，将其所有子节点Ni配上指向N的指针放入OPEN首部，置d（Ni）＝d（N）＋1，转步2。3.可采纳的有界深度优先搜索算法(1)问题：当⊿d

>1时，是否能保证找到最优解？2023/2/5人工智能533.可采纳的有界深度优先搜索算法(2)步1把初始节点S0放入OPEN表中，置d(S0)=0，dm=dm0，G=NULL。步2若OPEN表为空，则考察CLOSED表是否有待扩展节点：（1）若无待扩展节点，则判断G表是否为空：若为空，搜索失败，退出；否则，取出G表最后面的节点Sg，Sg即为所求最优解，搜索成功，退出；（2）若有待扩展节点，则取出CLOSED表中待扩展节点放入到OPEN表中，令dm=dm+⊿d，转步2；3.可采纳的有界深度优先搜索算法(3)步3取OPEN表中首部的节点N放在CLOSED表中；并冠以顺序编号n；步4若d（N）＞dm，则标N为待扩展节点，转步2；步5若N是目标节点Sg，则令dm＝d（Sg

）-1，把Sg放到G表的尾部，转步2。步6若N不可扩展，则转步2；步7否则，扩展N，将其所有子节点Ni配上指向N的返回指针放入OPEN表首部，置d（Ni）＝d（N）＋1，转步2。

2023/2/5人工智能542.4状态空间图的启发式搜索(1)1.启发性知识与启发函数启发性知识就是与被求解问题自身特性相关的知识，包括被求解问题的解的特性、解的分布规律和在实际当中求解此类问题的经验、技巧等，对应于问题求解框架中的控制性知识。启发函数要实现启发式搜索，需要把启发性知识形式化，即用一定的函数表示出来，通过函数计算来评价每种选择的价值大小，用以指导搜索过程，这样的函数称为启发函数。2023/2/5人工智能552023/2/5人工智能562.4状态空间图的启发式搜索(2)2.启发函数的设计在实际设计过程中，启发函数是用来估计搜索树节点x与目标节点接近程度的一种函数，通常记为h（x）。启发函数可以是：（1）一个节点到目标节点的某种距离或差异的量度；（2）一个节点处在最佳路径上的概率；（3）根据主观经验的主观打分等。2023/2/5人工智能572.4状态空间图的启发式搜索(3)2.4.1启发式搜索算法2.4.2启发式搜索的A算法和A*算法2.4.3

A*算法在游戏中的应用2023/2/5人工智能582.4.1启发式搜索算法（1）启发式搜索用启发函数来导航，其搜索算法就要在状态图一般搜索算法基础上再增加启发函数值的计算与传播过程，并且由启发函数值来确定节点的扩展顺序。按选择范围不同，启发式搜索分为：全局择优搜索局部择优搜索2023/2/5人工智能592.4.1启发式搜索算法（2）1.全局择优搜索基本思想：在OPEN表中保留所有已生成而未考察的节点，并用启发函数h(x)对它们全部进行估价，从中选出最优节点进行扩展，而不管这个节点出现在搜索树的什么地方。2.4.1启发式搜索算法（3）全局择优搜索算法：步1把初始节点S0放入OPEN表中，计算h(S0)；步2若OPEN表为空，则搜索失败，退出；步3否则，移出OPEN表中第一个节点N放入CLOSED表中，并冠以序号n；步4若目标节点Sg＝N，则搜索成功，利用CLOSED表中的返回指针找出S0到N的路径即为所求解，退出；步5若N不可扩展，则转步2；步6否则，扩展N，计算N的每个子节点x的函数值，并将N所有子节点x配以指向N的返回指针后放入OPEN表中，依据启发函数对节点的计算，再对OPEN表中所有节点按其启发函数值的大小以升序排列，转步2。2023/2/5人工智能602.4.1启发式搜索算法（4）2.局部择优搜索基本思想：局部择优搜索是在启发性知识导航下的深度优先搜索，在OPEN表中保留所有已生成而未考察的节点，对其中新生成的每个子节点x计算启发函数，从全部子节点中选出最优节点进行扩展，其选择下一个要考察节点的范围是刚刚生成的全部子节点，局部择优搜索算法：与全局择优搜索算法的区别仅在步6：步6否则，扩展N，计算N的每个子节点x的函数值，并将N的所有子节点x配以指向节点N的指针后，将全部子节点按启发函数值升序排列后放入OPEN表的首部，转步2。2023/2/5人工智能612.4.2启发式搜索的A算法和A*算法（1）启发函数是对当前节点到达目标节点未来可能要付出的代价的估计。在全局择优和局部择优搜索算法中，都没有考虑从初始节点到当前节点已经付出的实际代价。在很多实际问题中，已经付出的实际代价是必须考虑的，如TSP问题等。将两者同时考虑，用于指导搜索的算法称为A算法和A*算法。2023/2/5人工智能632.4.2启发式搜索的A算法和A*算法（2）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的接近程度估计值有利于搜索横向发展，提高搜索的完备性，但影响搜索效率。2.4.2启发式搜索的A算法和A*算法（3）代价g（x）的计算

g（x）表示从初始节点S0到节点x的代价：

g（S0）＝0

g（xj）＝g（xi）＋c（xi，xj）其中，c（xi，xj）表示父节点xi到子节点xj的代价ADCEB464332323462344632C1B1D1D2E1C2E2D3C3B2E4E36B32023/2/5人工智能642.4.2启发式搜索的A算法和A*算法（4）对估价函数

f（x）＝g（x）＋h（x）

令其中的h（x）=0时，这时得到的是代价树的非启发式搜索算法。按对节点的考察范围不同，可分为两种搜索策略：分支界限法将全局择优搜索算法中的h（x）替换为g（x），即可得到分支界限搜索算法。瞎子爬山法将局部择优搜索算法中的h（x）替换为g（x），即可得到瞎子爬山搜索算法。2023/2/5人工智能652023/2/5人工智能662.4.2启发式搜索的A算法和A*算法（5）步1把附有f（S0

）的初始节点S0放入OPEN表中；步2若OPEN表为空，则搜索失败，退出；步3否则，移出OPEN表中第一个节点N放入CLOSED表中，并冠以顺序编号n；步4若目标节点Sg＝N，则搜索成功，利用CLOSED表中的返回指针找出S0到N的路径即为所求解，退出。步5若N不可扩展，则转步2；2.4.2启发式搜索的A算法和A*算法（6）步6否则，扩展N，生成一组子节点xi，计算f（xi

），并对这组节点xi作如下处理：1）若xi是N的先辈节点，则删除之。2）若xi存在于OPEN或CLOSED表中，也删除之，但表明此时存在两条初始节点S0到xi的路径；如果新路径较短，则修改xi节点的返回指针（指向N），并修改xi及其后裔节点和f值；同时若xi存在于CLOSED表中，则将其移出放入OPEN表重新考察。3）对其余子节点配上指向N的返回指针放入OPEN表。步7对OPEN表中所有节点按f值以升序排列，转步2。2023/2/5人工智能672023/2/5人工智能682.4.2启发式搜索的A算法和A*算法（7）对步6的1）的说明：2.4.2启发式搜索的A算法和A*算法（8）对步6的2）的说明：2023/2/5人工智能692.4.2启发式搜索的A算法和A*算法（9）树式搜索例对于已存在于OPEN表中的节点（如果有的话）也删除之；删除之前要比较其返回初始节点的新路径与原路径，如果新路径短，则修改这些节点在OPEN表中的原返回指针，使其沿原路径返回。Path1Path2S0mnP先扩展后扩展P在n之前已是某一节点m的后继如图所示：说明从S0→P至少有两条路，这时有两种情况：f（Path2）<f（Path1），当前路径较好，要修改P的指针，使其指向n，即搜索之后的最佳路径。否则，原路径好。2023/2/5人工智能702.4.2启发式搜索的A算法和A*算法（10）对已存在于CLOSED表的节点，作与（2）同样的处理，并将其移出CLOSED表，放入OPEN表中重新扩展。S0过去生成P的路径现在生成P的路径过去对Ps的最优路径PsPmnka.P在n之前已是某一节点m的后继，所以需要做如同（2）同样的处理，如图右部所示。b.P在Closed表中，说明P的后继也在n之前已经生成，称为Ps。对Ps而言同样可能由于n→P这一路径的加入，又必须比较多条路径之后而取代价小的一条，如图左部所示。2023/2/5人工智能712.4.2启发式搜索的A算法和A*算法（11）f（x）＝g（x）＋h（x）探讨九宫重排问题的估价函数的设计过程。g（x）：对某一确定的节点，是确定的值。h（x）：不同的问题启发函数的定义不同，相同的问题也可以定义出不同的启发函数。衡量h（x）优劣的标准是看其是否能够准确反映出节点x到达目标的难易程度（距离）。估价函数定义探讨2023/2/5人工智能722.4.2启发式搜索的A算法和A*算法（12）2023/2/5人工智能7314832765S012384765Sg

估价函数f（x）＝g（x）＋h（x）因素1格局中将牌是否在家g(x)用节点深度d（x）来衡量如何定义？h（x）用x的格局与目标节点格局相比，不在家的将牌数目w(x)来衡量。例2.8

A算法在重排九宫问题中的应用。1

42837653238533414

28

37651

4

283

5761142

8376512384576212384765012384765Sg1扩展顺序f(x)值134827653

148

3

2765148327653441428637541428

37651284

376534128

43765128

4

37654261238476571

428376532556714

28

37651

4

283

576142

8376512384765Sg1扩展顺序f2(x)值134827654

148

3

27651483

276545134

8

27651

3482765513486

27566361

382476551

3482576798

143

27657

341

8

27651347

8

26513486

275713486

27578847810138247655111284376514

28

6

37514

2

8

3765788123847655128

138247652.4.2启发式搜索的A算法和A*算法（15）81263754a12384765Sg28146375b问题:是否对于所有的节点w(x)都能反映出从x节点变化到目标节点的难易程度（到目标的距离）？

w(a)=7

w(b)=6,从w（x）值看a格局离目标格局更远。

a格局真的比b格局距离目标更远吗？812637

5412384765Sga812637

54

128637

54128637

54128637

54123867

541238647

51238647512384765Sgw(a)=7实际距离为8123456782023/2/5人工智能772814376528143765

812437658124376581243765281463758132476581324765

13824765138247651238476512384765Sg81324765w(b)=6实际距离为1112345678910112023/2/5人工智能782.4.2启发式搜索的A算法和A*算法（18）

81263754a12384765Sg28146375b考虑因素2，定义h(x)=p(x)p(x)是x格局中每个将牌离家（Sg中的位置）的最短距离（不论路上是否放有其他将牌）的总和。02111111

p(a)=802122101

p(b)=9反映出a比b更容易到达目标格局实际距离为8实际距离为112023/2/5人工智能791

483

2765512384765Sg1扩展顺序f3(x)值134827655

148

3

27651483276577134

8

27651

3482765513486

27577231

382476551

348257674138247655512384765568

138247652023/2/5人工智能802.4.2启发式搜索的A算法和A*算法（20）

因素3格局中将牌回家的顺序812637

5412384765Sg2

8

146375ba

因素4中心位置是否有将牌沿着周围非中心方格上依顺时针检查x格局中的每一个将牌，如果其后紧跟着的将牌正好是目标格局中该将牌的后续者，该将牌得0分，否则得2分。在正中方格上有将牌得1分，否则得0分。

综合因素3和因素4的值，记为s(x)2023/2/5人工智能811

48

3

276520238522253014

28

37651

4

283

57610142

83765123845761812384765712384765Sg1扩展顺序f4(x)值1348276523

148

3

2765148327652228414286375301428

37651284

37651630128

43765128

4

3765171661238476572023/2/5人工智能822023/2/5人工智能832.4.2启发式搜索的A算法和A*算法（22）对A算法再限制其估价函数中的启发函数h(x)满足：对所有的节点x均有：h（x）h*（x）其中h*（x）是从节点x到目标节点的最小代价，这就称为A*算法。A*算法也称为最佳图搜索算法，利用A*算法，如果问题存在最优解，就保证能找到最优解。2.4.2启发式搜索的A算法和A*算法（23）例2.9修道士和野人问题。在河的左岸有五个修道士、五个野人和一条船，修道士们想用这条船将所有的人都运过河去，但受到以下条件的限制：（1）修道士和野人都会划船，但船一次最多只能运三个人；（2）在任何岸边及船上野人数目都不得超过修道士，否则修道士就会被野人吃掉。假定野人会服从任何一种过河安排，试规划出一种确保修道士安全过河方案。请定义启发函数，并给出相应的搜索树。2023/2/5人工智能842.4.2启发式搜索的A算法和A*算法（24）解：先建立问题的状态空间。问题的状态可以用一个三元数组来描述：

S＝(m,c,b)

m：左岸的修道士数c：左岸的野人数b：左岸的船数初始状态为：（5，5，1）

终止状态为：（0，0，0）

合法的操作只有使状态如下转换：从平衡状态（m=c）转换为修道士扎堆（m=0或m=5）从平衡状态（m=c）转换为平衡状态（m=c）从扎堆状态（m=0或m=5）转换为平衡状态（m=c）2023/2/5人工智能852.4.2启发式搜索的A算法和A*算法（25）

定义启发函数，若满足h（n）≤h*（n），即满足A*条件的。启发函数1：h（n）=0;启发函数2：h（n）=M+C;对状态（1，1，1），启发函数2不满足h（n）≤h*（n）

提示：不考虑限制条件的运送次数一定小于有限制条件的运送次数。2023/2/5人工智能862.4.2启发式搜索的A算法和A*算法（26）先考虑船在左岸的情况：如果不考虑限制条件，至少需要[（m+c-3）/2]*2+1化简后为：[（m+c-3）/2]*2+1大于等于m+n-2再考虑船在右岸的情况：同样不考虑限制条件。船在右岸，需要一个人将船运往左岸，因此，对于状态（m，c，0），需要的摆渡数，相当于船在左岸的（m+1，c，1）或（m，c+1，1），所以需要的最少摆渡数为：m+c+1-2+1=m+c综合条件，需要的最少摆渡数为m+c-2b。2023/2/5人工智能87（5，5，1）1h=8f=8（5,3,0）11h=8f=9（5,4,0）20h=9f=10（5,2,0）2h=7f=8（4,4,0）12h=8f=9（5,4,2）10h=7f=9（5,3,1）3h=6f=8（3,3,0）8h=6f=9（5,1,0）9h=6f=9（5,0,0）4h=5f=8（4,4,1）19h=6f=10（5,2,1）6h=5f=9（5,1,1）5h=4f=8（2，2，0）7h=4f=9（3，3，1）13h=4f=10（0，3，0）14h=3f=10扩展顺序h(x)及f(x)值2023/2/5人工智能88（0，3，0）14h=3f=10（0,4,1）15h=2f=10（0,5,1）h=3f=11（1,1,1）17h=0f=10（0,2,1）18h=0f=10（0,3,1）h=1f=11（0，0，0）21h=0f=11（0,1,0）16h=1f=10（0,2,0）h=2f=112023/2/5人工智能892023/2/5人工智能902.4.3

A*算法在游戏中的应用（1）启发式算法逐渐发展成为路径搜索算法的核心，除了A*算法以外，国内外研究者还在此基础上逐渐发展了许多其它智能算法，包括IDA*算法、D*算法等，它们的基本原理都借鉴了A*算法中的估价函数思想。目前，游戏业界的标准是使用A*算法或IDA*算法，A*算法一般要快一些，而IDA*算法则比A*算法要使用更少的内存。2.4.3

A*算法在游戏中的应用（2）如果游戏仅仅要求出从点A到达点B的一条最短路径的话，那么使用A*算法，将h(x)设计为对A点到B点的最短路径的估计就可以完成此任务；然而，真实游戏中往往还要考虑路上的障碍物、或者在从点A到点B的途中避免被看到或被射击到、以及敌方的位置和火力线等。在游戏设计中，使用A*算法寻找路径时，启发函数h(x)的设计还需要考虑更多的因素，如路径的距离、途中的障碍物、地形允许的行走速度、是否敌人视线与火力之下的位置、敌我双方暴露的时间和次数、敌方的威胁是否动态的、有掩护物和隐身处的路径等因素。2.4.3

A*算法在游戏中的应用（3）比如：对那些暴露在敌方火力侦查或是覆盖之下的位置增加其代价值，使得A*算法生成一条尽量避免敌人侦查或射击的路径；如果敌方的飞机处于被我方地对空导弹防御的区域，那么，同样暴露20秒，是一次暴露20秒，还是分四次暴露，一次暴露5秒，显然对我方来说代价是不一样的；另外，敌方的威胁是静态的或动态的，估价函数值计算出来也应该不同。当然，考虑更多的因素一定会增加代价计算量，所以，在实际当中，使用A*算法进行游戏设计时，还需要在获得战术能力和所付出的计算量之间做出权衡。2023/2/5人工智能932.5与或图表示及搜索技术2.5.1与或图表示2.5.2与或树的盲目搜索2.5.3与或树的启发式搜索问题分解：在问题求解过程中，常常将一个复杂的问题P分解为一组子问题，当这些子问题全部可解时，原问题P可解；任何一个子问题无解时，都将导致原问题P无解。即一个问题与一组子问题的“与”等价。如：保送研究生的条件是每门课程成绩都在85分以上。问题变换：有时将一个复杂的问题P变换为与之等价的一组子问题，其中任何一个子问题可解时，原问题P可解；全部子问题无解时，原问题P无解。即一个问题与一组子问题的“或”等价。如：保送研究生的条件中，要求英语成绩是通过六级考试，或者通过GRE考试。与或图：将问题对应节点，分解或变换关系对应边，这样，就可以将一个问题求解过程中的分解和变换过程表示为一棵与或图。与状态空间图的意义不同，这里的与或图对应的是问题空间图。2023/2/5人工智能942.5.1与或图表示（1）与或图的概念来源于问题求解中的分解和变换一个复杂的问题P常常可以分解为与之等价的一组子问题P1，P2，

…

Pn，当这些问题全部可解时，问题可解；任何一个子问题无解时，都将导致原问题P无解。即一个问题与一组子问题的与等价。一个复杂的问题P常常可以分别变换为与之等价的一组子问题P1，P2，

…

Pn，其中任何一个子问题可解时，问题可解；全部子问题无解时，原问题P无解。即一个问题与一组子问题的或等价。2.5.1与或图表示（2）例2.10猴子摘香蕉问题房间内有一只猴子位于A处，有一只箱子位于B处，还有一架梯子位于C处，A到B的距离与A到C是距离相同，梯子和箱子的重量相同。屋顶上D处挂着一串香蕉，猴子爬到梯子上或箱子上都能摘到香蕉。2023/2/5人工智能962.5.1与或图表示（3）2023/2/5人工智能97定义五个动作：f1(x,y)：表示猴子从x处走到y处；f2(x,y)：表示猴子推箱子从x处走到y处；f3(x,y)：表示猴子搬梯子从x处走到y处；f4()

：表示登上箱子；f5()：表示登上梯子；f6()

：表示摘到香蕉；则猴子摘香蕉问题的分解变换过程可用如下与或图表示：2023/2/5人工智能982.5.1与或图表示（4）例2.11证明四边形全等。分析：连接BD，B´D´，原来问题可以分解为两个子问题：Q1：证明ΔABC≌ΔA′B′C′Q2：证明ΔBCD≌ΔB′C′D′原来问题可以分为两个子问题解决。ABDCA´B´D´C´2.5.1与或图表示（5）问题Q1还可以再被分解为：

Q11

：证明AB＝A′B′Q12

：证明AD＝A′D′Q13

：证明∠A＝∠A′或

Q11´：证明AB＝A′B′Q12´：证明AD＝A′D′Q13´：证明BD＝B′D′问题Q2还可以再被分解为：

Q21

：证明BC＝B′C′Q22

：证明CD＝C′D′Q23

：证明∠C＝∠C′或

Q21´：证明BC＝B′C′Q22´：证明CD＝C′D′Q23´：证明BD＝B′D′´2023/2/5人工智能1002.5.1与或图表示（5）将原问题用图的形式表示如下：QQ1Q2Q11Q12Q13Q11'Q12'Q13'Q21Q22Q23Q21'Q22'Q23'弧线表示所连边为“与”的关系不带弧线的边为或关系2.5.1与或图表示（6）例2.12梵塔问题。

有1、2、3号杆，1号杆自上而下串着从小到大的n个金盘，要把1号杆上的n个金盘移到3号杆上。移动金盘的规则是：一次只能移一个金盘；移动的过程中不允许大盘压在小盘上。2023/2/5人工智能1013123122.5.1与或图表示（6）(1,1,1)=>(3,3,3)(1,1,1)=>(1,1,3)(1,2,3)=>(1,2,2)(3,2,2)=>(3,2,1)(3,3,1)=>(3,3,3)(1,1,3)=>(1,2,3)(3,2,1)=>(3,3,1)(1,1,1)=>(1,2,2)(1,2,2)=>(3,2,2)(3,2,2)=>(3,3,3)三阶梵塔问题的与或树2023/2/5人工智能1032.5.1与或图表示（7）与或图的几个概念：直接可解的问题称为本原问题。本原问题对应的节点称为终止节点。无子节点的节点称为端节点。子节点为与关系，则该节点为与节点。子节点为或关系，则该节点为或节点。与或图一般表示问题的变换过程，就是从原问题出发，运用某些规则不断的进行问题的分解（得到与分支）和变换（得到或分支），而得到一个与或图，与或图的节点一般代表问题，整个图就表示问题空间。2023/2/5人工智能1042.5.1与或图表示（8）与或图也可以用三元组表示：（Q0,F,Qn）Q0表示初始问题F表示问题变换规则集Qn表示本原问题集2.5.1与或图表示（9）节点的可解性判别：（1）终止节点是可解节点；（2）一个与节点可解，当且仅当其全部子节点可解；（3）一个或节点可解，只要其子节点至少有一个