輪講：アルゴリズムデザイン（第1回）
研究室の輪講で、「アルゴリズムデザイン」を読みます。
- 作者: Jon Kleinberg,Eva Tardos,浅野孝夫,浅野泰仁,小野孝男,平田富夫
- 出版社/メーカー: 共立出版
- 発売日: 2008/07/10
- メディア: 単行本
- 購入: 10人 クリック: 421回
- この商品を含むブログ (51件) を見る
第1回目は第4章グリーディアルゴリズムからスタートで、p103〜130を読みました。（第1〜3章は各自で読みましょう。）
以下、今回登場した問題の設定とアルゴリズムをメモしています。
アルゴリズム4.1 区間スケジューリング問題
n個の要求（それぞれ開始時刻s(i)と終了時刻f(i)がある）に対して、どれだけ多くの要求に答えられるようにスケジューリングができるのかを求める問題です。最適化するのは時間ではなく、答えられる要求数です。
1.開始時間が早い物から要求に応える
2.要求に応える時間が最短のものから選ぶ
3.他とかぶる区間が最も少ない物から選んでいく
上記の3つの手法が最初に提案されていますが、どの手法も最適解を求めることはできません。
最適解が求められるアルゴリズムは、終了時刻f(i)が最も早い要求から答えていく手法です。（最適解になる証明、計算時間は次回？）
アルゴリズム4.2 区間分割アルゴリズム
4.1と同じく、n個の要求（開始時間s(i)と終了時刻f(i)）に対するスケジューリングの問題です。ただし、今回は同時に複数個の要求に応えることができ、各要求に対してどこで要求に応えていいるのか、{1...d}のラベル付けをすることでスケジューリングをします。同時に答える要求の最大個数dをいかに少なくして、スケジューリングをするのかを解きます。
アルゴリズムは、開始時間s(i)が最も早いものからスケジューリングを決めていきます。その要求iよりも前に開始している要求がまだどれも持っていないラベルを、要求iのラベルとします。（複数個ラベルの候補がある場合には、任意に1つ選びます。）
アルゴリズム4.3 最大遅延最小化スケジューリングアルゴリズム
4.1、4.2とは違い、各要求に開始時刻と終了時刻はありません。その代わり、各要求に期限が与えられており、全ての要求のスケジューリングを考えます。同時に答えられる要求は1つのみです。求める解は、要求の遅延の長さの最大が最も小さい解です。例えば、要求aとbに対してスケジューリングした結果、要求aが3分遅延、bが2分遅延であれば、このスケジューリングの遅延はaの3分となります。この遅延が最も短い解を求めます。
アルゴリズムは、期限が最も早い要求から順に答えていく方法です。この手法で、最適解が求められます。（証明は次回？）
アルゴリズム4.4 最適キャッシングアルゴリズム
データにアクセスする順番があらかじめ分かっている時に、キャッシュにどの様にデータを保存すれば効率が良いのかを求める問題です。「効率が良い」とは、キャッシュにあるデータを追い出す回数が少ないことです。
アルゴリズムは、キャッシュから追い出すデータを決める時に、次に参照される時が最も遅いデータを追い出します。
