3

迷路を解くことは、ここ Stack Overflow で頻繁に議論されるトピックであることは知っています。ここで、皆さんが興味を持つかもしれない問題があります。

an*n 行列の形式の迷路が入力として与えられます。各要素は 0 ～ 9 の間にあります。0 から 9 までの一連の数字も与えられます。行列とシーケンス配列の次元も既知です。問題は、与えられたシーケンスを満たす (0,0) から (n-1,n-1) までのマトリックス内のすべての可能なパスを見つけることです。パスは、下、右、または下 + 右のみに移動できます。スレッドを使用して行う必要があります。

入力と出力の形式は、以下の例に示されています。

例: 例 1 http://gowthams.in/etc/1.PNG 例 2 http://gowthams.in/etc/2.PNG 例 3 http://gowthams.in/etc/3.PNG

各スレッドは、その位置 (i,j) を出力するか、何らかのデータ構造を更新して後で処理することができます。

この問題にアプローチする最善の方法は何ですか?

これは宿題の問題で、助けを求めることが許されています。私はどんな種類のコードも探していません。正しい方向へのいくつかの指針が欲しいだけです。

ありがとう！

4

1 に答える 1

3

的確なご指摘ありがとうございます。

1) この文はかなり不穏に思えます:

並列スキャンを確実にするために、マトリックス内の各エントリに対してスレッドを作成する必要があります。

これは、行列 NxN の場合、確実に N 2個のスレッドを作成する必要があることを意味するためです。これは、私にとってはかなり多すぎます。

ただし、ソリューションはさらに危険です。ルートのチェックを開始し、チェックごとに新しいスレッドを作成する必要があります。これにより、タスクを解決するために必要な指数関数的な数の新しいスレッドが作成されます。確かに何らかの最適化が必要です。これは動的最適化と呼ばれます。セルを使用して、インデックスからターゲットセルまで(i,j)のシーケンスを終了できるかどうかを共有メモリに保存します。idxそうすれば、同じサブタスクを複数回解決する必要がなくなります。そのようなタスクごとに条件付きロックを作成し[i,j,idx]、それを使用して、子スレッドが終了したときにそれに依存するスレッドに通知することをお勧めします。

2）複数のパスは問題になりません。割り当てを正しく読んだ場合、そのようなパスが存在するかどうかだけに興味がありますが、すべてのソリューションを見つけることはできません。

要求に応じて、正確な解決策を提供するのではなく、指示だけを提供します。これはまさに私が在宅勤務者を助ける傾向がある方法でもあります.

于 2012-11-04T12:41:37.123 に答える