◈6.0.5 问题归约

6.0.5 问题归约

本书中,我们一直注重说明某个特定的问题,然后给出解决问题的算法和数据结构。在许多情况下(以下列出了很多),我们发现如果能够将某个问题转化为已经解决的问题的某个形式,那么解决它将会更容易。在研究已经学习过的各种算法与形形色色的各种问题之间的关系之前,我们应该正式定义这个解决问题的过程。

定义。如果能够用解决问题 B 的算法得到一个解决问题 A 的算法,则说问题 A 能够被 归约 为问题 B。

这个概念在软件开发中显然并不陌生:当你使用一个库方法解决某个问题时,正是在将所需要解决的问题归约为该库方法所解决的问题。本书中,我们一直非正式地将能够归约为给定问题的其他问题称为 应用。

6.0.5.1 排序问题

我们在第 2 章第一次遇到了问题的归约,当时我们想说明的是高效的排序算法可以用于解决许多看起来与排序无关的其他问题。例如,在许多有趣的问题中,我们研究了以下几个问题。

  • 寻找中位数。给定一组数字的集合,找出中位数。
  • 不重复的值。在给定的集合中找出所有不同的值。
  • 最小平均完成时间的调度问题。给定一组任务的集合和它们的时耗,在一个处理器上应该如何安排调度使得它们的平均完成时间最小呢?

命题 H。以下问题可以被归约为排序问题:

  • 寻找中位数;
  • 统计不同的值;
  • ‰最小平均完成时间的调度问题。

证明。请见 2.5.3.4 节和练习 2.5.12。

我们还需要注意归约的成本。例如,我们可以在线性时间内找到一组数的中位数,但是如果归约为排序问题,那就需要线性对数级别的时间。即使是这样,额外的成本或许还是可以接受的,因为我们可以使用已有的排序实现。排序的价值在于以下 3 个方面:

  • 它有其自身的实用性;
  • 我们的算法能够有效解决排序问题;
  • 许多问题都能够归约为排序问题。

一般来说,我们将具有这些性质的问题称为 问题解决模型。和成熟的库一样,设计良好的问题解决模型能够大大扩展我们能够处理的问题域。但是,在过度关注于问题解决模型时容易犯下的一个错误被称为 Maslow 的锤子,这是由 A.Maslow 在 20 世纪 60 年代提出并广为人知的一句话: 如果你有一把锤子,那么什么东西都看起来都像颗钉子。如果沉迷于若干问题解决模型,我们就可能将它们当作 Maslow 的锤子一样来解决遇到的所有问题,从而妨碍了发现解决问题的更好方法,甚至是新的问题解决模型。尽管本书所讨论的模型都非常重要、实用且应用广泛,但是考虑各种其他可能性仍然是明智的选择。

6.0.5.2 最短路径问题

在 4.4 节学习最短路径算法时也遇到了问题归约的概念。在许多有趣的问题中,我们研究了以下几个。

  • 无向图中的单点最短路径问题。给定一幅加权 无向图 和起点 s,其中所有权重非负,回答“ 是否存在从 s 到给定目的顶点 v 的路径?如果有,找出这样一条 最短 路径(总权重最小)。”等类似问题。
  • 优先级限制下的并行任务调度问题。给定一组需要完成的任务,以及一组关于任务完成的先后次序的优先级限制。在满足限制条件的前提下应该如何在若干相同的处理器上(数量不限)安排任务并在最短的时间内完成所有任务?
  • 套汇。在给定的汇率表中找出一个套汇的机会。

和刚才一样,后两个问题看起来和最短路径问题并没有直接的关系,但最短路径算法能够有效地解决它们。这些示例问题虽然都很重要,但并没有什么代表性。许多非常重要的问题(太多了,无法一一讨论)都能够归约为最短路径问题——这是一个非常有效而重要的问题解决模型。

