|
|
发表于 2004-1-3 16:25:39| 字数 2,043| - 中国–上海–上海 教育网/上海财经大学教育网
|
显示全部楼层
求二部图最大匹配（指派问题）的匈牙利算法：
谈匈牙利算法自然避不开Hall定理，即是：对于二部图G，存在一个匹配M，使得X的所有顶点关于M饱和的充要条件是：对于X的任意一个子集A，和A邻接的点集为T(A)，恒有： |T(A)| >= |A|
匈牙利算法是基于Hall定理中充分性证明的思想，其基本步骤为：
1．任给初始匹配M；
2．若X已饱和则结束，否则进行第3步；
3．在X中找到一个非饱和顶点x0，作V1 ← {x0}, V2 ← Φ；
4．若T(V1) = V2则因为无法匹配而停止，否则任选一点y ∈T(V1)\V2；
5．若y已饱和则转6，否则做一条从x0 →y的可增广道路P，M←M⊕E(P)，转2；
6．由于y已饱和，所以M中有一条边(y,z)，作 V1 ← V1 ∪{z}, V2 ← V2 ∪ {y}， 转4；
关于求网络最大流和最小割的标号算法：
给定一个有向图G=(V,E)，把图中的边看作管道，每条边上有一个权值，表示该管道的流量上限。给定源点s和汇点t，现在假设在s处有一个水源，t处有一个蓄水池，问从s到t的最大水流量是多少。这就叫做网络流问题。用数学语言描述就是：
设G=(V,E)是一个流网络，设c(u, v)>＝0 表示从u到v的管道的流量上限。设s为源，t为汇。G的流是一个函数f: V×V →R，且满足下面三个特征：
1. 容量限制：对于所有的 u,v ∈ V, 要求f(u, v) <= c(u, v)
2. 斜对称性：对于所有的 u,v ∈ V, 要求f(u, v) = - f(v, u)
3. 流的会话：对于所有的 u ∈ V - {s, t}，要求∑ f(u, v) = 0；v∈V
f(u,v)称为从结点u到v的网络流，它可以为正也可以为负。流 f 的值定义为：
|f| = ∑ f(s, v)
v∈V
即从源出发的所有流的总和。
最大流问题就是找出给定流网络的最大流。网络流问题可以归结为一类特殊的线性规划问题。
寻找最大流的基本方法是Ford-Fulkerson方法，该方法有多种实现，其基本思想是从某个可行流F出发，找到关于这个流的一个可改进路经P，然后沿着P调整F，对新的可行流试图寻找关于他的可改进路经，如此反复直至求得最大流。现在要找最小费用的最大流，可以证明，若F是流量为V(F)的流中费用最小者，而P是关于F的所有可改进路中费用最小的可改进路，则沿着P去调整F,得到的可行流F'一定是流量为V(F')的所有可行流中的最小费用流。这样，当F是最大流时候，他就是所要求的最小费用最大流。
注意到每条边的单位流量费用B(i,j)≥0，所以F=0必是流量为0的最小费用流，这样总可以
从F=0出发求出最小费用最大流。一般的，设已知F是流量V(F)的最小费用流，余下的问题就是如何去寻找关于F的最小费用可改进路。为此我们将原网络中的每条弧<u,v>变成两条方向相反的弧：
1。前向弧<u,v>，容量C和费用B不变，流量F为0；
2。后向弧<v,u>，容量C为0，费用为-B，流量F为0；
每一个顶点上设置一个参数CT，表示源点至该顶点的通路上的费用和。如果我们得出一条关于F的最小费用可改进路时，则该路上的每一个顶点的CT值相对于其它可改进路来说是最小的。每一次寻找最小费用可改进路时前，源点的CT为0，其它顶点的CT为+∞。
设cost为流的运输费用，初始时由于F=0,则cost=0,我们每求出一条关于F的最小费用可改进路，则通过cost ← cost + ∑B(e)*d, （其中e∈P,d为P的可改进量）来累积流的运输费用
的增加量。显然，当求出最小费用最大流时，cost便成为最大流的运输费用了。
另外设置布尔变量break为最小费用可改进路的延伸标志，在搜索了网络中的每一个顶点后
，若break=true表示可改进路还可以延伸，还需要重新搜索网络中的顶点；否则说明最小费
用的可改进路已经找到或者最大流已经求出。
下面是算法的伪代码：
cost ← 0;
repeat
可改进路撤空；
设源点的CT值为0并进入可改进路；
repeat
break ← false;
for u ←1 to N do
begin
分析U出发的所有弧<U,V>;
if (<U,V>的流量可改进）and(源点至U有通路)and(U的CT值+<U,V>的费用 < V的CT值) then
begin
break ← true;
V的CT值 ← U的CT值+<U,V>的费用；
V进入可改进路经并为之标号；
end if
end for
until break=false
if 汇点已标号 then
begin
从汇点出发倒向修正可改进路的流量；
cost ← cost + ∑B(e)*d（其中e∈P,d为P的可改进量）；
end if
until 汇点未标号；
可见，上述的算法和求最大流的Edmonds-Karp标号算法几乎一样，因为这两种算法都使用宽度优先搜索来来寻找增广路径，所以复杂度也相同，都是O(VE)，其中V是节点数目，E是边数目。
Scource: Microsoft(China), Community |
|
[复制链接]
|自动提醒
狗仔卡
离线
提升卡
置顶卡
变色卡