图搜索技术(启发式)

《图搜索技术(启发式)》由会员分享，可在线阅读，更多相关《图搜索技术(启发式)（84页珍藏版）》请在金锄头文库上搜索。

1、第4章 图搜索技术 第4章 图搜索技术 4.1 状态图搜索4.2 状态图问题求解4.3 与或图搜索 4.4 与或图问题求解4.5 博弈树搜索第4章 图搜索技术 4.1.4 启发式搜索1问题的提出 前面我们讲的穷举搜索法，从理论上讲，似乎可以解决任何状态空间的搜索问题，但实践表明，穷举搜索只能解决一些状态空间很小的简单问题，而对于那些大状态空间问题，穷举搜索就不能胜任了。因为 大空间问题，往往会导致“组合爆炸”。 第4章 图搜索技术 2. 启发性信息启发式搜索就是利用启发性信息进行制导的搜索。启发性信息就是有利于尽快找到问题之解的信息。按其用途划分，启发性信息一般可分为以下三类：(1)用于扩展节

2、点的选择，即用于决定应先扩展哪一个节点，以免盲目扩展。(2)用于生成节点的选择，即用于决定应生成哪些后续节点，以免盲目地生成过多无用节点。(3)用于删除节点的选择，即用于决定应删除哪些无用节点，以免造成进一步的时空浪费。第4章 图搜索技术 一般来说启发信息过弱，产生式系统在找到一条路径之前将扩展过多的节点，即求得解路径所需搜索的耗散值（搜索花费的工作量）较大；相反引入强的启发信息，有可能大大降低搜索工作量，但不能保证找到最小耗散值的解路径（最佳路径），因此实际应用中，希望最好能引入降低搜索工作量的启发信息而不牺牲找到最佳路径的保证。第4章 图搜索技术 比较不同搜索方法的效果可用启发能力的强弱来

3、度量。在大多数实际问题中，人们感兴趣的是使路径的耗散值和求得路径所需搜索的耗散值两者的某种组合最小，更一般的情况是考虑搜索方法对求解所有可能遇见的问题，其平均的组合耗散值最小。如果搜索 方法1的平均组合耗散值比方法2的平均组合耗散值低，则认为方法1比方法2有更强的启发能力。实际上很难给出一个计算平均组合耗散值的方法，因此启发能力的度量也只能根据使用方法的实际经验作出判断，没有必要去追求严格的比较结果。第4章 图搜索技术 启发式搜索过程中，要对OPEN表进行排序，这就需要有一种方法来计算待扩展节点有希望通向目标节点的不同程度，我们总是希望能找到最有希望通向目标节点的待扩展节点优先扩展。一种最常用

4、的方法是定义一个评价函数（Evaluation function）对各个子节点进行计算，其目的就是用来估算出“有希望”的节点来。第4章 图搜索技术 3. 启发函数在启发式搜索中，通常用所谓启发函数来表示启发性信息。启发函数是用来估计搜索树上节点x与目标节点Sg接近程度的一种函数，通常记为h(x)。 第4章 图搜索技术 如何定义一个启发函数呢？启发函数并无固定的模式，需要具体问题具体分析。通常可以参考的思路有：一个节点到目标节点的某种距离或差异的度量；一个节点处在最佳路径上的概率；或者根据经 验的主观打分等等。例如，对于八数码难题，用h(x)就可表示节点x的数码格局同目标节点相比，数码不同的位置

5、个数。 第4章 图搜索技术 4.启发式搜索算法启发式搜索要用启发函数来导航，其搜索算法就要在状态图一般搜索算法基础上再增加启发函数值的计算与传播过程，并且由启发函数值来确定节点的扩展顺序。为简单起见，下面我们仅给出树型图的树式搜索的两种策略。 第4章 图搜索技术 1) 全局择优搜索全局择优搜索就是利用启发函数制导的一种启发式搜索方法。该方法亦称为最好优先搜索法，它的基 本思想是：在OPEN表中保留所有已生成而未考察的节点，并用启发函数h(x)对它们全部进行估价，从中选出最优节点进行扩展，而不管这个节点出现在搜索树的什么地方。第4章 图搜索技术 例4.5 用全局择优搜索法解八数码难题。初始棋局和

