PTT數位生活區 / Prob_Solve (計算數學 Problem Solving)

Re: [問題] Reduce LP成Min-cost flow

看板Prob_Solve (計算數學 Problem Solving)作者FRAXIS (喔喔)時間10年前 (2015/01/14 01:26)推噓1(1推 0噓 1→)

留言2則, 2人參與討論串5/5 (看更多)

※ 引述《DJWS (...)》之銘言： : 推 FRAXIS: http://www.slideserve.com/xaviera-bowers/6486226 01/13 01:55 : → FRAXIS: 第八頁的地方似乎就是這題..只是我看不懂他的解法.. 01/13 01:55 : 我也看不太懂，我猜是這樣： : 令a[i]=h[i]-h[i+1] : h[i]加1 <=> a[i-1]減1 且 a[i]加1。 : h[i]減1 <=> a[i-1]加1 且 a[i]減1。 : 　　h[i]加1，可以視作「一單位的水從a[i-1]流到a[i]」。 : 　　h[i]減1，可以視作「一單位的水從a[i]流到a[i-1]」。 : 因此設定a[i-1]到a[i]是無向邊（只能選其中一個方向流動）。 : 　　h[i]加1或者減1，minimize的對象就加1。 : 因此該無向邊費用設定成1。 : 　　當無向邊的流量越少，則minimize的對象就越小。 : 　　因此設定為最小費用流。 : 若a[i]<-d，则至少要从别的地方拿个1，且不能多于|a[i]|-d个1； : 因此从点i向t连边，容量下界|a[i]|-d，上界|a[i]|+d，费用0。 : 　　題目規定相鄰兩數差a[i]的範圍是 -d ~ +d （d是正數） : a[i]<-d　就必須把a[i]補到變成-d，至少需要補-d - a[i] = |a[i]| - d。 : 　　把邊拉往target，是為了強迫source一定要補東西進來， : 　　要從哪個入口補入都可以（每一個h[i]都可以調整） : 設定出口的容量上下限，就能控制入口補多少東西進來。 : 大概就是這種感覺 : 然後我覺得他的source和target顛倒過來應該也OK... 我好像大概了解了，不知道有沒有錯.. 輸入為A，然後前處理計算P[i] = A[i] - A[i+1]，我們要求解B[]。令 X[i] 為變數表示 A[i] 的增加量。 Y[i] 為變數表示 A[i] 的減少量。所以 B[i] = A[i] + X[i] - Y[i]，目標是要極小化X[i] + Y[i]的總和。我們希望-D <= B[i] - B[i+1] <= D 也就是 -D <= A[i] + X[i] - Y[i] - A[i+1] - X[i+1] + Y[i+1] <= D 也就是 -D - P[i] <= X[i] - Y[i] - X[i+1] + Y[i+1] <= D - P[i] 拆成兩個限制式，然後轉成標準式 X[i] - Y[i] - X[i+1] + Y[i+1] + S[i] = D - P[i] (1) X[i] - Y[i] - X[i+1] + Y[i+1] - T[i] = -D - P[i] (2) 從(1)和(2)可知S[i] + T[i] = 2D，所以其實只要保留其中一個限制式，然後設定S或是T的上限為2D即可。最後把這n-1個等式加總，然後兩邊都乘以負一，得到一個新的多餘的限制式。但是結果會是一個min-cost flow的形式，就可以用min-cost flow解了。在(1)和(2)，我們可以多作一些處理。當D < P[i]時，(1)的右邊 < 0，所以可以設定S[i]的下界為P[i] - D。當-D > P[i]時，(2)的右邊 > 0，所以可以設定T[i]的下界為-P[i] - D。在這兩種case，右手邊都可以化簡為0。 -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 129.170.195.149 ※ 文章網址: https://www.ptt.cc/bbs/Prob_Solve/M.1421169993.A.910.html ※ 編輯: FRAXIS (129.170.194.148), 01/14/2015 23:59:13