3

問題：

ターン数を減らすために最適化した A* アルゴリズムを変更します。アルゴリズムは、(a,b) から ANY TILE ADJACENT TO (x,y) へのパスを見つけるようになりました。可能な場合は (x+1,y) または (x-1,y) が優先されます。

私の試みた解決策：

  1. 元の A* アルゴリズムを (a,b) から (x,y) に実行します。
  2. (x-1, ) または (x+1, )を通過するパスの最後の座標を見つけます。
  3. その座標平面に * から y への直線アクセス可能な垂直線がある場合は、その線に従うようにパスを修正します。

ビジュアル デモンストレーション: (X にアクセスできない S から E へのパス)

......S           .....S  
.     X           .    X
.          =>     .     
.                 .
E                E.

ただし、次のような場合に私のソリューションが機能するかどうかはわかりません。

......S            .....S  
.     X            .    X
.X        ???     X.     
.                  .
E                E..

誰でもこの問題の解決策を考えられますか?

注: A* アルゴリズムは、方向転換の回数を考慮して結果のパスのターン数を少なくする以外は一般的なものです。

4

2 に答える 2

2

A* は、実際にはダイクストラのアルゴリズムの情報に基づいたバージョンです。したがって、[単一のソースから]すべての頂点への最短経路を見つけるように [許容ヒューリスティック関数を使用して]設計されています。

に隣接するすべてのタイルをターゲット頂点として定義できます[A* は複数のターゲットを適切に処理できます]。また、ヒューリスティック関数を変更して、任意のターゲット ノード(x,y)に許容値を与える必要があります。これは単に変更するだけで実行できますが、場合によってはもっと良い方法があるかもしれません。h'(tile) = max { h(tile) - 1 , 0}

上記を確立した後、元の A* に次の変更を加えることができます。

  1. [上記のように、ターゲット タイルを拡張した後] ターゲット タイルへのパスが見つかるまで、A* を実行します。パスの長さを とするd。
  2. ここで、開いているノードA*の最小 f(tile)値が厳密に よりも大きくなるまで、現在の状態で実行を続けdます。ソースから長さのパスで到達可能なすべてのタイルを見つけることが保証されますd。具体的には、長さのソースからのパスを持つすべてのターゲット タイルを見つけることができますd。[許容可能なヒューリスティック関数を仮定]。
  3. これらすべてのタイルから、「優先するもの」を選択し、それらへのパスを返すことができます。優先タイルが見つからない場合は、任意のターゲット タイルへのパスを返します。

それが役立つことを願っています！

于 2012-04-14T21:45:53.663 に答える
0

ヒューリスティック関数を変更して、ポイント(x+1,y)とをわずかにブーストし(x-1,y)ます。次に、パスを終了してから2ステップの場合、それらの2つのポイントを優先して関係が解除されます。

于 2012-04-15T22:17:56.897 に答える