6、目标棋局同例3。解 设启发函数h(x)为节点x的格局与目标格局相比数码不同的位置个数。以这个函数制导的搜索树如图 47所示。图中节点旁的数字就是该节点的估价值。由图可见此八数问题的解为：第4章 图搜索技术 图47 八数码问题的全局择优搜索 第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的返回

7、指针后放入OPEN表中，再对OPEN表中的所有子节点按其函数值大小以升序排序，转步2。第4章 图搜索技术 2) 局部择优搜索局部择优搜索与全局择优搜索的区别是，扩展节点N后仅对N的子节点按启发函数值大小以升序排序，再将它们依次放入OPEN表的首部。故算法从略。 第4章 图搜索技术 4.1.5 加权状态图搜索1. 加权状态图与代价树例4.6 图48(a)是一个交通图，设A城是出发地，E城是目的地，边上的数字代表两城之间的交通费。试求从A到E最小费用的旅行路线。 第4章 图搜索技术 图48 交通图及其代价树 第4章 图搜索技术 可以看出，这个图与前面的状态图不同的地方是边上附有数值。它表示边的一种

8、度量（此例中是交通费，当然也可以是距离）。一般地，称这种数值为权值，而把边上附有数值的状态图称之为加权状态图或赋权状态图。 第4章 图搜索技术 显然，加权状态图的搜索与权值有关，并且要用权值来导航。具体来讲，加权状态图的搜索算法，要在一般状态图搜索算法基础上再增加权值的计算与传播过程，并且要由权值来确定节点的扩展顺序。同样，为简单 起见，我们先考虑树型的加权状态图代价树的搜索。所谓代价，可以是两点之间的距离、交通费用或所需 时间等等。通常用g(x)表示从初始节点S0到节点x的代价，用c(xi,xj)表示父节点xi到子节点xj的代价，即边(xi,xj)的代价。从而有g(xj)g(xi)c(xi,

9、xj)而 g(S0)0第4章 图搜索技术 也可以将加权状态图转换成代价树来搜索，其转换方法是，从初始节点起，先把每一个与初始节点相邻的节点作为该节点的子节点；然后对其他节点依次 类推，但对其他节点x，不能将其父节点及祖先再作为x的子节点。例如，把图48(a)所示的交通图转换成代价树如图48(b)所示。 第4章 图搜索技术 2.分支界限法(最小代价优先法)其基本思想是：每次从OPEN表中选出g(x)值最小的节点进行考察，而不管这个节点在搜索树的什么位置上。可以看出，这种搜索法与前面的最好优先法（即全局择优法）的区别仅是选取扩展节点的标准不同， 一个是代价值g(x)（最小），一个是启发函数值h(x

10、)（最小）。这就是说，把最好优先法算法中的h(x)换成g(x)即得分支界限法的算法。 第4章 图搜索技术 分支限界法的基本思想分支限界法常以广度优先或以最小耗费（最大效益）优先的方式搜索问题的解空间树。在分支限界法中，每一个活结点只有一次机会成为扩展结点。活结点一旦成为扩展结点，就一次性产生其所有儿子结点。在这些儿子结点中，导致不可行解或导致非最优解的儿子结点被舍弃，其余儿子结点被加入活结点表中。从活结点表中取下一结点成为当前扩展结点，并重复上述结点扩展过程。这个过程一直持续到找到所需的解或活结点表为空时为止。第4章 图搜索技术 常见的两种分支限界法（1）队列式(FIFO)分支限界法按照队列先

11、进先出（FIFO）原则选取下一个节点为扩展节点。 （2）优先队列式分支限界法按照优先队列中规定的优先级选取优先级最高的节点成为当前扩展节点。第4章 图搜索技术 第4章 图搜索技术 第4章 图搜索技术 第4章 图搜索技术 3.最近择优法(瞎子爬山法)同上面的情形一样，这种方法实际同局部择优法类似，区别也仅是选取扩展节点的标准不同，一个是 代价值g(x)（最小），一个是启发函数值h(x)（最小）。这就是说，把局部择优法算法中的h(x)换成g(x)就可得最近择优法的算法。 现在我们用代价树搜索求解例4.6中给出的问题。我们用分支界限法得到的路径为ACDE这是一条最小费用路径(费用为8)。 第4章 图

