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

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

分割統治法

分割統治アプローチでは、問題はいくつかの小さなサブ問題に分割されます。次に、サブ問題が再帰的に解決され、組み合わされて、元の問題の解決策が得られます。

分割統治法には、各レベルで次の手順が含まれます。

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

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

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

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

動的計画法は、問題をより小さなサブ問題に分割する最適化手法であり、各サブ問題を解決した後、動的計画法はすべてのソリューションを組み合わせて最終的なソリューションを取得します。分割統治法とは異なり、動的計画法はサブ問題の解を何度も再利用します。

フィボナッチ数列の再帰的アルゴリズムは、動的計画法の一例です。

バックトラッキングは、組み合わせの問題を解決するための最適化手法です。これは、プログラムによる問題と実際の問題の両方に適用されます。エイトクイーンの問題、数独パズル、迷路の通過は、バックトラッキングアルゴリズムが使用される人気のある例です。

バックトラックでは、必要なすべての条件を満たす可能な解決策から始めます。次に、次のレベルに移動し、そのレベルで満足のいく解決策が得られない場合は、1つのレベルに戻って、新しいオプションから始めます。

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

分枝限定法の目的は、ターゲットへの最低コストのパスを維持することです。解決策が見つかると、解決策を改善し続けることができます。分枝限定法は、深さ限定検索と深さ優先探索で実装されます。

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

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