[貪欲法 考え方] 部分問題の最適化を繰り返して大きな問題を解く
プログラムはとある現実の問題を解くために書くものです。問題に対して適切なプログラムを書くためにはまず、「その問題がどんな問題であるか」を理解し、適切に解釈する必要があります。
フレームワーク思考など、問題解決のアプローチを謳ったビジネス書などがありますが、プログラミングにもその類のものがあります。
問題解決のフローチャート
プログラムは問題解決の手順書ですが、それらの手順はアルゴリズムによって構成されています。つまりプログラムはアルゴリズムの組み合わせで構成されているわけです。そして、そのほとんどのアルゴリズムは決して新規で新奇なものではなく、偉大な先人の考えた枠組みのなかで構築されているものです。
車輪の再発明をすることも大変勉強的ではありますが、実社会においては目の前の問題をより素早く解決することが要請されます。ですので、まず問題の解釈を行い、それに対して「適切なアルゴリズムを選択する」ことが肝要です。
一般的な問題解決の方法は下記のようなフローチャートとして知られています。
上記のとおり、一般的な問題解決のアプローチとして、まず、その問題が貪欲法で解けるのかを考えます。
貪欲法
貪欲法とは、その問題に対して、
- 部分的な最適処理を繰り返すことで最終的な結論を導くアルゴリズムです
イメージとして、あなたが瓦礫からレンガの壁を作ることを想像してみてください。
この問題は
- レンガの壁をつくる
ことが目的となります。
ただし、「瓦礫から」という条件をわすれないでください。つまり、レンガの壁をつくるまえに瓦礫から使えそうなレンガを選ばなければならないのです。
- 瓦礫からレンガを選ぶ
という問題がまず解くべき問題なのです。
この使えそうな瓦礫を選ぶ行為が貪欲法の「部分的な最適化」に相当します。壁をつくるために最適なレンガの選択を繰り返すことで一段づつ壁を作っていくわけですね。
よって、この問題は
- 瓦礫のなかから使えそうなレンガの選択を繰り返すことでレンガの壁をつくる
ことで解くことができます。
貪欲法が利用されているアルゴリズム
- 挿入ソート
- 選択ソート
- トポロジカルソート
- プリム法
- クラスカル法
- 活動選択(例：コンサートスケジュール)
- コイン交換（例：ATM）
- 分数ナップザック
今回はここまで、ではでは