知识卡片

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

二部匹配归约为单位容量流

理解等级:中级

把二部图左右两侧分别接到源点和汇点;源到左点、可行配对边、右点到汇的容量均为1。整数最大流中的单位流配对边组成匹配,源汇边容量保证每个顶点至多参与一次。

反向残量边允许重新安排已有配对;最大匹配的数量最优,但可能存在多个不同匹配。

234的左右集合应是不相交集合,并非没有跨集合连接;可行配对正是跨两侧的边。输出匹配大小最大,不保证唯一。

235的03388例子通过反向残量重新配对;03389–03390仅从pairs创建顶点映射,若集合有孤立元素,map.get可能为空;左右集合对象相等或编号与汇点构造不一致也需处理。实现应校验两侧成员、唯一标识和配对合法性。

236以n、m、k表示两侧大小和配对边数,构图 O(n+m+k),扫描配对边输出结果 O(k);最大流计算本身的成本不能省略。

243把任务分配建模为每一侧单位容量;若要求所有任务完成,须同时指定总匹配量或满足每个需求,而不能只最小化非负费用。

这张卡片看不懂?

已有反馈 · 0 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 5 处

    • · 查看原书依据

      二部图匹配 匹配问题有多种形式。我们考虑如下这种情况,五个求职者会面试五个职位。每个求职者都已经列出了满足能力要求的职位。现在的任务就是将尽可能多地分配工作给求职者,但是每份工作只能提供给一位求职者。我们会非常惊讶地发现可以使用Ford-Fulkerson算法来解二部图匹配问题。在计算机科学中,这种

    • · 查看原书依据

      配对集合中得到的一个配对集合(si,tj),P。这个集合的规模是最大能够匹配上的配对数目。算法保证不存在更多的匹配数(虽然会有其他的匹配方式能够得到同样多的匹配个数)。

    • · 查看原书依据

      流为1的边(si,tj),输出选中了匹配(si,tj)∈P。为了简化表述,例8-5的代码中删除了错误检测[1]。 例8-5:使用Ford-Fulkerson的二部图匹配 [1]要了解更多的细节,请参见代码库中的algs.model.network.matching.Bipartite-Matchin

    • · 查看原书依据

      O(k)的时间来将解映射成二部图问题的解。

    • · 查看原书依据

      任务分配问题 任务分配问题是转运问题的一个变种,有着更多的限制条件:每个供应节点只能供应一个单位,需求节点也只需要一个单位。

    参考来源

    - 位置:《算法技术手册》第8章《二部图匹配》(spine1634;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1597.html;u233-ch08-006)。 - 结论依据:233全文及235的03388图与代码对照实读。 - 原始内容:二部图匹配 匹配问题有多种形式。我们考虑如下这种情况,五个求职者会面试五个职位。每个求职者都已经列出了满足能力要求的职位。现在的任务就是将尽可能多地分配工作给求职者,但是每份工作只能提供给一位求职者。我们会非常惊讶地发现可以使用Ford-Fulkerson算法来解二部图匹配问题。在计算机科学中,这种 - 位置:《算法技术手册》第8章《输入/输出》(spine1634;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1597.html;u234-ch08-006)。 - 结论依据:234的左右集合应是不相交集合,并非没有跨集合连接;可行配对正是跨两侧的边。输出匹配大小最大,不保证唯一。 - 原始内容:配对集合中得到的一个配对集合(si,tj),P。这个集合的规模是最大能够匹配上的配对数目。算法保证不存在更多的匹配数(虽然会有其他的匹配方式能够得到同样多的匹配个数)。 - 位置:《算法技术手册》第8章《解决方案》(spine1635;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1598.html;u235-ch08-006)。 - 结论依据:235的03388例子通过反向残量重新配对;03389–03390仅从pairs创建顶点映射,若集合有孤立元素,map.get可能为空;左右集合对象相等或编号与汇点构造不一致也需处理。实现应校验两侧成员、唯一标识和配对合法性。 - 原始内容:流为1的边(si,tj),输出选中了匹配(si,tj)∈P。为了简化表述,例8-5的代码中删除了错误检测[1]。 例8-5:使用Ford-Fulkerson的二部图匹配 [1]要了解更多的细节,请参见代码库中的algs.model.network.matching.Bipartite-Matchin - 位置:《算法技术手册》第8章《分析》(spine1636;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1599.html;u236-ch08-006)。 - 结论依据:236以n、m、k表示两侧大小和配对边数,构图 O(n+m+k),扫描配对边输出结果 O(k);最大流计算本身的成本不能省略。 - 原始内容:O(k)的时间来将解映射成二部图问题的解。 - 位置:《算法技术手册》第8章《任务分配问题》(spine1641;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1604.html;u243-ch08-006)。 - 结论依据:243把任务分配建模为每一侧单位容量;若要求所有任务完成,须同时指定总匹配量或满足每个需求,而不能只最小化非负费用。 - 原始内容:任务分配问题 任务分配问题是转运问题的一个变种,有着更多的限制条件:每个供应节点只能供应一个单位,需求节点也只需要一个单位。