人工智能课件-启发式搜索问题-3

启发式搜索算法前面我们讲解了无信息搜索算法通过系统化地生成新状态并且检验它们是否为目标状态来寻找问题的解。但不幸的是，一般来说，问题的规模（问题所有可能出现的状态数）是比较大的，就拿8数码问题这样一个并不太复杂的问题来说，其规模就达到9！/2＝181440个状态。当问题有解时，如何缩小查找范围，快速有效地找到问题的解，甚至是问题的最优解，正是搜索所要讨论的问题。多数情况下前面描述的那些算法无效。从现在开始我们将向大家展示有信息的搜索策略----利用问题的特定知识能够有效地找到解。有信息搜索算法•启发式搜索算法A•最佳优先搜索算法•贪婪最佳优先搜索算法•A*算法•局部搜索算法•爬山法•模拟退火算法•局部定向算法•遗传算法启发式搜索算法•启发式信息在问题求解中的应用最早出现在1958年西蒙和纽厄尔的一篇早期论文中，但是短语“启发式搜索”和估计到目标距离的启发函数出现的比较晚（纽厄尔和Ernst,1965;Lin,1965).随后，1966年Doran和Miche对启发式搜索应用于许多问题进行了广泛的研究，尤其是对八数码和十五数码游戏。虽然Doran和Miche完成了在启发式搜索中路径长度和“外显率”（路径长度和已经访问过的节点总数的比率）的理论分析，但他们忽略了当前路径长度提供的信息；Hart，尼尔森和Raphael于1968年提出了A*算法，将当前路径长度与启发式搜索相结合，后来Hart等人于1972年又做了一些修正；以后人们陆续对算法进行改进；1985年Dechter和Pearl论证了A*算法的最优效率。迄今为止关于启发式和启发式搜索算法的最前面资料是Pearl于1984撰写的教材《启发式》，感兴趣的同学可以参阅。搜索算法的最新结果通常出现在《人工智能》上。•启发式搜索是利用问题拥有的启发信息来引导搜索，达到减少搜索范围，降低问题复杂度的目的。这种利用启发信息的搜索过程都称为启发式搜索方法。在研究启发式搜索方法时，先说明一下启发信息应用，启发能力度量及如何获得启发信息这几个问题，然后再来讨论算法及一些理论问题。一般来说:•启发信息强，可以降低搜索的工作量，但可能导致找不到最优解；•启发信息弱，一般会导致搜索的工作量加大，极端情况下演变为盲目搜索，但有可能找到最优解。我们希望，通过引入启发知识，在保证找到最佳解的情况下，尽可能减少搜索范围，提高搜索效率。启发式搜索算法A这是一个重要而又困难的问题，从理论上要研究启发信息和最佳路径的关系，从实际上则要解决获取启发信息方法的问题。比较不同搜索方法的效果可用启发能力的强弱来度量。在大多数实际问题中，人们感兴趣的是使路径的耗散值和求得路径所需搜索的耗散值两者的某种组合最小，更一般的情况是考虑搜索方法对求解所有可能遇见的问题，其平均的组合耗散值最小。如果搜索方法1的平均组合耗散值比方法2的平均组合耗散值低，则认为方法1比方法2有更强的启发能力。实际上很难给出一个计算平均组合耗散值的方法，因此启发能力的度量也只能根据使用方法的实际经验作出判断，没有必要去追求严格的比较结果。启发式搜索过程中，要对OPEN表进行排序，这就需要有一种方法来计算待扩展节点有希望通向目标节点的不同程度，我们总是希望能找到最有希望通向目标节点的待扩展节点优先扩展。一种最常用的方法是定义一个评价函数f（Evaluationfunction）对各个子节点进行计算，其目的就是用来估算出有希望的节点来。如何定义一个评价函数呢？通常可以参考的原则有：一个节点处在最佳路径上的概率；求出任意一个节点与目标节点集之间的距离度量或差异度量；根据格局（博弈问题）或状态的特点来打分。即根据问题的启发信息，从概率角度、差异角度或记分法给出计算评价函数的方法。启发式搜索算法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：IFOPEN＝（）THENEXIT（FAIL）；③n:＝FIRST（OPEN）；④IFGOAL（n）THENEXIT（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），标记mj到n的指针。·IFf（n，mk）f（mk）THENf（mk）:＝f（n，mk），标记mk到n的指针；比较f（n，mk）和f（mk），f（mk）是扩展n之前计算的耗散值。·IFf（n，ml）f（ml）THENf（m1）:＝f（n，m1），标记ml到n的指针，ADD（ml，OPEN）；当f（n，ml）f（ml）时，把ml重放回OPEN中，不必考虑修改到其子节点的指针。⑦OPEN中的节点按f值从小到大排序；⑧GOLOOP。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）＝mink（n，ti），其中ti是目标节点集，k（n，ti）就是从n到每一个目标节点最小耗散值路径的耗散值，h*（n）是其中最小值的那条路径的耗散值，而具有h*（n）值的路径是n到ti的最佳路径。由此可得f*（n）＝g*（n）＋h*（n）就表示s→ti并约束通过节点n的最佳路径的耗散值。当n＝s时，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是一个好的优先的搜索策略。下面再以八数码问题为例说明好的优先搜索策略的应用过程。设评价函数f(n)形式如下：f(n)=d(n)+W(n)其中d(n)代表节点的深度，取g(n)=d(n)表示讨论单位耗散的情况；取h(n)=W(n)表示“不在位”的将牌个数作为启发函数的度量，这时f(n)可估计出通向目标节点的希望程度。下图表示使用这种评价函数时的八数码游戏搜索树，图中括弧中的数字表示该节点的评价函数值f。算法每一循环结束时，其OPEN表和CLOSED表的排列如下：算法执行OPEN表CLOSED表初始化(s(4))()第1轮循环结束(B(4)A(6)C(6))(s(4))第2轮循环结束(D(5)E(5)A(6)C(6)F(6))(s(4)B(4))第3轮循环结束(E(5)A(6)C(6)F(6)G(6)H(7))(s(4)B(4)D(5))第4轮循环结束(I(5)A(6)C(6)F(6)G(6)H(7)J(7))(s(4)B(4)D(5)E(5))第5轮循环结束(K(5)A(6)C(6)F(6)G(6)H(7)J(7))(s(4)B(4)D(5)E(5)I(5))第6轮循环结束(L(5)A(6)C(6)F(6)G(6)H(7)J(7)M(7))(s(4)B(4)D(5)E(5)I(5)K(5))第7轮循环结束第4步成功退出根据目标节点L返回到s的指针，可得解路径S(4)，B(5)，E(5)，I(5)，K(5)，L(5)下图给出的是使用A算法求解8数码问题的搜索图。其中A、B、C等符号，只是为了标记节点的名称，没有特殊意义。这些符号旁边括弧中的数字是该节点的评价函数值f。而圆圈中的值，则表示节点的扩展顺序。从图中可以看出，在第二步选择节点B扩展之后，OPEN表中f值最小的节点有D和E两个节点，他们的f值都是5。在出现相同的f值时，A算法并没有规定首先扩展哪个节点，可以任意选择其中的一个节点首先扩展。返回使用启发函数的八数码游戏的搜索树根据目标节点L返回到s的指针，可得解路径S(4)，B(5)，E(5)，I(5)，K(5)，L(5)。上图给出的是使用A算法求解8数码问题的搜索图。其中A、B、C等符号，只是为了标记节点的名称，没有特殊意义。这些符号旁边括弧中的数字是该节点的评价函数值f。而圆圈中的值，则表示节点的扩展顺序。从图中可以看出，在第二步选择节点B扩展之后，OPEN表中f值最小的节点有D和E两个节点，他们的f值都是5。在出现相同的f值时，A算法并没有规定首先扩展哪个节点，可以任意选择其中的一个节点首先扩展。•思想:对每一个节点使用评估函数f(n)–“最有希望”的（节点）评估扩展最有希望的未扩展节点•执行:按照最有希望的降序排列边缘中的节点•特例:–贪婪最佳优先搜索–A*搜索–最佳优先搜索对罗马尼亚城市图中可以通过从Arad到Bucharest的直线距离来估计从Arad到Bucharest的最低耗散路径的耗散值（使用按公里计算的步骤成本评估）•评估函数f(n)=h(n)(heuristic)•=从n到目标goal的成本评估••例如,hSLD(n)=从n到Bucharest的直线距离••贪婪最佳优先搜索扩展似乎离目标goal最近的节点。即只使用启发函数h(n)来评价节点。贪婪最佳优先搜索贪婪最佳优先搜索案例贪婪最佳优先搜索案例贪婪最佳优先搜索案例贪婪最佳优先搜索案例贪婪最佳优先搜索算法性能•完备性?否–在循环中会陷入困境，例如IasiNeamtIasiNeamt••时间复杂性?O(bm),但一个好的启发函数heuristic能够极大改善算法性能••空间复杂性?O(bm)–在内存中要保存所有节点••最优性?否A*搜索•当在算法A的评估函数中，使用的启发函数h(n)是处在h*(n)的下界范围，即满足h(n)≤h*(n