【摘要】：用来评估节点重要性的函数称为评估函数。其一般形式为：其中，g表示从初始节点S0到节点x的实际代价；h表示从x到目标节点S0的最优路径的评估代价，它体现了问题的启发式信息，其形式要摄据问题的特性确定，h称为房发式函数。因此，启发式方法把对问题状态的描述转换成了对问题解决程度的描述，这一程度用评估函数的值来表示。这里只是说明了评估函数的含义及如何选择评估函数和计算评估函数值。
在搜索过程中，关键的一步就是如何选择下一个要考察的节点，选择的方法不同就形成了不同的搜索策略。如果在选择节点时能充分利用与问题有关的特征信息，估计出节点的重要性，就能在搜索时选择重要性较高的节点，以利于求得最优解。我们称这个过程为启发式搜索。“启发式”实际上代表了“大拇指准则”：在大多数情况下是成功的，但不能保证一定成功的准则。
用来评估节点重要性的函数称为评估函数。评估函数f（x）定义为从初始节点S0出发，约束地经过节点x到达目标节点Sg的所有路径中最小路径代价的估计值。其一般形式为：
其中，g（x）表示从初始节点S0到节点x的实际代价；h（x）表示从x到目标节点S0的最优路径的评估代价，它体现了问题的启发式信息，其形式要摄据问题的特性确定，h（x）称为房发式函数。因此，启发式方法把对问题状态的描述转换成了对问题解决程度的描述，这一程度用评估函数的值来表示。
如对八数码问题（图4－4），评估函数可以表示为：(www.xing528.com)
图4-4 八数码问题
其中，d（x）表示节点x在搜索树中的深度，w（x）表示节点x中不在目标状态中相应位置的数码个数，w（x）就包含了问题的启发式信息。一般来说，菜节点w（x）越大，即“不在目标位”的数码个数越多，说明它离目标节点越远。
对初始节点S0，由于d（S0）＝0，w（S0）＝4，因此，f（S0）＝4。这里只是说明了评估函数的含义及如何选择评估函数和计算评估函数值。在搜索过程中除了需要计算初始节点的评估函数外，更多的是需要计算新生成节点的评估函数。
免责声明：以上内容源自网络，版权归原作者所有，如有侵犯您的原创版权请告知，我们将尽快删除相关内容。
