摘 要： 探讨了问题空间中的启发式搜索技术，给出了构造启发式函数的基本方法，指出提高启发能力的措施和影响启发式搜索效率的主要因素。
关键词： 问题空间 搜索空间 启发式搜索 启发函数 搜索效率
搜索是人工智能研究的最基本问题。目前用于搜索的方法主要有盲目搜索和启发式搜索。盲目搜索法不适宜解决大而复杂的问题，因为要在盲目搜索中找到一个解，所需扩展的节点数目很大，并且当这些节点的扩展次序完全随意时，将耗费大量的计算时间和存储空间，搜索效率很低。启发式搜索法则是利用与问题有关的信息进行搜索，将知识或经验与搜索相结合，从而达到减少搜索量、提高搜索效率的目的。思维信息加工理论认为：人脑对信息处理的一个重要特点就是运用启发式，即人在进行认知活动时，常常利用一些生活中常用的启发式规则很简单地考虑几种可能性，而不是同时考虑解决问题的各种可能性，并对各种可能性进行权衡比较。启发式是凭借经验的求解问题方法，不能保证问题一定得到解决，但却常常能有效地求解问题。
启发式搜索法是人工智能解决问题的主要技术，而启发能力和搜索效率则是评价一个智能搜索系统的关键因素。本文首先研究问题空间中启发式搜索函数的构造，然后在此基础上探讨启发能力并进行启发式搜索效率的评估。
1 问题空间与搜索空间
对许多应用领域而言，问题求解是最基本的。事实上不管是对人还是对机器，解决问题的能力都是衡量其智能的一个标准。问题空间由所求解的问题构成，而问题的求解过程又可看成是一个搜索过程。为了进行搜索，首先必须用某种形式把问题表示出来。
定义4 问题空间的状态模型M可用一个4元组表示，即M=（I，F，G，C）。其中I是问题的所有初始状态集合，F是算符的集合，G是目标状态的集合，C为费用的集合。
这样，问题空间的搜索问题就由状态集合、引起状态转移的操作算符集合和用于指出状态转移成本的费用函数组成。搜索的目的就是寻找从初始状态到目标状态的最小成本路径。若把每个状态看成一个节点，则问题空间的状态模型可用一个有向图表示。这个图不一定全连通，即从某些状态不一定到达另一些状态，但在每个连通的部分，每条弧代表一个算符，它把一个状态引向另一个状态。如果从某个初始状态（节点）出发，有一条路径通向目标状态（节点），则称此目标状态所代表的问题在当前的初始状态下是可解的。
定义5 在问题的状态图中，解题路径所经过的所有状态的集合，称为搜索空间。
通常搜索空间与问题空间的关系为：搜索空间
问题空间。假定问题的初始状态、算符和目标状态的定义都是完全确定的，则要解决的问题就是如何有效地确定一个搜索空间，以及如何有效地搜索这个给定的空间。通常，若要有效地确定一个搜索空间，则需要某些与具体问题领域有关的特性信息，即启发式信息。而对给定的搜索空间进行有效的搜索，则需要有好的搜索策略。二者结合就构成了所谓的启发式搜索策略。这种策略可以大大提高解题效率，它也是人工智能领域使用最普遍的搜索策略。对启发式搜索策略可从四个方面进行评价：(1)完整性。当问题有解时，该策略能否保证找到一个解；(2)时间复杂性。多长时间找到一个解；(3)空间复杂性。进行搜索时需要多少存储量；(4)最优性。当有若干个不同的解时，该策略能否找到最高质量的解。
2 启发函数和启发能力
在搜索过程中，关键的一步是如何确定要扩展的节点，不同的确定方法就形成不同的搜索策略。如果在确定节点时能充分利用与问题求解有关的特性信息，估计出节点的重要性，就能在搜索时选择重要性较高的节点进行扩展，从而求得最优解。而启发式搜索正是这种利用问题自身的某些特性信息，指导搜索朝着最有希望的方向前进的一种方法。在启发式搜索中，用于评价节点重要性的函数称为估价函数，该函数表示从初始节点S0经过节点x到达目标节点Sg的最优路径的代价估计值，其一般形式为：f(x)=g(x)+h(x)。其中g(x)为从初始节点S0到节点x已经实际付出的代价，它指出了搜索的横向趋势，有利于搜索的完备性，但影响搜索效率。当希望有较高的搜索效率，且只关心到达目标节点的路径时，g(x)可以忽略，但此时会影响搜索的完备性。h(x)为节点x到目标节点Sg的最优路径的估计代价，它体现了问题的启发性信息，又称为启发函数，其形式要根据问题的特性确定。启发函数h(x)所携带的启发性信息越多，搜索时扩展的节点数就越少，搜索的效率就越高。因此在确定f(x)时，要权衡利弊，使g(x)与h(x)各占适当的比重。
由f(x)=g(x)+h(x)看出，启发式搜索实际上涉及二种计算：
(1)确定下一个扩展节点的元级计算。首先要构造一个启发式估价函数f(x)，该函数基于指定问题领域的信息，通常是状态描述的一个实数值函数。一般约定，下一个要扩展的节点x是f(x)值最小的节点，并且当下一个要扩展的节点是目标节点时，搜索过程中止。
(2)扩展指定的节点和产生相应搜索路径的目标级计算。对f(x)值最小的节点进行扩展，根据约定产生节点的一个后继节点或所有后继节点，然后在后继节点上再次进行元级计算。如此往复，从而生成整个搜索空间，并在此空间中根据节点的扩展路径，找到一条从初始节点S0到目标节点Sg的通路，即求得问题的一个解。
由于f(x)基于指定问题领域的信息，因此构造和选择合适的启发函数h(x)就成为启发式搜索策略的一个关键问题。就构造h(x)而言，通常必须对求解的问题有比较深入的理解。目前构造启发函数h(x)的方法主要有三种：(1)根据处在最优路径上的节点的概率构造h(x)；(2)根据任意节点x与目标集G（Sg∈G）之间的距离量度或差别量度构造h(x)；(3)在棋类博弈中，根据棋局的某些特点，决定棋步的得分数来构造h(x)等。
总之，构造启发函数应满足二方面的要求：一是函数要简单易算，二是函数要有较高的精确度。对很多问题，这二方面的要求是相互矛盾的。简单易算的启发函数往往精确度较低，估计某条路径好坏程度的误差较大；而精度高的启发函数，虽然能有效地估计搜索路径的好坏程度，但函数往往比较复杂，计算函数值要花较多的时间，总计算量很大。因为在各种搜索算法中，被估值的叶子节点的数目与搜索的时间有着接近线性的关系，随着搜索层数的加深，叶子节点的数目迅速上升，启发函数被数以百万次的调用，将花费大量的运算时间。所以构造一个好的启发函数，必须要权衡这二种因素。
确定一种启发式搜索方法是否比另一种启发式搜索方法具有更强的启发能力，往往与启发函数h(x)的选择有关。启发函数是将问题状态的描述详细计划成一种对此问题状态满意程度的量度，其目的在于当搜索过程中有一条以上的路径可以使用时，引导搜索走最有利的路径。启发函数对搜索空间中的每个节点的重要性估计得越准，解决问题的过程就会越直接和越快。因此，对同一个问题，选用不同的h(x)，将得到不同的搜索过程，当然搜索效率也不同。一般而言，对于不太复杂的求解问题，通常选用0≤h(x)≤h*(x)，以求问题的最优解，而且在满足h(x)≤h*(x)的前题下，h(x)的值越大越好。h(x)值越大，表明它携带的启发性信息就越多。h*(x)为节点x到目标节点Sg的最优路径的代价。对于比较复杂的求解问题，为了加大启发能力，可适当选用h(x)＞h*(x)。这样虽然牺牲了算法的可采纳性，不能保证得到最优解，但却有益于使搜索集中指向目标，且在初始节点附近尽量有限的范围内进行，从而减少了扩展节点的数量，并能得到一个满意解。
3 启发式搜索效率
启发式搜索在解决困难问题上是一种非常有效的工具，其搜索效率不仅取决于过程自身的启发能力，而且还与被求解问题的有关属性等多种因素有关。下面将讨论启发式搜索效率问题。
(1)从问题求解所需知识的角度看，运用知识的目的就是为了减少搜索量。如果解决一类智能问题涉及的知识越多，则搜索量就越少。因此，提高搜索效率的途径之一就是逐步积累知识并恰当使用有助于减少搜索的信息与知识。指导搜索的启发知识实际上是一种控制元知识，即是关于如何用问题领域知识的知识和关于问题求解方法的知识。搜索效率在很大程度上决定于问题的表示方法，而问题的表示方法又与知识的表达方式有关。启发式搜索实际上是在二个空间中进行的，一个是状态空间，一个是知识空间。利用算符作用于旧状态而得到新状态，这是在状态空间中移动，查看新状态是否即是目标状态，其为搜索过程。然而，当确定采用哪一个算符或确定选择哪一个状态进行扩展时，则需要参考事先准备好的、且与问题领域有关的知识，这就需要到知识空间去搜索。因此在选择和使用知识方面，合理地构造知识库并建立高效的知识推理机制，也是提高搜索效率的关键因素之一。
(2)从搜索过程的角度看，通常用二个参数来度量搜索效率。一个参数是渗透率P，定义为P=L/T。其中L为初始节点到目标节点的路径长度，T为整个搜索过程中所生成的节点总数。渗透率反映了搜索过程中从初始节点向目标节点前进时搜索区域的宽度，它度量出搜索过程所产生的搜索树是“单枝延伸”还是“多枝密叶”。当L=T时，P=1表示搜索过程每次只生成一个节点，且该节点恰好是解路径上的节点，搜索效率最高。P越小，表示搜索时产生的无用节点越多，搜索效率越低。另一个参数是有效分枝因子B，它描述了一个搜索过程朝着目标前进的激烈程度。设L为搜索路径长度，T为搜索过程中生成的节点总数，则有：
(3)从增加启发能力的角度看，可以通过使用一些非低约束的函数h(x)以可接纳性为代价来换取搜索效率。也就是说，一个可能不是最优的路径比最优路径更容易找到，一个非较低约束的h(x)比一个较低约束的h(x)更容易计算。在这些情况下，效率可能会成倍地增加。另一种方法是通过对估价函数f(x)中的h(x)部分加权，即用f(x)=g(x)+w*h(x)表示估价函数，以增加其启发能力，从而达到提高搜索效率的目的。w是一个正数，非常大的w值会过分强调启发式部分，而非常小的w值会突出搜索的广度优先特性。实验结果表明，如果w值与搜索树上的节点成反比，则会提高搜索效率。
(4)从启发式控制策略的角度看，选择合适的启发式搜索算法对解决问题的效率有举足轻重的影响。通常比较启发式搜索算法的因素主要包括：时间T、空间S、解质量Q和效率E。对于给定的机器平台M和所选择的启发式搜索算法x而言，时间度量T(M，x)依赖于算法x在执行过程中的各种耗时计算，如节点的扩展与生成所需的时间、启发式估值计算所需的时间、路径深度检测和阈值检测所需的时间等。空间度量S(M，x)依赖于算法x在给定的问题领域产生的节点数目Tx和每个节点所需的存储字数WM，即S(M，x)=Tx*WM。解的质量Q(x)依赖于最优路径长度D与由启发式算法x获得的解路径长度Lx的比值，即Q(x)=D/Lx。该式表明一个好的启发式搜索算法应该有较高的求解质量，它实际上也反映了启发式搜索算法的效率。所以启发式搜索效率度量E(x)依赖于搜索空间的平均分枝度β、生成节点的总数Tx和搜索路径长度Lx，即E(x)=β*Lx/ Tx。E(x)越大，搜索效率越高。
4 结束语
本文对人工智能中经典的启发式搜索问题进行了探讨，详细分析和研究了启发式搜索过程中启发函数的构造、启发能力和启发式搜索效率等一些基本要素，对实际应用具有一定的指导意义。目前，在启发式搜索领域还有许多问题值得研究，如寻找大问题的优化解、对确定范围的问题给出高质量的求解、使用不完整和不确定的信息处理动态环境和复杂情况、智能博弈评估、分析和预测启发式搜索算法的性能等。
参考文献
1 Buro M.Improving heuristic mini-max search by supervised learning. Artificial Intelligence，2002；(134)
2 Al-Ayyoub A E，Masoud F A.Heuristic search revisited. The Journal of Systems and Software，2000；(55)
3 Muller M.Partial order bounding：A new approach to evaluation in game tree search.Artificial Intelligence，2001；(129)
4 王永庆.人工智能原理与方法.西安：西安交通大学出版社，1998
5 王士同.多因素问题的启发式搜索算法MFRA*.计算机学报.1996；19(2)
6 赵丹青，胡宝玉.状态空间搜索的几种算法讨论.中南民族学院学报（自然科学版），2001；20(3)
7 许精明.状态空间的启发式搜索方法研究.微机发展.2002；(4)