選擇一個啓發式功能

我仍然試圖弄清楚爲什麼我的啓發式選擇會影響我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。 –

回答