[問題] 最優子結構
看板Prob_Solve (計算數學 Problem Solving)作者hortune (enutroh)時間8年前 (2016/11/06 21:10)推噓1(1推 0噓 0→)留言1則, 1人參與討論串1/1
如題
在證明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
推
11/06 21:36, , 1F
11/06 21:36, 1F
Prob_Solve 近期熱門文章
PTT數位生活區 即時熱門文章
