我如何判断一个特定的启发式是否可以接受，为什么我的不可以？
How can I tell if a particular heuristic is admissible, and why mine is not?
可接受启发式的定义是"does not overestimate the path of a particular goal"。
我正在尝试编写一个 Pac-Man 启发式算法来寻找吃点的最快方法，其中一些点随机散布在网格中。然而，它没有通过我的入学考试。
以下是我的算法步骤：
sum = 0, list = grid.getListofDots()
1. Find nearest dot from starting position (or previous dot that was removed) using manhattan distance
2. add to sum
3. Remove dot from list of possible dots
4. repeat steps 1 - 3 until list is empty
5. return the sum
既然我使用的是曼哈顿距离，难道这不应该被接受吗？如果不是，是否有任何建议或其他方法使该算法可接受？
您的启发式方法不可接受。另一个例子是：
你的成本是 9，但最佳路径的成本是 6。
一个非常非常简单的可接受启发法是：
number_of_remaining_dots
但不是很紧。一个小的改进是：
manhattan_distance_to_nearest_dot + dots_left_out
其他可能性是：
distance_to_nearest_dot // Found via Breadth-first search
或
manhattan_distance_to_farthest_dot
可接受启发式的定义是"does not overestimate the path of a particular goal"。 我正在尝试编写一个 Pac-Man 启发式算法来寻找吃点的最快方法，其中一些点随机散布在网格中。然而，它没有通过我的入学考试。 以下是我的算法步骤：
sum = 0, list = grid.getListofDots()
1. Find nearest dot from starting position (or previous dot that was removed) using manhattan distance
2. add to sum
3. Remove dot from list of possible dots
4. repeat steps 1 - 3 until list is empty
5. return the sum
既然我使用的是曼哈顿距离，难道这不应该被接受吗？如果不是，是否有任何建议或其他方法使该算法可接受？
你的成本是 9，但最佳路径的成本是 6。
一个非常非常简单的可接受启发法是：
number_of_remaining_dots
但不是很紧。一个小的改进是：
manhattan_distance_to_nearest_dot + dots_left_out
其他可能性是：
distance_to_nearest_dot // Found via Breadth-first search
或
manhattan_distance_to_farthest_dot