作者DJWS (...)
看板Prob_Solve
标题Re: [问题] 最大流最小费用问题
时间Fri Apr 3 08:51:45 2015
1F：→ saladim: 虽然还没全懂 似乎是这样: No negative cycle => Cost'会 04/02 15:25
2F：→ saladim: >=0 ==> 所以可用Dijk所以reduced cost在此变成非负!! 04/02 15:26
3F：→ saladim: 又没有negative cycle跟integer cost就有optimal sol. 故 04/02 15:27
4F：→ saladim: 得解...虽然就是各位先进所说的 用我的理解走一遍 ORZ 04/02 15:28
5F：→ saladim: 其他有提到的再继续看.....@-@|| 04/02 15:28
6F：→ saladim: (min cost flow跟 min cost max flow有什麽关联还没懂..) 04/02 15:30
文献有两类，分为 linear programming (大宗) 、图论算法 combinatorics (极少)
所以要花点时间去转换那些术语
7F：推 FRAXIS: 其实 min cost flow 有很多变化形.. 所以很难搞清楚.. 04/02 22:38
其实没有所谓很多变化形
主要是因为没有人把它厘清清楚 (至少我看过的资料皆是如此)
－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－
flow问题有两类
maximum flow (最佳化问题)
feasible flow (判定问题)
max flow是大家最熟悉的。
CLRS讲的就是 max flow，流量越大越好。
feasible flow是判断是否存在一个流。
通常这类问题会额外设定每条边的流量下限，不然没有讨论意义(trivial)。
顺带一提，CLRS里面只讲流量上限(就是capacity network)。
－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－
流有两种：
st flow (有起点终点)
flow (一直循环的)
st flow 很经典，在 CLRS 上面介绍的就是 st flow。
st代表source/target，从起点流动到终点，有头有尾。
通常这类问题只要设定流量上限，就有讨论意义了。
如果想让事情更复杂，可以设定下限，甚至推广成负数。
flow 在线性规划、或者进阶的演算法课程，才会谈。
没有起点终点，水会不断的循环流动。
通常这类问题会设定流量上限下限、supply/demand，不然没有讨论意义。
－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－
前面2x2种排列组合，一共得到四种问题。
但是只有这两个问题比较有讨论意义，其他都不重要。
max st flow (文献常省略st，因为古人没搞清楚。)
feasible flow
引入了cost之後，就是先前文章提到的：
min cost max st flow (文献常省略st，因为古人没搞清楚。)
min cost feasible flow (文献常省略feasible，依命名惯例。)
min cost max st flow在tarjan的书上有介绍一点点。
需要证明的是：cost network的最短路径，以最少的方式增加，最终得到最佳解。
min cost flow在orlin的书上介绍的很详细。
网路上的资料几乎都是抄他的。
然後min cost flow有一些莫名其妙的特例，
例如circulation problem/transportation problem之类的。
这些都不是重点，这些只是流量下限为0、supply/demand为0之类的，
图论方式的演算法还是一样没变。
线性规划的演算法可能有差一点点，我没有仔细去研究。
－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－
再来谈 reduction
学过 NP-complete 之後，我们知道问题可以互相变来变去，用一个问题解另一个问题
考虑前面提到的 2x2=4 个问题
maximum flow (没办法定义何谓max) (我们不讨论它)
---------------------------------------------------------------
feasible st flow
-> feasible flow (拉一条边从t到s)
-> maximum st flow (1. 流量下限挪至supply/demand)
(2. 建立s和t，s连到supply，demand连到t)
上面的问题，可以用下面的解。
引入了cost之後也一样是这个顺序。
所以最重要的其实是 min cost max st flow 的演算法。
只是 orlin 完全没提。又因为网路上的资料都是抄 orlin 的，所以......
－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－
再来才是真的变化形
0/1 flow
minimax flow
b-flow
multi-commodity flow
这都很恶心，一般学生根本就不会想碰。我自己也没有研究。
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 111.250.61.177
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Prob_Solve/M.1428022308.A.4B7.html
※ 编辑: DJWS (111.250.61.177), 04/03/2015 09:09:34
※ 编辑: DJWS (111.250.61.177), 04/03/2015 09:17:03
※ 编辑: DJWS (111.250.61.177), 04/03/2015 09:19:39
※ 编辑: DJWS (111.250.61.177), 04/03/2015 09:20:08
※ 编辑: DJWS (111.250.68.64), 04/03/2015 13:17:21
8F：推 saladim: 感谢 持续研究中 @-@ 04/06 22:07
9F：→ DJWS: 加油! 04/07 06:28