4.1 貪欲アルゴリズムの定義。
貪欲アルゴリズム (Greedy Algorithms) っていうのは、 各ステップで局所的に最適な選択をすることによって解決策を構築するアルゴリズムのクラスなんだ。 これらの選択は現在の状態に基づいて行われ、将来的に再評価されないんだよ。
貪欲アルゴリズムは、ある量を最大化または最小化することを目的とした最適化問題を解決するためによく使われるんだ。
貪欲アルゴリズムの基本原則
- 貪欲な選択: 各ステップで、アルゴリズムは最も良いローカルオプションを選ぶんだ。 グローバルに最適な解決策につながると信じられるものね。
- 最適な部分構造: 問題は、ローカルに最適な解決策を組み合わせて グローバルに最適な解決策を得ることができるという特性を持っていなければならないんだ。
- 単調性: 次のステップでローカルに最適な選択をしても 解決策が悪化しないことが必要だよ。
貪欲アルゴリズムの利点と欠点
利点:
- 実装の簡単さ: 貪欲アルゴリズムはしばしば理解しやすくて実装しやすいんだ。
- 効率性: 動的プログラミングのような、もっと複雑なアルゴリズムよりも速く動くことが多いよ。
欠点:
- グローバル最適性の欠如: 貪欲アルゴリズムは常にグローバルに最適な解決策にはならないことがあるんだ。
- 全ての問題には向いていない: 特定の問題だけが貪欲アルゴリズムで解決できるんだ。
貪欲アルゴリズムで最良の解決策が達成される問題のクラスがあるんだ。こういうのを知っておくと役立つよ。
4.2 コイン交換問題。
タスク:
異なる額面のコインがあるんだ。与えられた金額のお釣りをするために、最小枚数のコインを見つける必要があるよ。
解決策:
残りの金額を超えない最大額面のコインを常に取るんだ。
時間計算量: O(n), ここで n はコインの種類数だよ。
Pythonのコード例:
def min_coins(coins, amount):
coins.sort(reverse=True)
count = 0
for coin in coins:
while amount >= coin:
amount -= coin
count += 1
return count
4.3 ナップサック問題
タスク:
既知の価値と重さを持つアイテムがあるんだ。固定サイズのナップサックにできるだけ多くの価値を入れたいよ。
このバージョンの問題では アイテムは分割可能 なんだ。例えば、さまざまな穀物を1,000グラムでも512グラムでも欲しいように買える。
解決策:
単位コスト（価値/重さ）でアイテムをソートして、ナップサックがいっぱいになるまで最大の単位コストを選ぶんだ。
時間計算量: O(n log n), ここで n はアイテムの数だよ。
Pythonのコード例:
class Item:
def __init__(self, value, weight):
self.value = value
self.weight = weight
self.ratio = value / weight
def fractional_knapsack(items, capacity):
items.sort(key=lambda x: x.ratio, reverse=True)
total_value = 0.0
for item in items:
if capacity >= item.weight:
total_value += item.value
capacity -= item.weight
else:
total_value += item.ratio * capacity
break
return total_value
4.4 セグメントカバレッジ問題
タスク:
直線上に端点 (x1, x2) で示されるセグメントがあるんだ。ターゲットセグメントを覆う最小数のセグメントを見つける必要があるよ。
解決策:
セグメントを右端でソートして、現在の点をカバーする最小のセグメントを選ぶんだ。
時間計算量: O(n log n), ここで n はセグメントの数だよ。
Pythonのコード例:
def min_segments(segments):
segments.sort(key=lambda x: x[1])
count = 0
end = -float('inf')
for seg in segments:
if seg[0] > end:
end = seg[1]
count += 1
return count
GO TO FULL VERSION