1

各セルが 1 または 0 のいずれかを含むことができる 2 次元の m*n グリッドを考えてみましょう。このグリッドを移動することにより、トラバーサルが取得できる最大値を見つけます。値は、1 セルを斜めにトラバースすることで増加できます。グリッドの走査は、次の規則に従います。

  1. 左上のセルから開始します。
  2. 各セルで、走査は 1 グリッド下に移動するか、1 グリッド右に移動するか、斜めに移動します (1 グリッド下に移動し、1 グリッド右に移動します)。セルに 1 が含まれていて、トラバーサルが斜めに移動する場合、トラバーサル値は 1 増加します。
  3. トラバーサルはグリッドから移動できません (右端で右に移動できない場合、下端で下に移動できない場合)。
  4. 右下隅で終了します。

単純なアルゴリズムは、3*m*n 回のトラバーサルをすべて考慮し、最大値を選択します。誰かがより良い解決策を考え出すのを手伝ってくれますか? 同様の問題を解決するアルゴリズムはありますか?

これはインタビューの質問ではありません。Smith-Waterman アルゴリズムを最適化するために必要です。

例:

次のグリッドの最大値は 2 です。

ここに画像の説明を入力

これの最大値は 7 です。

ここに画像の説明を入力

4

3 に答える 3

3

動的計画法を使用します。

dp[i, j] = maximum value obtainable from [1, 1] to [i, j]
dp[1, _] = dp[_, 1] = 0 -> we cannot get to any of these diagonally
dp[i, j] = max(dp[i - 1, j], -> come from above
i, j > 1       dp[i, j - 1], -> come from the left
               dp[i - 1, j - 1] + v[i, j] -> come diagonally and add what is at [i, j]
              )

答えは にありますdp[m, n]。

複雑さはO(n*m)で、入力を読み取るだけでこれだけかかるので最適です。

ノート：

単純なアルゴリズムでは、3*m*n 回のトラバーサルがすべて考慮され、最大値が選択されます。

これは実際にはである必要があります3 to the power of (n*m)。なぜなら、各セルに対して、総当たりで 3 つの可能性があるからです。

于 2014-03-09T07:08:16.570 に答える
1

問題は、頂点がセルを表し、エッジが隣接するセルまたは斜めの隣接するセル間の可能な接続を表すグラフの問題に変換できます。

すべてのエッジの重みは 0 ですが、1 セルから始まる斜めの移動を表すものを除きます。

問題を有向非巡回グラフ (DAG) の最長経路問題に変換しました。これは、負の等価重みを持つ DAG で最短経路問題を解くことと同じです (つまり、重み 1 のすべてのエッジが重み -1 になります)。

負の重みを持つ DAG の最短パスには、Bellman-Ford アルゴリズムを使用します。http://en.wikipedia.org/wiki/Bellman-Ford_algorithm

于 2014-03-25T15:48:19.877 に答える
0

対角線上を再帰的に分岐し、最も高い値のみをインテリジェントに枝刈りする方法があるかもしれませんが、このアプローチは複雑すぎます。

並列化可能な Smith-Waterman アルゴリズムについてこの質問をしましたが、最終的にこれを使用しますhttp://biochem218.stanford.edu/Projects%202002/Byang.pdf

于 2014-03-09T23:23:54.283 に答える