距離度量啓發式信息性

Question

擁有曼哈頓距離啓發式和啓發式更是把

greater value of (square root(x1-x2),square root(y1-y2)) 

你怎麼會考慮他們的信息性，並且它們在從搜索到b，其中僅橫在網格中的最短路徑admissable並允許垂直運動？

在所有情況下測試它們時，第二種啓發式方法總是採用對角方式，有時候發現的節點數量明顯小於曼哈頓。但情況並非總是如此，這讓我感到困惑。

Answer 1

給定當前點a = (x1, y1)和目標b = (x2, y2)。我會讓dist1(a, b)表示曼哈頓距離，dist2(a, b)表示您提出的其他啓發式。我們有：

dist1(a, b) = |x1 - x2| + |y1 - y2|

dist2(a, b) = max(sqrt(|x1 - x2|), sqrt(|y1 - y2|))

請注意，我改變你的新提出的啓發式有點採取的絕對差值的平方根，而不是僅僅的差異，因爲對負數的平方根會導致問題。無論如何，應該很容易看出，對於任何a和b,dist1(a, b) >= dist2(a, b)。

由於在只允許垂直和水平移動的網格情況下，兩種啓發式都是可接受的，這通常意味着兩者（曼哈頓距離）的最大啓發式更有效，因爲它會更接近真相。

在OP中，您實際上提到您正在測量「發現的節點數」，並且對於第二個啓發式，這有時會更小（更好）。有了這個，我假定你的意思是說你正在運行A *算法，並且你正在測量從邊界/開放列表/優先級隊列中彈出的節點的數量/你想要的任何項使用。

我的猜測是，發生的情況是，如果多個節點在邊界上有相同的分數（通常稱爲f），那麼您的打破平局就會很糟糕。你提出的第二種啓發式確實傾向於選擇沿着當前節點和目標之間對角線的節點，而曼哈頓距離則沒有這種趨勢。當邊界中的多個節點具有相等的（f）分數時，良好的決勝因子將是優先考慮迄今爲止具有高實際成本的節點（通常被稱爲g）和低啓發成本（通常被稱爲h ）。這可以通過明確比較g或h得分，或者通過簡單地將所有啓發式得分乘以略大於1（例如，1.0000001）的數字來實現。欲瞭解更多信息，請參閱http://theory.stanford.edu/~amitp/GameProgramming/Heuristics.html#breaking-ties