15.5 まとめ
1. 重要な振り返り
- 貪欲法は通常、最適化問題を解くために用いられ、その原理は各意思決定段階で局所最適な決定を行い、全体最適解を得ることを目指すというものである。
- 貪欲法は反復的に次々と貪欲な選択を行い、各ラウンドで問題をより小さな部分問題へと変換し、最終的に問題を解決する。
- 貪欲法は実装が簡単であるだけでなく、問題を解く効率も高い。動的計画法と比べると、貪欲法の時間計算量は通常より低い。
- 硬貨両替問題では、ある種の硬貨の組み合わせに対しては貪欲法で最適解を保証できるが、別の組み合わせではそうではなく、非常に悪い解を見つけてしまう可能性がある。
- 貪欲法による解法に適した問題は、貪欲選択性と最適部分構造という 2 つの性質を備えている。貪欲選択性は、貪欲戦略の有効性を表している。
- 一部の複雑な問題では、貪欲選択性を証明するのは容易ではない。相対的には、反例による否定のほうが簡単であり、硬貨両替問題がその一例である。
- 貪欲法の問題を解く流れは主に 3 段階に分かれる。すなわち、問題分析、貪欲戦略の決定、正しさの証明である。このうち、貪欲戦略の決定が中核であり、正しさの証明はしばしば難所となる。
- 分数ナップサック問題は 0-1 ナップサックを基に、品物の一部を選ぶことを許しているため、貪欲法で解くことができる。貪欲戦略の正しさは背理法で証明できる。
- 最大容量問題は全探索で解くことができ、時間計算量は \(O(n^2)\) である。貪欲戦略を設計し、各ラウンドで短い板を内側へ動かすことで、時間計算量を \(O(n)\) に最適化できる。
- 最大分割積問題では、2 つの貪欲戦略を順に導いた。すなわち、\(\geq 4\) の整数はすべてさらに分割すべきであり、最適な分割因子は \(3\) である。コードにはべき乗演算が含まれており、時間計算量はその実装方法に依存し、通常は \(O(1)\) または \(O(\log n)\) である。