貪欲アルゴリズムの可視化
貪欲法は各段階で今よい候補を選び、後で選び直しません。区間の最早終了やハフマンの最低頻度の合併を、コードと同期させ、正しさの根拠とともに見ます。
短い規則が正しいとは限りません。最早開始、最大価値、次の最安値などは書きやすくても、証明が必要です。交換論法では、最適解の選択を一つずつ貪欲な選択へ置き換え、質を下げないと示します。
各レッスンの内容
| レッスン | 貪欲な規則 | 安全性の根拠 | 観察するもの |
|---|---|---|---|
| 区間スケジューリング | 両立する区間の最早終了を選ぶ | 最適解の最初と交換しても、後に使える空きを減らさない | 別の最適予定を貪欲な予定へ変える過程 |
| ジャンプゲーム | 各索引で最遠到達境界を延ばす | 最大 nums[i] まで跳べるため到達集合が連続し、切れ目を越せない | オレンジの弧と緑の境界、全経路がゼロへ集まる失敗 |
| ハフマン符号 | 最低頻度の二部分木を合併する | 低頻度の葉を深くする費用が小さく、最適接頭符号を構成できる | 優先キューで木を作り、固定長とのビット数を比べる |
| 分数ナップサック | 密度順に入れ、最後を切る | 分割が密度を保つとき最適だが、不可分なら失敗する | 密度の矩形と 205／220／240 の比較 |
推奨する学習順序
- 区間スケジューリング：一資源、一規則で、交換しても区間数が減らない様子を見ます。
long-blockerは最早開始という誤った規則の反例です。 - ジャンプゲーム：最遠位置一つを状態にします。到達集合が連続した前半部分という不変条件を学び、同じ数を一度交換しただけで結論が逆になる例から、配置の重要性を見ます。
- ハフマン符号：作った二分木の形が答えです。既定の文は 23 ビット、固定長は 33 ビットで、均一頻度の例では同点になります。その場合、接頭符号木は一記号二ビットを改善できません。
- 分数ナップサック：分割可能という前提を検証します。同じ密度規則でも、0/1 の選択へ変えると最適解に負ける例を再生します。
四つの後は、グラフの Dijkstra と最小全域木へ進めます。同じく貪欲な証明を使いますが、グラフのデータ構造と不変条件が中心です。