人工智能中图搜索算法159

第4章图搜索技术第1页第4章图搜索技术4.1状态图搜索4.2状态图问题求解4.3与或图搜索4.4与或图问题求解4.5博弈树搜索图搜索是人工智能的核心技术之一，人工智能的许多分支领域都涉及到图搜索。这里的图是指节点和有向边组成的网络。按连接同一节点的各边间的逻辑关系，图可分为或图（直接图）和与或图两类。第4章图搜索技术第2页4.1状态图搜索4.1.1状态图我们通过例子引入状态图的概念。例4.1走迷宫是人们熟悉的一种游戏，如图4—1就是一个迷宫。如果我们把该迷宫的每一个格子以及入口和出口都作为节点，把通道作为边，则该迷宫可以由一个有向图表示(如图4—2所示)。那么，走迷宫其实就是从该有向图的初始节点(入口)出发，寻找目标节点(出口)的问题，或者是寻找通向目标节点(出口)的路径的问题。第4章图搜索技术第3页图4—1迷宫图S1S2S3S4S5S6S7S8S9S0Sg第4章图搜索技术第4页图4—2迷宫的有向图表示S1S2S3S4S5S6S7S8S9S0Sg第4章图搜索技术第5页例4.2在一个3×3的方格棋盘上放置着1,2,3,4,5,6,7,8八个数码，每个数码占一格，且有一个空格。这些数码可在棋盘上移动，其移动规则是：与空格相邻的数码方可移入空格。现在的问题是：对于指定的初始棋局和目标棋局(如图4—3所示)，给出数码的移动序列。该问题称为八数码难题或重排九宫问题。第4章图搜索技术第6页图4—3八数码问题2831476581324765初始棋局目标棋局第4章图搜索技术第7页图4—3—1八数码棋局移动规则2831476528314765初始棋局中间棋局2318476528314765中间棋局中间棋局第4章图搜索技术第8页可以看出，我们把一个棋局作为一个节点，相邻的节点就可以通过移动数码产生出来。这样，所有节点就可由他们的相邻关系连接成一个有向图。可以看出，图中的一条边（即相邻两个节点的连线）就是对应一次数码移动，反之，一次数码移动也对应图中的一条边。而数码移动是按数码的移动规则进行的。所以，图中的一条边也就代表一个移动规则或移动规则的一次执行。于是，这个把数码问题就是要在该有向图中寻找目标节点，或找一条从初试节点到目标节点的路径问题。第4章图搜索技术第9页图4—5八数码问题的广度优先搜索22178634582736451827163452282763451238276345114687634512787345126152163458782345817631645827931458276171621786345381635472108354276181654273813542761821786345481356247128456217381546273138136274521202178365452178634511119第4章图搜索技术第10页以上两个问题都是在某个有向图中寻找目标或路径问题，这种问题图搜索问题。把描述问题的有向图称为状态空间图，简称状态图。图中的节点代表问题中的一种格局，一般称为问题的一个状态，边表示两个状态之间的联系。在状态图中，从初始节点到目标节点的一条路径或者所找到的目标节点，就是问题的解（路径解）。状态图实际上是一类问题的抽象表示。事实上，有许多智力问题(如梵塔问题、旅行商问题、八皇后问题、农夫过河问题等)和实际问题（如路径规划、定理证明、演绎推理、机器人行动规划等）都可以归结为在某一状态图中寻找目标或路径的问题。因此，研究状态图搜索具有普遍意义。第4章图搜索技术第11页4.1.2状态图搜索在状态图中寻找目标或路径的基本方法就是搜索。所谓搜索，顾名思义，就是从初始节点出发，沿着与之相连的边试探地前进，寻找目标节点的过程(也可以反向进行)。搜索过程中经过的节点和边，按原图的连接关系，形成树型的有向图，称为搜索树。搜索过程应当随时记录搜索痕迹。1.搜索方式用计算机来实现状态图的搜索，有两种昀基本的方式：树式搜索和线式搜索。所谓树式搜索，形象地讲就是以“画树”的方式进行搜索。即从树根（初始节点）出发一笔一笔地描出来的。第4章图搜索技术第12页准确地讲，树式搜索就是在搜索过程中记录所经过的所有节点和边。所以，树式搜索所记录的轨迹始终是一棵“树”，这棵树也就是搜索过程中产生的搜索树。线式搜索，形象地讲就是以“画线”的方式进行搜索。准确地讲，线式搜索就是在搜索过程中只记录那些当前认为是处在所找路径上的节点和边。所以，线式搜索所记录的轨迹始终是一条“线”（折线）。线式搜索的基本方式可以分为不回溯和可回溯两种。怎样从搜索树中找出所求路径呢？这只需要在扩展节点时记住节点间的父子关系。当搜索成功后从目标节点反向沿搜索树所作标记追溯回去一直到初始节点，便可得到一条从初始节点到目标节点的路径，即问题的一个解。第4章图搜索技术第13页2.搜索策略由于搜索具有探索性，所以要提高搜索效率(尽快地找到目标节点)，或要找昀佳路径(昀佳解)就必须注意搜索策略。对于状态图搜索，已经提出了许多策略，它们大体可分为盲目搜索和启发式（heuristic）搜索两大类。盲目搜索就是无“向导”搜索。树式盲目搜索就是穷举搜索，线式盲目搜索对不可回溯的是随机碰撞搜索，对可回溯的穷举搜索。启发式搜索是有“向导”搜索，利用启发性信息引导的搜索。按搜索范围的扩展顺序不同，搜索又可分为广度优先和深度优先两种搜索。对于树式搜索，既可深度优先进行，也可广度优先进行。对于线式搜索则总是深度优先进行。第4章图搜索技术第14页3.搜索算法由于搜索的目的是为了寻找初始节点到目标节点的路径，所以在搜索过程中就得随时记录搜索轨迹。为此，我们用一个称为CLOSED表的动态数据结构来专门记录考查过的节点。显然，对于树式搜索来说，CLOSED表中存储的正是一棵不断成长的搜索树；而对于线式搜索来说，CLOSED表中存储的是一条不断伸长的折线，它可能本身就是所求的路径(如果能找到目标节点的话)。第4章图搜索技术第15页另一方面，对于树式搜索来说，还得不断地把待考查的节点组织在一起，并做某种排列，以便控制搜索的方向和顺序。为此，我们采用一个称为OPEN表的动态数据结构，来专门登记当前待考查的节点。OPEN表和CLOSED表的结构如图4—4所示。第4章图搜索技术第16页图4—4OPEN表与CLOSED表示例节点父节点编号编号节点父节点编号OPEN表CLOSED表考查过的节点待考查的节点第4章图搜索技术第17页树式搜索算法：步1把初始节点S0放入OPEN表中；步2若OPEN表为空，则搜索失败，退出。步3取OPEN表中前面第一个节点N放入CLOSED表中，并冠以顺序编号n；步4若目标节点Sg=N，则搜索成功，结束。步5若N不可扩展，则转步2；步6扩展N，生成一组子节点，对这组子节点作如下处理：（1）删除N的先辈节点（如果有的话）；（2）对已存在于OPEN表中的节点（如果有的话）也删除掉；但删除之前要比较返回初始节点的新路径与原路径，如果新路径“短”，则修改这些节点在OPEN表中的返回指针，使其沿新路返回；第4章图搜索技术第18页（3）对已存在于CLOSED表中的节点（如果有的话），也作与（2）同样的处理，修改返回指针，并且将其移出CLOSED表，放入OPEN表重新扩展（为了重新计算代价）；（4）对其余子节点配上指向N的返回指针依次放入OPEN表的某处，或对OPEN表进行重新排序，转步2。说明：（1）返回指针是父节点在CLOSED表中的编号；（2）步6修改返回指针的原因是，因为这些节点又被第二次生成；（3）这里对路径的长短是按路径上的节点数来痕量的，还可以按代价（如距离、时间、费用）衡量。第4章图搜索技术第19页4.1.3穷举式搜索为简单起见，下面我们先讨论树型结构的状态图搜索，并仅限于树式搜索。按搜索树生成方式的不同，树式穷举搜索又分为广度优先和深度优先两种搜索方式。这两种方式也是昀基本的树式搜索策略，其他搜索策略都是建立在它们之上的。下面先介绍广度优先搜索。第4章图搜索技术第20页1.广度优先搜索广度优先搜索就是始终先在同一级节点中考查，只有当同一级节点考查完之后，才考查下一级节点。或者说，是以初始节点为根节点，向下逐级扩展搜索树。所以，广度优先策略的搜索树是自顶向下一层一层逐渐生成的。广度优先搜索算法：步1把初始节点S0放入OPEN表中；步2若OPEN表为空，则搜索失败，退出。步3取OPEN表中前面第一个节点N放入CLOSED表中，并冠以顺序编号n；步4若目标节点Sg=N，则搜索成功，结束。第4章图搜索技术第21页步5若N不可扩展，则转步2；步6扩展N，将其所有子节点配上指向N的返回指针依次放入OPEN表的尾部，转步2。其中的OPEN表是一个队列，CLOSED表是一个顺序表，表中各节点按顺序编号，正被考察的节点在表中编号昀大。如果问题有解，OPEN表中必然出现目标节点Sg，那么，当搜索到目标节点Sg时，算法结束，然后根据返回指针在CLOSED表中往回追溯，直至初始节点，所得的路径即为问题的解。广度优先搜索亦称为宽度优先或横向搜索。这种策略是完备的，即如果问题的解存在，用它则一定能找到解，且找到的解还是昀优解（即昀短的路径）。这是优点，缺点是搜索效率低。第4章图搜索技术第22页例4.3用广度优先搜索策略解八数码难题。由于把一个与空格相邻的数码移入空格，等价于把空格向数码方向移动一位。所以，该题中给出的数码走步规则也可以简化为：对空格可施行左移、右移、上移和下移等四种操作。设初始节点S0和目标节点Sg分别如图4—3的初始棋局和目标棋局所示，我们用广度优先搜索策略，则可得到如图4—5所示的搜索树。第4章图搜索技术第23页图4—5八数码问题的广度优先搜索22178634582736451827163452282763451238276345114687634512787345126152163458782345817631645827931458276171621786345381635472108354276181654273813542761821786345481356247128456217381546273138136274521202178365452178634511119第4章图搜索技术第24页2.深度优先搜索深度优先搜索就是在搜索树的每一层始终先只扩展一个子节点，不断地向纵深前进，直到不能再前进(到达叶子节点或受到深度限制)时，才从当前节点返回到上一级节点，沿另一方向又继续前进。这种方法的搜索树是从树根开始一枝一枝逐渐形成的。深度优先搜索算法：步1把初始节点S0放入OPEN表中；步2若OPEN表为空，则搜索失败，退出。第4章图搜索技术第25页步3取OPEN表中前面第一个节点N放入CLOSED表中，并冠以顺序编号n；步4若目标节点Sg=N，则搜索成功，结束。步5若N不可扩展，则转步2；步6扩展N，将其所有子节点配上指向N的返回指针依次放入OPEN表的首部，转步2。其中的OPEN表是一个栈，这是与宽度优先搜索算法的唯一区别。第4章图搜索技术第26页例4.4对于八数码问题，应用深度优先搜索策略，可得如图4—6所示的搜索树。深度优先搜索亦称为纵向搜索。由于一个有解的问题树可能含有无穷分枝，深度优先搜索如果误入无穷分枝(即深度无限)，则不可能找到目标节点。所以，深度优先搜索策略是不完备的。另外，应用此策略得到的解不一定是昀佳解(昀短路径)。第4章图搜索技术第27页图4—6—1八数码问题的深度优先搜索22178634582736451827163452282763451238276345114687634512787345126152163458782345817631645827931458276171621786345381635472108354276181654273813542761821786345481356247128456217381546273138136274521202178365452178634511119第4章图搜索技术第28页图4—6—2八数码问题的深度优