algorithm - A* 的水壶启发式函数

Question

对于经典的水壶搜索问题，即使是三个以上的水壶，A*搜索算法可以使用哪些可接受的函数？

编辑：

我知道http://www.dave-reed.com/csc550.S02/HW/HW4.html，但该功能显然不一致。

Answer 1

有两种通用的方法来设计一个可接受的启发式。两者都通过解决一个更简单的问题来工作。启发式值就是到更简单问题中目标的距离。

1. 放松

通过忘记负面影响可以简化问题。例如，如果您曾经有过一夸脱水，那么它会在需要时随时可用。

基于图的可达性启发式规划教程。

2. 抽象

忽略一些细节可以简化问题。例如，一个更简单的目标可能会忽略最后一个水壶中的水量。

您可以将预先计算的启发式值存储在模式数据库中。关键是更简单的抽象问题，价值是启发式价值。

正式介绍。