15.5 まとめ
- 貪欲アルゴリズムは最適化問題を解決するためによく使用され、原理は各決定段階で局所的に最適な決定を行い、グローバルに最適な解を達成することです。
- 貪欲アルゴリズムは貪欲な選択を次々と反復的に行い、各ラウンドで問題をより小さな部分問題に変換し、問題が解決されるまで続けます。
- 貪欲アルゴリズムは実装が簡単なだけでなく、問題解決効率も高いです。動的プログラミングと比較して、貪欲アルゴリズムは一般的により低い時間計算量を持ちます。
- コイン交換問題において、貪欲アルゴリズムは特定のコインの組み合わせに対して最適解を保証できますが、他の組み合わせでは貪欲アルゴリズムが非常に悪い解を見つける可能性があります。
- 貪欲アルゴリズム解法に適した問題は2つの主要な性質を持ちます：貪欲選択性と最適部分構造。貪欲選択性は貪欲戦略の効果を表します。
- 一部の複雑な問題では、貪欲選択性を証明することは簡単ではありません。逆に、無効性を証明することはしばしばより容易で、コイン交換問題などがその例です。
- 貪欲問題の解決は主に3つのステップから構成されます：問題分析、貪欲戦略の決定、正しさの証明。このうち、貪欲戦略の決定が重要なステップであり、正しさの証明がしばしば挑戦となります。
- 分数ナップサック問題は0-1ナップサック問題に基づいてアイテムの一部の選択を可能にし、したがって貪欲アルゴリズムを使用して解決できます。貪欲戦略の正しさは背理法によって証明できます。
- 最大容量問題は全探索法で解決でき、時間計算量は \(O(n^2)\) です。貪欲戦略を設計することで、各ラウンドで短い板を内側に移動し、時間計算量を \(O(n)\) に最適化します。
- 切断後の最大積問題において、2つの貪欲戦略を導出します：\(\geq 4\) の整数は継続的に切断されるべきで、最適な切断因子は \(3\) です。コードにはべき乗演算が含まれ、時間計算量はべき乗演算の実装方法に依存し、一般的に \(O(1)\) または \(O(\log n)\) です。