命题 I。以下问题能够归约为加权图中的最短路径问题:

  • 非负权重的无向图中的单点最短路径问题;
  • 优先级限制下的并行调度问题;
  • 套汇问题;
  • 其他许多问题。

例证。请见 4.4.4.2 节命题 R、4.4.5.2 节框注“优先级限制下的并行任务调度问题的关键路径方法”和 4.4.6.9 节框注“货币兑换中的套汇”。

6.0.5.3 最大流量问题

最大流量问题在许多情况下同样非常重要。我们可以去掉流量网络中的各种限制并解决相关的流量问题,也可以用它解决其他网络或者图的处理问题,甚至是非网络问题。例如以下问题。

  • 就业安置。大学里的就业指导中心会为学生安排公司面试。这些面试的结果是一系列工作机会。假设一次成功的面试表示了学生和公司之间的相互认可且学生将会接受这份职位,那么这样的就业安置数量当然是越多越好。有可能为每一位学生安排一份工作吗?最多可能安排多少份工作?
  • 产品配送。假设有一家只生产一种产品的公司,它拥有能够生产产品的工厂,能够暂时储存产品的物流分配中心以及销售商品的零售直营店。公司需要定期将产品通过物流分配中心分发到各地的直营店,而各地的分配通道的配送能力各有不同。有可能使各地仓库的供应量与直营店的销售量相匹配吗?
  • 网络可靠性。一种简化的模型可以将一个计算机网络看成是通过交换机连接所有电脑的一组主干网,任意两台电脑都能够通过交换机和主干线相互连接。切断某一对计算机之间的连接最少需要切断多少条主干线?

同样,这些问题各不相关,也看起来不属于流量网络的问题范畴,但它们都可以被归约为最大流量问题。

命题 J。以下问题可以归约为最大流量问题:

  • 就业安置;
  • 产品配送;
  • 网络可靠性;
  • 其他许多问题。

例证。这里只证明第一个问题(又叫做 最大二分图匹配问题),其他的将留作练习。我们可以为给定的就业安置问题构造一个对应的最大流量问题。图中的所有边均由学生指向公司,然后添加一个起点且对于每个学生都有一条从起点指向他的边,添加一个终点且对于每个公司都有一条由公司指向终点的边。图中的每条边的容量都是 1,请见图 6.0.25。现在,这个网络中的最大流量问题的每个解都是对应的二分图匹配问题的的解(请见命题 F 的推论)。匹配中的所有边的两个顶点都正好分别属于学生和公司两个集合且它们在最大流量配置中都会是饱和的。首先,网络流总是会给出一个合法的匹配:因为每个顶点都既有一条流入边(来自于起点)和一条流出边(指向终点)且经过的流量最多为 1,所以每个顶点最多只能出现在一个匹配中。其次,匹配不可能含有更多的边,因为任意类似的匹配都意味着一个比最大流量算法的结果更好的流量配置。

图 6.0.25 将二分图匹配问题归约为网络流问题示例

例如,如图 6.0.26 所示,一个增广路径最大流量算法可能会使用路径 s → 1 → 7 → t、 s → 2 → 8 → t、 s → 3 → 9 → t、 s → 5 → 10 → t、 s → 6 → 11 → t 和 s → 4 → 7 → 1 → 8 → 2 → 12 → t 计算得到匹配 1-8、 2-12、 3-9、 4-7、 5-10 和 6-11。因此,在示例中可以找到一种将所有学生和工作相匹配的方法。每条增广路径都会使一条由起点指出的边和一条指向终点的边充满。我们可以注意到,这些边都不是逆向边,因此最多只存在 V 条增广路径,总运行时间与 VE 成正比。

图 6.0.26 二分图匹配中的增广路径

最短路径和最大流量算法都是重要的问题解决模型,因为它们和排序算法有着相同的性质:

  • 它们有其自身的实用性;
  • 我们的算法能够有效解决它们;
  • 许多问题都能够归约为这些模型。

