网站建设中常见问题分析,wordpress pc,新手怎么做网站推广,怎么在互联网做网站【图与网络数学模型】3.Ford-Fulkerson算法求解网络最大流问题 一、网络流模型1. 概述2. 可行流3. 增广链 二、示例1. 最大流问题2. Alternate Formulation#xff1a;最小截量问题 三、Ford-Fulkerson 算法1. 导入库2. 初始化残差图3. 定义查找增广路径4. 定义循环5. 程序运行… 【图与网络数学模型】3.Ford-Fulkerson算法求解网络最大流问题 一、网络流模型1. 概述2. 可行流3. 增广链 二、示例1. 最大流问题2. Alternate Formulation最小截量问题 三、Ford-Fulkerson 算法1. 导入库2. 初始化残差图3. 定义查找增广路径4. 定义循环5. 程序运行 四、其它发现参考文献 一、网络流模型
1. 概述
许多系统中包含了流量问题例如公路系统中有车辆流控制系统中有信息流供水系统中有水流金融系统中有现金流等。
在生物安全领域和医疗系统中也包括就诊、挂号、检查、治疗、转院等过程涉及的患者流医疗设备、药品、医用材料等的采购、配送、使用等过程涉及的医疗资源流以及医疗质量控制流和医保支付流等等。
对于这样一些包含了流量问题的系统我们往往要求出其系统的最大流量。给一个带收发点的网络每条弧的赋权称为容量在不超过每条弧的容量的前提下确定每条弧的流量求出从发点到收点的最大流量这类问题通常称为最大流问题。
2. 可行流
网络流一般在有向图上讨论定义网络上支路的容量为其最大通过能力记为 c i j c_{ij} cij支路上的实际流量记为 f i j f_{ij} fij图中规定一个发点s一个收点t节点没有容量限制流在节点不会存储容量限制条件0 ≤ f i j f_{ij} fij ≤ c i j c_{ij} cij平衡条件 ∑ v j ∈ A ( v i ) f i j − ∑ v j ∈ B ( v i ) f j i { v ( f ) i s 0 i ≠ s , t − v ( f ) i t \sum_{v_j \in A\left(v_i\right)} f_{i j}-\sum_{v_j \in B\left(v_i\right)} f_{j i}\left\{\begin{array}{cc} v(f) is \\ 0 i \neq s, t \\ -v(f) it \end{array}\right. vj∈A(vi)∑fij−vj∈B(vi)∑fji⎩ ⎨ ⎧v(f)0−v(f)isis,tit
满足上述条件的网络流称为可行流总存在最大可行流。
当支路上 f i j c i j f_{ij}c_{ij} fijcij 称为饱和弧v( f )为可行流的流量。
最大流问题也是一个线性规划问题。
3. 增广链
设 f 是一个可行流 μ \mu μ 是 v s v_s vs 从 v t v_t vt 到的一条链若 μ \mu μ 满足下列条件则 μ \mu μ 是可行流的一条增广链
弧 ( v i , v j ) ∈ μ \left(v_i, v_j\right) \in \mu^{} (vi,vj)∈μ上 0 ≤ f i j c i j 0\leq{f}_{i_j}c_{i j} 0≤fijcij即 μ \mu^{} μ 中每一条弧是非饱和弧弧 ( v i , v j ) ∈ μ − \left(v_i, v_j\right) \in \mu^{-} (vi,vj)∈μ−上 0 f i j ≤ c i j 0f_{i j} \leq c_{i j} 0fij≤cij即 μ − \mu^{-} μ−中每一条弧是非零流孤。
二、示例
1. 最大流问题
给定一个图该图表示每个边都有一个容量的流网络。此外给定图中的两个顶点源 ‘s’ 和接收器 ‘t’使用以下约束找到从 s 到 t 的最大可能流量 该问题的最大流量为23 2. Alternate Formulation最小截量问题
把网络分割为两个成分的弧的最小集合其中一个成分包含 s s s 点另一个包含 t t t 点一般包含 s s s 点的成分中的节点集合用 V V V 表示,包含 t t t 点的成分中的节点集合用 V ˉ \bar{V} Vˉ 表示截量集容量是指截量集中前向弧的容量之和 C ( V , V ˉ ) ∑ i ∈ V j ∈ V ˉ c i j C(V, \bar{V})\sum_{\substack{i \in V \\ j \in \bar{V}}} c_{i j} C(V,Vˉ)i∈Vj∈Vˉ∑cij
福特-富克森定理网络的最大流等于最小截量集容量。
从原始图中“减去”最大流路径得到下图 标记从 s 到达的所有节点——调用可到达节点集 A 将这些节点和其他节点分开 从图中删除红色的边使得删除这些边后没有从 s 到 t 的路径 相应的最大流量路径为 − s → a → b → t : 11 − s → c → a → b → t : 1 − s → c → d → b → t : 7 − s → c → d → t : 4 \begin{aligned} -s \rightarrow a \rightarrow b \rightarrow t: 11 \\ -s \rightarrow c \rightarrow a \rightarrow b \rightarrow t: 1 \\ -s \rightarrow c \rightarrow d \rightarrow b \rightarrow t: 7 \\ -s \rightarrow c \rightarrow d \rightarrow t: 4 \end{aligned} −s→a→b→t:11−s→c→a→b→t:1−s→c→d→b→t:7−s→c→d→t:4
三、Ford-Fulkerson 算法
在1962年L.R.Ford和D.R.Fulkerson发明了一种解决最大流量问题的有效方法。它是一种沿着由起点到终点的路径逐步增加流量的通用方法因此它也是同类算法的基础。在经典文献中它被称为Ford-Fulkerson算法但它也被称为增广路径算法。
Ford-Fulkerson最大流量算法 网络中的初始流量为零沿着任意从起点到终点且不含有饱和的正向边或是空逆向边的增广路径增大流量直到网络中不存在这样的路径为止。
1. 导入库
from collections import defaultdict2. 初始化残差图
初始化残差图residual graph以及行数 ROW。 def __init__(self, graph):self.graph graph # 残差图self. ROW len(graph)# self.COL len(gr[0])3. 定义查找增广路径
使用广度优先搜索来找到从源点 s 到汇点 t 的一条增广路径同时更新父节点数组 parent。 def BFS(self, s, t, parent):visited [False]*(self.ROW)queue []queue.append(s)visited[s] Truewhile queue:u queue.pop(0)for ind, val in enumerate(self.graph[u]):if visited[ind] False and val 0:queue.append(ind)visited[ind] Trueparent[ind] uif ind t:return Truereturn False4. 定义循环
在 FordFulkerson 方法中使用 while 循环来不断寻找增广路径并更新残差图直到没有增广路径为止。 def FordFulkerson(self, source, sink):parent [-1]*(self.ROW)max_flow 0 while self.BFS(source, sink, parent) :path_flow float(Inf)s sinkwhile(s ! source):path_flow min (path_flow, self.graph[parent[s]][s])s parent[s]max_flow path_flowv sinkwhile(v ! source):u parent[v]self.graph[u][v] - path_flowself.graph[v][u] path_flowv parent[v]return max_flow5. 程序运行
from collections import defaultdictclass Graph:def __init__(self, graph):self.graph graphself. ROW len(graph)def BFS(self, s, t, parent):visited [False]*(self.ROW)queue []queue.append(s)visited[s] Truewhile queue:u queue.pop(0)for ind, val in enumerate(self.graph[u]):if visited[ind] False and val 0:queue.append(ind)visited[ind] Trueparent[ind] uif ind t:return Truereturn Falsedef FordFulkerson(self, source, sink):parent [-1]*(self.ROW)max_flow 0 while self.BFS(source, sink, parent) :path_flow float(Inf)s sinkwhile(s ! source):path_flow min (path_flow, self.graph[parent[s]][s])s parent[s]max_flow path_flowv sinkwhile(v ! source):u parent[v]self.graph[u][v] - path_flowself.graph[v][u] path_flowv parent[v]return max_flowgraph [[0, 16, 13, 0, 0, 0],[0, 0, 10, 12, 0, 0],[0, 4, 0, 0, 14, 0],[0, 0, 9, 0, 0, 20],[0, 0, 0, 7, 0, 4],[0, 0, 0, 0, 0, 0]]g Graph(graph)source 0; sink 5print (The maximum possible flow is %d % g.FordFulkerson(source, sink))运行结果为 The maximum possible flow is 23 四、其它发现
Edmonds和Karp发明的另一种Ford-Fulkerson算法的实现是优先处理能够将流量增大最多的增广路径。对于这种以及其他一些方法可以通过稍加修改Dijkstra的最短路径算法、由优先队列得到剩余容量最大的正向边或是流量最大的逆向边来实现。或者也可以寻找最长增广路径或是随机选择增广路径。
各种最大流量算法的分析仍然是一个有趣而活跃的研究领域。从理论角度来说我们已经得到了各种最大流量算法在最坏情况下的上界但这些上界大多远远高于实际应用中所观察到的真实成本而且也比较小的下界线性级别高出许多。
“最大流量算法的实际应用仍然既是一门艺术也是一门科学。它的艺术之处在于为特定的应用场景选择最有效的策略它的科学之处在于对问题本质的理解。”
参考文献
Derigs U, Meier W. Implementing Goldberg’s max-flow-algorithm—A computational investigation[J]. Zeitschrift für Operations Research, 1989, 33(6): 383-403.Ahuja R K, Kodialam M, Mishra A K, et al. Computational investigations of maximum flow algorithms[J]. European Journal of Operational Research, 1997, 97(3): 509-542.Cherkassky B V, Goldberg A V. On implementing push-relabel method for the maximum flow problem[C]//International Conference on Integer Programming and Combinatorial Optimization. Springer, Berlin, Heidelberg, 1995: 157-171.Thomas H. Cormen,Charles E. Leiserson,Ronald L. Rivest,Clifford Stein算法导论. 美国麻省理工学院出版社2009
