3

私は現在、乱数を含む 2 次元配列でタスクを実行する必要があるプロジェクトに取り組んでいます。配列は、山の頂点 (高さ) を表すグリッドを形成します。最後のタスクを除くすべてのタスクを解決しました。

最後のタスクは、最小のピークから最大のピークに至る経路が存在するかどうかを見つけることです (最短である必要はありません)。道は絶え間なく成長するピークで構成されている必要があり、それより低いピークを踏むことはできません。

簡単にするために、3x3 グリッドで表した例を次に示します (元のサイズははるかに大きく、正方形である必要はありません。ユーザーが望むように生成され、数字は完全にランダムです)。

2  4  5    
1  3  8
9  7  10

可能な方法は、1-3-7-10、1-3-8-10、1-2-4-5-8-10 です。

ある種の再帰を使用する必要があると確信しています。*パスファインダーについて読みましたが、それを使用するには、「障害物」（ステップできないノード=小さなピーク）を含む「マップ」が必要であり、それはまさに私が作成できないものです。あなたは外出先でそれを見つけるだけです。

つまり、7 番を「例外リスト」に入れることができるということです。手順 1-9-7 は禁止されていますが、手順 1-3-7-10 は完璧なので、例外リストに 7 を入れるのは間違いです。

4

3 に答える 3

3

重要なのは、最初に配列を「有向グラフ」に変換することです。これは、ルールに従って有効なセル間の移動のみで構成される有向グラフです。このダイグラフは、{FromCell, ToCell} で構成されるエントリの配列またはリストになります。

有向グラフには、次のようなデータが含まれます。

2,4
4,5
5,8
1,2
1,3
1,9
3,4
3,8
3,7
8,10
7,10

ここから、A* アルゴリズム、または他の多くのアルゴリズムのいずれかを適用できるはずです。

（注：あなたがこれを自分でやりたいと思っているので、私は完成した回答を投稿していません）

とはいえ、バックトラッキングを使用して総当たり再帰検索を実行することもできます。おそらく最も効率的ではありませんが、これは最も簡単な解決策です。

于 2012-11-20T19:49:40.157 に答える
0

次のことができます。

  1. マトリックスから重み付きグラフを作成します (各エッジの重みは絶対値 (2 つのノードの値の差) になります)

    2 - 4 - 5

|   |   |

1 - 3 - 8

|   |   |

9 - 7 - 9

(2, 4) の重みはabs(4 - 2) = 2

(4, 5) の重みはabs(4 - 5) = 1

  1. エッジの重みを考慮した最短経路アルゴリズムを適用しますhttp://www.informatics.susx.ac.uk/courses/dats/notes/html/node147.html

  2. ノードの値が昇順でないソリューションを削除します

于 2012-11-20T19:49:53.613 に答える
0

（投稿を修正し、ここに回答を配置しました。）

これが私が最終的に解決した方法です：

最小値と最大値は既にあるので、元の配列をゼロで囲みました。デフォルトではゼロを生成しないため、ゼロは配列のグローバルな最小値です。これにより、私が外にいるか配列にいるかを毎回チェックする必要はありません (より大きな数字を踏むだけです)。

2 つのキュー (QueueX、QueueY) を作成しました。最小の番号から始めます (最初にキューに入れ、配列 t[x,y] の x,y 変数に与え、次にキューから外します)。

次に、すべての大きな数値の「座標」をそれぞれのキューに入れます。実際のポイント (t[x,y]) の周りに大きな数値がすべて見つかった場合は、次の X、Y 座標をキューに入れます。これが新しい実際のポイントになります (冒頭で説明したように)。そして検査は繰り返される。

全体が while サイクルにあり、キューの 1 つが空になるまでそのままになります。

任意の検査で、X、Y が最大ピークの X、Y 座標と同じである場合は、戻り、パスが存在します。while サイクルの最後に、X、Y が max の X、Y と同じでない場合、パスはありません。

私の説明がある程度理解できることを願っています。英語は私の母国語ではありません。よろしければ、ここにコードを投稿できます。

于 2015-02-05T20:11:12.707 に答える