アルゴリズムiは次のように私が持っている問題が行く

Question

に移動することができる（簡略化）：

• Iボード、n×m個の正方形の行列として表される（nはMに等しいかもしれないを有しますそれは）
  
• 、Pゲームの部分
  
• 各ゲームの駒があり、それが
  
• PIECを回しています、それは取ることができますどのように多くの手順で事前に定義された速度を、していますあなたは交差する余分な動きを必要としない（あなたは通過する際に余分な速度が0になります）、1回の余分な動きが必要なもの、
  A）すべての観光スポット：あなたは単に私が知りたい、私のゲームボード内の特定の[i,j]位置にゲームピースを与え、そう
  
（壁のような）を介して

を取得することはできません速度に移動することができます。
b）ボード上の特定の[k,l]の位置

a）解決済み、b）はほとんどありません。次のように 現在私が使用しているアルゴリズムは、サイズnの配列がn-1に0から行くの言語を想定し、行く：

• として移動のコストを表しスピード* 2 + 1サイズのsqaure行列を作成します。
  
• 速度* 2 + 1サイズの別の正方行列を作成します。これには各セルの余分なコストが含まれています（可能なものは次のとおりです。それは壁であるか、その中の別の部分が無限の値であるために交差しません）（ピースは[速度、速度]の位置にあります）
  
• 前の2つの合計である速度* 2 + 1サイズの別の正方行列を作成します（ピースは[速度、速度]の位置にあります）
  
• 各セルの値が：すべての隣接セルの最小コスト+ 1 +セルの余分なコスト。そうでなければ、それを修正して、行列全体をもう一度始めます。

例：
PはXが交差する余分な動きを必要とする細胞である、Eが余分な動きを必要としない空のセルであり、Wは壁である、作品です。

X,E,X,X,X 
X,X,X,X,X 
W,E,E,E,W 
W,E,X,E,W 
E,P,P,P,P 

第1の行列：

2,2,2,2,2  
2,1,1,1,2  
2,1,0,1,2  
2,1,1,1,2  
2,2,2,2,2 

第2のマトリックス：

1,0,1,inf,1  
1,1,1,1,1  
inf,0,0,0,inf  
inf,0,1,0,inf  
0,inf,inf,inf,inf 

和：

3,2,3,3,3  
3,2,2,2,3  
inf,1,0,1,inf  
inf,1,2,1,inf  
inf,inf,inf,inf,inf 

[0,0]がではないので、私はそれを修正： 和：

4,2,3,3,3  
3,2,2,2,3  
inf,1,0,1,inf  
inf,1,2,1,inf  
inf,inf,inf,inf,inf 

[0,1]が2+1+0ないので、私はそれを修正： 和：[0,2]ので

4,3,3,3,3  
3,2,2,2,3  
inf,1,0,1,inf  
inf,1,2,1,inf  
inf,inf,inf,inf,inf 

は、私はそれを修正し、2+1+1ない。 合計：

4,2,4,3,3  
3,2,2,2,3  
inf,1,0,1,inf  
inf,1,2,1,inf  
inf,inf,inf,inf,inf 

どちらが正しいですか回答？この問題は、私はで（何かを見つけることができませんでした）、または誰もがどのようにポイントA）を解決するために私を伝えることができるならば、それを検索することができます名前を持っている場合、私が知りたいのは何
です。

私は最適な解決策が必要なので、私は動的プログラミングアルゴリズムを使いました。ランダムな歩行者は良いかもしれない？ AFAIK、このソリューションは（まだ）失敗していませんが、私はそれの正確さの証拠がありません、そして、私はそれが動作することを確認したいです。

Answer 1

A-starが移動するの平方当たり2Dボードやコスト上の障害物を与える最短経路を決定するための標準的なアルゴリズムです。特定の移動が有効かどうかをテストするためにも使用できますが、実際にすべての有効な移動を実際に生成するには、単に開始位置を開始し、正方形が有効な1つの四角いマークで移動し、再び同じ広場を訪れないようにしています。これは、各呼び出しで最大4回呼び出される再帰的アルゴリズムとなり、有効な移動を効率的に生成します。いくつの四角形のような制約がある場合、一度に異なるコストで移動することができます。