人工智能a算法

精选文档1启发式搜索算法A启发式搜索算法A ，一般简称为 A 算法，是一种典型的启发式搜索算法。其基本思想是：定义一个评价函数 f，对当前的搜索状态进行评估，找出一个最有希望的节点来扩展。评价函数的形式如下：f（n） g（n） h（ n）其中 n 是被评价的节点。f（n）、g（n）和 h（n）各自表述什么含义呢？我们先来定义下面几个函数的含义，它们与f（n）、 g（n）和 h（ n）的差别是都带有一个 * 号。g*(n)：表示从初始节点s 到节点 n 的最短路径的耗散值；h*(n)：表示从节点 n 到目标节点 g 的最短路径的耗散值； f*(n)=g*(n)+h*(n) ：表示从初始节点 s 经过节点 n 到目标节点 g 的最短路径的耗散值。而 f（n）、g（ n）和 h（n）则分别表示是对 f*（n）、g*（ n）和 h*（ n）三个函数值的的估计值。是一种预测。 A 算法就是利用这种预测，来达到有效搜索的目的的。它每次按照 f(n)值的大小对 OPEN 表中的元素进行排序， f 值小的节点放在前面，而 f值大的节点则被放在OPEN 表的后面，这样每次扩展节点时，都是选择当前f 值最小的节点来优先扩展。.精选文档利用评价函数f（ n） g（n） h（n）来排列OPEN 表节点顺序的图搜索算法称为算法A。过程 A OPEN: （ s）， f （s）:g（ s） +h （ s）; LOOP ：IF OPEN （ ）THEN EXIT （ FAIL ）；n: FIRST（ OPEN ）；IF GOAL （ n） THEN EXIT （SUCCESS）； REMOVE （ n， OPEN ）， ADD （n， CLOSED ）； EXPAND （ n） mi ，计算 f（n，mi）g（n，mi）+h（ mi）；g（n，mi）是从 s 通过 n 到 mi 的耗散值， f（n，mi）是从 s 通过n、 mi 到目标节点耗散值的估计。 ADD（ mj，OPEN ），标记 mi 到 n 的指针。 IF f （n，mk）f （ mk）THEN f（mk）:f（ n， mk），标记mk 到 n 的指针；比较f（n，mk）和 f（ mk）， f（mk）是扩展 n之前计算的耗散值。 IF f （n，m1）f （ m1）THEN f（m1）:f（ n， m1），标记m1 到 n 的指针， ADD （m1，OPEN ）；当 f（n，m1）f （ m1）时，把 m1 重放回 OPEN 中，不必考虑修改到其子节点的指针。 OPEN 中的节点按 f 值从小到大排序；GO LOOP ；.精选文档A 算法同样由一般的图搜索算法改变而成。在算法的第 7 步，按照 f 值从小到大对OPEN 表中的节点进行排序，体现了A 算法的含义。算法要计算 f(n)、g(n)和 h(n)的值，g(n)根据已经搜索的结果，按照从初始节点s 到节点 n 的路径，计算这条路径的耗散值就可以了。而 h(n)是与问题有关的，需要根据具体的问题来定义。有了 g(n)和 h(n)的值，将他们加起来就得到f(n)的值了。在介绍一般的图搜索算法时我们就曾经让大家注意过， 在这里我们再强调一次， 请大家注意 A 算法的结束条件： 当从 OPEN 中取出第一节点时，如果该节点是目标节点，则算法成功结束。而不是在扩展一个节点时， 只要目标节点一出现就立即结束。 我们在后面将会看到， 正是由于有了这样的结束判断条件， 才使得A 算法有很好的性质。算法中 f（n）规定为对从初始节点 s 出发，约束通过节点 n 到达目标点 t，最小耗散值路径的耗散值 f*(n) 的估计值，通常取正值。 f（n）由两个分量组成，其中 g（n）是到目前为止，从 s到 n 的一条最小耗散值路径的耗散值， 是作为从 s 到 n 最小耗散值路径的耗散值 g*(n)的估计值， h（ n）是从 n 到目标节点 t，最小耗散值路径的耗散值 h*(n)的估计值。设函数 k（ ni， nj）表示最小耗散路径的实际耗散值（当 ni 到 nj 无通路时则 k（ ni，nj）无意义），则 g*（ n） k（s，n），h*（n） min k（n， ti），其中ti 是目标节点集， k（n，ti）就.精选文档是从 n 到每一个目标节点最小耗散值路径的耗散值，h*（n）是其中最小值的那条路径的耗散值，而具有h*（n）值的路径是n到 ti 的最佳路径。 由此可得 f*（n） g*（n）h*（n）就表示 s ti 并约束通过节点 n 的最佳路径的耗散值。当 ns 时，f*（s）=h*（ s）则表示 s ti无约束的最佳路径的耗散值，这样一来，所定义的 f（n） =g（n）+h （n）就是对 f*(n) 的一个估计。 g（n）的值实际上很容易从到目前为止的搜索树上计算出来， 不必专门定义计算公式，也就是根据搜索历史情况对 g*(n)作出估计，显然有 g(n) g*(n) 。 h(n)则依赖于启发信息，通常称为启发函数，是要对未来扩展的方向作出估计。算法A 是按 f(n)递增的顺序来排列OPEN 表的节点，因而优先扩展f（n）值小的节点，体现了好的优先搜索思想， 所以算法 A 是一个好的优先的搜索策略。图 2.6 表示出当前要扩展节点 n 之前的搜索图，扩展 n 后新生成的子节点 m1（.精选文档 mj ）、 m2（ mk ）、 m3（ m1 ）要分别计算其评价函数值：.精选文档图 2.6 搜索示意图f(m1)=g(m1)+h(m1)f(n，m2)=g(n， m2)+h(m2)f(n，m3)=g(n， m3)+h(m3)然后按第 6 步条件进行指针设置和第7 步重排 OPEN 表节点顺序，以便确定下一次要扩展的节点。用 A 算法来求解一个问题，最主要的就是要定义启发函数h(n)。对于 8 数码问题 ，一种简单的启发函数的定义是：h(n) 不在位的将牌数什么是 不在位的将牌数 呢？我们来看下面的两个图。.精选文档.精选文档其中左边的图是8 数码问题的一个初始状态，右边的图是 8 数码问题的目标状态。 我们拿初始状态和目标状态相比较， 看初始状态的哪些将牌不在目标状态的位置上， 这些将牌的数目之和， 就是不在位的将牌数 。比较上面两个图，发现 1、2、6 和 8 四个将牌不在目标状态的位置上， 所以初始状态的 不在位的将牌数 就是 4，也就是初始状态的 h 值。其他状态的 h 值，也按照此方法计算。下面再以八数码问题为例说明好的优先搜索策略的应用过程。 设评价函数 f(n)形式如下：f(n)=d(n)+W(n)其中 d(n)代表节点的深度，取 g(n)=d(n)表示讨论单位耗散的情况；取 h(n)=W(n) 表示 不在位 的将牌个数作为启发函数的度量，这时 f(n)可估计出通向目标节点的希望程度。图2.7 表示使用这种评价函数时的搜索树， 图中括弧中的数字表示该节点的评价函数值 f。算法每一循环结束时，其 OPEN 表和 CLOSED 表的排列如下：.精选文档根据目标节点L 返回到 s 的指针，可得解路径S(4)，B(5)，E(5)， I(5)，K(5) ，L(5)图 2.7 给出的是使用A 算法求解8 数码问题的搜索图。其中A 、B、 C 等符号，只是为了标记节点的名称，没有特殊意义。 这些符号旁边括弧中的数字是该节点的评价函数值f。而圆圈中的值， 则表示节点的扩展顺序。从图中可以看出，在第二步选择节点B 扩展之后， OPEN 表中 f 值最小的节点有D 和 E 两个节点，他们的f 值都是 5。在出现相同的f 值时， A 算法并没有规定首先扩展哪个节点，可以任意选择其中的一个节点首先扩展。.精选文档图 2.7 八数码问题的搜索树本文档部分内容来源于网络，如有内容侵权请告知删除，感谢您的配合！.