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

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

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

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

※ 引述《bleed1979 (口德是一種美德)》之銘言： : 標題: Re: [問題] Reduce LP成Min-cost flow : 時間: Tue Jan 13 00:39:39 2015 : ※ 引述《FRAXIS (喔喔)》之銘言： : : 在網路上看到一個問題： : : 給定一個整數陣列 A ，一個正整數D，要求設計一個演算法把 : : A 修改成 B （長度不變），使得 B 中相鄰的元素的差值都小於D， : : 且最小化 |A[i] - B[i]| 的總和。 : : http://www.careercup.com/question?id=5207197178920960 : : 我自己想的解法是使用Linear programming，但是我又感覺這 : : 問題似乎是可以用Min-cost flow來解的，只是我找不出來怎麼作。 : : 不知道有沒有人有其他解法？ : : 考慮一般性的情況，給定一個LP的 formulation ，有沒有什麼 : : 技巧，在某些條件滿足的狀況下，可以把LP轉成Min-cost flow？ : : 因為我覺得設計LP比想出network flow的模型容易許多。 : : 推 dreamoon: 真是巧妙的題目... 01/13 13:43 : → dreamoon: 有上下界的最小花費網路流 01/13 13:44 : 推 dreamoon: 是說我可不覺得任何LP都可以換成min-cost flow @@ 01/13 13:47 我知道LP不可能都可以換成min-cost flow，因為min-cost flow是LP的特例。但是在某些情況下，先設計好LP，然後就可以系統化的轉換成min-cost，這會比直接設計min-cost來的容易一些。比如說這一題： https://www.byvoid.com/blog/noi-2008-employee 實際上的想法是這樣，先設計一個LP，其限制式為 Ax = b (1) 而一個min-cost flow的限制式必須滿足 Yx = b, Y的值為-1, 0, 1，每一列必須有剛好一個1和-1，b為整數且總和為0。只要Y滿足這條件，就可以使用min-cost flow演算法。（x的限制式必須是非負，或是在一個正整數區間）所以要解(1)，就對A矩陣作列運算，想辦法轉成滿足min-cost flow條件的Y矩陣即可。（也可以對行作scaling，只是這題用不到）然後回到我原本問的題目，我可以設計LP如下： B[i]是變數，代表修改後的值，Y[i]代表修改A[i]的cost，我們可得到下列關係 B[i] - B[i+1] <= D B[i+1] - B[i] <= D B[i] - A[i] <= Y[i] A[i] - B[i] <= Y[i] 最後兩個不等式是來描述Y[i] = |A[i] - B[i]|。因為是對Y[i]的總和作極小化，所以在最佳解時Y[i] = |A[i] - B[i]| 但是我怎麼想也沒辦法把這LP跟我google到的min-cost flow解答作連結。而且我也不太知道那個min-cost flow的解答到底是不是正確的，所以才上來發問。 -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 129.170.195.149 ※ 文章網址: https://www.ptt.cc/bbs/Prob_Solve/M.1421156928.A.CFE.html