简介在搜索过程中，关键的一步是如何确定要扩展的节点，不同的确定方法就形成不同的搜索策略。如果在确定节点时能充分利用与问题求解有关的特性信息，估计出节点的重要性，就能够在搜索时选择重要性较高的节点进行扩展，从而求得最优解。而启发式搜索正是这种利用问题自身的某些特性信息，指导搜索朝着最有希望有方向前进的一种方法。在启发式搜索中，用于评价节点重要性的函数叫做评价函数。评价函数的主要任务就是估计等搜索结点的重要程度，以确定结点的优先级程度。评价函数的一般形式为f(x)=g(x)+h(x)其中g(x)为初始节点S0到节点x已经实际付出的代价。当希望有较高的搜索效率，且只关心到达目标节点的路径时，g(x)可以忽略，但此时会影响到搜索的完备性。h(x)为节点x到目标节点Sg的最优路径的估计代价，它体现了总是的启发性信息，又称为启发函数，其形式要根据总是的特性而定。启发函数h(x)所携带的启发性的信息越多，搜索时扩展的节点数就越少，搜索的效率就越高。因此在确定f(x)时，要使得g(x)与h(x)各占适当的比率。在实际问题求解时，g(x)可以根据已经搜索的节点信息计算出来，而启发函数h(x)依赖