6.0.5 问题归约
Robert Sedgewick Kevin Wayne
本书中，我们一直注重说明某个特定的问题，然后给出解决问题的算法和数据结构。在许多情况下（以下列出了很多），我们发现如果能够将某个问题转化为已经解决的问题的某个形式，那么解决它将会更容易。在研究已经学习过的各种算法与形形色色的各种问题之间的关系之前，我们应该正式定义这个解决问题的过程。
定义。如果能够用解决问题 B 的算法得到一个解决问题 A 的算法，则说问题 A 能够被归约为问题 B。
这个概念在软件开发中显然并不陌生：当你使用一个库方法解决某个问题时，正是在将所需要解决的问题归约为该库方法所解决的问题。本书中，我们一直非正式地将能够归约为给定问题的其他问题称为应用。
6.0.5.1 排序问题
我们在第 2 章第一次遇到了问题的归约，当时我们想说明的是高效的排序算法可以用于解决许多看起来与排序无关的其他问题。例如，在许多有趣的问题中，我们研究了以下几个问题。
寻找中位数。给定一组数字的集合，找出中位数。
不重复的值。在给定的集合中找出所有不同的值。
最小平均完成时间的调度问题。给定一组任务的集合和它们的时耗，在一个处理器上应该如何安排调度使得它们的平均完成时间最小呢？
命题 H。以下问题可以被归约为排序问题：
寻找中位数；
统计不同的值；
最小平均完成时间的调度问题。
证明。请见 2.5.3.4 节和练习 2.5.12。
我们还需要注意归约的成本。例如，我们可以在线性时间内找到一组数的中位数，但是如果归约为排序问题，那就需要线性对数级别的时间。即使是这样，额外的成本或许还是可以接受的，因为我们可以使用已有的排序实现。排序的价值在于以下 3 个方面：
公开
同步至部落
取消
完成
0/2000
荧光笔
直线
曲线笔记
复制
AI
- 深入了解
- 翻译
- 解释
- 总结
本文深入探讨了问题归约的概念及其在算法和数据结构中的实际应用。作者以排序问题、最短路径问题和最大流量问题为例，说明了许多看似无关的问题都可以归约为这些经典问题，并给出了相应的命题和例证。文章强调了问题解决模型的重要性，指出良好的问题解决模型能够扩展问题处理的范围，但也提醒读者不要过度依赖某一问题解决模型，以免忽视更好的解决方法或新的问题解决模型。此外，文章还介绍了线性规划作为一个重要的问题解决模型，并探讨了其在解决各种问题中的广泛应用。通过具体案例生动地阐述了问题归约的概念及其在算法和数据结构中的实际应用，为读者提供了深入理解和应用问题归约的指导。文章内容丰富，涵盖了算法和数据结构领域的重要概念和实际应用，对于希望深入了解和应用问题归约的读者具有重要的参考价值。
仅可试看部分内容，如需阅读全部内容，请付费购买文章所属专栏
《算法（第 4 版）》
《算法（第 4 版）》
立即购买
登录 后留言
精选留言
由作者筛选后的优质留言将会公开显示，欢迎踊跃留言。
收起评论