A *和曼哈頓距離成本

Question

您好這個學期我們開始了一個AI課程，我們有一個項目，計算在NxN董事會達到目標的最佳路線。這塊木板也可以隨機包含我們不能穿過的障礙物，而且我們也只能垂直和水平移動。每次垂直移動的成本爲1.0，水平移動的成本爲0.5。我們被要求用曼哈頓啓發式方法用A *算法進行計算。我的問題是：當我們計算曼哈頓距離（我知道你必須添加水平和垂直「方塊」直到你達到目標），我們必須增加成本到每個「平方」（0.5或1.0）？。或曼哈頓距離只是計算你需要達到目標的「方塊」？

Answer 1

您需要使用問題的距離，即1和0.5。

當使用A *時，從開始到當前節點的距離將是沿着到該點的實際路徑的1秒和0.5秒的總和，並且估計到結束的剩餘距離將是1和沿着「完美路徑」0.5s，即沒有障礙物。

我希望能回答你的問題。

Answer 2

由於曼哈頓不計算平方，因爲它計算的最簡單的成本與在相同重量的垂直和水平移動情況下計數平方相同，因此您應該將成本添加到每個平方。