知识卡片
网络流建模先区分容量与成本
网络流模型用顶点和有向边表达输送关系;容量限制每条边的流量,成本刻画单位流量代价。最大流最大化源到汇的流量;最小费用流在指定流量或供需约束下最小化总成本;二部匹配可规约为单位容量最大流。
运输、转运及任务分配可建立不同网络约束,目标和可行条件不能仅凭问题名称互换。通用线性规划与专用算法的性能应按实例与实现评估。
227限定整数容量并讨论邻接表与矩阵;边是否平行、源汇是否不同和初始流是否可行需由接口定义。达到最大流后,可通过残量可达集合构造最小割。
这张卡片看不懂?
这张卡片已通过人工审查,不再接受失败反馈。
已有反馈 · 0 条
还没有人提交反馈。
在整书笔记中的位置
- · 网络流建模先区分容量与成本
- · 输入/输出
原书出处 · 2 处
- · 查看原书依据
最大流 给定一个网络,网络中的每条边都有一个最大容量,计算出这个网络能够支持的最大流。 首先我们会阐述网络流问题之间的关系,这样能够帮助我们理解这些问题是如何解决的。图8-1描绘的是这些问题的关系。一条有向边将问题的一般化实例和问题的特例联系起来。例如运输问题就是转运问题的一个特例,因为运输图并不包
- · 查看原书依据
整数容量c(u,v)以及一个实际的流f(u,v)。 输出 Ford-Fulkerson会处理每条边(u,v)。计算出给定的容量限制下,从s到t的最大流。这个时候,Ford-Fulkerson也计算出来了这个网络的最小割,也就是说形成瓶颈的边集。
参考来源
- 位置:《算法技术手册》第8章《概述》(spine1627;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1590.html;u224-ch08-001)。
- 结论依据:224全文及03376问题关系图实读。
- 原始内容:最大流 给定一个网络,网络中的每条边都有一个最大容量,计算出这个网络能够支持的最大流。 首先我们会阐述网络流问题之间的关系,这样能够帮助我们理解这些问题是如何解决的。图8-1描绘的是这些问题的关系。一条有向边将问题的一般化实例和问题的特例联系起来。例如运输问题就是转运问题的一个特例,因为运输图并不包
- 位置:《算法技术手册》第8章《输入/输出》(spine1628;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1591.html;u227-ch08-001)。
- 结论依据:227限定整数容量并讨论邻接表与矩阵;边是否平行、源汇是否不同和初始流是否可行需由接口定义。达到最大流后,可通过残量可达集合构造最小割。
- 原始内容:整数容量c(u,v)以及一个实际的流f(u,v)。 输出 Ford-Fulkerson会处理每条边(u,v)。计算出给定的容量限制下,从s到t的最大流。这个时候,Ford-Fulkerson也计算出来了这个网络的最小割,也就是说形成瓶颈的边集。