曼哈頓，歐幾里德和切比雪夫在A *算法

Question

我迷茫了什麼曼哈頓，歐幾里德和切比雪夫的一個A *算法的目的。難道僅僅是距離計算或做A *算法找到根據這些指標（垂直&水平或對角或三個）以不同的方式路徑。我的這三個指標的印象是，他們有所見本網站計算距離的各自不同的方法：和https://lyfat.wordpress.com/2012/05/22/euclidean-vs-chebyshev-vs-manhattan-distance/

但有些人告訴我，A *算法只移動垂直和水平如果使用了曼哈頓指標必須被這樣畫出來。只有對角線爲 euclidian，並且可以朝chebyshev的三個方向移動。

所以我想澄清的是，A *算法是基於指標（曼哈頓，切比雪夫和歐幾里得）在不同的方向上運行，還是運行在所有方向上，但基於指標的啓發成本不同。我是一名學生，因此對此感到困惑，因此任何可能的澄清都將受到讚賞！

Answer 1

其實，事情有點反過來，即我們通常知道的運動類型，我們感興趣的是，這種運動類型決定哪個是最好的指標（曼哈頓，切比雪夫，歐幾里德）是用於啓發式。

更改啓發式不會改變相鄰小區的連通性。

爲了使A *算法根據特定的移動類型（，即僅水平+垂直或對角線等）找到路徑，應相應地設置鄰居枚舉過程。 （在節點從隊列中彈出之後，節點的相鄰節點的枚舉在算法的主循環內的某個地方完成）。

簡言之，不啓發式，但一個節點的鄰居列舉的方式確定運動的A *算法允許的哪種類型。

然後，一旦一個移動類型成立，並編碼成如上述所描述的算法中，也重要的是找到一個很好的試探法。啓發式需要滿足某些標準才能生效（它不需要高估距目標的距離），因此一些啓發式規則與某些運動類型不兼容。選擇一個無效的啓發式方法不再保證A *在完成時找到正確的解決方案。爲啓發式一個好的選擇是精確地使用所選擇的移動類型（例如曼哈頓爲水平/垂直，等）下的一個測量距離。