数学建模离散优化模型与算法设计.ppt

数学建模离散优化模型及算法设计 第 9章： 某些 P问题及其算法 之前 ,我们介绍了与计算复杂性有关的一些基本概念 .人们发现 ,在离散 问题中存在着两个互不相交的类： P类与 NP完全类（若 P NP）。前者具 有求解的有效算法而后者不可能有这种算法。从这一点上讲， P问题可 以看成是一类具有良好性质而又较容易求解的问题，而 NP完全问题则是 固有地难解的。 在 8.4中看到，有着广泛应用背景的线性规划问题是一个 P问题。这样， 作为线性规划子问题的运输问题及作为运输问题子问题的指派问题自然 更是 P问题。虽然从平均的角度讲，人们似乎更常遇到 NP完全问题，但 P 仍不失为一个十分重要的问题类。一方面，很多 P问题象线性规划一样有 着极广泛的应用前景，且它们本身又是十分有趣的；另一方面，它们也 是研究一些更为复杂、难解的问题时经常被采用的研究工具。在本章中， 将再介绍一些经常遇到的 P问题并给出求解它们的有效算法。 一、拟阵问题及贪婪算法 在 P类中又存在着一个被称为拟阵的具有更为良好性质的问题类，其中的 任一问题均可用一种被称为贪婪法的方法来求解，而这一性质并不是所有 的 P问题都具有的。 例 9.1 （最小生成树问题 MST） 给定一连通图 G=（ V， E）， ， 有一表示边长的权 C（ e）（表示顶点间的距离或费用），求此图的具有 最小总权的生成树。 e 此问题的标准形式为给定一完全图 G，其每边赋有一权数，求此完全图的 最小生成树。所谓树是指连通而无圈的图，单独的一个点也可看成一颗 树。树用 (U， T)表示， U为树的顶点， T为树的边集。不相交的树的集合 被称为森林。一个连通图的生成树是指图中具有最多边数的一棵树。容 易证明，对于一个连通图 G， G 的任一生成树必有 V -1条边。 求解最小生成树的算法主要依据下面的定理： 定理 9.1 设 （ V1， T1）， （ Vk ,Tk） 为连通图 G中的森林， V1 U V2U Vk=V。 k,若仅有一个顶点在 Vi中的具有最小权的边为（ ,u）， 则必有一棵 G的最小生成树包含边（ ,u）。 ,1i 根据定 1可以作了如下算法：任选一点 ，令 若 V1=V，停；否则，找出仅有一个顶点在 V1中的边里具有最小权的边 （ ,u），设，将 u加入 V1（ ,u）加入 T。重复上述步骤，直到 V1=V。 1 11: , : .VT 证明 ：设 G的一棵最小生成树（ V， T）不含（ ,u）。将（ ,u）加入 T， 由于（ V， T）是生成树， T U（ ,u）中含有过（ ,u）的唯一的圈。不 妨设 ，则 ，此圈中的点不全由 Vi中的点组成 ,因此必存在 圈中的另一边 。删去边 得到一新的生成树（ V， T1）， T1= ，须其总权不超过（ V， T）的权 ,即（ V， T） 是包含边（ ,u）的最小生成树。 iV iV , iiuu u , uu 例 9.2 求图 9.1中图 G的最小生成树。 解 ： 不妨从顶点开始寻找。 标号 1，先加入 （因为边权 最小）， 标号 2。再加入 标号 3。 ，每次加入一条一顶点已标 号加一顶点未标号而又具有最小权的边，直到所有顶点均标号为止。找 到的最小生成树已用又线标在图 9.2中。 1 1 1,V 2 12 2 44 容易看出算法的计算量为 O (V)2 ，所以此算法是有效算法，若 G具有 O（ ）条边，其中 n= V ，计算量的界还是不能改进的，因为每条 边至少应被检查一次。 2nC 由例 9.2可以看出，算法执行的每一步均加入一条可以加入的（即不生成 圈的）具有最小权的边，而不去考虑它对以后选取的影响，这种算法被 称为贪婪算法。 例 9.3 (入树问题 ) 给出一个有向图 G=（ V， A），对 A中的每一条孤 e，给 出一个权 C（ e），求 A的一个具有最大权（或最小权）的子集 B，要求 B 中任意两条孤都没有公共的终点。 考察下面的入树问题实例： 例 9.4 给出有向图 G=（ V， A） （图 9.3） ，孤上标出的数字为该边的 权，求此图具有最大权的入树。 解：由于入树不能包含具有公共终点的孤，故对每一顶点 只能选 取一条入孤。为使选出的弧具有最大权，只需要对每一顶点选取权最大 的入孤，可用计算量为 O（ V E ）的贪婪法求解，具有最大权的 入树为 。 i 1 2 2 1 2 4 4 5 5 3, , , , , , , , , 类似地，出树问题也可以用贪婪法求解。 例 9.5 (矩阵拟阵问题 )给出一个矩阵 Amxn，记其 n个列向量为 e1, ， en。 设对每一列向量 en已指定一权 C（ en）求 的一个线性无 关的子集，它具有最大的权和。 1, ,i in 易见，这一问题也可以用贪婪法求解。集合 的线性无关的 子集被称为独立子集，利用贪婪法必可求得具有最大权的独立子集，可用 线性代数知识加以证明 （见习题 1） 。 1, ,i in 例 9.6 求矩阵 A的列向量具有最大权和的独立子集 7*45762101 5431000 1273121 4531011 A C(ei) 8 4 7 5 2 6 4 解： 采用贪婪法，先取权最大的列 e1，同时对 A作高斯消去，逐次加入 线性无关的向量： A的列向量中具有最大权的独立子集为 。 1 3 5 4 取 e6 取 e4 取 e3 4 5 1 1 0 2 0 5 4 3 1 0 0 0 3 3 4 2 1 1 0 4 5 3 1 0 1 1 1 2 3 1 1 1 0 5 4 3 1 0 0 0 3 3 4 2 1 1 0 4 5 3 1 0 1 1 A 4 / 9 0 4 / 19 4 / 9 0 2 0 4 / 5 1 4 / 3 4 / 1 0 0 0 3 3 4 2 1 1 0 4 5 3 1 0 1 1 定义 9.1 (拟阵 ) 设 E是一个有限集， 为 E的部分子集构成的封闭系统（即 若 ，则必有 ）。若 M=（ E， ）上的离散优化问题的每一 实例均可用贪婪算法求出最优解，则称 M为一拟阵。（注： 被称为独立系 统）。 ,AA A 现以矩阵拟阵为例，对定义 9.1作一说明。 对矩阵拟阵的每一实例， E=e1, en为矩阵列向量的集合， 为 E的线性无 关子集构成的系统，称为独立系统，其元素被称为独立子集。由于 E的任一 线性无关子集的子集也是 E的线性无关子集，故独立系统 是封闭的。又由 于这一离散优化问题的任一实例都可用贪婪法求解，故构成一拟阵，被称 为矩阵拟阵。例 9.1被称为图拟阵，例 9.3被称为划分拟阵。 拟阵问题（或称拟阵结构） 有一个明显而又本质的特性，其任一极大独立 子集中包含着相同个数的元素，从而可以引入基的概念。例如，矩阵列向 量的所有线性无关极大组均具有相同的向量个数，这就导出了基 即矩 阵列秩的概念。对于图拟阵，每一极大独立集均为一生成树，其边数均为 |V|-1。对于划分拟阵，孤集被划分成个 |V|个子集，每一子集由指向同一 顶点的孤组成。显然，任一极大独立集应在每一子集中取一条孤，故其基 数为顶点个数。 我们不加证明地引入下面的定理，虽然其证明并不十分困难。 定理 9.2 E为一有限集合，为 E的部分子集构成的封闭独立系统。以下 两个条件均为 M=(E, y)构成拟阵（即其上的优化问题可用贪婪法求解） 的充分必要条件： （条件 2） 若 I、 I均为 A的两个极大独立集，则 |I|=|I|。 AE （条件 1） 若 I、 I |I| M|， G 中至少含一条路，其中 M中的边多于 M中的边，不难看出，这条路是 G的 关于 M的增广路。 现在可以看出，找最大匹配的关键在于找增广路。读者不难用顶点标号 的办法（由未盖点出发），作出一个求解两分图匹配的增广路算法。此 算法稍加改动，还可以用于非两分图的情况。 三、网络流问题 网络流问题是又一类具有广泛应用前景的 P问题，本节将介绍一些有关 网络流问题的基本理论与算法。 1、最大流问题（ MFP） 边赋值的有向图称为网络。给定一个网络，其边赋值表示该边的容量。最 大流问题要求在不超过边容量的前提下求出网络中两个指定顶点之间的最 大流。例如：当网络是通讯网时，我们可能会去求出网络中两个指定点间 的最大通话量；当网络是城市的街道时，我们又可能会去求两地间的最大 交通流，即单位时间内允许通过的车辆数等等。 建模： 给定一有向图 G=（ V， A）， A的每一条孤（边）（ i,j）上已赋一 表示边容量的非负整数 C（ i,j）。并已指定 V中的两个顶点 s、 t，分别称 它们为发点和收点。 设网络中已存在一个流（不一定是最大流），记孤（ i,j）上的流量为 （ i,j），记 s发出的总流量（即 t收到的总流量）为 ，根据平衡条件，可 得如下的约束条件， ，有 i 其中是 指 A中以顶点 i为起点的孤集， 是指 A中以 i为终点的孤集 , ( .1)式表示 s发出流为 ， t收入的流为 ，其余各点只起中转作用， 既不增加也不消耗流量。根据边容量限止，还应有 iA iA , , , ,i j C i j i j A 而我们的愿望是使总流量尽可能地大。 即在（ 9.1）、 (9.2)式约束下 使达到最大，易见，这是一个线性规划问题的子问题，故 类。 P tiv tsi siv jiji Aiji Aiji 若 若 若 .0),(),( ),( ),( 对于一个较为复杂的网络，要想直接找出最大流是不太可能的。为了简 化问题，我们先引入一些符号。 记 、 为 的两个不相交的子集， s ，用（，）表示发 点在，收点在的边集， 记 ，并定义如下的切割概念： ,P t Q , , , , , , i P j Q i P j Q P Q i j C P Q C i j 定义 9.5 （切割） 设 是 的顶点集合 的一个真子集， 为 关于 的补集。若 、 满足 且 则称 和 为的一个切割。 P P SP tP P 根据切割的定义可以看出，当和 为一切割时，如果去掉连接 和的 边集（ ， ），就切断了由通往 t的所有通路。所以，对网络的任一 切割（ ， ）， （ ， ）必为最大流的一个上界， 而 。 P P P P ,P P P P 例 9.9 网络如图 9.6所示，边（弧）上的两数字分别表示边容量及实际流 量。取，则，显然 、 是网络 的一个切割。对于这一切割容易算出 而网络的流量 。 P , 6 , , 9P P C P P 为了尽可能地增大网络上的流量，按如下方法作出一个和 具有相同顶 点并具有相同发点和收点的增广网络 （ ） （简记 ）。 包含 两类边，对中每一条边（ i， j） ： A （ 1）若 ，作正向边（ i， j） , 规定容量 ，即剩余容量。 ,i j C j i , , ,C j i C j i j i （ 2）若 ，作反向边（ j,i）， 规定容量 事实上是边（ j,i）上最多可减少的容量。 ,0ij , , ,C j i j i C j i 第一类边称为正规边，第二类边则称为增广边。例如由图 9.6中的流可以 作出其相应的增广网络图 9.7，其中实箭线为正规定，虚箭线为增广边， 边上的数字为边容量。 如果增广网络上存在着由 s t的通路 p（称为原网络的一条增广路）， 记 ，则只要在 P中的一切正规边上增加流量 a，而在对应 增广边（ j, i）， G的边（ i, j）上减少流量 a，就得到 G的一个由 s t的增 大了流量 a的更大的流。例如，从图 9.7上可以找出增广路 ， a=2。于是，图 9.6中的流可改进增大为图 9.8(a)中的流，总流 量为 7。由于其增广网络图 9.8(b)中不再存在增广路，无法再继续增大。 容易看出，若取 s出发（在增广网络上）可到达的点的集合为 P，则 P= , ， = , , , ， C（ P， ） =7，而流量已达到 7，故此 流已是最大流。 ( , )m i n ( , )i j Pa C i j P P （ 1） ( , ) ( , ) , ( , ) ( , )i j C i j i j P P （ 2） ( , ) 0 , ( , ) ( , )i j i j P P 故 ， 已不能再增大，（注：这是线性规划的补松驰定理）。 ( , ) ( , )P P C P P 综上所述，有下面的有关网络流问题的定理。 定理 9.5 （ Ford和 Fulkerson最大流最小切割定理） 任一由 s到 t的流， 其流量不大于任一切割的容量 C（ P， ），而最大流的流量则等于最小 切割的容量。进而 为最大流且（ P， ）为最小切割当且仅当： （ 1） 有 （ 2） 有 。 P P ( , ) ( , )i j P P ( , ) ( , )i j C i j ( , ) ( , )i j P P ( , ) 0ij 增广路可以通过对顶点标号的方法来寻找。由于边容量均为整数，而每次 经改进，流量至少增加一，故算法总能很快求得最大流。 定理 9.4 网络 G上的流是最大流的充要条件为其增广网络上不存在由 s到 t 的通路。 证明： 若增广网络上存在由 s到 t的通路 P，则对 P上的正规边（ i, j）增加流 量 a，对 P的增广边（ j, i）对应 G的边（ i, j）减少流量 a，即可得到一个更 大的可行流。若增广网络上不存在由 s到 t的路，记增广图上 s可达到的点组 成的集合为 P，则对切割（ P, ）必有： P 2、最小费用最大流问题 对于一个给定的网络，由发点 s到收点 t常常存在着多个具有相同流量的最 大流。如图 9.9所示，图中的（ a）、（ b）、（ c）均是流量为 7的最大流， 边上的两个数字依次为容量和边上的实际流量。有时候，当流流经一条边 时需支付一定的费用，我们不仅希望找出一个最大流，而且希望找出的最 大流在具有相同流量的流中具有最小的总费用，这时问题可描述为：对有 向图 G=（ V， A）的每条边（弧）（ i, j）给定一个边容量 C（ i, j）及一个 单位流量费用 l(i, j)。希望求出由 s到 t的最大流，使得总费用最少，即求最 大流 *，使 * ( , ) ( ) m in ( , ) ( , ) i j A L l i j i j 最大流 例如，在交通网络中， l(i, j)可以是 i, j之间的距离或运费。自然，在运送 相同数量货物时，我们希望总距离或总运费最小。现在，我们将以最大 流问题的增广路算法为基础，导出求解最小费用最大流问题的算法。 对于网络上的一个现行流 ，作出其增广网络 G( )，对 G中的正规边 赋值 l(i, j)，对 G中的增广边 (i, j)则赋值 l(i, j)。 定义 9.6 增广网络 G上由 s到 t的流量为零但边流量不全为零的流称为一个循环流。 最小费用最大流问题可以变换成为一个线性规划问题，根据线性规划理 论可以证明下面的定理： 定理 9.6 网络中的流 是最小费用的，当且仅当其增广网络 G中不存在 负费用的循环流（证明略）。 例 9.10 图 9.10（ a）给出了有向图 G上的一个可行流，其中弧上的三个数 字分别为容量、单位流费用及实际流量。图 9.10（ b）为相应的增广网络， 其中边（弧）上的两个数字分别为容量及单位流费用。求此网络的一个更 小费用流。 从图 9.10（ b）中可以找出一个负费用循环流 s 2 1 s（其余边流量 为 0），每单位流量的总费用为 5。调整此循环流上的流量，得到图 9.11（ a）中的流。原先的流总费用为 17，调整后的总费用为 12，减少值 为负费用循环流的总费用。 图 9.11（ a）中流的增广网络（ b）中已不存在负费用循环流，它是一个最小 费用的流。 定理 9.7 设 1是网络上流量为 的最小费用流， 2是其增广网络上由 s到 t的 最小费用单位流增广路，则 1+2是此网络流量为 +1的最小费用流。 证明： 设 1+2不是流量为 +1的最小费用流，由定理 6，在 1+ 2的增广网 络中必存在一负圈 C。记构造 2的增广路为 P。由于 1是最小费用流， 1的增广网络中不存在负圈，故 C中必有一边（ i, j），其反向边（ j, i）含 在 P中（因为如若不然， C不含 P中任意边，则 C将含在 1的增广网络中，与 1 为最小费用流的假设矛盾，见图 9.12），但这又说明 P （ C（ i, j）是 S到 t的更小费用单位流增广路，与 P是最小费用单位流增广路的假设矛盾。 根据定理 9.7及定理 9.6，求最大流的算法只需稍作 变动即可用来求解最小费用最大流。算法可以用 归纳方式给出，当 =0时，可取 =0，这显然是 =0 的最小费用流。在以后逐次增大流量时，若增广 网络中存在着多于一条增广路时，每次均选用其 中单位流费用最小的一条。这样，每次得到的均 为相同流量的流中费用最小的，而最后得到的即 为最小费用最大流。 网络流问题的算法在解决实际问题时常常被用到。它可用来求解运输问 题、指派问题及赋权两分图匹配问题（等价于指派问题），也可用来寻 找网络的瓶颈 即最小切割（ P， ）确定的边。作为一个网络流问题 的应用实例，我们来求解例 9.7中的婚姻姻问题：增加发点 s和收点 t，将 原图的边改为有向边，所有边的容量为 1。找出最大财礼数 28，以此数 减每边原有的财礼费，并用此差为各边的费用，得一最小费用最大流问 题（未注数字的边费用均为零），其网络图见图 9.13。此问题在使用三 次增广路后可求得最佳结果。 P 四、最短路径问题 最短路径问题是又一个经常遇到的 P问题，它在工艺流程的安排、管道或 网络的铺设、设备更新等实际生产中常被用到，是网络规划的基本问题 之一。顾名思义，最短路径求的是以下问题：给定一个网络，如何求出 网络中指定两点间总距离（或总费用）最小的路径。 例 9.11 给定图 9.14中的网络，边上的数字为两顶点间的距离（或费用）， 求由 A到 E的最短路径。 求解最短路径问题的 Dijkstra算法体现了动态规划算法的基本思想。若点 P在 A到 E的最短路上，则 P到 E的最短路径必整个地包含在 A到 E的最短路 径上。因为，若不然，将由 P到 E的最短路径导出 A到 E的更短路径，从而 导出矛盾。算法既可以通过对顶点逐次标号来实现，也可以通过矩阵运 算进行。在使用标号法时，既可以从起点开始标，也可以从终点开始标。 （两者目的略有不同）对例 9.11中的网络，如从起点 A开始标导，先在 A 点标上 0。再找出离 A最近的点 B3，标上 A到 B3的最短矩离 1并记录下 A点 （表明由 A而来）。一般，在标新顶点时，先找出离已标号顶点最近的顶 点。比较各已标号顶点（与拟标号顶点有边相连）的标号与它到拟标号 顶点距离之和，找出各种中最小者作为新顶点的标号，并记录下其前的 已标号顶点。直到拟到达的终点已标号为止。例如，图 9.15指出， A到 E 的最短路径为 A B2 C1 D1 E，最短距离为 19。 容易看出，算法是多项式时间的。在标每一顶点时，最多作了 | V |次运算。 算法进行中，事实上在构造一棵由已标号顶点及它们与其前行点间的边 组成的树。每一顶点均不可能重复标号，故总计算量的一个上界为 O （ |V|2）。 按一般习惯，动态规划算法常按逆顺序进行。图 9.16给出了按向前标号的 结果，最短路径已用双线划出。 从图 9.15中可看出 A到各点的距离及最短路径，而从图 9.16中则可看出由 各点到 E点的距离及最短路径，这是两者的区别。 读者不难给出一般问题的计算步骤，也不难推广得到能求出任意两点间最 短路径的算法。 作为最短路径问题的一个应用实例，我们来研究下面的设备更新问题： 例 9.12 某单位使用一种设备。该设备在 5年内的预期价格见表 9.1，使用 不同年数的设备的年维修费用见表 9.2 。现准备制订一个五年内的设备 更新计划，使五年内支付的设备购置费用及总维修费用最少。 这显然是一个十分有意义的实际问题，即使作为个人，也会经常遇到更 换交通工具、家用电器等设备更新问题的实例。当然，作为一般情况， 还可能要考虑残值，如购买了新车，旧车可以折价处理，回收资金与已 使用年数有关。 解： 作有向图图 9.17，图中点 i表示第 i年初（或第 i 1）年末），弧（ i, j） 上的数字表示第 i年初购买设备到第 j年初更换，在该段时间内的总费用。 例如，弧（ ， ）上的数 68表示第一年初购买设备到 5年后的第六年 初更换，需支付购设备费 10万元及各年维修费 58 万元，共计 68万元。 问题化为求由顶点 到顶点 的最短路。 容易看出，作出 n年设备更新问题的有向图将问题化为最短路径问题大约 需要 O(n2)计算量，其后要求求解的最短路径问题的计算量也是 O(n2)，故 设备更新问题可在 O(n2)时间内求解。 表 9.1 表 9.2 第 i年 1 2 3 4 5 价格（万年） 10 10 11 12 13 已使用年数 0 1 2 3 4 （万年） 4 8 11 15 20 五、欧拉圈与最短邮路问题 欧拉圈问题起源于著名的七桥问题。给定一个无向图 G=（ V， E），问能 否由一个顶点出发，经且仅经过每条边一次并返回原出发顶点。如果能够， 则每一个这样的圈被称为图 G的欧拉圈，而图 G则被称为是一个欧拉图。 显然，图 G为欧拉图的充要条件是它可以被一笔画出且首尾相连（当首尾 不能相连时则被称为欧拉路）。由此，立即可得出下面的定理： 定理 9.8 G为 欧拉图的充要条件是： G是连通的且 G的每一个顶点都与偶 数条件相关联。 把关联偶数条边的顶点称为偶顶点，把关联奇数条边的顶点称为奇顶点， 则容易看出奇顶点的个数必为偶数个（因为每一笔画都产生一个起点与 一个终点），又易得出 定理 9.9 G为欧拉路的充要条件为： G是连通的且奇顶点的个数为 2。 综合定理 9.8和定理 9.9可知， G可一笔画出的充要条件为 G是连通的且奇顶 点的个数为 0或 2，当奇顶点个数为零时，尚可设法使起点和终点相重。 下面的图 9.18（ a）为欧拉圈，而图 9.18（ b）则为欧拉路，后者虽可一笔 画出，但必须以一个奇顶点为起点，以另一个奇顶为终点。 图的连通性可以十分容易地用标号算法加以检验。而图的奇顶点数又可 通过对其顶点一一检测而求得。容易看出总计算量是多顶式时间的，故 欧拉圈问题和欧拉路问题均是十分简单的 P问题，从而，等价地，一笔画 问题也可十分容易地求解：若图 G是欧拉图，则从任一顶点出发均可将它 一笔画出；若图 G是欧拉路，则由一奇顶点出发，一一经偶顶点地走过各 条边，最后到达另一奇顶点，即可将 G一笔画出；否则 G不能一笔画出， （当然，如何走法仍需规划一下）。 与欧拉图有较大联系的另一有名的 P问题是无向图上的中国邮路问题。给 定一个无向图，它的每一条边上都赋有一个表示该边长度（或费用）的权。 要求从一指定顶点出发，至少经过每一条边一次最后返回原出发点，并使 经过边的总长度最小。其中如重复走过某些边，则边长应重复计算，重复 几次计算几次。一个由邮局出发去各街道送信最后返回邮局的邮递员遇到 的问题就是一个中国邮路问题。 无向图上的中国邮路问题也不难解决。若无向图 G是欧拉图，则任一欧 拉图都提供了一条最佳邮路。若 G不是欧拉图，如前所说，图中的奇顶 点数必为偶数。然后，求出任意两个奇顶点之间的最短路径及最短矩离 最短路径长度），再解一个奇顶点之间的最小权匹配（或指派问题，注 意这里的距离矩阵是对称的）。将各匹配奇点间的最短路径加入 G中， 就得到了最知路问题的解，我们将在 9.5中考察一个这类问题的实例。 在本节中，我们例举了几个较为典型而又时常遇到的 P问题。由于事实上 存在着无穷多个 P问题，而且即使某问题是 NP完全的，它的许多特殊条 件下的子问题也仍然可以是多项式时间可解的，因而我们不可能对 P类作 一完整的介绍。如果本章内容能起到抛砖引玉的作用，使读者看到一些 P 问题所具有的某些特征及构造算法上的某些技巧，那么，我们的目的也 就达到了。从上述 P问题（包括第八章中的线性规划、运输问题及指派问 题）可以看出，它们都可以用某种逐次改进的方法来求解。每次改进中 的计算量是多项式界的，改进的次数也是多项式界的。线性规划的单纯 形法例外，改进次数可能达到指数次。但即使是线性规划问题，也已经 找到了具有这种特性的算法，如椭球算法、卡马卡算法，虽然其结构是 相当复杂的，但计算量却是多项式时间的。 最后，我们还想强调几点： 1、许多表面有点相象的问题事实上可能具有完全不同的计算复杂性。 这样的例子举不胜举，我们略举一、二，以提醒读者注意。 （ 1）最短路径问题是 P问题，而由一点出发到达每一顶点一次（不必返回 原点）的哈密顿路问题及由一顶点出发经所有顶点一次到达另一顶点的最 短路径问题 流浪的旅行商问题（ WTSP）均是 NP完全的。这里只增加 了每个顶点都要去一次的要求，但问题发生了质的变化，由 P问题变成了 NP完全问题。 （ 2）指派问题与 TSP也有相似之处，前者求一置换而使目标值最小，后者 求一循环置换（不包含子圈）而使目标值最小。前者是 P问题，而后者则是 NP完全的。 （ 3）欧拉圈问题求由一顶点出发经且仅经过每边一次回到原顶点的圈，而 TSP则求由一顶点出发经且仅经过每个顶点一次返回原顶点的圈。前者是十 分容易的 P问题，而后者是极其困难的 NP完全问题，迄今还没有求解它的较 好算法。 （ 4）线性规划问题、运输问题及指派问题均为 P问题，但相应的整数线性 规划及 01规划均为 NP完全的。 （ 5）无向图中国邮路问题是 P问题，而有向图中中国邮路问题则是 NP完 全的，（容易看出，会解有向图上的某问题必也会解无向图上的相同问题， 但反之不真）。 2、求最小的问题是 P问题，求最大的问题可以是 NP完全的，这样的例子 也不少。例如，最短路径问题是 P问题，而最长简单路径（不含圈的路径） 问题却是 NP完全的。如若不然，我们可以利用它的有效算法如下构造出 哈密顿问题的有效算：令图 G=（ V， E）的所有边的权均为 1，以一端点 为起点求到其余各顶点的最长简单路径。由于简单路径不含圈，所有顶 点均不会重复到达，故 G有哈密顿路当且仅当存在一起点及一终点，其最 长简单路径为 | V | 1。由于哈密顿路问题是 NP 完全的，故最长简单路径 问题的有效算法不可能存在，除非 P=NP。所以，如果你想设计一个求图 上两点间的最长简单路径的有效算法，不管你是多么努力，最终必将以 失败告终。又譬如，网络流中的最大流问题是 P问题。相应地，最小切割 问题也是 P问题（它是最大流问题的对偶问题，见线性规划的对偶理论）。 但可以证明，最大切割问题却是 NP完全的。 总之，在研究离散模型时应当极其小心。一方面，我们必须先搞清问题的 计算复杂性，而另一方面，条件的微小改变就有可能将一个 P问题转变为 NP完全的。当然，相反的转变也完全是可能的。 9.2 关于 NP完全性证明的几个例子 上节介绍了几个 P问题及求解它们的算法。从某种意义上说，可以认为这 些问题已被较好地解决了。然而，在研究离散问题时并非都能遇上这样 的好运。正如第八章所讲，存在着大量具有 NP完全性的问题，虽然许多 人作了巨大的努力，仍未找到任何有效算法。其中的许多问题，例如 TSP， 甚至经受了两代数学家的顽强攻击，竟然毫无进展。各种迹象使人们来 越来越倾向于相信，对这些问题根本不存在有效算法，自 1972年 Cook发 表那篇著名的论文以来，这些问题越来越多地被发现。因此，当我们着 手研究一个离散问题时，不得不首先搞清遇到的会不会也是这样一个问 题。有时，我们可以从有关书籍或文献中查到它，因为别人早已对它作 过研究。例如可查阅 M.R.Garey和 D.S.Johnoson的著作“计算机和难解 性”，其中例举了大量 NP完全问题。但这类问题事实上有无限多个，很 多时候，我们会遇到一些对其计算机复杂性一无所知的问题。这时，假 如我们仍要去研究它，首当其冲的问题就是搞清问题的性质，以便保证 研究工作沿正确的途径展开。要判定一个离散问题的性质没有一个固定 的程式可以沿用（虽然总是用多项式转换的方法），常常要用到较高的 技巧，并要求对问题的组合结构有相当的了解。尽管如此，别人的经验 对我们仍然是很有用的。本节将再分析一些问题，看看别人是如何判定 它们的 NP完全性的。 例 9.13 （独立集问题） 给定图 G=（ V， E），求 G的一个最大独立集。 所谓独立集是指 V的一个子集 ，有 1 , , , 1 ,kii s t k ( , )stii E 例 9.14 （复盖问题） 给定图 G=（ V， E），求 G的顶点的一个最小复盖。 所谓复盖是指 V的一个子集 C， ， u C或 C至少有一个成立。 ( , )uE 对于例 9.13和例 9.14，我们为叙述方便，采用了图的语言，其实也完全可 以将它们表达成其他方式。 定理 9.10 独立集问题与点复盖问题都是 NP完全的。 证明 称图 为图 G的补集，若 与 G有相同的顶点集，且（ i,j）是 的 边当且仅当它不是 G的边。显然，求 G的独立集即求 的团，由 G作出 可 在多项式时间内完成，故独立集问题等价于团问题。而团问题是 NP完全的 （见第八章六个基本 NP完全问题），故独立集问题是 NP完全的。类似地， 容易证明 K是 G的团当且仅当 V K是 的复盖，故点复盖问题也是 NP完全 的。事实上，对任意 中的边（ i,j），有（ i,j）不在 G中，故 i,j不能全 在 G的团 K中，从而 i与 j中至少有一个在 V K中，由边（ i,j）的任意性可 知， V K中，由边（ i,j）的任意性可知， V K 必为 的一个复盖。 G G G G G G G G 前面已经讲过，哈密顿圈问题已被证明是 NP完全的，从而可得出 TSP是 NP 完全的，哈密顿问题是 NP完全的，进而又可得出有向图上的哈密顿圈、哈 密顿路和 TSP也是 NP完全的，因为用两条具有相反方向的弧来代替每一条 边，就可将一个无向图上的问题转化为一个有向图上的问题，从而任一有 向图问题的有效算法必能用来求解无向图问题。 例 9.15 （背包问题） 给定一组整数 C=c1, cn以及一整数 K，问是否存在 C的一个子集 S，使得 。 i icSCK 不难看出，背包问题是 NP完全的，因为若取 ， 问题就化成了划分问题。 1 1 2 n i i KC 例 9.15之所以被称为背包问题是因为它等价于其优化形式：以 K为“背包” 的容量，欲将 C中的整数装入背包中，使背包中的各数之和尽可能地大 （求 C的子集 S，使 且尽可能大），即要求求解 0 1（线性）规 划问题： i icSCK St xi0， xi1 xi为整数 1 m a x n ii i cx 1 n ii i c x K 例 9.16 （装箱问题 Bin packing）有一批待装箱的物品 J=p1, pn， pj的长度为 l(pj)。现有一批容量为 C的箱子（足够数量）， 要求找到一种装箱方法，使得所用的箱子数最少。 例 9.16是一个一维的装箱问题。例如，我们有一批具有相同长度的钢材，如 果想取出几根已知长度的钢料生产某种设备，当然会希望少用几根原始钢材 以减少浪费。此时，我们就遇到了一个一维的 Binpacking问题。当我们想 从购买来的三夹板上锯出 n块已知长、宽的板来制作家具时，遇到的是二维 Binpacking问题。而当我们真正想把一批已知长、宽、高的物体装入具有 相同尺寸的箱子时，又遇到了三维的。下面的定理 告诉我们，即使是一维 的 Binpacking问题也是 NP完全的，故二维和三维的 Binpacking问题更 不可能是 P问题（它们也是 NP完全的）。 定理 9.11 （一维） Binpacking问题是 NP完全的。 证明： 易见，划分问题可转化为 Bin packing问题。事实上， 取 ， J=c1, cn可划分为两个相等的集合的充要条件是 它们可装入两只容量为 C的箱中。 1 1 2 n j j Cc 从某种意义上讲， 3划分问题（即分为三个相等子集的问题）也许比 2 划分问题更难，因为已经找到了求解 2划分问题的一些较好算法（称为 伪多项式时间算法）。但对 3划分问题不可能存在类似算法，由于本书 篇幅有限，不再作详尽的讨论。读者不难发现， Binpacking问题至少不 会比 3划分问题容易。顺便指出， Binpackin问题中的臬子容量 C可以 取为 1，这样的问题与例 9.16是等价的。 例 9.17 （排序问题 Scheduling） 拟用 m台机器加工 n个零件，对零件的加 工可以提出各种不同的附加条件，希望排出一个加工顺序（或时间表），使 在某种衡量标准下所求得的加工顺序为最佳。 Scheduling是一类应用面极广的离散问题，可以讲它不是一个问题，而是一 类问题，因为不同的机器环境、不同的加工要求或不同的衡量标准所得出的 模型是不同的。按目前流行的做法，人们常用三个参数 ， ， 来描述一个 特定的排序问题，并记为 /排序问题，其中 描述机器情况， 描述加工零 件时的附加要求或附加条件， 表示衡量排序好坏的标准。按此方法分类， 有人作过统计，认为至少有 9000多个不同的排序问题已被或多或少地研究过， 其中 76%为 NP完全的 ， 12%的为 P问题 ，余下的 12%目前还未搞清其计算 复杂性，但根据种种迹象 ，大部分可能是 NP完全的。有关排序问题，目前 已有十多本专著及至少数千篇论文，这里不准备细述专业知识，仅以几个排 序问题模型为例，来分析其计算复杂性。 Jm/ no wait /Cmax问题是 NP完全的。在这一模型中， =Jm， J代表一类被 称为 Job shop的问题， m表示有 m台机器。 Job shop意指每一工件要在 m台 机器的每一台上加工（当不需某台加工时可令加工时间为零），且各工件 使用机器的顺序可以不同。 =no wiat，表示任一工件在开始第一道工序加 工后不允许中间等待，直到它的各道加工均被完成。 =Cmax表示排序优劣 的评价标准是全系统的加工时间最短，即由第一台机器开始加工起到最后 一台机器完工为止的时间跨度最小。第八章例 8.8（轧钢问题）就是 Jm/no wait/Cmax排序问题的一个实例。在那里已经证明了这一问题等价与 TSP， 从而是 NP完全的。 P2/Cmax问题是 NP完全。这里， =P2表示是一个 2台机器的平行机问题， 即有两台完全相同的机器，每一工件只需在其中任意一台上加工一次即可。 =，表示工件加工没有附加要求或条件。 =Cmax的解释同上。容易看出， 这一问题至少不会比划分问题容易，故不可能是 P问题。 在上面的例 9.13到例 9.17中，我们又列举了几个 NP完全问题，它们的 NP完 全性证明都非常简单。但一般地讲，事情决非如此简单，要将某一 NP完 全问题多项式时间转化为我们要研究的问题，常常需要用到一些巧妙而又 精细的技巧。下面给出一个稍难一些的例子，供有兴趣的读者参考。 讨论 1/rj, prmp/ 排序问题，我们将证明它是 NP完全的，这是一个 一台机器的排序问题，待加工的工件 Tj有一个准备时间 rj， rj0，仅当 trj时 它才能被加工。 prmp表示加工允许中断以便先加工其他工件，未完成的加 工可在此后的某一时期补上。各工件的重要程度不同，对每一 Ti有一权因 子 wj。评判排序优劣的标准为各工件完工时间 Cj的加权和 越小越好。 1 n jj j wC jjwC 这一问题很难直接利用前面提到过的那些 NP完全问题来证明其 NP完全性。 我们将用到下面的已被证明的 NP完全问题。 例 9.18 （三元划分问题） 给定 3t个正整数的集合 a1, a3t，令 ，问是否能将此集合划分成两两不相交的 t个子集， 使得每一子集恰含总和为 b的三项，（标准型中可设 ）。 3 1 1 t i i bat , 42ibbia 现在，我们来证明，对三元划分问题的每一实例，总可构造出一个等价的 1/1/rj, prmp/ 排序问题的实例，（因此，会解后者就必会解前者）。 jjwC 对例 9.18给出的三元划分问题，作如下的 1/rj , prmp/ 排序问题实例， 该例中共有 4t 1项加工任务。相应数据为 1 n jjj wC j=1,3 t，令 rj=0，需加工时间 Pj=aj, wj=1 j=3t+1,4 t 1，令 rj= (j 3t)(b+1) 1 Pj=1, wj=2 等价性证明可分以下几步完成，有兴趣的读者可以自己完成它： （ 1）证明最后 t 1项工件应尽早加工，否则必将增大 ，因为它们 的 wj=2，而前 3t项则有 wj=1。这样，这 t 1项工件应分别在 b, b + 1, 2b + 1, 2b + 2, ( t 1) b +1 2, (t 1)b + t 1时段内加工。除去加工这 t 1项 工件的时段，整个加工期还留下长度均为 b的 t个时段。 jjwC （ 2）若三元分划问题有解，可利用每一时段加工一个子集中的工件，此 时不必中断任何工件的加工，而 若三元分划问题无解，则必有 Z Z是与排序无关的一个常数，而 =Z当且仅当三元划分有解。 13 ( 1 ) 3 / 2 1 )j j j k j K t w C a a t b Z jjwC jjwC 9.3 分枝定界法与隐枚举法（精确算法） 在上一章中我们已经看到，整数规划、 01规划都是 NP完全的。事实上， 仅对部分变量有非负约束的线性规划（称为混合整数规划）也是 NP完全 的。这样，一方面不可能找到求解的有效算法，另一方面枚举所有可能 情况的办法对规模较大的例子又无法实现。出于实际需要，人们不得不 采取一些折中的办法，即以枚举为基础，选用一些减少计算量的技巧或 规则，以增大算法的实用效果。前面已经指出，所谓指数算法实际上是 指在最坏的情况下可能达指数时间的计算量，它并不排斥在大多数情况 下算法表现出好的性态。例如，求解线性规划的单纯形法从理论上讲是 指数算法，但在实际应用时它又一般表现得出奇地好（已经证明，其平 均计算量仅为 O(nlog2n)）。这一实例鼓舞人们去对其余问题寻找类似的 算法。虽然迄今为止还没有一个 NP完全问题被发现具有类似单纯形法那 样漂亮的指数算法，这也许是由问题的 NP完全性本身决定的（注意：线 性规划问题是 P问题，具有良好的组合结构）。但人们的努力并没有完全 白费，有些 NP完全问题已有了一些在实际应用时值得一试的求解算法。 我们将在本节举几个实例来介绍这类算法。 一、分枝定界法 例 9.19 某房屋出租单位有活动资金 91万元，拟购房出租，现有两种房屋， 一种每套 13万元，只有四套；另一种每套 18.2万元，数量不限。该单位每月 可用于照料租房的工时总计为 140 小时，第一种房每套每月需照料 4小时， 第二种房每套每月需照料 40小时。第一种房月租金收入为 2000元，第二种 房月租金收入为 3000元。问此单位应购两种房各多少套才能使总收入最大 建模 设 x1、 x2分别为购买两种房的套数，显然 x1、 x2必须为整数，故要求 求解整数规划（ ILP） max 0.2 x1 + 0.3x2 S.t 13x1 + 18.2x291 4 x1 + 40 x2140 x14 x1、 x20且为整数 解 ： 先不考虑整数要求，求解与上述整数规划（ ILP）相应的线性规划 LP0（称之为与（ ILP）相应的松驰线性规划），解得 x1=2.44， x2=3.26， maxZ=1.466万元。 分析： 若将变量四舍五入化整，虽满足了变量的整数要求，但一方面得 到的有可能不是可行解，另一方面即使得到的是可行解，也不能保证它 是最优解。有人曾构造出一个实例，其最优解有一百多万种四舍五入的 可能情况，但得到的均非可行解。对本例，因只有两个变量，共有四种 可能，即化整为（ 2,3），（ 2,4），（ 3,3），（ 3,4），其中只有 x1=2， x2=3是可行的，目标值为 Z=1.3万元，并非最优解（最优解为 x1=4， x2=2， Z*=1.4万元）。不难看出，对只有两个变量的问题都不能通过化整的办法 来求得最优解，对变量数较多的实例，情况将更为复杂。 求解松驰线性规划虽无法找出最优整数解，但却指出了该实例目标函数值 的一个下界（指标准型 min问题）。在本实例中，由于问题是求目标值最 大的，我们可以看出，既然不考虑整约束时的最优目标值为 1.466 万，则 （ ILP）的最优目标值不可能超过 1.466万，从而我们知道了最优目标值的 一个上界。 下面介绍一种分枝定界技巧 从（ ILP）的松驰线性规划的最优解中选取一个非整分量（通常选离整数 最远的分量），例如我们选取 x1，考察两个新的松驰线性规划。 （ LP1） max 0.2 x1 + 0.3x2 S.t 13x1 + 18.2x291 4 x1 + 40 x2140 x12 x1、 x20且为整数 （ LP2） max 0.2 x1 + 0.3x2 S.t 13x1 + 18.2x291 4 x1 + 40 x2140 x13 x14 x1、 x20且为整数 可以看出，（ ILP）的最优解必在（ LP1）与（ LP2）的可行域之一中， 但（ LP0）的最优解 （ 2.44,3.26）已不在（ LP1）与（ LP2）的可行域中 （这正是分枝的目的）。 （ LP1）的最优解为（ 2， 3.3），最优目标值为 1.39万元，其可行域中不包 含具有更大目标值的可行解，（ LP2）的最优解为（ 3,2.86），最优目标值 为 1.458万元。 由于（ LP1）与（ LP2）的最优解均非整数解，还需继续搜索，现选取最优 目标值最大的（ LP2）进行分枝，即增加约束 x22作子问题（ LP3），增加 约束 x23作子问题（ LP4）。 （ LP4）无可行解，（ LP3）有最优解（ 4, 2）， 该分枝的最优目标值 Z=1.4。于是，对 x13的分枝（ LP2），我们已求得最 优解（注（ LP1）已不必再求解）目标值的一个上界（ UB） Z=1.4。另一方 面，又同时 求得一整数解其目标值 Z=1.4，故已有整数最优解目标值的一个 下界（ LB） Z=1.4 至此，我们已运用分枝定界法求得了整数规划例 9.19的最优解，整个过程 见图 9.18所示。读者不难看出算法的实质，并由此总结出算法。 为了让读者看清在各种不同类型的问题中是如何使用分枝定界法的，下面 我们再举一例： 例 9.20 要调配红、蓝、白、黑、黄五种颜色的油漆。清洗调配工具所需花 费的时间既和原来调配什么颜色有关又和拟调配什么颜色有关，各种情况 下所需的时间见表 9.3所示。问应当如何调配较好（要求先建立模型）。 对例 9.20我们作如下理解，一个油漆工每天都要使用上述五种颜料，从而 他应当在完成工作后清洗好工具，以便第二天开始同样顺序的调色。如 果该工人只需调配一次而不必考虑以后的工作，问题可以作类似的讨论， （注：此工人只有一块调色板）。 表 9.3 现调 原调 红 蓝 白 黑 黄 红 蓝 白 黑 黄 / 7 4 20 8 6 / 5 19 8 18 17 / 24 16 4 3 4 / 6 8 7 5 22 / 考察五种颜色间的指派问题，将甲色指派给乙色理解为“用完甲色清洗工 具，其后使用乙色”。相应的费用矩阵为 6 18 4 8 7 17 3 7 4 5 4 5 20 19 24 22 8 8 16 6 M M M M M 红 蓝 白 黑 黄 红 兰 白 黑 黄 其中，“ M”表示充分大的正实数。 利用求解指派问题的匈牙利算法，对矩阵逐次变换如下： 6 18 4 8 7 17 3 7 4 5 4 5 20 19 24 22 8 8 16 6 M M M M M 4 2 14 0 4 3 4 14 0 4 4 0 1 0 1 19 1 0 5 3 6 2 2 10 0 5 1 M M M M M 2 9 0 3 4 9 0 3 2 0 1 0 0 2 1 0 0 2 2 2 5 0 M M M M M 0 7 0 1 2 7 0 1 0 1 2 0 1 0 0 2 0 0 3 0 M M M M M 在变换过程中， M的值可能改变，它们均表示充分大的正整数，为简便 起见，不妨仍用 M表示。从最后一个矩阵立即可得此调色问题的一个最 优顺序：红 蓝 黑 白 黄（黄 红）。 读者不难发现，利用指派问题的算法求得调色问题例 2的解纯系巧合。事 实上，调色问题可看成旅行商问题的实例。 TSP是 NP完全的，而求解指 派问题的匈牙利算法是多项式时间算法，不可能用来求解 TSP的每一实 例。例如，如果将例 9.20的费用矩阵改为 1 2 3 4 5 1 4 8 6 8 4 2 5 7 11 13 5 3 11 6 8 4 4 4 5 7 2 2 2 5 10 9 7 5 5 M M A M M M _ 共计减 20 1 2 3 4 5 1 1 0 4 2 4 2 0 2 6 8 3 7 2 4 0 4 3 5 0 0 5 5 4 2 0 M M A M M M 相应的指派 1 2， 3 5 4不构成一个旅行回路（哈密顿圈），它含有两 个子圈（ 1,2）和（ 3,5,4）。 一般地，调色问题（即 TSP的实例）可试用分枝定界法求解。如对长阵 A，由 于从其相应的等价问题矩阵 A1中可找到费用为 0的最优指派，故可知 20是其总 费用的一个下界。现作如下两个分枝：（ 1）取 2 1，即 2指派给 1（简记成 （ 21），则不能再有 1 2，将矩阵 A1中位于第一行及第二列的元素 0改写成 M，在不允许（ 12）的限止下两问题的最优指派相同，作变换： 1 2 3 4 5 1 4 2 4 2 2 0 2 2 0 0 3 2 4 0 0 4 0 4 5 0 0 3 0 0 5 4 2 0 2 2 0 M M M M M M M M M M M M M M M M M M M M M M M M 2 （累计减 24新下界） 此时又可作如下分枝： （情况 1）取（ 14） 0 0 00 00 2 2 2 M M M M MMMM M M M M M M M M M （累计减 26新下界） （情况 2）不取（ 14）（简记为（ 14） 2 022 003 040 0 22 MM MM MM MMMM MMM （累计减 26 新下界） 情况 1中位于第四行第二列的元素改为 M是因为此时不能取 4 2,否则将含 子圈（ 1， 4， 2）。 两种情况又可分别变换为 （情况 1）取（ 14） MMM MMM MMM MMMM MMMM 00 00 00 0 0 求得（ 1， 4， 5， 3， 2） （情况 2）（ 14） MM M MMM MMMM MM 222 0003 00 0 000 求得（ 1， 4， 5， 3， 2） 两个旅行圈的费用均为 26（指在原问题中）。 （ 2）不取 2 1，将矩阵 A1改写为 M M M MM M M M M MM M 0242 0050 0424 640 4240 2 0242 0053 0427 862 4240 -3 累计减 25 求得（ 1， 2， 3， 5， 4） 比较各分枝，求得原问题的最优解（ 1， 2， 3， 5， 4），最优目标值为 25， 如图 9.20所示。 需要指出的是，虽然在上面的实例中计 算量并不是很大，但对于 n较大的实例， 用以上介绍的分枝定界法求解旅行商问 题效果并不理想，如何构造实用效果更 好的分枝定界算法仍然是一个值得进一 步研究的问题。 二、隐枚举法 现考察 0-1规划的一个实例： 例： 9.21 试求解 0-1规划： S.t 约束条件（ 1） 约束条件（ 2） 约束条件（ 3） 或 1 321 523m a x x