人工智能中图搜索算法159.pdf

,。。,图可分为或图(直接图)和与或图两类。。,如图4—1就是一个迷宫。如果我们把该迷宫的每一个格子以及入口和出口都作为节点,把通道作为边,则该迷宫可以由一个有向图表示(如图4—2所示)。那么,走迷宫其实就是从该有向图的初始节点(入口)出发,寻找目标节点(出口)的问题,或者是寻找通向目标节点(出口)的路径的问题。第2页第4章图搜索技术S1S2S3S4S5S6S0S7S8S9Sg图4—1迷宫图第3页第4章图搜索技术S1S2S3S0S4S5S6S7S8S9Sg图4—×3的方格棋盘上放置着1,2,3,4,5,6,7,8八个数码,每个数码占一格,且有一个空格。这些数码可在棋盘上移动,其移动规则是:与空格相邻的数码方可移入空格。现在的问题是:对于指定的初始棋局和目标棋局(如图4—3所示),给出数码的移动序列。该问题称为八数码难题或重排九宫问题。第5页第4章图搜索技术2838131424765765初始棋局目标棋局图4—3八数码问题第6页第4章图搜索技术2832831414765765初始棋局中间棋局23283**********中间棋局中间棋局图4—3—1八数码棋局移动规则第7页第4章图搜索技术可以看出,我们把一个棋局作为一个节点,相邻的节点就可以通过移动数码产生出来。这样,所有节点就可由他们的相邻关系连接成一个有向图。可以看出,图中的一条边(即相邻两个节点的连线)就是对应一次数码移动,反之,一次数码移动也对应图中的一条边。而数码移动是按数码的移动规则进行的。所以,图中的一条边也就代表一个移动规则或移动规则的一次执行。于是,这个把数码问题就是要在该有向图中寻找目标节点,或找一条从初试节点到目标节点的路径问题。第8页第4章图搜索技术28311476523452832328328314184141647657657657567891011121383283232328283283283214714184184143145164164765657657657657675751415161718192021832831232342828328328321471484181431456416765657657657657617574522238381321424765765图4—5八数码问题的广度优先搜索第9页第4章图搜索技术以上两个问题都是在某个有向图中寻找目标或路径问题,这种问题图搜索问题。把描述问题的有向图称为状态空间图,简称状态图。图中的节点代表问题中的一种格局,一般称为问题的一个状态,边表示两个状态之间的联系。在状态图中,从初始节点到目标节点的一条路径或者所找到的目标节点,就是问题的解(路径解)。状态图实际上是一类问题的抽象表示。事实上,有许多智力问题(如梵塔问题、旅行商问题、八皇后问题、农夫过河问题等)和实际问题(如路径规划、定理证明、演绎推理、机器人行动规划等)都可以归结为在某一状态图中寻找目标或路径的问题。因此,研究状态图搜索具有普遍意义。第10页