推 FRAXIS: 只要有一個 optimal solution 的子集合為 optimal 就夠了 11/06 21:36
如題
在證明greedy的時候
往往要證明greedy-choice property和optimal substructure
但是小弟今天在證明scheduling to minimize maximum lateness時
發現optimal substructure會證明不出來
optimal substructure的定義是
每個最優解greedy-choice後剩餘的必定是最優子集合
然而這題如果有3個工作分別是a b c
a的工作時間是 2 b的工作時間是 10 c的工作時間是 3
而deadline a 是 1 b是6 c 是5
則a->c->b c->a->b 皆是最優結構
maximum lateness 為9
但是 a->c 和 c->a的 maximum lateness
卻是1 和 4
c->a 並非是最優子結構
想請問是我對最優子結構的定義產生誤解嗎?
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 140.112.30.32
※ 文章網址: https://www.ptt.cc/bbs/Prob_Solve/M.1478437818.A.C32.html