問題タブ [divide-and-conquer]

動的プログラミングに関するメモを読んでいたところ、次のコメントに遭遇しました。

サブ問題が独立していない場合、つまりサブ問題がサブサブ問題を共有している場合、分割統治アルゴリズムは共通のサブサブ問題を繰り返し解決します。したがって、必要以上の作業を行います

これは何を意味するのでしょうか ？上記の点を明確にするために例を挙げていただけますか?

分割統治について話しているときは、常に再帰を使用します。分割統治はアルゴリズム設計の手法であることはすでに知っていますが、1つの質問があります。

すべての分割統治アルゴリズムの再帰ですか、または別の言い方をすれば、分割統治の考え方はすべての再帰で採用されていますか？

よくわかりません 。

通常のパーティションは、インデックス i <= j を持つ各要素が選択されたピボットよりも小さく、インデックス m > j を持つ各要素がピボットよりも大きくなるようなインデックス j を返すため、j がピボットであるという保証はありません。新しいピボット位置を正確に返す別のインプレース パーティション アルゴリズムを作成することは可能でしょうか? 最初はチョイスンピボットを最後に動かそうと思ったのですが、最適解には至りません。

私が理解していることから、行列を乗算するための Strassen の方法は最速であるはずです...しかし、Divide & Conquer 方法は私のテストでは明らかに最速です...私は何か間違ったことをしていますか? それともこれは正しいですか？

指示は次のとおりです。

したがって、すべてのメソッドに個別の「カウンター++」があり、時間を「記録/カウンター++」で分割します

これまでのところ、私の時間は次のとおりです: (上/下の順に: クラシック、分割統治、ストラッセン) (サイズ = マトリックスのサイズ)

サイズ 2

経過時間:8660 ナノ秒

経過時間:3849 ナノ秒

経過時間:5377 ナノ秒

サイズ 4

経過時間:24864 ナノ秒

経過時間:3080ナノ秒

経過時間:5229 ナノ秒

サイズ 8

経過時間:125435 ナノ秒

経過時間:2920 ナノ秒

経過時間:5196 ナノ秒

サイズ 16

経過時間:867149 ナノ秒

経過時間:1559 ナノ秒

経過時間:2853 ナノ秒

サイズ 32

経過時間:5191721 ナノ秒

経過時間:972ナノ秒

経過時間:1722 ナノ秒

サイズ 64

経過時間:8155785 ナノ秒

経過時間:874ナノ秒

経過時間:1696 ナノ秒

サンプル出力 サイズ 4 の行列の出力例を次に示します。

1 番目のランダム生成行列: 10 57 33 70
6 12 38 70
20 41 65 98
83 0 31 73
2 番目のランダム生成行列: 11 70 54 79
2 51 38 71
27 53 37 86
48 87 20 41
従来の乗算行列: 4475 53144
4476 9136 3586 7464
6761 15462 7003 14099
5254 13804 7089 12216
経過時間:21232 ナノ秒

分割統治乗算行列: 4475 11446 5327 10545
4476 9136 3586 7464
6761 15462 7003 14099
5254 13804 7089 12216
経過時間: 3042ナノ秒

Strassen 乗算行列: 4475 11446 5327 10545
4476 9136 3586 7464
6761 15462 7003 14099
5254 13804 7089 12216
経過時間: 5303ナノ秒

質問に行き詰まっており、一般的な方向性のヒント/ポイントが必要です (答えを求めるのではありません)。

この質問は、ほぼソートされたシーケンスを指定して、時間 O(n) で正しい順序を生成する分割統治アルゴリズムの詳細を求めています。

ほぼソートされているということは、リストが与えられたということです

x_1、x_2、.... x_n

ソートされたリストが

y_1、y_2、... y_n

そして、すべての i、j <= n について、このプロパティが尊重されます。

x_i == y_j && |ij| <= ルート(n)

私の頭に浮かんだ唯一のことは、リストを各レベルでルート（n）グループに分割することでした（これにより、最初の分割では最大でルート（n）の長さになります）が、どこにあるのかよくわかりません再帰的に元に戻すときに、一度に root(n) 個の要素を結合する必要があるためです。

