知识卡片

普通读书笔记卡 · 3646.g · 生成模型:未记录

网络流建模先区分容量与成本

理解等级:中级

网络流模型用顶点和有向边表达输送关系;容量限制每条边的流量,成本刻画单位流量代价。最大流最大化源到汇的流量;最小费用流在指定流量或供需约束下最小化总成本;二部匹配可规约为单位容量最大流。

运输、转运及任务分配可建立不同网络约束,目标和可行条件不能仅凭问题名称互换。通用线性规划与专用算法的性能应按实例与实现评估。

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也计算出来了这个网络的最小割,也就是说形成瓶颈的边集。