※ 引述《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://webptt.com/cn.aspx?n=bbs/Prob_Solve/M.1421156928.A.CFE.html