パス発見アルゴリズムの難易

Question

問題：

は、我々が少ないターン用に最適化A *アルゴリズムを変更します。アルゴリズムは、可能であれば（x + 1、y）または（x-1、y）が好ましくは である（a、b）からANY TILE ADJACENT TO（x、y）までの パスを見つける。

マイ試み溶液：

1. 実行元の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 *アルゴリズムは、結果のパスのターン数を減らすために、方向変更の回数を因数分解する以外の一般的なものです。

Answer 1

A *は、このように、実際[単一のソースからの全ての頂点への最短パスを見つけるために[admissible heuristic関数で】設計され、実際Dijkstra's algorithmが通知バージョンです。

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

上記を確立した後、我々は、元のA *に次の修正を得ることができます：あなたは、ターゲットタイルの拡張後[ などをターゲットタイルへのパスを見つけるまで、

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

私は助けてくれることを願っています！

Answer 2

ヒューリスティック機能を変更して、(x+1,y)と(x-1,y)という点をわずかに押し上げます。パスを終えるまでに2ステップがあれば、その2ポイントを優先してネクタイを壊します。