A*搜索求解三水壶问题的启发式函数设计疑问

结论 #

你设计的启发式函数完全不合理，无法在A*搜索中正常使用，核心问题如下：

• 未关联目标状态：启发式函数的核心作用是估计当前状态到目标状态的最小剩余代价，你的函数计算逻辑完全没有用到目标状态的数值，哪怕当前已经到达目标状态(8,3,0)，计算出的h值为8*1 + 3*1 + 0*0 = 11，而实际剩余代价为0，完全不符合启发式的基本定义。
• 不满足A要求的可采纳性：A算法要求启发式函数的估计值永远不大于实际剩余最小代价（可采纳性），才能保证找到最优解。你的函数取值是多个水壶的存水量之和，比如状态(8,2,0)距离目标仅需1步操作，但你的h值计算结果为8*1 + 2*1 + 0*0 = 10，远大于实际代价1，使用该启发式会导致A*优先搜索非最优路径，甚至无法找到正确解。
• 取值逻辑和动作代价无对应关系：三水壶问题通常默认单次倒水操作的代价为1，每次操作最多调整2个水壶的水量，你的函数直接累加非空水壶的存水量，数值大小和需要的操作步数没有任何合理的关联，无法起到引导搜索方向的作用。

适合该场景的启发式函数参考 #

你可以选择以下两种简单且满足可采纳性的启发式：

1. 差值归一化启发式：计算当前状态和目标状态各水壶水量的差值绝对值之和，再除以2（因为单次倒水最多可以减少2个单位的差值），公式为：
   h(x,y,z) = (|x - 8| + |y - 3| + |z - 0|) // 2
2. 不一致水壶计数启发式：统计当前和目标状态水量不一致的水壶数量，公式为：
   h(x,y,z) = (x != 8) + (y !=3) + (z !=0)

以上两种启发式的估计值永远不会超过实际需要的最小步数，既可以保证A*找到最优解，也能大幅减少搜索的状态数量。

内容的提问来源于stack exchange，提问作者legna