选择一个启发式功能

我仍然试图弄清楚为什么我的启发式选择会影响我a *实现的搜索时间。选择一个启发式功能

我有我的地图如下（不准确的大小）：

########### 
#   # 
# # # # # # 
#   # 
# # # # # # 
#   #

我选择我的启发式

option 1: h = abs(n.x - target.x) + abs(n.y - target.y) 
option 2: h = 2*(abs(n.x- target.x) + abs(n.y - target.y))

与option 1，算法运行比较正常，直到我必须从顶部移动到底，在这种情况下，需要很长的时间才能走上这条路。

与option 2，option 1时间改善了90％左右。

我试图阅读关于高估/低估，我不能拿出一个明确的解释。

可能是什么原因？另外，我的选择是否合理？

2016-08-03 r m

为什么不选择欧几里得距离？我从事这项工作已经有一段时间了，但给了一个2D地图空间，欧几里德距离应该给出一个最佳启发式。 –

你也应该用其他地图测试启发式方法，最好的启发式方法是通过取所有地图的平均时间（步长）来表现最好的启发式 – adhie

我也建议欧几里得距离，它给出了剩余路径的一个体面的估计，同时易于计算，因此速度很快。此外，这是可以接受的。 – adhie

看看this答案。有一个link一个很好的教程，解释并给出拇指规则关于哪种启发式应该选择不同类型的问题，然后友好的解释这些技术。

2016-08-03 19:17:49

从那个链接，这是我得到了一些D.选择1的想法，我选择了2。 –

回答