System of Difference Constraints
看板Prob_Solve (計算數學 Problem Solving)作者FRAXIS (喔喔)時間16年前 (2009/02/15 09:48)推噓0(0推 0噓 0→)留言0則, 0人參與討論串1/1
線性規劃的一種，針對所有的變數x1 ~ xn，存在有m條限制式，限制
式的形式都是 xi - xj < bk，其中b1 ~ bm都是整數，要求x1 ~ xn的
解的通式。
在Cormen演算法書上24.4節說此問題可以轉化成shortest path問題
，就是轉換成一個constraint graph，就可以求解。
但是習題24.4-11問說，如果b1 ~ bm是實數而不是整數時，而且要
求x1 ~ xn是整數，該如何求解？
習題24.4-12則是問b1 ~ bm是實數，且x1 ~ xn中只有一部分要求是
整數，該如何求解？
我想了很久還是想不太出來怎麼解決，有人知道該如何下手嘛？
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.119.162.51
Prob_Solve 近期熱門文章
PTT數位生活區 即時熱門文章
