🏃
AI Sketch（スケッチ） • 中級⏱️ 17 分で読める
貪欲アルゴリズム
アルゴリズムが貪欲になる原因は何ですか?
貪欲なアルゴリズムは、一度に 1 ステップずつ、過去の選択を再検討することなく、今最も最適と思われるオプションを常に選択してソリューションを構築します。後戻りもせず、先を見据えることもありません。
次の 2 つのプロパティが成立する場合に機能します。
- 貪欲な選択特性 - 局所的に最適な選択は、全体的に最適なソリューションにつながります。
- 最適な部分構造 - 各選択の後に残る問題は、同じ問題のより小さな例です。
アクティビティの選択 - 古典的な例
開始時刻と終了時刻を持つ一連のアクティビティを指定して、重複しないアクティビティの最大数を選択します。
貪欲な戦略: 終了時刻で並べ替え、常に最も早く終了するアクティビティを選択します。
def max_activities(intervals):
intervals.sort(key=lambda x: x[1])
count, end = 0, 0
for s, e in intervals:
if s >= end:
count += 1
end = e
return count
なぜこれが機能するのでしょうか?最も早く終了するアクティビティを選択すると、将来のアクティビティのための余地が最大限に残ります。これ以上の選択肢はありません。
ハフマンコーディング - コンセプト
2 つの最低周波数のシンボルを繰り返しマージすることで、最適なプレフィックスフリーのバイナリ コードを構築します。これは欲張りです。各ステップで最も安価なペアをマージします。その結果、頻繁に使用されるシンボルが短いコードを取得するツリーが作成されます。
🤯
ハフマン符号化は、JPEG、MP3、および ZIP 圧縮で使用されます。デビッド ハフマンは 1952 年に学生としてそれを発明しました - それは宿題でした!
ジャンプゲーム
nums[i] がインデックス i からの最大ジャンプ長である配列を指定して、最後のインデックスに到達できるかどうかを判断します。
貪欲なアプローチ: これまでに到達可能な最も遠いインデックスを追跡します。左から右にスキャンします。遅れた場合は false を返します。
def can_jump(nums):
farthest = 0
for i, jump in enumerate(nums):
if i > farthest:
return False
farthest = max(farthest, i + jump)
return True
🧠クイックチェック
ジャンプ ゲームでは、貪欲な変数「最も遠い」は何を表しますか?
ガソリンスタンド
ガソリンスタンドのある環状ルートを走行します。ステーション i では、燃料 gas[i] を獲得し、次のステーションに到達するために cost[i] を費やします。周回を完了できる開始駅を見つけるか、-1 を返します。
レッスン 9 / 100%完了
ディスカッション
ログイン ディスカッションに参加