リリース・改善中
Algorithm
貪欲法は各段階でその時点で最善に見える選択を行い、後戻りしない設計手法です。区間スケジューリング、ハフマン符号、分割可能ナップサックを高速に解きます。
貪欲法(グリーディ法)は、問題を一連の選択に分け、各段階で決められた基準に従ってその時点で最も良く見える候補を選び、その決定を二度と見直さないアルゴリズム設計手法です。候補をソートするか優先度付きキューに入れ、一つずつ取り出して採用するかを決める形がほとんどなので、コードは短く、計算量は多くの場合ソートやヒープ操作で決まる O(n log n) です。
貪欲法は当てはまる問題では最も速く単純な解法ですが、いつも正しいとは限りません。最適解を保証するには貪欲選択性と部分構造最適性が成り立つ必要があり、通常は交換論法で証明します。1・3・4の硬貨で6を作る問題のように反例が一つでもあれば、動的計画法を使う必要があります。ハフマン符号、ダイクストラ法による最短経路、最小全域木など、広く使われる重要なアルゴリズムにも貪欲法の考え方が含まれています。
学ぶときは区間スケジューリング(活動選択問題)から始め、「最も早く終わるものを選ぶ」という基準がなぜ正しいのかを交換論法で説明してみるのがよいでしょう。続いてハフマン符号、分割可能ナップサック、ヒープを使った会議室割り当てを実装し、小さな入力で全探索と結果を比べる習慣をつけると、コーディング面接や競技プログラミングで誤った貪欲基準を素早く見抜けます。
最初の貪欲な選択を含む最適解が必ず存在することが、貪欲法が正しく動くための中心的な条件です。
任意の最適解を一要素ずつ貪欲解に置き換えても悪くならないことを示し、基準の正しさを証明します。
終了時刻、重さあたりの価値、出現頻度などで候補を並べるかヒープから取り出すため、多くは O(n log n) で動作します。
任意の硬貨体系での両替や0/1ナップサックでは貪欲法が誤るため、動的計画法に切り替えます。
重ならない会議をできるだけ多く選ぶ区間スケジューリングです。会議を終了時刻順にソートし、直前に選んだ会議の終了後に始まる会議だけを採用します。ソートが O(n log n)、走査が O(n) で、例では11件の会議から4件を選びます。
greedy.py
def select_intervals(intervals):
"""Return a maximum set of non-overlapping half-open intervals [start, end)."""
chosen = []
last_end = float("-inf")
for start, end in sorted(intervals, key=lambda iv: iv[1]): # earliest end first
if start >= last_end:
chosen.append((start, end))
last_end = end
return chosen
meetings = [(1, 4), (3, 5), (0, 6), (5, 7), (3, 9), (5, 9), (6, 10), (8, 11), (8, 12), (2, 14), (12, 16)]
print(select_intervals(meetings)) # [(1, 4), (5, 7), (8, 11), (12, 16)]
python greedy.pyインストールから 貪欲法 の中心となる考え方まで、6 章で順を追って学びます。
貪欲法 について質問し、経験を共有し、意見を交わす場所です。
まだディスカッションはありません。最初の話題を始めましょう。
コメント 0件
ログイン · ログインするとコメントできます。
最初のコメントを書いてみましょう。