マンハッタンパスの検索で斜め方向の移動がサポートされていますか？

Question

マンハッタンの距離メトリックで対角線移動がサポートされているかどうか説明できますか？

Answer 1

admissible heuristicは決して距離を過大評価してはなりません。

0,0の開始点と10,10の宛先を考えてみましょう。

マンハッタンの距離メトリックは10 + 10 = 20です。斜めの移動が許可されている場合、真の距離を過大評価します。

したがって、対角線移動が許可されている場合、マンハッタン距離はA *の許容可能なヒューリスティックではありません。