輪講スライド: Greedy Algorithm (Part 1)

Introduction To Algorithms.
§16. Greedy Algorithm.
2010 / 06
2010年6月22日火曜日
What is Greedy Algorithm?
 DPでは全体の構造を分析していた
Optimal Substructure & Overlapping Subproblem
 Greedy Algorithm : 貪欲アルゴリズム
 部分的に最適解を積み上げる
2010年6月22日火曜日
What is Greedy Algorithm?
 部分的に最適解を作れば、全体も最適だ！
一般的に成り立つとは言えない
 それでもだいたい上手くいく(と主張)
2010年6月22日火曜日
Step of Greedy Algorithm.
 Optimal Substructureを決定
 再帰解を作成・選択時に一つの小問題が残るように
 安全に選択出来ると示す
 再帰アルゴリズムを作り、Iterativeに変換
2010年6月22日火曜日
とりあえず例題
2010年6月22日火曜日
§16.1 Activity-selection Problem
 アクティビティを排他的にスケジューリング
 Activity Set S = { a1 , a2 , ... , an }
 Activityは開始時刻sと終了時刻fを持つ
 0 <= s < f < ∞
2010年6月22日火曜日
§16.1 Activity-selection Problem
 Activityはfで単調になっていると仮定
i
1
2
3
4
5
6
7
8
9
10
11
si
1
3
0
5
3
5
6
8
8
2
12
fi
4
5
6
7
9
9
10
11
12
14
16
 相互的に実行可能な例 : { a3 , a9 , a11}
 最大な例 : { a1 , a4 , a8 , a11 }
2010年6月22日火曜日
§16.1 Activity-selection Problem
 Sの部分集合で最大のものを求めたい。
 動的計画法(DP)でも解けそう。
 とりあえずOptimal Substructureを考えよう
2010年6月22日火曜日
Optimal Substructure of §16.1
 Sij : aiより後に始まり ajより先に終わる
 相互に共存する最大な集合Aijを求める。
 Sijの中のActivity akで分割すると?
 二つの小問題が考えられる : Sik と Skj
 Aij = Aik ∪ { ak } ∪ Akj
2010年6月22日火曜日
Like Dynamic Programming
 Aij = Aik ∪ { ak } ∪ Akj
 動的計画法でやったように再帰計算式を考える。
 最適解の大きさ c[i][j] とする
2010年6月22日火曜日
Like Dynamic Programming
 再帰計算式が設定出来た
 Recursive でも Memoize でもして実装出来る
 実はもっと特徴がある
 Greedy Choice
2010年6月22日火曜日
Greedy Choice #01
 小問題を解くことなしにActivityを選択出来たらどうか
 実際例題ではGreedy Choiceだけを考えればいい
 選択：他のActivityに出来るだけ資源を残す
 この考え方から選べないか?(小問題解かないで)
2010年6月22日火曜日
Greedy Choice #02
 資源を残す? → 出来るだけ時間を残す
 時間を残す? → Activityをはやく終わらせる
 方針：最も早く終わるものを選ぶ(そのとき最適)
 方針：残りは可能なものを選ぶ
2010年6月22日火曜日
Greedy Choice #03
 与えられた表は終了時間順にソートしていた
 表の左から順に選んでいく
i
1
2
3
4
5
6
7
8
9
10
11
si
1
3
0
5
3
5
6
8
8
2
12
fi
4
5
6
7
9
9
10
11
12
14
16
2010年6月22日火曜日
Greedy Choice #04
 Sk = { ai ∈ S | si >= fk }
 例えばS1はa1より遅くはじまるActivity
 最初にa1を選ぶ
 S1が解くべき唯一の小問題になる
2010年6月22日火曜日
Imprement
 実装はDPでなくていい。普通に再帰でいい。
 P419 : RecursiveActivitySelector( s , f , k , n )
 k : 初期値0 , n : 全Activity数
 方針：最初に終わるのを探して再帰
 初期値：a0という仮想的なActivity(f0=0)
2010年6月22日火曜日
Code
void RAS( int s[], int f[], int k, int n){
int m = k + 1;
while( m <= n && s[m] < f[k])
m++;
if( m <= n ){
printf("%d ", m);
RAS( s , f, m , n );
}
}
2010年6月22日火曜日
Iterative
int N = 11;
void GAS( int s[], int f[]){
printf("%d ", 1);
int k = 1, m;
for( m = 2 ; m <= N ; m++ ){
if( s[m] >= f[k] ){
printf("%d ", m);
k = m;
}
}
}
2010年6月22日火曜日
一般的なこと
2010年6月22日火曜日
§16.2 Elements of Greedy Strategy
 Optimal SubstructureはDPと同じ(例より)
 Make choice that seems best at moment.(原則)
2010年6月22日火曜日
Steps.
 Optimal Substructure
 再帰的解法
 Greedy Choiceをした時に小問題が1つになるか?
 Greedy Choiceが常に安全に出来るか
 再帰的なアルゴリズムを作る
 再帰的なアルゴリズムをIterativeに
2010年6月22日火曜日
Design Greedy Algorithms
 最適化問題を選択と解くべき一つの小問題に割り当て
 Greedy Choice が作れる最適化問題に
解が存在することを示す。
 Optimal Substructure 実際に見つける
 大抵、DPでも解ける。
 いつも使えるわけではない
2010年6月22日火曜日
Key point 1.
 Greedy-choice property
 DPでは、選択が小問題の解に依存する → Bottom up
 Greedy Algorithm では、その時々で最適な選択
 小問題を解く前に、選択する。→ Top down
2010年6月22日火曜日
Key point 2.
 Optimal Substructure
 DPと同じ
2010年6月22日火曜日
Greedy vs DP
 どちらもOptimal Substructureを上手く使ってる
 どんな違いがあるのか…
 古典的な問題を使って詳しく調べよう!
2010年6月22日火曜日
詳しく調べるために
2010年6月22日火曜日
0-1 Knapsack Problem
 泥棒はお店で n 個のアイテムを見つけた
 i 番目のアイテムは vi ドル、重さが wi ポンド
 ナップサックには W ポンド入る
 出来るだけ上手くアイテムを持ちたい
 0-1 : take it or leave it
2010年6月22日火曜日
Fractional Knapsack Problem
 設定は同じ
 ただしアイテムは有理数個が持てる
 0-1 と Fractionalの微妙な違い
 ただしFractionalはGreedyで解ける
 けれども0-1は上手く解けない
2010年6月22日火曜日
How to Solve
 ポンド毎の価値を求める( vi / wi )
2010年6月22日火曜日
その他の話題
 §16.3 Huffman Codes
 §16.4 Matroids and greed methods
 §16.5 A task-scheduling problem as a matroid
2010年6月22日火曜日
Problem
 16-1 Coin changing
 16-2 Scheduling to minimize average completion time
 16-3 Acyclic Subgraphs
 16-4 Scheduling variations
 16-5 Off-line caching
 16-1 Coin changing
2010年6月22日火曜日
終わり
 Huffman Code は別にいいかな…
 Matroid関係はそのうち読みたい
 これからGraphやります
 具体的には§22-26
2010年6月22日火曜日
オマケ
 Greedy Algorithm : 1971 ∼
 組合せ最適化問題とか
 英語Wikipediaの参考欄はこの本が載ってる
2010年6月22日火曜日