知识卡片

普通读书笔记卡 · 1292.g.1.e.1.b · 生成模型:未记录

问题归约要验证输入和解映射

理解等级:中级

把原问题的实例转为已知问题,求解后再把结果映射回原问题;需要证明可行性及目标值之间的对应,并计入转换成本。比如二部匹配可归约成单位容量最大流,而第k个元素也可通过排序后取值,但不一定是最省时间的方法。

最大流算法族不能直接求解任意线性规划;最小费用流和一般线性规划还需各自的目标与约束处理。

这张卡片看不懂?

已有反馈 · 0 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    • · 查看原书依据

      问题归约为另一个有解的问题 问题归约(Problem reduction)是计算机科学和数学中用于解决问题的一个基本方法。一个简单的例子,假如你需要一个算法来找到列表中的第四大的元素。不需要编写什么特殊的代码,你只需要用任何一种排序算法排个序,就能够在一个有序的列表中取到第四大的元素了。使用这个方法

    参考来源

    - 位置:《算法技术手册》第11章《原则:如果没有显而易见的解法,将问题归约为另一个有解的问题》(spine1691;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1653.html;u304-ch11-003)。 - 结论依据:304全文及03471网络流汇总表实读。 - 原始内容:问题归约为另一个有解的问题 问题归约(Problem reduction)是计算机科学和数学中用于解决问题的一个基本方法。一个简单的例子,假如你需要一个算法来找到列表中的第四大的元素。不需要编写什么特殊的代码,你只需要用任何一种排序算法排个序,就能够在一个有序的列表中取到第四大的元素了。使用这个方法