12、搜索技术 4.1.6 启发式图搜索的A算法和A*算法前面我们介绍了图搜索的一般算法，并着重讨论了树型图的各种搜索策略。本节我们给出图搜索的两种典型的启发式搜索算法。1.估价函数利用启发函数h(x)制导的启发式搜索，实际是一种深度优先的搜索策略。虽然它是很高效的，但也可 能误入歧途。 第4章 图搜索技术 所以，为了更稳妥一些，人们把启发函数扩充为估价函数。估价函数的一般形式为：f(x)g(x)h(x)其中g(x)为从初始节点S0到节点x已经付出的代价，h(x)是启发函数。即估价函数f(x)是从初始节点S0到达节点x处已付出的代价与节点x到达目标节点Sg的接近程度估计值之总和。有时估价函数还可以表

13、示为f(x)d(x)h(x)第4章 图搜索技术 f (n) = g (n) + h (n)h (n)体现了搜索的启发信息。如果 h (n)=0，g (n)=d (n) 时，就是广度优先搜索法。一般在 f(n) 中，g(n)的比重越大，越倾向于广度优先搜索；h(n)的比重越大，越倾向于深度优先搜索。有了f(n)，就可以对各个待扩展结点的价值进行估计，从OPEN表中选择出最有希望的结点扩展。第4章 图搜索技术 2. A算法A算法是基于估价函数f(x)的一种加权状态图启发式搜索算法。其具体步骤如下：步1 把附有f(S0)的初始节点S0放入OPEN表；步2 若OPEN表为空，则搜索失败，退出。步3 移

14、出OPEN表中第一个节点N放入CLOSED表 中，并冠以顺序编号n；步4 若目标节点Sg=N，则搜索成功，结束。步5 若N不可扩展，则转步2； 步6 扩展N，生成一组附有f(x)的子节点 ，对这些 子节点按mj,mk,ml三类分别进行处理，并对Open表中的节点重新排序。第4章 图搜索技术 A算法求解八数码 问题的搜索树第4章 图搜索技术 第4章 图搜索技术 搜索中的数据结构不同于广度优先搜索使用的队，也不同于深度优先搜索使用的栈，而是一个按结点 的 f 值的大小为序排列的一个表，有时也称为“优先队”。进入优先队的结点不是简单地排在队末尾，而是根据其 f 值的大小插入队中合适的位置。每次从队中

15、优先取出f 值最小的结点加以扩展。第4章 图搜索技术 例：一个结点有多条通道的搜索树的有序搜索过程：设 g 为已搜索的路程代价h 为将要付出的估计代价(a) AJIHDCBEGF初始结点目标结点h=3h=1h=0h=1h=2h=2h=2h=3h=3h=4第4章 图搜索技术 (c)(b) Ag=0h=3f=3g=1h=4f=5g=1h=2f=3g=1h=3f=4优先队：FBHFHBA设g 为已搜索的路程代价 h 为将付出的估计代价算出 f 值对OPEN 表重排序AJIHDCBEGF初始结点目标结点h=3h=1h=0h=1h=2h= 2h=2h=3h=3h=4第4章 图搜索技术 (d)g=1h=4

16、f=5g=2h=1f=3g=1h=3f=4DHBAF优先队：DBH算出f值对OPEN表重排序AJIHDCBEGF初始结点目标结点h=3h=1h=0h=1h=2h= 2h=2h=3h=3h=4第4章 图搜索技术 g=1h=4f=5g=3h=0f=3g=1h=3f=4EHBADFGg=3h=1f=4目 标 结 点(e)AJIHDCBEGF初始结点目标结点h=3h=1h=0h=1h=2h= 2h=2h=3h=3h=4第4章 图搜索技术 当搜索开始时，树根结点进入优先队中，因为队中只有一个结点，故无序可排。 图中的h值虽标为精确值，实际上应为估算值。结点按 f 的大小送入优先队中。 下一个要扩展的结点是队中 f 值最小的结点。 启发式搜索的一般规则 :根据规则生成当前结点的子状态。检查每个状态是否已在open表或closed表, 防止循环。每个状态n都赋以f(n)值。Open表中的状态按f值排序。通过保存这些状态,能从一无效路径上