这段简短的讨论只是为了介绍这个概念。如果你能学习一门有关运筹学的课程,就将会学到许多能够归约为这些模型的其他问题以及更多的问题解决模型。

6.0.5.4 线性规划

运筹学的基础之一是 线性规划(Linear Programming,LP),请见图 6.0.27。它的主要思想是将给定的问题归约为以下数学形式。

图 6.0.27 线性规划问题示例

线性规划。给定一个由 M 个 线性不等式 组成的集合和含有 N 个决策变量的线性等式,以及一个由该 N 个决策变量组成的线性 目标函数,找出能够使目标函数的值最大化的一组变量值,或者证明不存在这样的赋值方案。

线性规划是一种极为重要的问题解决模型,因为:

  • 非常多的重要问题都能够归约为线性规划问题;
  • 我们的算法能够有效解决线性规划问题。

在讨论其他问题解决模型时的“该问题有其自身的实用性”就不必提了,因为能够归约为线性规划问题的实际问题实在是太多了。

命题 K。以下问题均可归约为线性规划问题:

  • 最大流量问题;
  • 最短路径问题;
  • 许多许多其他问题。

例证。我们只证明第一个问题并将第二个留作练习 6.50。考虑一个由不等式和等式所组成的系统,其中每一个约束变量都对应着一条边,两个不等式也对应着一条边,每一个等式对应着一个顶点(起点和终点除外)。约束变量的值就是边中的流量,不等式指明了边中的流量必须在 0 和边的容量之间,而等式说明指向每个顶点的所有边中的流量之和必须和从该顶点指出的所有边中的流量之和相等。任意最大流量问题都可以用这种方式归约为一个线性规划问题,而它的解又可以很容易地归约为最大流量问题的解。图 6.0.28 给出了一个具体的示例。

图 6.0.28 将网络流问题归约为线性规划问题

命题 K 中所说的“许多许多其他问题”有三个含义。第一, 添加约束条件和扩展线性规划模型非常简单。第二, 问题的归约是有传递性的,因此能够归约为最短路径和最大流量问题的所有问题也能够归约为线性规划问题。第三,也是更普遍的一种情况,即 各种最优化问题都能够直接构造为线性规划问题。事实上, 线性规划 这个词的意思就是“将一个最优化问题构造为一个线性规划问题”。这种用法出现在“programming”这个词被用作计算机领域的“编程”之意之前。和非常多的问题都可以归约为线性规划问题同样重要的是,解决线性规划问题的高效算法已经发明了数十年了。其中最著名的是 G. Dantzig 在 20 世纪 40 年代发明的 单纯形法(simplex algorithm)。理解单纯形法并不困难(请见本书网站上对它的简单实现)。更近一些的时候,L. G. Khachian 在 1979 年演示了 椭球法(ellipsoid algorithm)并推动了 20 世纪 80 年代 内点法(interior point methods)的发展。对于人们在现代应用中遇到的各种大型线性规划问题, 内点法 是对 单纯形法 的有效补充。现在,解决线性规划问题的程序都已经十分健壮、久经考验、高效并且对于现代公司机构的基本运作起到了关键的作用。它在科学领域甚至应用程序中的运用也在不断扩展。如果线性规划模型能够表示你的问题,那么离问题的解决也就不远了。

非常现实地说,线性规划是各种问题解决模型的鼻祖,因为非常多的问题都能向它归约。很自然,这一点也使我们不禁思考是否存在比线性规划问题更强大的问题解决模型。还有哪些问题无法归约为线性规划问题?下面就是一个例子。

负载均衡。给定一组任务和完成它们的时间,应该如何在两个相同的处理器上分配任务使得所有任务的总完成时间最短?

我们能够找到一个更加一般的问题解决模型并高效解决它的实例吗?这样的思考得到的结果是 不可解性,它也将是本书的最后一个话题。