並列アルゴリズム-設計手法

並列アルゴリズムに適した設計手法を選択することは、最も困難で重要なタスクです。並列プログラミングの問題のほとんどには、複数の解決策があります。この章では、並列アルゴリズムの次の設計手法について説明します-

分割統治
貪欲な方法
動的計画法
バックトラッキング
分岐とバインド
線形計画

分割統治法

分割統治アプローチでは、問題はいくつかの小さな副問題に分割されます。次に、副問題が再帰的に解決され、元の問題の解決策を得るために結合されます。

分割統治アプローチには、各レベルで次の手順が含まれます-

分割-元の問題はサブ問題に分割されます。
征服-副問題は再帰的に解決されます。
結合-副問題の解決策を組み合わせて、元の問題の解決策を取得します。

分割統治アプローチは、次のアルゴリズムに適用されます-

二分検索
クイックソート
ソートをマージ
整数乗算
マトリックス反転
行列乗算

貪欲な方法

最適化ソリューションの貪欲なアルゴリズムでは、いつでも最適なソリューションが選択されます。貪欲なアルゴリズムは、複雑な問題に非常に簡単に適用できます。次のステップで最も正確なソリューションを提供するステップを決定します。

このアルゴリズムは greedy と呼ばれます。これは、小さいインスタンスに対する最適なソリューションが提供されると、アルゴリズムがプログラム全体を考慮しないためです。解決策が考慮されると、貪欲なアルゴリズムは同じ解決策を再度考慮しません。

貪欲なアルゴリズムは、可能な限り小さいコンポーネントパーツからオブジェクトのグループを再帰的に作成します。再帰は、特定の問題の解決策がその問題の小さなインスタンスの解決策に依存する問題を解決する手順です。

動的計画法

ダイナミックプログラミングは最適化手法であり、問題をより小さなサブ問題に分割し、各サブ問題を解決した後、ダイナミックプログラミングはすべてのソリューションを組み合わせて究極のソリューションを取得します。分割統治法とは異なり、動的プログラミングでは、サブ問題に対するソリューションを何度も再利用します。

フィボナッチ数列の再帰アルゴリズムは、動的プログラミングの例です。

バックトラッキングアルゴリズム

バックトラッキングは、組み合わせの問題を解決する最適化手法です。これは、プログラムの問題と現実の問題の両方に適用されます。 8つのクイーンの問題、数独パズル、迷路を進むことは、バックトラッキングアルゴリズムが使用される一般的な例です。

バックトラッキングでは、考えられるすべての条件を満たすソリューションから始めます。次に、次のレベルに移動し、そのレベルで満足のいく解決策が得られない場合は、1つのレベルに戻り、新しいオプションから始めます。

分岐とバインド

分岐限定アルゴリズムは、問題の最適な解決策を得るための最適化手法です。解決策の全領域で、与えられた問題に対する最適な解決策を探します。最適化される関数の境界は、最新の最適なソリューションの値とマージされます。これにより、アルゴリズムは解空間の一部を完全に見つけることができます。

分岐限定検索の目的は、ターゲットへの最低コストのパスを維持することです。ソリューションが見つかると、ソリューションを改善し続けることができます。分岐限定検索は、深さ限定検索および深さ優先検索で実装されます。

線形計画

線形計画法は、最適化基準と制約の両方が線形関数である幅広いクラスの最適化ジョブを表します。これは、最大の利益、最短の経路、または最低のコストなど、最高の結果を得るための手法です。

このプログラミングでは、変数のセットがあり、それらに絶対値を割り当てて、線形方程式のセットを満たし、与えられた線形目的関数を最大化または最小化する必要があります。

Parallel-algorithm-design-techniques

目次