为下面的问题(A*)找到一个好的启发式方法

Question

我正在试着为下面的问题找一个启发式函数。给你n桶最大容量max_i，当前容量curr_i和绘画的颜色colour_i，i= 1，n和一个可能的颜色组合列表: col1 + col2 -> col3。问题的最终状态是一组配对(数量，颜色)，它们必须在buckets #(final_state) <= no中找到。桶的数量。

我们的目标是混合这些存储桶，例如在最后，来自最终状态的每一对都至少在一个存储桶中找到。每次移动时，如果要倒入的桶未满，则可以从一个桶倒入另一个桶。

问题是我想不出一个经典的启发式方法来解决这个问题，因为我不能比较来自初始状态和最终状态的存储桶(它不是唯一的)。启发式必须是从当前状态到最终状态的移动次数，还是可以是随着我们接近范围而减少的某个数字？

Answer 1

启发式方法必须是admissible，所以它不应该低估实际距离。随着你越来越接近目标，原则上它应该更精确，因此可能会突然更快地变小。但是，只要它不被低估，这是非常好的。

由于到目标的距离通常是移动的次数，很难看出它怎么会是完全无关的东西。因此，是的，启发式应该与移动的数量相关，但不是必须的，只要它是悲观的而不是乐观的。