貪欲法
各段階で局所的に最良の選択を重ね、結果が全体でも最適になることを期待する戦略。常にそうとは限らないが、使える場面は意外に多い。
成り立つのは、問題が貪欲選択性(局所最適が全体最適につながる)と最適部分構造を持つときだ。典型例はダイクストラ法(貪欲+DP)、クラスカル法とプリム法による最小全域木、ハフマン符号化、活動選択問題。
うまくいけば高速(通常O(n log n))で実装も容易。罠は、貪欲に見えてそうではない問題(ナップサック問題、分割問題)だ。貪欲法が通用しないときの競合相手は動的計画法とバックトラッキングである。