[アルゴリズム]矩形和

矩形の合成問題の解答と説明

:今日はDPやダイナミックプランニングと呼ばれるダイナミックプランニング法に関する問題にほとんど執着しています(?)同じように、李文帝も同じだ.このタイプの答えはもっと解...まず今週はできるだけ多くの問題に触れたいのですが...難しすぎます.

もんだいぶんせき

問題は、

(x,y)~(z,a)から(任意のx,y,z,a)までの範囲内のすべての数字を加算する値を返すことです.

の条件の下で、n,mは所与のテーブルの大きさの横、縦の値が最大1000であるため、テーブルの大きさは最大1000*1000=10000000である.

また,質問のうち任意のx,y,z,aに対する質問は最大100万回まで質問できる.すなわち,最大100万回まで特定座標から特定座標への求和を問うことができる.これに基づいて、最悪の場合、100万個の問題を完全に探求的に表分析すれば、100万回*百万回は、事実上完全に探求しても解決できない問題である.

もんだいせっけい

もし

が見つからなかったら、どんな方法で解けばいいですか?まず私が学んだ2つの方法は分割征服法,動的計画法である.どちらも再帰呼び出しに関するソリューションですが、いずれにしてもそれらで解決できますか?

で「動的計画法」を使用して解きます.ではまず、

1)要求解の値を定義する(ローカル問題を定義する)。

私たちが最終的に要求した値は範囲内の数の和です.

というように、これと似たようなものを求めてみると、フィボナッチ数列のように、以前の値で現在の値を求める形で、あるいは再帰構造の値(非常に抽象的で難しいが)

を導出することができる.

和を求める観点から,前の後を求める方式を考えると,まず0,0から任意(x,y)の和を求めることができる.
そうすれば、こんなルールが见つかるはずだ.正直、これは創意的な面で、どうやってこれを発見できるかは説明できません.これは大量の練習、あるいは正直直感的なものです.いずれにしても、上の図を説明すれば、(0,0)~(1,1)を要求する和が成立することがわかります. T(n,m) = T(n,m-1)+T(n-1,m)-T(n-1,m-1) + T(n,m)
ここで、T(n,m)とは、(0,0)を基準として任意のn,mの間の数の和を求める式であり、この図を基準として式を説明すると、T(1,1)は、0,0を基準として1,1の間の数の和を求め、T(1,1)=表中の(1,0)+(0,1)-(0,0)+(1,1)+(1,1)+(1,1)+(1,1)
= -2 + -8 + 1 + -9 = -18
表示されます.これは、赤い線で区切られた部分の和+黄色い線で区切られた部分の和+が、現在検索する範囲の右下隅にある要素の値(浅緑の円)になります.黄、赤い線を計算するときに2回(0,0)計算される式です.この場合、x=0、すなわち、最初の行の式が通じない点に注意してください.T(0,3)を求めるために上記の式T(0,2)+T(−1,3)−T(−1,2)+T(0,3)を用いると、−1は一部に値がないので式は使えなくなる.したがって、最初の行は、例えば、現在の要素に前の要素を加える方法で計算されるべきである.T(n,m) =
1)最初の行:
=実表(n,m)+T(n,m-1)
=表中の(n,m)に対応する要素+その軸上の前の要素の和
2)2行目から:
= T(n,m-1)+T(n-1,m)-T(n-1,m-1) + T(n,m)
: 그럼 우리는 1번 단계로 어떤 값을 구할지를 결정했고(0,0부터 임의의 수 n,m까지의 요소들의 합을 구하기), 그것을 하다가 그것을 구하기 위한 식까지(위의 식)구했다. これは動的計画法の第2段階が完了したことを示している.

3）実コード実装

:以上のダイナミックプランニング式はコードで実現されており、エラーの部分j-1,i-1がそれぞれ0未満である場合、すなわち、上記で確立した式が適用できない部分については、最初の行のみが例外処理され、そうすることはできず、最上位と最左辺の行に対して例外処理を行うべきである.実際の実施では、アレイごとに実施されるので、x軸が-1の計算、y軸が-1の計算を例外的に処理しなければならない!

:最上位の問題テーブルをテストケースに戻し、0、0から特定の座標の和までの配列を生成し、上図に出力します.出力がよく見えるので、次のステップに進みます.

実際には、問題の設計はまだ終わっていません.我々が要求するのは(0,0)から特定座標までの数の和ではなく,(x,y)~(z,a)のように任意のx,y,z,aに対して要素の和を求める.ただそれを求めるために、問題を部分的にまとめ(ダイナミックプランニング法で)、今では元の主な問題を解決することができます.
:問題で示した例を考えると,(1,2)~(3,3)を求める.私たちが把握している情報に基づいてこれらの情報を導出するには、まず(0,0)からの情報を持っているので、これらの情報を利用するには、上図のようにピンク部分(問題の例)の和を求めることができ、それをめぐってand(0,0)を囲むことができます.最初の範囲の薄い緑色のブロック部分からピンク部分と青部分とオレンジ部分を外せばいいのではないでしょうか.(この場合は重複する部分を取り除く必要があります)浅緑色の部分(0,0から3,3までの範囲)-
[青の範囲(0,0から3,1の範囲)+オレンジの範囲(0,0から0,3の範囲)-減算を繰り返す範囲:黄色の範囲]
:上記の式を考えると、完全に問題を解くことができます.しかし、この場合、もう1つのブランチは処理する必要があります.
-このときlocationは[x,y,z,a]リスト(x,y,z,aは上で指定したインデックス範囲の順)
-boardは、上記で作成した0、0から特定の座標の合計からなる2次元配列

である.

ブランチ処理

まず、問題において提起された問題の範囲が0,0からであれば、プレート上に整理されたテーブルで見つけてすぐに戻るだけでよい(ex,0,0)~(3,3)、プレート[3][3].

しかし、開始頂点のインデックスが(0,x)である場合、

または(x,0)、

最後の開始点のインデックスが0でない場合、

=>これは私たちが最初にカラーブロックで表した場合の分割処理です.」ライトグリーン-(青+オレンジ-黄色)「

」

まとめとコメント

:この問題はダイナミックプランニング法のほかに、考慮すべき要素がたくさんあります.しかし、ダイナミックプランニング法にますます自信があるようだ.要求される値を定義することが最も重要であり、値を定義する過程でトピックを利用して再帰構造を見つけなければならない.すなわち,これまでの自分(例えばn−1)を用いてnの構造を求めることができる.これを見つけて、それを救う方法を見つけて、それから問題を解けばいいです.話は簡単だが、難しいから練習を続けよう.