アルゴリズム----五大アルゴリズムの貪欲法

欲張り法(Greedy algorithm)は、欲張りアルゴリズムとも呼ばれ、ステップ選択ごとに現在の状態で最良または最良(すなわち最も有利)の選択を行い、結果が最良または最良になることを望むアルゴリズムである.
1.基本概念
欲張りアルゴリズムとダイナミックプランニングの違いは、サブ問題ごとに解決策を選択し、後退できないことです.ダイナミックプランニングでは、以前の演算結果が保存され、以前の結果に基づいて現在が選択され、ロールバック機能があります.
欲張りアルゴリズムとは,問題を解く際に,常に現在から見れば最良の選択をすることである.すなわち,全体の最適化を考慮せずに,ある意味での局所最適解にすぎない.欲張りアルゴリズムには固定的なアルゴリズムフレームワークがなく、アルゴリズム設計の鍵は欲張り戦略の選択である.欲張りアルゴリズムはすべての問題に対して全体的に最適解を得ることができるのではなく,選択した欲張り戦略は,ある状態以降の過程が以前の状態に影響を及ぼさず,現在の状態にのみ関係する無後効性を備えなければならないことに注意しなければならない.だから、採用した貪欲な戦略に対して、後効性がないかどうかをよく分析しなければならない.
貪欲法はいくつかの最適化問題を解決することができて、例えば:図の中の最小生成木を求めて、ハフマン符号化を求めます......その他の問題に対して、貪欲法は一般的に私たちが要求した答えを得ることができません.一つの問題が貪欲法で解決できると、貪欲法は一般的にこの問題を解決する最善の方法である.欲張り法の効率性とその求めた答えが最良の結果に近いため、欲張り法は補助アルゴリズムとして使用したり、要求結果が特に正確ではない問題を直接解決したりすることもできる.
2.適用範囲
貪欲な戦略が適用される前提は、局所最適化戦略がグローバル最適解を生成することである.実際,貪欲アルゴリズムが適用されることは少ない.一般に,1つの問題解析が貪欲アルゴリズムに適用されるかどうかは,まずその問題の下のいくつかの実際のデータを選択して解析すれば判断できる.
3.欲張り法の手順
1.問題を記述する数学モデルを構築する.
2.解く問題をいくつかのサブ問題に分ける.
3.各サブ問題を解き、サブ問題の局所最適解を得る.
4.サブ問題の解の局所最適解を元の解の1つの解に合成する.
4.実装手順

           ；
while （           ）
{ 
       ，           ；
}
                 ；

5.典型的な問題
(1)0-1リュック問題
(2)馬盤
具体的な実装については、次を参照してください.http://baike.baidu.com/view/298415.htm?fromtitle=%E8%B4%AA%E5%BF%83%E6%B3%95