2011年4月27日 星期三
2011年4月12日 星期二
greedy straegy abstract
為了解一個問題，把 [ Introduction to Algorithms ] 抓來亂翻了一下，
再配合交大 [ 譚老師的講義 ]，把 greedy algorithm 部份研讀了一下，
大概領悟力不夠，還是不能融會貫通，只好把重點節錄起來，慢慢消化：
以下 Greedy Algorithm 以 Greedy 簡稱之
Dynamic Algorithm 以 Dynamic 簡稱之
Optimal Solution 以 Opt. 簡稱之
Greedy 簡單說就是：經由一連串的選擇，找出全局最佳解，每次
選擇時，是找出當時的最佳解，這種 heuristic 的方法，就稱為 Greedy.
Greedy 異於 Dynamic 的解法，不像 Dynamic 找出所有 subproblems 的解，再慢慢
用 table 記下，累積到全局：而是先把問題分成一個 greedy choice + subproblem ，
這個 greedy choice 是一個局部最佳解，並且用 recursive 方式繼續 下去解 subproblem。
最後的結果，使得 Greedy 不一定得到 Opt.，但是很快，而且結果可以接近 Opt.
很多時候，由於這種早期決定的性質，Greedy 無法找到 Opt.
當然，如果能證明，這個 greedy choice 是全局 Opt. 的一環，那麼就可以確保，一系列
的 greedy choice 可以找到全局 Opt.
下面是從 [Wiki] 節錄的，Greedy 的兩個重要成份：
Greedy choice property
We can make whatever choice seems best at the moment and then solve
the subproblems that arise later. The choice made by a greedy algorithm
may depend on choices made so far but not on future choices or all the
solutions to the subproblem. It iteratively makes one greedy choice
after another, reducing each given problem into a smaller one.
In other words, a greedy algorithm never reconsiders its choices.
This is the main difference from dynamic programming, which is exhaustive
and is guaranteed to find the solution.
After every stage, dynamic programming makes decisions based on all
the decisions made in the previous stage, and may reconsider the
previous stage's algorithmic path to solution.
Optimal substructure
"A problem exhibits optimal substructure if an optimal solution
to the problem contains optimal solutions to the sub-problems."
以下列出一些例子來討論：
例一 0-1 knapsack problem : 假設有 n 種礦石，以 1,2...n 代表這 n 種礦石，
第 i 種重量是 w[i] ，價值是 v[i]，限定載重上限為 W 的情形下，
怎樣拿會最有價值？
例二 fractional knapsack problem : 假設有 n 種礦石粉末，以 1,2...n 代表這 n 種礦石，
第 i 種重量是 w[i] ，價值是 v[i]，限定載重上限為 W 的情形下，
怎樣拿會最有價值？
這兩種問題，都有 Optimal substructure 的特性 ----- 假設最有價值的裝法 載重是 W，
則裝入礦石 j 後，對於剩下的 n-1 種礦石 ( 就是 j 已拿光後 ) 最有價值的載重
剩下 W-W[j]
fractional knapsack problem 可以用 Greedy 找到 Opt. ：
因為當每次選擇 價值/重量 比最高的礦石粉 j 時，可以確定把 j 拿完，
是最好地選擇。若 j 拿完還有多餘的載重量，就選擇 價值/重量 比
次高的礦石粉，此時 所作的 greedy selection 就是符合 global Opt. 的選擇。
0-1 knapsack problem 無法用 Greedy 找到 Opt. ：
反例 ：考慮三種礦石，都只有一個：
v[1]=60 , w[1]=10
v[2]=100, w[2]=20
v[3]=120, w[3]=30
upper weight W= 50
1 的 價值/重量 比最高，選取 1 剩下可載重 40，但是選 1 不會得到 Opt.
Opt. 是選 2+3, total value =220
但是 0-1 knapsack problem 可以用 Dynamic 找到 Opt.
另外，有漂亮的數學證明， 符合 matroid 結構的問題，可以用 greedy 得到 Opt.
（ matroid 是比較深的主題，有空再來研究吧！）
#
再配合交大 [ 譚老師的講義 ]，把 greedy algorithm 部份研讀了一下，
大概領悟力不夠，還是不能融會貫通，只好把重點節錄起來，慢慢消化：
以下 Greedy Algorithm 以 Greedy 簡稱之
Dynamic Algorithm 以 Dynamic 簡稱之
Optimal Solution 以 Opt. 簡稱之
Greedy 簡單說就是：經由一連串的選擇，找出全局最佳解，每次
選擇時，是找出當時的最佳解，這種 heuristic 的方法，就稱為 Greedy.
Greedy 異於 Dynamic 的解法，不像 Dynamic 找出所有 subproblems 的解，再慢慢
用 table 記下，累積到全局：而是先把問題分成一個 greedy choice + subproblem ，
這個 greedy choice 是一個局部最佳解，並且用 recursive 方式繼續 下去解 subproblem。
最後的結果，使得 Greedy 不一定得到 Opt.，但是很快，而且結果可以接近 Opt.
很多時候，由於這種早期決定的性質，Greedy 無法找到 Opt.
當然，如果能證明，這個 greedy choice 是全局 Opt. 的一環，那麼就可以確保，一系列
的 greedy choice 可以找到全局 Opt.
下面是從 [Wiki] 節錄的，Greedy 的兩個重要成份：
Greedy choice property
We can make whatever choice seems best at the moment and then solve
the subproblems that arise later. The choice made by a greedy algorithm
may depend on choices made so far but not on future choices or all the
solutions to the subproblem. It iteratively makes one greedy choice
after another, reducing each given problem into a smaller one.
In other words, a greedy algorithm never reconsiders its choices.
This is the main difference from dynamic programming, which is exhaustive
and is guaranteed to find the solution.
After every stage, dynamic programming makes decisions based on all
the decisions made in the previous stage, and may reconsider the
previous stage's algorithmic path to solution.
Optimal substructure
"A problem exhibits optimal substructure if an optimal solution
to the problem contains optimal solutions to the sub-problems."
以下列出一些例子來討論：
例一 0-1 knapsack problem : 假設有 n 種礦石，以 1,2...n 代表這 n 種礦石，
第 i 種重量是 w[i] ，價值是 v[i]，限定載重上限為 W 的情形下，
怎樣拿會最有價值？
例二 fractional knapsack problem : 假設有 n 種礦石粉末，以 1,2...n 代表這 n 種礦石，
第 i 種重量是 w[i] ，價值是 v[i]，限定載重上限為 W 的情形下，
怎樣拿會最有價值？
這兩種問題，都有 Optimal substructure 的特性 ----- 假設最有價值的裝法 載重是 W，
則裝入礦石 j 後，對於剩下的 n-1 種礦石 ( 就是 j 已拿光後 ) 最有價值的載重
剩下 W-W[j]
fractional knapsack problem 可以用 Greedy 找到 Opt. ：
因為當每次選擇 價值/重量 比最高的礦石粉 j 時，可以確定把 j 拿完，
是最好地選擇。若 j 拿完還有多餘的載重量，就選擇 價值/重量 比
次高的礦石粉，此時 所作的 greedy selection 就是符合 global Opt. 的選擇。
0-1 knapsack problem 無法用 Greedy 找到 Opt. ：
反例 ：考慮三種礦石，都只有一個：
v[1]=60 , w[1]=10
v[2]=100, w[2]=20
v[3]=120, w[3]=30
upper weight W= 50
1 的 價值/重量 比最高，選取 1 剩下可載重 40，但是選 1 不會得到 Opt.
Opt. 是選 2+3, total value =220
但是 0-1 knapsack problem 可以用 Dynamic 找到 Opt.
另外，有漂亮的數學證明， 符合 matroid 結構的問題，可以用 greedy 得到 Opt.
（ matroid 是比較深的主題，有空再來研究吧！）
#
訂閱：
文章 (Atom)