人工智能第4章图搜索技术

第4章图搜索技术第4章图搜索技术4.1状态图搜索4.2状态图问题求解4.3与或图搜索4.4与或图问题求解4.5博弈树搜索第4章图搜索技术4.1状态图搜索4.1.1状态图例4.1如图是一个迷宫。将迷宫的每一个格子以及入口和出口都作为节点，把通道作为边，则该迷宫可以由一个有向图表示。走迷宫其实就是从该有向图的初始节点(入口)出发，寻找目标节点(出口)的路径的问题。S1S2S3S4S5S6S7S8S9S0SgS1S2S3S4S5S6S7S8S9S0Sg第4章图搜索技术例4.2八个数码问题。每个数码占一格，有一个空格。数码在棋盘上移动规则是：与空格相邻的数码方可移入空格。问题：对于指定的初始棋局和目标棋局，给出数码的移动序列。2831476581324765事实上，有许多问题(如梵塔问题、旅行商问题、八皇后问题、农夫过河问题、路径规划、定理证明、演绎推理、机器人行动规划等）都可以归结为在某一状态图中寻找目标或路径的问题。第4章图搜索技术4.1.2状态图搜索在状态图中寻找目标或路径的基本方法就是搜索：从初始节点出发，沿着与之相连的边试探地前进，寻找目标节点的过程(也可以反向进行)。1.搜索方式计算机实现状态图搜索的两种最基本方式：–树式搜索：从树根出发，是以“画树”的方式进行搜索。–线式搜索：在搜索过程中只记录当前走过的节点和边，所形成的轨迹是一条线。进一步可回溯/不可回溯搜索。第4章图搜索技术2.搜索策略搜索具有探索性，要提高搜索效率(尽快地找到目标节点)，或要找最佳路径(最佳解)就必须注意搜索策略。对于状态图搜索，已经提出了许多策略，它们大体可分为盲目搜索和启发式（heuristic）搜索两大类。盲目搜索：无向导启发式搜索：有向导（全局最优/局部最优/最佳图搜索…）对于类树搜索：深度优先/广度优先第4章图搜索技术3.搜索算法框架由于搜索的目的是为了寻找初始节点到目标节点的路径，所以在搜索过程中就得随时记录搜索轨迹。为此，用一个称为CLOSED表的动态数据结构来专门记录考查过的节点。对于树式搜索来说，CLOSED表中存储的是一棵不断成长的搜索树；而对于线式搜索来说，CLOSED表中存储的是一条不断伸长的折线，它可能本身就是所求的路径(如果能找到目标节点的话)。编号节点父节点编号CLOSED表第4章图搜索技术另一方面，对于树式搜索来说，还得不断地把待考查的节点组织在一起，并做某种排列，以便控制搜索的方向和顺序。为此，采用一个称为OPEN表的动态数据结构，来专门登记当前待考查的节点。节点父节点编号OPEN表第4章图搜索技术4.1.3穷举式搜索为简单起见，先讨论树型结构的状态图搜索，并仅限于树式搜索。按搜索树生成方式的不同，树式穷举搜索又分为广度优先和深度优先两种搜索方式。广度优先(WSF)和深度优先(DSF)是最基本的树式搜索策略，其他搜索策略都是建立在它们之上的。第4章图搜索技术1.广度优先搜索广度优先搜索始终先在同一级节点中考查，只有当同一级节点考查完之后，才考查下一级节点。或者说，是以初始节点为根节点，向下逐级扩展搜索树。所以，广度优先策略的搜索树是自顶向下一层一层逐渐生成的。广度优先搜索算法：步1把初始节点S0放入OPEN表中；步2若OPEN表为空，则搜索失败，退出。步3取OPEN表中前面第一个节点N放入CLOSED表中，并冠以顺序编号n；步4若目标节点Sg=N，则搜索成功，结束。步5若N不可扩展，则转步2；步6扩展N，将其所有子节点配上指向N的返回指针依次放入OPEN表的尾部，转步2。第4章图搜索技术例4.3用广度优先搜索策略解八数码难题。由于把一个与空格相邻的数码移入空格，等价于把空格向数码方向移动一位。所以，该题中给出的数码走步规则也可以简化为：对空格可施行左移、右移、上移和下移等四种操作。设初始节点S0和目标节点Sg分别如图4—3的初始棋局和目标棋局所示，我们用广度优先搜索策略，则可得到如图4—5所示的搜索树。第4章图搜索技术图4—5八数码问题的广度优先搜索22178634582736451827163452282763451238276345114687634512787345126152163458782345817631645827931458276171621786345381635472108354276181654273813542761821786345481356247128456217381546273138136274521202178365452178634511119第4章图搜索技术2.深度优先搜索深度优先搜索就是在搜索树的每一层始终先只扩展一个子节点，不断地向纵深前进，直到不能再前进(到达叶子节点或受到深度限制)时，才从当前节点返回到上一级节点，沿另一方向又继续前进。这种方法的搜索树是从树根开始一枝一枝逐渐形成的。深度优先搜索算法：步1把初始节点S0放入OPEN表中；步2若OPEN表为空，则搜索失败，退出。步3取OPEN表头节点N放入CLOSED表中，并冠以顺序编号n；步4若目标节点Sg=N，则搜索成功，结束。步5若N不可扩展，则转步2；步6扩展N，将其所有子节点配上指向N的返回指针依次放入OPEN表的首部，转步2。第4章图搜索技术例4.4对于八数码问题，应用深度优先搜索策略，可得如图4—6所示的搜索树。深度优先搜索亦称为纵向搜索。由于一个有解的问题树可能含有无穷分枝，深度优先搜索如果误入无穷分枝(即深度无限,但解不在该分支内)，则不可能找到目标节点。所以，深度优先搜索策略是不完备的。另外，应用此策略得到的解不一定是最佳解(最短路径)。2178634512178634521786345217863452178634521786345217863452321786345421786345217863455217863456…第4章图搜索技术3.有界深度优先搜索广度优先和深度优先是两种最基本的穷举搜索方法，在此基础上，根据需要再加上一定的限制条件，便可派生出许多特殊的搜索方法。例如有界深度优先搜索。有界深度优先搜索:给出搜索树深度限制，当从初始节点出发沿某一分枝扩展到一限定深度时，就不能再继续向下扩展，而只能改变方向继续搜索。节点x的深度(即其位于搜索树的层数)通常用d(x)表示，则有界深度优先搜索算法如下：第4章图搜索技术步1把S0放入OPEN表中，置S0的深度d(S0)=0；步2若OPEN表为空，则失败，退出。步3取OPEN表头节点N，放入CLOSED表中，并冠以顺序编号n；步4若目标节点Sg=N，则成功，结束。步5若N的深度d(N)=dm(深度限制值)，或者若N无子节点，则转步2；步6扩展N，将其所有子节点Ni配上指向N的返回指针后依次放入OPEN表中前部，置d(Ni)=d(N)+1，转步2。第4章图搜索技术4.1.4启发式搜索1．问题的提出穷举搜索法从理论上，似乎可以解决任何状态空间的搜索问题，但实践表明，穷举搜索只能解决一些状态空间很小的简单问题，而对于那些大状态空间问题，穷举搜索就不能胜任了。因为大空间问题，往往会导致“组合爆炸”。第4章图搜索技术2.启发性信息启发式搜索就是利用启发性信息进行制导的搜索。启发性信息就是有利于尽快找到问题之解的信息。按其用途划分，启发性信息一般可分为以下三类：(1)用于扩展节点的选择，即用于决定应先扩展哪一个节点，以免盲目扩展。(2)用于生成节点的选择，即用于决定应生成哪些后续节点，以免盲目地生成过多无用节点。(3)用于删除节点的选择，即用于决定应删除哪些无用节点，以免造成进一步的时空浪费。第4章图搜索技术3.启发函数在启发式搜索中，通常用所谓启发函数来表示启发性信息。启发函数是用来估计搜索树上节点x与目标节点Sg接近程度的一种函数，通常记为h(x)。定义启发函数：启发函数并无固定的模式，需要具体问题具体分析。通常可以参考的思路有：一个节点到目标节点的某种距离或差异的度量；一个节点处在最佳路径上的概率；或者根据经验的主观打分等等。例如，对于八数码难题，用h(x)就可表示节点x的数码格局同目标节点相比，数码不同的位置个数。4.启发式搜索算法启发式搜索要用启发函数来导航，其搜索算法就要在状态图一般搜索算法基础上再增加启发函数值的计算与传播过程，并且由启发函数值来确定节点的扩展顺序。第4章图搜索技术1)全局择优搜索全局择优搜索就是利用启发函数制导的一种启发式搜索方法。该方法亦称为最好优先搜索法，它的基本思想是：在OPEN表中保留所有已生成而未考察的节点，并用启发函数h(x)对它们全部进行估价，从中选出最优节点进行扩展，而不管这个节点出现在搜索树的什么地方。第4章图搜索技术全局择优搜索算法如下：步1把初始节点S0放入OPEN表中，计算h(So)；步2若OPEN表为空，则搜索失败，退出。步3移出OPEN表中第一个节点N放入CLOSED表中，并冠以序号n；步4若目标节点Sg=N，则搜索成功，结束。步5若N不可扩展，则转步2；步6扩展N，计算每个子节点x的函数值h(x)，并将所有子节点配以指向N的返回指针后放入OPEN表中，再对OPEN表中的所有子节点按其函数值大小以升序排序，转步2。第4章图搜索技术例4.5用全局择优搜索法解八数码难题。初始棋局和目标棋局同例3。解设启发函数h(x)为节点x的格局与目标格局相比数码不同的位置个数。以这个函数制导的搜索树如图4—7所示。图中节点旁的数字就是该节点的估价值。由图可见此八数问题的解为：21786345S02178634521786345217863452178634544S155217863452178634521786345217863455354S2217863452S32178634521786345Sg03八数码问题的全局择优搜索第4章图搜索技术2)局部择优搜索局部择优搜索与全局择优搜索的区别是，扩展节点N后仅对N的子节点按启发函数值大小以升序排序，再将它们依次放入OPEN表的首部。21786345S02178634521786345217863452178634544S1552178634521786345542178634542178634521786345Sg54第4章图搜索技术2.分支界限法(最小代价优先法)g(x):从初始点S0到x的代价；其基本思想是：每次从OPEN表中选出g(x)值最小的节点进行考察，而不管这个节点在搜索树的什么位置上。可以看出，这种搜索法与前面的最好优先法（即全局择优法）的区别仅是选取扩展节点的标准不同，一个是代价值g(x)（最小），一个是启发函数值h(x)（最小）。这就是说，把最好优先法算法中的h(x)换成g(x)即得分支界限法的算法。第4章图搜索技术4.1.5加权状态图搜索——最近择优法(瞎子爬山法)1.加权状态图与代价树例4.6设A城是出发地，E城是目的地，边上的数字代表两城之间的交通费。试求从A到E最小费用的旅行路线。ACBDE324634(a)A34C1B146D2E1D3C332C2E332E4E2B2D12346(b)交通图及其代价树第4章图搜索技术可以看出，这个图与前面的状态图不同的地方是边上附有数值。它表示边的一种度量（此例中是交通费，当然也可以是距离）。一般地，称这种数值为权值，而把边上附有数值的状态图称之为加权状态图或赋权状态图。第4章图搜索技术加权状态图的搜索与权值有关，并且要用权值来导航。具体来讲，加权状态图的搜索算法，要在一般状态图搜索算法基础上再增加权值的计算与传播过程，并且要由权值来确定节点的扩展顺序。为简单起见，先考虑树型的加权状态图——代价树的搜索。所谓代价，可以是两点之间的距离、交通费用或所需时间等等。用g(x)表示从初始节点S0到节点x的代价，用c(xi,xj)表示父节点xi到子节点xj的代价，即边(xi,xj)的代价。从而有g(xj)＝g(xi)＋c(xi,xj)而g(S0)＝0第4章图搜索技术也可以将加权状态图转换成代价树来搜索，其转换方法是，从初始节点起，先把每一个与初始节点相邻的节点作为该节点的子节点；然后对其他节点依次类推