1
A *（星）の最短経路を見つける問題 - 具体的な例この例では
（写真を参照してください）、マンハッタンのヒューリスティックがあるため、西先ブロックのunwalkableブロックのパスを遅らせます。
私はこれをどのように修正できますか？宛先を見つけた後でも、開いているリスト（灰色のブロック）のブロックをチェックし続ける必要がありますか？もし私がそれをしなければならないなら、私はダイクストラを使うかもしれません。私は星に行ったり、解決策があれば、このような不完全な状態で生きなければならないのですか？
私は自分の研究を行い、Web上のチュートリアル/記事と同じように機能する独自のアルゴリズムを実装しましたが、最短パスを見つけることができないような特定のインスタンスに実行し続けます。
対角線は、場合によっては様々な、より重大な問題を引き起こします。私はそれの例を投稿しますが、最初にユークリッドがどのように運賃を支払うかを見ていきます。私はユークリッドを試したことがありませんでした。私はこの時点で他の選択肢はありません。 –
@ NathanielG.M。パフォーマンスの差は無視できるはずですが、Diagonalヒューリスティックには何も間違ってはいけません。存在する場合は、実装に問題があります。 –
対角の場合は、fコストが最も低い場所が目的地から反対方向に向かう場合があります。目的地を見つけるにはあまりにも多くのノードを通過します。特に多くの回廊がある地図では、行き詰まりに遭遇し、別の経路を探すために公開リストを調べなければなりません。それは最終的に最短の道を見つけるが、それはそれほど多くの探索を取るべきではないようにいつも私に思われた。さらにテストすると、あなたが正しいことが分かります。ユークリッドでパフォーマンスはかなり良いです。答えをありがとう。 –