图搜索与问题求解.ppt

第3章 图搜索与问题求解,2023/8/10,人工智能,2,推理与搜索,图搜索技术是人工智能的核心技术之一。任一搜索过程也都是一个推理过程。隐式图的搜索过程是一种利用局部性知识构造全局性答案的过程。在各种搜索过程中，人工智能最感兴趣的是那些具有很强选择性的启发式方法，即那些利用很局部的状态空间可以有效地找到问题的解的方法。机器学习等很多过程都是在假设空间中搜索目标的过程。,2023/8/10,人工智能,3,第3章 图搜索与问题求解,3.1 状态图知识表示（状态图搜索问题求解）3.2 状态图搜索3.3 与或图知识表示（与或图搜索问题求解）3.4 与或图搜索3.5 博弈树搜索,2023/8/10,人工智能,4,3.1 状态图知识表示,3.1.1 状态、操作和状态空间3.1.2 修道士和野人的状态空间3.1.3 梵塔问题的状态空间3.1.4 重排九宫问题和隐式图3.1.5 问题求解的基本框架,2023/8/10,人工智能,5,状态、操作和状态空间（1）,例3.1走迷宫,走迷宫问题就是从该有向图的初始节点出发，寻找目标节点的问题，或者是寻找通向目标节点的路径问题。,2023/8/10,人工智能,6,3.1.1 状态、操作和状态空间（2）,例3.2八数码难题(重排九宫问题),初始棋局,目标棋局,以上两个问题抽象来看，都是某个有向图中寻找目标或路径的问题，在人工智能技术中，把这种描述问题的有向图称为状态空间图，简称状态图。,棋局作为节点，相邻节点通过移动数码一个一个产生出来，所有节点由它们的相邻关系连成一个有向图。,2023/8/10,人工智能,7,3.1.1 状态、操作和状态空间（3）,状态（State）p62为了描述某一类事物中各个不同事物之间的差异而引入的最少的一组变量q的有序组合，表征了问题的特征和结构。表示成矢量形式：状态在状态图中表示为节点。,2023/8/10,人工智能,8,3.1.1 状态、操作和状态空间（4）,状态转换规则（操作 operator）引起状态中某些分量发生改变，从而使一个具体状态变化到另一个具体状态的作用。它可以是一个机械性的步骤、过程、规则或算子。操作描述了状态之间的关系。状态转换规则在状态图中表示为边。在程序中状态转换规则可用数据对、条件语句、规则、函数、过程等表示。,2023/8/10,人工智能,9,3.1.1 状态、操作和状态空间（5）,状态空间（State Space）问题的状态空间是一个表示该问题全部的可能状态及相互关系的图。状态空间一般用赋值有向图表示，记为：（S，F，G）S：问题的可能有的初始状态的集合；F：操作的集合；G：目标状态的集合。,2023/8/10,人工智能,10,3.1.1 状态、操作和状态空间（6）,状态空间中问题求解在状态空间表示法中，问题求解过程转化为在图中寻找从初始状态Qs出发到达目标状态Qg的路径问题，也就是寻找操作序列的问题。状态空间的解为三元组Qs：某个初始状态Qg：某个目标状态a：把Qs变换成Qg的有限的操作序列状态转换图,2023/8/10,人工智能,11,3.1.1 状态、操作和状态空间（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,迷宫问题规则集描述了图中所有节点和边。类似于这样罗列出全部节点和边的状态图称为显式状态图，或者说状态图的显式表示。,2023/8/10,人工智能,12,3.1.1 状态、操作和状态空间（8）,补充例1 三枚钱币，能否从下面状态翻动三次后出现全正或全反状态。,反,正,反,正,正,正,反,反,反,初始状态s,目标状态集合0,7,2023/8/10,人工智能,13,3.1.1 状态、操作和状态空间（9）,引入一个三元组(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)。,翻动钱币的操作抽象为改变上述状态的算子，即Fa,b,c a:把钱币q0翻转一次 b:把钱币q1翻转一次 c:把钱币q2翻转一次 问题的状态空间为,2023/8/10,人工智能,14,3.1.1 状态、操作和状态空间（10）,状态空间图,（0，0，0）,（1，0，1）,（0，0，1）,（0，1，0）,（1，1，0）,（1，0，0）,（0，1，0）,（1，1，1）,a,c,a,b,a,c,a,b,c,b,b,c,2023/8/10,人工智能,15,3.1.2 修道士和野人问题的状态空间（1）,补充例2 修道士和野人问题。在河的左岸有三个修道士、三个野人和一条船，修道士们想用这条船将所有的人都运过河去，但受到以下条件的限制：（1）修道士和野人都会划船，但船一次最多只能运两个人；（2）在任何岸边野人数目都不得超过修道士，否则修道士就会被野人吃掉。假定野人会服从任何一种过河安排，试规划出一种确保修道士安全过河方案。,2023/8/10,人工智能,16,3.1.2 修道士和野人问题的状态空间（2）,解：先建立问题的状态空间。问题的状态可以用一个三元数组来描述：S(m,c,b)m：左岸的修道士数 c：左岸的野人数 b：左岸的船数 右岸的状态不必标出，因为：右岸的修道士数m3m 右岸的野人数c3c 右岸的船数b=1-b,2023/8/10,人工智能,17,3.1.2 修道士和野人问题的状态空间（3）,2023/8/10,人工智能,18,3.1.2 修道士和野人问题的状态空间（4）,操作集Fp01,p10,p11,p02,p20,q01,q10,q11,q02,q20,2023/8/10,人工智能,19,3.1.2 修道士和野人问题的状态空间（5）,2023/8/10,人工智能,20,3.1.3 梵塔问题的状态空间（1）,例3.9 二阶梵塔问题 一号杆有A、B两个金盘，A小于B。要求将AB移至三号杆，每次只可移动一个盘子，任何时刻B不能在A上。,用二元组（SA，SB）表示状态，SA表示A所在杆号，SB表示B所在杆号，全部状态如下：（1，1），（1，2），（1，3）（2，1），（2，2），（2，3）（3，1），（3，2），（3，3）,2023/8/10,人工智能,21,3.1.3 梵塔问题的状态空间（2）,B,A,A,A,A,A,B,A,B,B,B,B,B,2023/8/10,人工智能,22,3.1.3 梵塔问题的状态空间（3）,转换规则：A（i，j）表示金盘A从第i号杆移到j号杆 B（i，j）表示金盘B从第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），B（3，2）初始状态（1，1），目标状态（3，3）梵塔问题用状态图表示为：,2023/8/10,人工智能,23,3.1.3 梵塔问题的状态空间（4）,1,1,2,1,3,1,2,3,3,3,1,3,3,2,1,2,2,2,A(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),2023/8/10,人工智能,24,n（n3）阶梵塔问题,假设金片Pk从小片到大片按下标k顺序编号，即k=1，2，3，n，n阶梵塔问题状态空间可用矢量表示为：(P1,P2,P3,Pk,Pn)Pk表示第k个金片穿在编号为Pk的宝石针上，Pk=1，2，3初始状态 S0=(1,1,1,1,1)目标状态 Sg1=(2,2,2,2,2)Sg2=(3,3,3,3,3),2023/8/10,人工智能,25,n（n3）阶梵塔问题,n阶梵塔问题的操作集合表示为：F=Rk(i,j)|i,j=1,2,3，k=1，2，n全部可能状态数为3n个，最佳解长度为2n-1。三阶梵塔问题状态图,S0=(1,1,1),Sg2=(3,3,3),Sg1=(2,2,2),2023/8/10,人工智能,26,3.1.4 重排九宫问题和隐式图（1）,例3.8重排九宫问题（八数码难题）,将棋局用向量A(X0，X1，X2，X3，X4，X5，X6，X7，X8)表示，其中Xi为变量，值表示方格Xi内的数字。初始状态 S0（0，2，8，3，4，5，6，7，1）目标状态 Sg（0，1，2，3，4，5，6，7，8）数码的移动规则就是该问题的状态变化规则。经分析，该问题共有24条规则，分为9组。,初始棋局,目标棋局,2023/8/10,人工智能,27,3.1.4 重排九宫问题和隐式图（2）,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组规则 r5(X1=0)(X2=n)X1=n X2=0；r6(X1=0)(X8=n)X1=n X8=0；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；,2023/8/10,人工智能,28,3.1.4 重排九宫问题和隐式图（3）,八数码的状态图可表示为（S0,r1,r2,r24,Sg）八数码问题状态图仅给出了初始节点和目标节点，其余节点需用状态转换规则来产生。类似于这样表示的状态图称为隐式状态图，或者说状态图的隐式表示。,2023/8/10,人工智能,29,3.1.4 重排九宫问题和隐式图（4）,如何隐式的描述一个状态空间有描述问题状态的有关知识，包括该问题的各状态分量的取值情况，开始条件、结束条件、各种约束条件等等。需要由任何一个状态生成其所有直接后继节点的的有关知识。,2023/8/10,人工智能,30,3.1.4 重排九宫问题和隐式图（5）,例3.10 旅行商问题(TravelingSalesmanProblem，简称TSP)。设有n个互相可直达的城市，某推销商准备从其中的A城出发，周游各城市一遍，最后又回到A城。要求为该推销商规划一条最短的旅行路线。该问题的状态为以A打头的已访问过的城市序列:A S0:A。Sg:A,A。其中“”为其余n-1个城市的一个序列。状态转换规则：规则1 如果当前城市的下一个城市还未去过，则去该城市，并把该城市名排在已去过的城市名序列后端。规则2 如果所有城市都去过一次，则从当前城市返回A城，把A也添在去过的城市名序列后端。,2023/8/10,人工智能,31,3.1.5 问题求解的基本框架（1）,问题求解所需要的知识与描述问题的状态有关的各种叙述性知识。描述状态之间的变换关系的各种过程性知识。一般以一组操作的形式出现的。任何一个操作都含有条件和动作两部分，条件给定了操作的适用范围，动作描述了由于操作而引起的状态中某些分量的变化情形。描述如何根据当前状态和目标状态选择合适的操作的控制性知识。根据叙述性和过程性知识可以构造问题的状态空间。一般讲状态空间是一个赋值有向图，节点对应着问题的状态，边对应操作。,2023/8/10,人工智能,32,3.1.5 问题求解的基本框架（2）,问题求解就是在图中寻找一条从初始节点到达目标节点的通路或操作序列。首先从操作集中选择可作用在当前状态上的操作；如果符合条件的操作有许多个，则要从挑选出最有希望导致目标状态的操作施加到当前状态上，以便克服组合爆炸；如果解的长度很大，还需要更为复杂的克服组合爆炸的技术。,2023/8/10,人工智能,33,3.2 状态图搜索,状态图搜索穷举式搜索启发式搜索加权状态图搜索启发式图搜索的A算法和A*算法状态图搜索策略小结,2023/8/10,人工智能,34,3.2.1 状态图搜索（1）,搜索：从初始节点出发，沿着与之相连的边试探地前进，寻找目标节点的过程。搜索过程中经过的节点和边，按原图的连接关系，便会构成一个树型的有向图，这种树型有向图称为搜索树。搜索进行中，搜索树会不断增长，直到当搜索树中出现目标节点，搜索便停止。这时从搜索树中就可很容易地找出从初始节点到目标节点的路径（解）来。,2023/8/10,人工智能,35,3.2.1 状态图搜索（2）,1 搜索方式树式搜索 在搜索过程中记录所经过的所有节点和边。树式搜索所记录的轨迹始终是一棵树，这棵树也就是搜索过程中所产生的搜索树。线式搜索 在搜索过程中只记录那些当前认为在所找路径上的节点和边。不回溯线式搜索可回溯线式搜索,2023/8/10,人工智能,36,3.2.1 状态图搜索（3）,2 搜索策略盲目搜索 无向导的搜索，树式盲目搜索就是穷举搜索，不回溯的线式搜索是随机碰撞式搜索，回溯的线式搜索也是穷举式搜索。启发式搜索 是利用“启发性信息”引导的搜索策略。“启发性信息”就是与问题有关的有利于尽快找到问题解的信息或知识。启发式搜索分为不同的策略，如全局择优，局部择优，最佳图搜索。按扩展顺序不同分为广度优先和深度优先。,2023/8/10,人工智能,37,3.2.1 状态图搜索（4）,3 搜索算法搜索的目的是为了寻找初始节点到目标节点的路径，搜索过程中就得随时记录搜索轨迹。ClOSED表动态数据结构来记录考察过的节点。OPEN表的动态数据结构来专门登记当前待考查的节点。,OPEN表,CLOSED表,2023/8/10,人工智能,38,3.2.1 状态图搜索（5）,树式搜索算法 步1 把初始节点S0放入OPEN表中。步2 若OPEN表为空，则搜索失败，退出。步3 取OPEN表中第一个节点N放在CLOSED表中；并冠以顺序编号n；步4 若目标节点Sg=N，成功退出。步5 若N不可扩展，转步2。步6 扩展N，生成一组节点，对这组子节点作如下处理：,2023/8/10,人工智能,39,3.2.1 状态图搜索（6）,（1）删除N的先辈节点（如果有的话）。（2）对已存在于OPEN表中的节点（如果有的话）也删除之；删除之前要比较其返回初始节点的新路径与原路径，如果新路径“短”，则修改这些节点在OPEN表中的原返回指针，使其沿新路径返回。（3）对已存在于CLOSED表的节点，作与（2）同样的处理，并且将其移出CLOSED表，放入OPEN表中重新扩展。（4）对其余子节点配上指向N的返回指针后放入OPEN表中某处，或对OPEN表进行重新排序，转步2。,2023/8/10,人工智能,40,3.2.1 状态图搜索（7）,树式算法的几点说明返回指针指的是父节点在CLOSED表中的编号。步6中修改指针的原因是返回初始节点的路径有两条，要选择“短”的那条路径。这里路径长短以节点数来衡量，在后面将会看到以代价来衡量。按代价衡量修改返回指针的同时还要修改相应的代价值。,2023/8/10,人工智能,41,3.2.1 状态图搜索（8）,图 3-5 修改返回指针示例,2023/8/10,人工智能,42,3.2.1 状态图搜索（9）,树式搜索例对于已存在于OPEN表中的节点（如果有的话）也删除之；删除之前要比较其返回初始节点的新路径与原路径，如果新路径短，则修改这些节点在OPEN表中的原返回指针，使其沿原路径返回。,Path1,Path2,S0,m,n,P,先扩展,后扩展,P在n之前已是某一节点m的后继,如图所示：说明从S0P至少有两条路，这时有两种情况：f（Path2）f（Path1），当前路径较好，要修改P的指针，使其指向n，即搜索之后的最佳路径。否则，原路径好。,2023/8/10,人工智能,43,3.2.1 状态图搜索（10）,对已存在于CLOSED表的节点，作与（2）同样的处理，并将其移出CLOSED表，放入OPEN表中重新扩展。,S0,过去生成P的路径,现在生成P的路径,过去对Ps的最优路径,Ps,P,m,n,k,a.P在n之前已是某一节点m的后继，所以需要做如同（2）同样的处理，如图右部所示。b.P在Closed表中，说明P的后继也在n之前已经生成，称为Ps。对Ps而言同样可能 由于nP这一路径的加入，又必须比较多条路径之后而取代价小的一条，如图左部所示。,2023/8/10,人工智能,44,3.2.1 状态图搜索（11）,例：设当前搜索图和搜索树如图所示,S0,n,P,m,Ps,Ps,S0,n,P,m,Ps,Ps,F,F,2023/8/10,人工智能,45,3.2.1 状态图搜索（12）,若启发函数f(n)为从S0到节点n的最短路径的长度，用边的数目来考察，当前扩展的节点是搜索图中的n,P是n的后继,S0,n,P,m,Ps,Ps,n,P,Ps,Ps,S0,m,F,F,2023/8/10,人工智能,46,3.2.1 状态图搜索（13）,P的指针改变后，修改搜索树结果如下：,n,P,Ps,S0,F,m,Ps,2023/8/10,人工智能,47,3.2.1 状态图搜索（14）,不回溯线式搜索算法 步1 把初始节点S0放入CLOSED表中；步2 令N S0；步3 若N是目标节点，则搜索成功，结束。步4 若N不可扩展，则搜索失败，退出。步5 扩展N，选取其一个未在CLOSED表中出现过的 子节点N1放入 CLOSED表中，令NN1，转步3。,2023/8/10,人工智能,48,3.2.1 状态图搜索（15）,可回溯的线式搜索步1 把初始节点S0放入CLOSED表中；步2 令N S0；步3 若N是目标节点，则搜索成功，结束。步4 若N不可扩展，则移出CLOSED表中的末端节点Ne，若NeS0，则搜索失败，退出。否则以CLOSED表新的末端节点Ne作为 N，即令N Ne，转步4；步5 扩展N，选取其一个未在CLOSED表中出现过的子节点N1放入 CLOSED表中，令N N1，转步3。,2023/8/10,人工智能,49,3.2.2 穷举式搜索（1）,广度优先搜索（算法Aed）策略 始终在同一级节点中考查，当同一级节点考查完了之后，才 考查下一级节点。搜索树自顶向下一层一层逐渐生成。算法 步1 把初始节点S0放入OPEN表中；步2 若OPEN表为空，则搜索失败，退出。步3 取OPEN表中第一个节点N放在CLOSED表中；并冠以顺序编号n；步4 若节点N为目标节点，成功退出。步5 若N不可扩展，转步2；步6 扩展N，将其所有子节点配上指向N的指针放入OPEN尾部，转步2。,2023/8/10,人工智能,50,3.2.2 穷举式搜索（2）,2023/8/10,人工智能,51,3.2.2 穷举式搜索（3）,广度优先搜索的特点广度优先中OPEN表是一个队列，CLOSED表是一个顺序表，表中各节点按顺序编号，正被考察的节点在表中编号最大。广度优先搜索又称为宽度优先或横向搜索。广度优先策略是完备的，即如果问题的解存在，则它一定可以找到解，并且找到的解还是最优解。广度优先搜索策略与问题无关，具有通用性。缺点搜索效率低。,2023/8/10,人工智能,52,3.2.2 穷举式搜索（4）,八数码问题,2023/8/10,人工智能,53,3.2.2 穷举式搜索（5）,八数码广度优先搜索,2023/8/10,人工智能,54,3.2.2 穷举式搜索（6）,深度优先搜索（过程Apd）搜索策略 在搜索树的每一层始终先扩展一个子节点，不断地向纵深前进，直到不能再前进，才从当前节点返回到上一级节点，从另一方向继续前进。算法 步1 把初始节点S0放入OPEN表中；步2 若OPEN表为空，则搜索失败，退出。步3 取OPEN表中第一个节点N放在CLOSED表中；并冠以编号n；步4 节点N为目标节点，成功退出。步5 若N不可扩展，转步2；步6 扩展N，将其所有子节点配上指向N的指针放入OPEN首部，转 步2。,2023/8/10,人工智能,55,3.2.2 穷举式搜索（7）,2023/8/10,人工智能,56,3.2.2 穷举式搜索（8）,深度优先搜索的特点OPEN表为一个堆栈。深度优先又称纵向搜索。一般不能保证找到最优解。当深度限制不合理时，可能找不到解，可以将算法改为可变深度限制，即有界深度优先搜索。最坏情况时，搜索空间等同于穷举。,2023/8/10,人工智能,57,3.2.2 穷举式搜索（9）,八数码深度优先搜索,2023/8/10,人工智能,58,3.2.2 穷举式搜索（10）,有界深度优先搜索（过程Acd）搜索策略 给出搜索树深度的限制，当从初始节点出发沿某一分支扩展到一定深度限制时，就不能再继续往下扩展，而只能改变方向继续搜索。算法 步1 把初始节点S0放入OPEN表中，置S0的深度d（S0）0；步2 若OPEN表为空，则搜索失败，退出。步3 取OPEN表中第一个节点N放在CLOSED表中；并冠以编号n；步4 若节点N为目标节点，成功退出。步5 若N的深度d（N）dm（深度限制值），或者若N无子节点，则转步2；步6 扩展N，将其所有子节点Ni配上指向N的指针放入OPEN首部，置的d（Ni）d（N）1，转步2。,2023/8/10,人工智能,59,3.2.2 穷举式搜索（11）,a1,a2,a3,a6,b1,b2,b4,b3,b5,S,2023/8/10,人工智能,60,3.2.2 穷举式搜索（12）,有界深度优先搜索存在的问题深度界限的选择很重要 dm 若太小，则达不到解的深度，得不到解；若太大，既浪费了计算机的存储空间与时间，又降低了搜索效率。由于解的路径长度事先难以预料，所以要恰当地给出dm的值是比较困难的。即使能求出解，它也不一定是最优解。,2023/8/10,人工智能,61,3.2.2 穷举式搜索（13）,有界深度优先搜索改进dm随搜索深度不断加大（迭代加深搜索）先任意给定一个较小的数作为dm，然后进行上述的有界深 度优先搜索，当搜索达到了指定的深度界限dm仍未发现目标节点，并且CLOSED表中仍有待扩展节点时就将这些节点送回OPEN表，同时增大深度界限dm，继续向下搜索。如此不断地增大dm，只要问题有解，就一定可以找到它。增加一个R表 此时找到的解不一定是最优解。为找到最优解，可增设一 个表(R)，每找到一个目标节点Sg后，就把它放入到R的前，并令dm等于该目标节点所对应的路径长度，然后继续搜索。由于后求得的解的路径长度不会超过先求得的解的路径长度，所以最后求得的解一定是最优解。,2023/8/10,人工智能,62,3.2.2 穷举式搜索（14）,迭代加深搜索过程：步1 把初始节点S0放入OPEN表中，置S0的深度d（S0）0，dm为任意初值。步2 若OPEN表为空，则考查CLOSED表是否有待扩展节点：若无，则问题无解，退出。若有，则取出CLOSED表中待扩展节点放入到OPEN表中，令 dm=dm+d。,2023/8/10,人工智能,63,3.2.2 穷举式搜索（15）,步3 取OPEN表中第一个节点N放在CLOSED表中；并冠以编号n；步4 若节点N为目标节点，成功退出。步5 若N的深度d（N）dm（深度限制值），则标N为待扩展节点，则转步2；步6 N无子节点，则转步2；步7 扩展N，将其所有子节点Ni配上指向N的指针放入OPEN首部，置 d（Ni）d（N）1，转步2。,2023/8/10,人工智能,65,3.2.3 启发式搜索（1）,启发式搜索的目的利用知识来引导搜索，达到减少搜索范围，降低问题复杂度。启发性信息的强弱 强：降低搜索的工作量，但可能导致找不到最优解。弱：一般导致工作量加大，极限情况下变为盲目搜索，但可能可以找到最优解。启发性信息的类型用于扩展节点的选择用于生成节点的选择用于删除节点的选择,2023/8/10,人工智能,66,3.2.3 启发式搜索（2）,启发函数启发函数是用来估计搜索树节点x与目标节点接近程度的一种函数，通常记为h（x）。定义启发函数的参考思路一个节点到目标节点的某种距离或差异的量度。一个节点处在最佳路径上的概率根据主观经验的主观打分等。启发式搜索算法启发式搜索要用启发函数来导航，其搜索算法就要在状态图一般搜索算法基础上再增加启发函数值的计算与传播过程，并且由启发函数值来确定节点的扩展顺序。,2023/8/10,人工智能,67,3.2.3 启发式搜索（3）,全局择优搜索全局择优搜索就是利用启发函数制导的一种启发式搜索方法。该方法亦称为最好优先搜索法。基本思想：在OPEN表中保留所有已生成而未考察的节点，并用启发函数h(x)对它们全部进行估价，从中选出最优节点进行扩展，而不管这个节点出现在搜索树的什么地方。,2023/8/10,人工智能,68,3.2.3 启发式搜索（4）,全局择优搜索算法 步1 把初始节点S0放入OPEN表中，计算h（S0）；步2 若OPEN表为空，则搜索失败，退出。步3 移出OPEN表中第一个节点N放入CLOSED表中，并冠以序号n；步4 若目标节点Sg N，则搜索成功结束。步5 若N不可扩展，则转步2。步6 扩展N，计算每个子节点x的函数值h（x），并将所有子节点配以指向N的返回指针后放入OPEN表中，再对OPEN表中所有子节点按其函数值的大小以升序排列，转步2。,2023/8/10,人工智能,69,3.2.3 启发式搜索（6）,启发函数h(x)为节点x与目标格局相比数码不同的位置个数。从图看出解为：S0，S1，S2，S3，Sg。,Sg,8 1 32 47 6 5,2023/8/10,人工智能,70,3.2.3 启发式搜索（7）,局部择优搜索局部择优搜索是一种启发式搜索方法，是对深度优先搜索方法的一种改进。基本思想是当每一个节点被扩展后，按h(x)对每一个子节点计算启发值，并选择最小者作为下一个要考察的节点，由于每次都只是在子节点的范围内选择下一个要考察的节点，范围比较狭窄，所以称为局部择优搜索。,2023/8/10,人工智能,71,3.2.3 启发式搜索（8）,局部择优搜索算法 步1 把初始节点S0放入OPEN表中，计算h（S0）；步2 若OPEN表为空，则搜索失败，退出。步3 移出OPEN表中第一个节点N放入CLOSED表中，并冠以序号n；步4 若目标节点Sg N，则搜索成功结束。步5 若N不可扩展，则转步2。步6 扩展N，计算N每个子节点x的函数值h（x），并 将N的子节点按估计值升序排列放入OPEN表的首 部，为每个子节点配置指向节点N的指针，转步 2。,2023/8/10,人工智能,72,加权状态图搜索（1）,例3.6 交通图A城是出发地，E是目的地，数字表示两城之间交通费用。求A到E的最小费用的旅行路线。,A,D,C,E,B,4,6,4,3,3,2,2023/8/10,人工智能,73,加权状态图搜索（2）,加权状态图与代价树边上附有数值的状态图称为加权状态图或赋权状态图，这种数值称为权值。加权状态图的搜索加权状态图的搜索与权值有关，并且要用权值来导航。具体来讲，加权状态图的搜索算法，要在一般状态图搜索算法基础上再增加权值的计算与传播过程，并且要由权值来确定节点的扩展顺序。代价的计算 g（x）表示从初始节点S0到节点x的代价。c（xi，xj）表示父节点xi到子节点xj的代价 g（xj）g（xi）c（xi，xj）g（x0）0,2023/8/10,人工智能,74,加权状态图搜索（3）,加权状态图转换为代价树搜索从初始节点出发，先把每一个与初始节点相邻的节点作为该节点的子节点。然后对其他节点依次类推，但对其他节点x，不能将其父节点及祖先再作为x的子节点。,A,D,C,E,B,4,6,4,3,3,2,3,2,3,4,6,2,3,4,4,6,3,2,C1,B1,D1,D2,E1,C2,E2,D3,C3,B2,E4,E3,6,B3,2023/8/10,人工智能,75,加权状态图搜索（4）,分支界限法（A*eg）其基本思想是：每次从OPEN表中选出g(x)值最小的节点进行考察，而不管这个节点在搜索树的什么位置上。与全局择优法的区别,2023/8/10,人工智能,76,加权状态图搜索（5）,分支界限搜索算法步1 把初始节点S0放入OPEN表中，计算g（S0）；步2 若OPEN表为空，则搜索失败，退出。步3 移出OPEN表中第一个节点N放入CLOSED表中，并冠以序号n；步4 若目标节点Sg N，则搜索成功结束。步5 若N不可扩展，则转步2。步6 扩展N，并将所有子节点配以指向N的返回指针后放 OPEN表中；计算每个子节点x的函数值g（x），再对OPEN表中所有子节点按g（x）值的大小以升 序排列，转步2。,2023/8/10,人工智能,77,加权状态图搜索（6）,最近择优法（瞎子爬山法）基本思想：每次仅考察N的子节点的g（x），选取N的子节点中代价最小的子节点进行扩展。最近择优法与局部择优法的区别：,3,2,3,4,6,2,3,4,4,6,3,2,C1,B1,D1,D2,E1,C2,E2,D3,C3,B2,E4,E3,6,B3,A,2023/8/10,人工智能,79,加权状态图搜索（7）,代价树的有界深度优先法与直接树的有界深度优先相比，用gm来代替最大深度dm。,2023/8/10,人工智能,80,加权状态图搜索（8）,代价树深度优先搜索搜索的解为A-C-D-E,2023/8/10,人工智能,81,内容回顾：树形图树式搜索策略比较,S0,Sg,2,3,a,b,4,6,1,5,c,d,g,f,h,i,j,k,5,f,5,4,3,7,8,9,h（x），有利于搜索纵向发展，提高搜索效率，但影响完备性。,g（x），有利于搜索横向发展，提高完备性，但影响搜索效率。,穷举式搜索,启发式搜索,加权状态图搜索,2023/8/10,人工智能,82,启发式图搜索的A算法和A*算法（1）,1.估价函数 将启发函数与代价函数相结合，为了防止在单独利用启发函数的时候误入歧途。f（x）g（x）h（x）,f（x）是初始节点S0到达节点x处已付出的代价与节点x到达目标节点Sg的接近程度估计值总和。是g（x）与h（x）的折中。,wh（x）,通过调整w的值，使结果偏重效率或偏重完备性。,2023/8/10,人工智能,83,启发式图搜索的A算法和A*算法（2）,2.A算法步1 把附有f（S0）的初始节点S0放入OPEN表中；步2 若OPEN表为空，则搜索失败，退出。步3 移出OPEN表中第一个节点N放入CLOSED表中，并冠以顺序编号n；步4 若目标节点SgN，则搜索成功，结束。步5 若N不可扩展，则转步2；,2023/8/10,人工智能,84,启发式图搜索的A算法和A*算法（3）,步6 扩展N，生成一组附有f（x）的子节点，对这组节点作如下处理：（1）考察是否有已在OPEN表或CLOSED表中存在的节点；若有则再考察其中有无N的先辈节点，若有则删除之；对于其余节点，也删除之，但由于它们被第二次生成，需考虑是否修改已经存在于OPEN表或CLOSED表中的这些节点及其后裔的返回指针和f（x）的值，修改原则是抄f（x）值小的路走”。（2）对其余子节点配上指向N的返回指针后放入OPEN表中，并对OPEN表按f（x）以升序排列，转步2。,2023/8/10,人工智能,85,回顾：树式搜索一般算法（1）,树式搜索例对于已存在于OPEN表中的节点（如果有的话）也删除之；删除之前要比较其返回初始节点的新路径与原路径，如果新路径短，则修改这些节点在OPEN表中的原返回指针，使其沿原路径返回。,Path1,Path2,S0,m,n,P,先扩展,后扩展,P在n之前已是某一节点m的后继,如图所示：说明从S0P至少有两条路，这时有两种情况：f（Path2）f（Path1），当前路径较好，要修改P的指针，使其指向n，即搜索之后的最佳路径。否则，原路径好。,2023/8/10,人工智能,86,回顾：树式搜索一般算法（2）,对已存在于CLOSED表的节点，作与（2）同样的处理，并将其移出CLOSED表，放入OPEN表中重新扩展。,S0,过去生成P的路径,现在生成P的路径,过去对Ps的最优路径,Ps,P,m,n,k,a.P在n之前已是某一节点m的后继，所以需要做如同（2）同样的处理，如图右部所示。b.P在Closed表中，说明P的后继也在n之前已经生成，称为Ps。对Ps而言同样可能 由于nP这一路径的加入，又必须比较多条路径之后而取代价小的一条，如图左部所示。,2023/8/10,人工智能,87,启发式图搜索的A算法和A*算法（4）,f（x）g（x）h（x）,探讨九宫重排问题的估价函数的设计过程。,g（x）：对某一确定的节点，是确定的值。,h（x）：不同的问题启发函数的定义不同，相同的问题也可以定义出不同的启发函数。,衡量h（x）优劣的标准是看其是否能够准确反映出节点x到达目标的难易程度（距离）。,3.估价函数定义探讨,2023/8/10,人工智能,88,启发式图搜索的A算法和A*算法（5）,九宫重排问题（八数码难题）,将棋局用向量A(X0，X1，X2，X3，X4，X5，X6，X7，X8)表示，其中Xi为变量，值表示方格Xi内的数字。初始状态 S0（0，2，8，3，4，5，6，7，1）目标状态 Sg（0，1，2，3，4，5，6，7，8）数码的移动规则就是该问题的状态变化规则。经分析，该问题共有24条规则，分为9组。,初始棋局,目标棋局,2023/8/10,人工智能,89,启发式图搜索的A算法和A*算法（6）,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组规则 r5(X1=0)(X2=n)X1=n X2=0；r6(X1=0)(X8=n)X1=n X8=0；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；,2023/8/10,人工智能,90,启发式图搜索的A算法和A*算法（7）,例1：九宫重排问题如下图所示初始节点S0与目标节点Sg。,估价函数f（x）g（x）h（x）,因素1 格局中将牌是否在家,g(x)用节点深度d（x）来衡量,如何定义？,h（x）用 x的格局与目标节点格局相比，不在家的将牌数目w(x)来衡量。,4,2,3,6,5,2 8 3 1 47 6 5,4,4,2 8 31 47 6 5,5,5,5,6,4,6,4,1 2 37 8 4 6 5,6,1 2 38 47 6 5,4,1,扩展顺序,f(x)值,2023/8/10,人工智能,92,启发式图搜索的A算法和A*算法（9）,8 1 26 37 5 4,a,问题:是否对于所有的节点w(x)都能反映出从x节点变化到目标节点的难易程度（到目标的距离）？,w(a)=7 w(b)=6,从w（x）值看a格局离目标格局更远。,a格局真的比b格局距离目标更远吗？,8 1 26 37 5 4,a,8 1 2 6 37 5 4,1 28 6 37 5 4,1 28 6 37 5 4,1 28 6 37 5 4,1 2 38 67 5 4,1 2 38 6 47 5,1 2 38 6 47 5,w(a)=7,实际距离为8,1,2,3,4,5,6,7,8,2 8 14 37 6 5,2 8 1 4 37 6 5,8 12 4 37 6 5,8 12 4 37 6 5,8 12 4 37 6 5,2 8 14 6 37 5,8 1 3 2 4 7 6 5,8 1 32 4 7 6 5,1 38 2 4 7 6 5,1 38 2 4 7 6 5,1 2 38 4 7 6 5,8 1 32 47 6 5,w(b)=6,实际距离为11,1,2,3,4,5,6,7,8,9,10,11,2023/8/10,人工智能,95,启发式图搜索的A算法和A*算法（12）,w（x）并不能很好地反映从x节点变化到目标节点的难易程度。w(x)启发信息不够。,因素2 格局中将牌离家的