21

セルの 2D グリッドがあり、その一部が壁で埋められているとします。キャラクターは、ある正方形から水平または垂直に 1 ステップ離れた任意の正方形に移動できますが、壁を越えることはできません。

開始位置と終了位置が与えられると、A* アルゴリズムと許容ヒューリスティックを使用して、開始位置から終了位置までの最短経路を見つけることができます。この現在の設定では、目的地までの距離を決して過大評価しないため、マンハッタンの距離は許容されます。

ここで、壁に加えて、世界にテレポーターのペアがあるとします。テレポーターに足を踏み入れると、すぐにキャラクターがリンクされたテレポーターに転送されます。テレポーターの存在は、テレポーターを使用して距離を縮めることで、最適なマンハッタン距離を歩くよりも速く目的地に到達できる可能性があるため、上記の許容可能なヒューリスティックを破ります。たとえば、T とマークされたテレポーター、S とマークされた開始位置、および E とマークされた終了位置を持つこの線形世界を考えてみましょう。

T . S . . . . . . . . . . . . . E . T

ここで、最善のルートは、左側のテレポーターまで歩いてから、左に 2 歩進むことです。

私の質問は次のとおりです。テレポーターのあるグリッドの世界で、A* の適切な許容ヒューリスティックは何ですか?

ありがとう！

4

2 に答える 2

15

あなたの世界にあまり多くのテレポーターがない場合は、次のヒューリスティックを試してみます。ここで、は cellとMHD(a,b)の間のマンハッタン距離 で、は cell に最も近いテレポーターです。abT(i)i

h(x,y) = min( MHD(x,y), MHD(x,T(x)) + MHD(T(y),y) )
于 2013-01-20T19:29:38.747 に答える
7

テレポーターのグラフを作成します。

  • 各テレポーター用のノードと終了位置用のノードがあります。
  • 各ノードを他のノードに接続するエッジがあり、完全に接続されたグラフを形成します。
  • エッジの重みには、各ノードの宛先セル（テレポーターに入るときに移動するセル）と他のすべてのノードの間のマンハッタン距離を使用します。

ダイクストラのアルゴリズムを使用して、各ノードから端までの最短距離を計算します。

これで、特定の位置とすべてのノードの間の最小距離に加えて、ノードから端までの事前に計算された距離をヒューリスティック関数として使用できます。ダイクストラのアルゴリズムは、前処理ステップとして1回だけ実行する必要があります。ただし、テレポーターの数がセルの数の大きな割合である場合は、より単純なヒューリスティック関数を使用するよりもメリットが得られない可能性があります。

于 2013-01-20T19:38:41.157 に答える