また、再帰の複雑さの方程式は次のようになることもわかりました。

T(n) = ルート(n) * T(n/ルート(n)) + d * ルート(n)

これにより、master's theoremO(n) 時間であることが証明できます。

だから、私は分割で正しい方向に進んでいるように見えますが、特別な方法で分割する必要があるのか​​ 、それとも特定の方法で比較する必要があるのか​​\u200b\u200bわかりません。

編集：おそらくこれが正しい答えでした。

アルゴリズムは次のとおりです。n > 1 の場合、シーケンスの 2 つの (近似) 半分のそれぞれを再帰的に並べ替えます。これで、すべての要素が正しい位置に配置されました。ただし、中央から √n の位置にある要素を除きます (これが正しい理由がわかりますか?)。そのため、これらの位置の要素をマージします。T(n) を n 個の要素のソートに使用する時間とすると、n > 1 の場合、次のようになります。

T(n)≤2T(⌈n=2⌉) +c * √n

√(n) = n ^.5および .5 < 1 = log ₂ 2 なので、分割統治の再帰のマスター定理は、T(n)∈O(n) を教えてくれます。

両方の半分をソートする時間は O( ⁿ ⁄ ₂ * log( ⁿ ⁄ ₂ )) であり、結果として O(n*logn) になり、最終的なマージは O(√ n * √n) これは O(n) であり、合計 O(n*logn + n) -> O(n*logn) となります

次元が非常に大きいと仮定します（マトリックス内の最大10億個の要素）。行列-ベクトル積のキャッシュ忘却アルゴリズムをどのように実装しますか？ウィキペディアに基づいて、再帰的に分割統治する必要がありますが、多くのオーバーヘッドがあるように感じます。そうすることは効率的でしょうか？

質問と回答のフォローアップ：行列とベクトルを使用したOpenMP

openmpを使用してGuibas Stolfi delaunay 三角形分割を並列化しようとしています。

ここで並列化することが 2 つあります。私はすべての可能なアプローチを試みましたが、無駄でした。

分割 () で従うアプローチ (分割 n 征服) は、マージソート () のアプローチと同じですが、同じ並列化手法 (omp セクション) の適用は、マージソートに対してのみ機能します。

ここに示す並列化手法を試しましたが、それでもうまくいきません。ネストされた並列処理についてどこかで読みましたが、それを実装する方法がわかりません。分割統治アルゴリズムがどのように並列化されているか説明できる人はいますか?

CODE:メイン関数と適用されたセクション構成でマージソートが 2 回呼び出されました。除算関数で同じことを行っても機能しません

次の特別な局所性プロパティを持つ 3SAT インスタンスを考えてみましょう。ブール式に n 個の変数があり、それぞれの句が互いに +-10 以内の変数を含むように、1、2、3....n の番号が付けられているとします。このような 3SAT のインスタンスを解くための線形時間アルゴリズムを与えてください。

私は問題を解決できませんでしたが、私の直感では、問題をグラフにマッピングできれば解決できるかもしれませんが、それ以上先には進めない..

配列 a[1..n] のある順序付けられた型 (つまり、x < y は常に定義されています) の要素の配列で、「分割統治」アルゴリズムを使用して配列内の最小値を見つけたいと考えています。

任務の本当の意味とは？

ご存知のとおり、Rは大規模な分析を実行するための最も効率的なプラットフォームではありません。3つのパラメータを含む大きなデータフレームがある場合：

そして、各グループで計算を実行し（たとえば、X、Yでピアソンのrを計算）、結果を新しいデータフレームに格納したかったので、次のように実行できます。

明らかな問題は、強力なマルチコアマシンであっても、これが非常に遅いことです。

私の質問は次のとおりです。たとえば、グループごとまたはグループのブロックごとに個別のスレッドを使用して、この計算を並列化することは可能ですか？この単純な分割統治問題を解決するためのクリーンなRパターンはありますか？

ありがとう、Mulone