アルゴリズムの選書：最適化の答えを説明する
計算手順を選ぶ前に、何を最適化し、何を許すかを決めます。無料の証明中心の本、広い疑似コードの参照書、実装とモデル化の本を役割で選び、三冊を同時に通読する代わりに不足する説明を補います。
学習順路・例題の編集責任：University Reading List編集プロジェクト。 編集と選定の方法 · 出典確認日:
対象と編集責任
初歩のプログラミング、再帰、データ構造と離散数学を学んだ後の設計・解析の順路です。Ericksonもこれらを前提とします。以下のデータと解答は本サイトの創作であり、教科書問題の転載や実務での検証結果ではありません。
出発点を選ぶ
三冊を比較する
Algorithms
Jeff Erickson · 版: 1 · 2019
無料の証明・設計の主教材
- 選ぶ場面
- 帰納法を使い、反例と漸化式を自分で組み立てたいとき。
- 別の教材が適する場面
- スタック、ハッシュ表や構文そのものを初めて学ぶ段階。
- 読む範囲
- 2019年版の1–4章、その後に5–8章のグラフを選択。
- 限界と注意点
- 著者は前提となるデータ構造の省略を明示し、依頼による演習解答の提供もしません。無料本文と解答集は別です。
選ぶ前に試す
3–4章を使い、下の五仕事で終了時刻順が報酬最大化に失敗する理由を説明します。
確認すること: 実行可能な貪欲解と、それより報酬が大きい実行可能解を示します。仕事数の多さを目的と混同しません。
アルゴリズムイントロダクション
Thomas H. Cormen et al. · 版: 4 · 2022
広い第四版の参照書
- 選ぶ場面
- 指定教材、または多くの手法を一貫した疑似コードで参照したいとき。
- 別の教材が適する場面
- 短い導入が必要で、章を選択する準備がないとき。
- 読む範囲
- 第四版のDynamic ProgrammingとGreedy Algorithmsを探し、解析・データ構造を必要に応じて復習。
- 限界と注意点
- 2022年の選定ハードカバーISBNは9780262046305。教員専用資料や別の電子商品への権利を約束しません。
選ぶ前に試す
最適化の部分問題を文章で定義し、続きの判断に不要な情報を明らかにしてから漸化式にします。
確認すること: 状態の定義から選択肢と基底が決まります。式の形を知っているだけでは最適部分構造の説明になりません。
アルゴリズム設計マニュアル
Steven S. Skiena · 版: 3 · 2020
問題のモデル化を助ける本
- 選ぶ場面
- 応用の話を組合せ問題へ変換し、実装の選択肢を比べたいとき。
- 別の教材が適する場面
- カタログや共同編集解答だけで証明を代用したいとき。
- 読む範囲
- 第三版の実践設計、特に動的計画法の10章。モデルを定義してからカタログへ。
- 限界と注意点
- 著者サイトの解答Wikiは共同編集で、正しさを保証していません。議論を点検する材料として使います。
選ぶ前に試す
同じ予約問題を物語と、報酬・互換性を持つ区間モデルの二通りで記述します。
確認すること: 話にある条件がモデルに入るか、除外が明示されています。有名な問題名でも条件を消してはいけません。
準備を確認する
実行可能性と最適性の違いは？
前者は全制約を満たすこと、後者は実行可能な全候補との目的値の比較です。良さそうな一例だけではどちらの一般的証明にもなりません。
帰納法は何を支える？
小さい部分問題の最適解と現在の最適解を結びます。場合分けが最適解の全可能性を含む必要があります。
実行時間の説明に必要なのは？
nと入力表現、数える操作を定義します。整列、前駆計算、表、復元を別々に数えます。
成果物を作る六つの段階
準備できた成果物: 0 / 6
自己記録用のチェックであり、評価ではありません。チェック情報は当サイトに送信されません。
-
モデルを書く
読む範囲: Erickson0章とSkienaのモデル化。
作るもの: 固定開始・終了、半開区間、報酬、一資源と総報酬の目的を記述。
確認すること: 端点で接する仕事は基本モデルでは互換です。移動・準備時間は含めません。
-
近道を反証する
読む範囲: Erickson4章とCLRSの貪欲法。
作るもの: 終了時刻順を実行し、より良い実行可能候補と比較。
確認すること: 選んだIDを示します。一つの反例は当該普遍命題を否定し、全貪欲法の失敗は意味しません。
-
状態を定義する
読む範囲: Erickson3章とCLRSの動的計画法。
作るもの: 終了順に並べ、V(j)とp(j)を文章で定義。
確認すること: V(j)は先頭j仕事、p(j)は互換な最後の前仕事、なければ0。
-
表と根拠を作る
読む範囲: 同じ動的計画法の範囲。
作るもの: 各行の二候補と前駆を記録し、仕事列を復元。
確認すること: jを除くか含むかが全場合を覆い、含む場合は互換な接頭部分を解きます。
-
制約を変える
読む範囲: Skiena10章と追加問題。
作るもの: 準備間隔を加え、表を流用する前に互換性を再計算。
確認すること: pの変更が旧解を無効にできます。漸化式の外形が同じでも入力関係は変わります。
-
監査できる結果にする
読む範囲: 弱かった段階の教材へ戻る。
作るもの: モデル、反例、表、復元、計算量、境界テストを提出。
確認すること: 他人が報酬と制約を再現できます。小さい一回の計時は漸近解析ではありません。
解答付きの例題
創作例題：早く終わる順は報酬を最大化しない
五仕事の(開始,終了,報酬)はa=(0,3,5), b=(3,5,4), c=(0,5,12), d=(5,7,3), e=(4,8,11)。一資源で重ならない仕事を選び、最大報酬と終了時刻順の結果を比較します。
前提
区間は半開で、終了直後に次を開始できます。時刻は固定、分割不可、報酬は非負で加算。準備間隔や不確実性はありません。同じ終了時刻はb,cの順に並べます。これは表の順であり、最適値を変えません。
- 終了順の貪欲法はa,b,dを選び、5+4+3=12。実行可能なa,eは16なので、この手法は重み付き目的を一般には解けません。
- a,b,c,d,e順の前駆はp=[0,1,0,3,1]。V(0)=0、V(j)=max(V(j−1),reward(j)+V(p(j)))。最後の仕事を含む・含まないで場合が分かれます。
- V=[0,5,9,12,15,16]。最終行からeと前駆aを復元し、11+5=16。
- 整列と二分探索による前駆はO(n log n)、表と復元はO(n)、記憶O(n)。五仕事の確認と一般的正当化を区別します。
解答と解釈
最大報酬はa,eの16。三仕事の貪欲解は12です。個数と報酬は違う目的です。
結果を検証する
独立に32部分集合を列挙して重なる候補を除き、同じ最適値を得ます。表の数値だけでなく復元した端点を確認します。
前提を変えて考える
追加問題：必要な間隔を入れる
仕事と報酬を保ち、選択した仕事の間に少なくとも2時間単位の間隔を要求します。最後の後には不要で、時刻は移動できません。
- finish(i)+2≤start(j)なのでp=[0,0,0,1,0]。aはdの前に置けますが、bやeの前には置けません。
- 新しいVは[0,5,5,12,12,12]。cだけで12。旧a,eは3+2>4で不可能です。
解答と解釈
最適値はc単独の12。漸化式は保ち、互換性データを作り直します。旧報酬から一定額を引くのは別のモデルです。
結果を検証する
変更後の互換条件で再列挙します。一仕事には最後の間隔は不要です。旧最適値は緩和モデルの上界であり、ここでの実行可能解ではありません。
よくある誤り
疑似コードを証明とする
この五仕事で正解するだけでは全入力での正しさになりません。一般的議論と有限テストを分けます。
問題名だけでモデルを決める
準備時間などの制約が既知の帰着を壊すことがあります。除外条件を先に記述します。
計算量の一部だけ数える
整列や二重ループの前駆探索を無視して全体を線形と呼ばないでください。実装と上界を対応させます。
次に進む前に
- 目的と互換性の全条件を説明できる。
- 漸化式を説明し、実行可能な仕事列を復元できる。
- 前提を一つ変え、変更すべきデータや議論を示せる。
出典と版の確認
出典確認日:
- Jeff Erickson: 2019 edition, prerequisites and chapter files
2019年版、無料本文、前提と章順は著者資料で確認。試行課題とデータは本サイト独自です。
- MIT Press: Introduction to Algorithms, fourth edition
出版社が第四版と2022年、紙・電子の別識別子を確認。教員資料の利用権を約束しません。
- Springer: The Algorithm Design Manual, third edition
出版社の設計・参照という範囲に基づく選定です。学習効果を測定した比較ではありません。
- Author-hosted third-edition chapter and solution index
動的計画法の位置と共同編集解答の限界を著者サイトで確認しました。
提案する学習活動であり、公式の課題や全巻通読の主張ではありません。