可采纳启发式的定义是“不会高估到达特定目标的路径”。我正在尝试为Pac-Man编写一个启发式方法，用于寻找吃掉点点的最快方法，其中一些点点随机分布在网格上。然而，我的启发式方法未能通过可采纳性测试。以下是我的算法步骤：

sum = 0, list = grid.getListofDots()1. 从起始位置（或之前移除的点点）找到最近的点点，使用曼哈顿距离2. 将距离加到sum中3. 从可能的点点列表中移除该点点4. 重复步骤1-3直到列表为空5. 返回sum

由于我使用了曼哈顿距离，这不应该是可采纳的吗？如果不是，有没有建议或其他方法可以使这个算法变得可采纳？

回答：

如所说，你的启发式方法不可采纳。另一个例子是：

你的成本是9，但最佳路径的成本是6。

一个非常简单且可采纳的启发式方法是：

number_of_remaining_dots

但它不够精确。一个小的改进是：

manhattan_distance_to_nearest_dot + dots_left_out

其他可能性包括：

distance_to_nearest_dot   // 通过广度优先搜索找到

或者

manhattan_distance_to_farthest_dot