图搜索算法理论基础.pdf

图搜索算法的理论基础 朱全民 图搜索策略 综合数据库 与问题相关的所有数据元素构成的集合 ，用来表述问题 状态或有关事实 。 产生式规则 构建了综合数据库以后 ，还需要研究问题的移动规则， 称为产生式规则 。 搜索策略 搜索策略的实质是确定如何选取规则的方式 。有两种基 本方式 ：一种是不考虑给定问题所具有的特定知识，系 统根据事先确定好某种固定顺序 ，依次调用规则或随机 调用规则 ，这实际上是盲目搜索的方法。另一种是考虑 问题领域可应用的知识，动态地确定规则的排列次序， 优先调用较合适的规则使用 ，这就是通常所说的启发式 搜索策略 。 一些基本概念 节点 ：记录扩展的状态。 1 根节点 弧/边：记录扩展的路径 。 搜索树 ：描述搜索扩展的 整个过程 。 2 3 节点的耗散值 叶子节点 4,5,6,7,8 令C(i,j)为从节点n 到n 的这 i j 段路径 （或者弧）的耗散 4 5 6 7 值,一条路径的耗散值就等 于连接这条路径各节点间 所有弧的耗散值总和 。可 8 以用递归公式描述如下： 搜索树 C(n ,t)= C(n , n )+ C(n , t) i i j j 八数码问题 在3*3组成的九宫格棋盘上 ，摆有八个将牌，每一个将牌 都刻有1—8中的某一个数码。棋盘中留有一个空格，允许 其周围的某一个将牌向空格中移动 ，如右图所示。这样通 过移动将牌就可以不断改变的布局结构 ，给出一个初始布 局（称初始状态 ）和一个目标布局 （称目标状态），问如 何移动将牌，才能实现从初始状态到目标状态的转换。 综合数据库 {P }，其中1=x,y=3，P ∈{0,1,2,3,4,5,6,7,8}，且P 互不相等 xy xy xy 用Pascal语言描述如下： type T8no = array[1..3,1..3]of integer; {棋盘状态 } TList = record {描述一个节点} Father : integer; {父指针} dep : byte; {深度} x , y : byte; {空格的位置} state : T8no; end; const Max=10000; var s, t : T8no; {s为初始状态，t为目标状态} List : array[0..max] of TList; {综合数据库 } 产生式规则