《人工智能3第3章》由会员分享，可在线阅读，更多相关《人工智能3第3章（230页珍藏版）》请在金锄头文库上搜索。
1、第3章 图搜索与问题求解,图搜索技术是人工智能中的一个核心技术之一，人工智能的许多分支领域都涉及到图搜索。这里的图是指由节点和有向边组成的网络。按连接同一节点的各边间的逻辑关系划分，图又可分为或图(也称直接图)和与或图两大类。从而，图搜索也就分为或图搜索和与或图搜索两大类。或图通常称为状态图。3.1 状态图搜索；3.2 状态图问题求解3.3 与或图搜索；3.4 与或图问题求解3.5 博弈树搜索,3.1 状态图搜索3.1.1 状态图3.1.2 状态图搜索1.搜索方式， 2.搜索策略， 3.搜索算法3.1.3 穷举式的搜索1.广度优先搜索， 2. 深度优先搜索，3.有界深度优先搜索3.1.4 启发
2、式搜索3.1.5 加权状态图搜索3.1.6 启发式图搜索的A算法和A*算法3.1.7 状态图搜索策略小结,如图31就是一个迷宫。如果我们把该迷宫的每一个格子以及入口和出口都作为节点，把通道作为边，则该迷宫可以由一个有向图表示(如图32所示)。,3.1 状态图搜索,3.1.1. 状态图我们通过例子引入状态图的概念。例3.1. 走迷宫是人们熟悉的一种游戏，,3.1 状态图搜索,3.1.1. 状态图我们通过例子引入状态图的概念。例3.1. 走迷宫是人们熟悉的一种游戏，,那么，走迷宫其实就是从该有向图的初始节点(入口)出发，寻找目标节点(出口)的问题，或者是寻找通向目标节点(出口)的路径的问题。,3.
3、1.1. 状态图例3.2 在一个33的方格棋盘上放置着1，2，3，4，5，6，7，8八个数码，每个数码占一格，且有一个空格。,这些数码可在棋盘上移动，其移动的规则是：与空格相邻的数码方可移入空格。现在的问题是：对于指定的初始棋盘和目标棋盘（如图33所示），给出数码的移动序列。,3.1.1. 状态图例3.2 在一个33的方格棋盘上放置着1，2，3，4，5，6，7，8八个数码，每个数码占一格，且有一个空格。,a,例3.3 例3.5,图33 八数码问题示例,该问题称为八数码难题或重排九宫问题。,3.1.1. 状态图可以想象，如果我们把一个棋局作为一个节点，相邻的节点就可以通过移动数码，一个一个地产生
4、出来。这样，所有节点就可由它们的相邻关系连成一个有向图。可以看出，图中的一条边(即相邻两个节点的连线)就是对应一次数码移动，反之，一次数码移动也就对应着图中的一条边。而数码移动是按数码的移动规则进行的。所以，图中的一条边也就代表一个移动规则或者移动规则的一次执行。于是，这个八数码问题也就是要在该有向图中寻找目标节点，或找一条从初始节点到目标节点的路径问题。,3.1.1. 状态图以上两个问题虽然内容不同，但抽象地来看，它们都是在某个有向图中寻找目标或路径的问题。人工智能科学中，把这种描述问题的有向图称为状态空间图，简称状态图。之所以称为状态图，是因为图中的节点代表问题中的一种格局，一般称为问题的
5、一个状态；边表示两节点之间的某种联系，如它可以是某种操作、规则、变换、算子、通道或关系等等。在状态图中，从初始节点到目标节点的一条路径，或者所找的目标节点，就是相应问题的一个解。根据实际需要，路径解可以表示为边的序列或节点的序列。例如，上面例3.1的解可以是节点序列，而例3.2的解可以是边(即棋步)序列。,3.1.1. 状态图状态图实际上是一类问题的抽象表示。事实上，有许多智力问题(如梵塔问题、旅行商问题、八皇后问题、农夫过河问题等)和实际问题(如路径规划、定理证明、演绎推理、机器人行动规划等)都可以归结为在某一状态图中寻找目标或路径的问题。因此，研究状态图搜索具有普遍意义。梵塔问题（P.63
6、例3. 9） 旅行商问题TSP（P.65例2.10） 八皇后问题（P.85第13题） 农夫过河问题（P.84第6题）,3.1.2. 状态图搜索在状态图中寻找目标或路径的基本方法就是搜索。所谓搜索，就是从初始节点出发，沿着与之相连的边试探前进，寻找目标节点的过程(也可以反向进行)。当目标节点找到后，路径也就找到了。所以，寻找目标和寻找路径是一致的。由于图中有许多节点和边，因此，搜索过程中，经过的节点和边，按图的连接关系，便会构成一个树型的有向图。这种树型有向图称为搜索树。随着搜索的进行，搜索树会不断地生长，直到当搜索树中出现目标节点时，搜索便停止。这时从搜索树中就可容易地找出从初始节点到目标节点
7、的路径来。所以，在搜索过程中应当随时记录搜索轨迹。如何用计算机来实现上述搜索？我们从三方面介绍：1.搜索方式2.搜索策略 3.搜索算法,3.1.2. 状态图搜索1.搜索方式用计算机来实现状态图的搜索，有两种最基本的方式：树式搜索和线式搜索。树式搜索，就是以“画树”的方式进行搜索。即从树根(初始节点)出发，一笔一笔地描出一棵树来。准确地讲，树式搜索就是在搜索过程中记录所经过的所有节点和边。所以，树式搜索所记录的轨迹始终是一棵“树”，这棵树也就是搜索过程中所产生的搜索树。线式搜索，就是以“画线”的方式进行搜索。线式搜索在搜索过程中只记录那些当前处在寻找路径上的节点和边。所以，线式搜索记录的轨迹始终
8、是一条“线”(折线)。线式搜索的基本方式又可分为不回溯和可回溯两种。,3.1.2. 状态图搜索1.搜索方式不回溯的线式搜索：每到一个“叉路口”，仅沿其中的一条路继续前进，即对每一个节点始终都仅生成一个子节点(如果有子节点的话)。生成子节点也称对节点进行扩展。如果扩展到某一个节点，该节点恰好就是目标节点，则搜索成功；如果直到不能再扩展时，还未找到目标节点，则搜索失败。可回溯的线式搜索:每一个节点都仅扩展一条边(生成一个子节点)，但是，当不能再扩展时，则退回到上一个节点，然后再扩展另一条边(如果有的话)。这样，要么最终找到了目标节点，搜索成功；要么一直回溯到初始节点也未找到目标节点，则搜索失败。,
9、3.1.2. 状态图搜索1.搜索方式树式搜索成功后，还需再从搜索树中找出所求路径，而线式搜索只要搜索成功，则“搜索线”就是所找的路径，即问题的解。那么，又怎样从搜索树中找出所求路径呢？这只需在扩展节点时记住节点间的父子关系即可。这样，当搜索成功时，从目标节点反向沿搜索树按所作的标记追溯回去，一直到初始节点，便可得到一条从初始节点到目标节点的路径，即问题的一个解。,3.1.2. 状态图搜索2.搜索策略由于搜索具有探索性，所以要提高搜索效率(尽快地找到目标节点) 就必须注意搜索策略。对于状态图搜索，大体可分为盲目搜索和启发式搜索两大类。树式盲目搜索就是穷举式搜索；而线式盲目搜索，对于不回溯就是随机
10、碰撞式搜索，对于可回溯也是穷举式的搜索。启发式搜索则是利用“启发性信息”引导的搜索。所谓“启发性信息”，就是与问题有关的，有利于尽快找到问题解的信息或知识。例如：“欲速则不达”、“知已知彼，百战不殆”、“学如逆水行舟不进则退”等格言，都是指导人们行为的启发性信息。根据启发性信息使用方式的不同，启发式搜索又可分为：全局择优、局部择优等等。按搜索范围的扩展顺序的不同，搜索又可分为广度优先和深度优先两种类型。对于树式搜索，既可深度优先进行，也可广度优先进行。对于线式搜索则总是深度优先进行。,3.1.2. 状态图搜索3.搜索算法搜索的目的是为了寻找初始节点到目标节点的路径，所以在搜索过程中需要随时记录
11、搜索轨迹。为此，我们用一个称为CLOSED表的动态数据结构来专门记录考查过的节点。另一方面，对于树式搜索来说，还得不断地把待考查的节点组织在一起，并做某种排列，以便控制搜索的方向和顺序。为此，我们采用一个称为OPEN的动态数据结构，来专门登记当前待考查的节点。OPEN表和CLOSED表的结构如图34所示。,下面我们给出树式搜索和线式搜索的一般算法。,3.1.2. 状态图搜索3.搜索算法树式搜索算法： 步1 把初始节点So放入OPEN表中； 步2 若OPEN表为空，则搜索失败，退出。 步3 移出OPEN表中第一个节点N放入CLOSED表中，并冠以顺序编号n； 步4 若目标节点SgN，则搜索成功，
12、结束。 步5 若N不可扩展，则转步2； 步6 扩展N，生成一组子节点，对这组子节点作如下处理；(1)删除N的先辈节点(如果有的话)； (2)对已存在于OPEN表的节点(如果有的话)也删除之；但删除之前要比较其返回初始节点的新路径与原路径，如果新路径“短”，则修改这些节点在OPEN表中的原返回指针，使其沿新路返回；(3)对已存在于CLOSED表的节点(如果有的话)，作与(2)同样的处理，并且再将其移出CLOSED表，放入OPEN表重新扩展(为了重新计算代价)；(4)对其余子节点配上指向N的返回指针后放入OPEN表中某处，或对OPEN表进行重新排序，转步2。,3.1.2. 状态图搜索3.搜索算法树
13、式搜索算法： 步6 扩展N，生成一组子节点，对这组子节点作如下处理；(1)删除N的先辈节点(如果有的话)； (2)对已存在于OPEN表的节点(如果有的话)也删除之；但删除之前要比较其返回初始节点的新路径与原路径，如果新路径“短”，则修改这些节点在OPEN表中的原返回指针，使其沿新路返回；(3)对已存在于CLOSED表的节点(如果有的话)，作与(2)同样的处理，并且再将其移出CLOSED表，放入OPEN表重新扩展(为了重新计算代价)；(4)对其余子节点配上指向N的返回指针后放入OPEN表中某处，或对OPEN表进行重新排序，转步2。说明：(1)这里的返回指针也就是父节点在CLOSED表中的编号。(
14、2)步6中修改返回指针的原因，是因为这些节点又被第二次生成，所以它们返回初始节点的路径已有两条，但这两条路径的“长度”可能不同。那么，当新路短时自然要走新路。,3.1.2. 状态图搜索3.搜索算法树式搜索算法： 步6 扩展N，生成一组子节点，对这组子节点作如下处理；(1)删除N的先辈节点(如果有的话)； (2)对已存在于OPEN表的节点(如果有的话)也删除之；但删除之前要比较其返回初始节点的新路径与原路径，如果新路径“短”，则修改这些节点在OPEN表中的原返回指针，使其沿新路返回；(3)对已存在于CLOSED表的节点(如果有的话)，作与(2)同样的处理，并且再将其移出CLOSED表，放入OPE
15、N表重新扩展(为了重新计算代价)；(4)对其余子节点配上指向N的返回指针后放入OPEN表中某处，或对OPEN表进行重新排序，转步2。说明：(3)这里对路径的长短是按路径上的节点数来衡量的，后面我们将会看到路径的长短也可以其“代价”(如距离、费用、时间等)衡量。若按其代价衡量，则在需修改返回指针的同时还要修改相应的代价值，或者不修改返回指针也要修改代价值(为了实现代价小者优先扩展)。,3.1.2. 状态图搜索3.搜索算法线式搜索算法：不回溯的线式搜索(P.53) 步1；步2；步3 ；步4 ；步5 ；可回溯的线式搜索(P.53) 步1；步2；步3 ；步4 ；步5 ；上述算法仅是搜索目标节点的算法，
16、当搜索成功后，需要指出路径，则还须由CLOSED表再找出路径。找路径的方法是：对于树式搜索，从CLOSED表中序号最大的节点起，根据返回指针追溯至初始节点So，所得的节点序列或边序列即为所找路径；对于线式搜索，CLOSED表即是所找路径。,3.1.3.穷举式的搜索为简单起见，下面我们先讨论树型结构的状态图搜索，并仅限于树式搜索。按搜索树生成方式的不同，树式穷举搜索又分为广度优先和深度优先两种搜索方式。这两种方式也是最基本的树式搜索策略，其他搜索策略都是建立在它们之上的。下面先介绍广度优先搜索。1.广度优先搜索广度优先搜索就是始终先在同一级节点中考查，只有当同一级节点考查完之后，才考查下一级节点。或者说，是以初始节点为根节点，向下逐级扩展搜索树。所以，广度优先策略的搜索树是自顶向下一层一层逐渐生成的。,3.1.3.穷举式的搜索1.广度优先搜索例3.3 用广度优先搜索策略解八数码难题。由于把一个与空格相邻的数码移入空格，等价于把空格向数码方向移动一位。所以，该题中给出的数码走步规则也可以简化为：对空格可施行左移、右移、上移和下移(改为左移、上移、右移和下移)等四种操作。设初始节点So和目标节点Sg分别如图33的初始棋局和目标棋局所示，我们用广度优先搜索策略，则可得到如图36所示的搜索树。广度优先搜索算法：(P.54)步1；步2；步3 ；步4 ；步5 ；步6 ；,
