Pythonで貪欲法(Greedy Algorithm)を実装してみる-ABC076

今回の記事ではPythonで貪欲法(Greedy Algorithm)を実装していきます。

貪欲法は最適化手法の中でも基本的なアルゴリズムで比較的実装も簡単なので書けるようにしておきましょう。

貪欲法とは

貪欲法とはその場その場で最善の手のみを選び続けるというアルゴリズムです。

問題を部分問題に分割し、それぞれの問題を独立して評価を行います。

少し動的計画法(DP)にも似ていますが、異なっている点として貪欲法は以下のような特徴があります。

• 保持する状態は常に一つ
• 一度選択した要素を再考する事は無い

このような特徴があるために貪欲法で得られた解が最適解ではない可能性があることに注意しましょう。

例題

それでは問題を解いていきます。今回は以下の問題を扱います。
atcoder.jp

問題文

square1001 は、電光掲示板に整数 1が表示されているのを見ました。
彼は、電光掲示板に対して、以下の操作 A, 操作 B をすることができます。
・操作 A： 電光掲示板に表示する整数を「今の電光掲示板の整数を 2倍にしたもの」に変える。
・操作 B： 電光掲示板に表示する整数を「今の電光掲示板の整数に Kを足したもの」に変える。
square1001 は、操作 A, 操作 B 合計で N回 行わなければなりません。 そのとき、N 回の操作後の、電光掲示板に書かれている整数として考えられる最小の値を求めなさい。

制約

1≤N,K≤10
入力はすべて整数

実装

問題としては非常に簡単なので、貪欲法を理解するのに良い問題かなと思います。

実装の方針としてはまずN回正しい操作を選ぶという問題を部分問題に分割して考えます。

そして1回の操作ごとにその場での最適な操作方法を選びます。

すなわち、for文で操作Aと操作Bを行った時の整数の小さい方をひたすら選び続けるだけです。

私は以下のように実装してみました。

n = int(input())
k = int(input())
start = 1
for i in range(n):
    start = min(start*2,start+k)
print(start)

簡単ですね。

もう少し難しい問題を解いてみたいという人はぜひ以下のような問題にもチャレンジしてみてください。
atcoder.jp

さいごに

貪欲法を知らなかったけど貪欲法を実装したことあったなと思った方もいるのではないでしょうか。

私もそうでした。これからはちゃんと貪欲法を理解したうえで実装していきたいと思います。

おわり