关于组合最优化介绍

[拼音]：zuhe zuiyouhua

[外文]：ombinatorial optimization

又称组合规划，它是在给定有限集的所有具备某些特性的子集中，按某种目标找出一个最优的子集的一类数学规划。初期，它所研究的问题，如广播网的设置、开关电路设计、航船运输路线的计划、旅游路线的安排、人与工作间的对应分配、课程时间表的制定、装箱（装车）问题、运输网络中或工程施工中薄弱环节的分析、制定露天煤矿开采计划等，都是网络上的一些极值问题，后来，对这些问题进行概括和抽象，在理论上研究了拟阵中的一些更一般性的组合最优化问题及其算法。

设 是一个由有限个元素所组成的集合，F为E的一个子集簇，其中Ei是E 的具有某种特性的子集。设ƒ是定义在F上的实值函数。所谓组合最优化问题，是指寻找一个子集Ei使对任意属于F的Ej，都有

，

并称这样的Ei为组合最优化问题的最优解。对每一个元素 ei，有一个给定的实数 с（ei），称为ei的权。对每一个子集Ei，若ƒ（Ei）为Ei中各元素的权之和，即，则相应的组合最优化问题称为线性组合最优化问题。ƒ(Ei)称为Ei的权。

设G＝(V，E)是一个图，其中V是点集，E是边集。对每一个边有一给定的实数，称为边的权，具有权的图称为网络。例如，若G表示一个铁路图，边表示相邻两点间的铁路线，边的权表示两点间的距离，则 G是表示距离的网络。若边的权表示两站间的铁路运输最大能力（即容量），则G就是一个容量网络。如下面问题是网络上基本的组合最优化问题。

（1）在一个网络中，给定两个点vs、vt，寻求一个联结vs、vt的链，使链中各边的权之和为最小。这就是所谓最短路问题。其中的子集Ei是联结vs与vt的各个链上的边的集合。

（2）在一个网络中，求一个支撑树，使树中各边的权之和为最大（或最小）。这就是所谓最大（或最小）支撑树问题。广播网的最优设计，往往可归结为这个问题。这里的Ei则是支撑树的边的集合。

（3）在一个网络中，求一个边无关集，使各边的权之和最大。这就是所谓最优边无关集。这里的Ei是各个边无关集。若图是二部图，则边无关集可解释为人与工作之间的一种对应分配方式。因此也可称为最优匹配问题。

（4）边的一个子集S，若在图中减去S后，就没有任何联结vs和vt的链，则S 称为一个分离vs和vt的截集。截集中各边的权之和称为截量。寻求一个分离vs和vt的截集，使其截量最小。这就是所谓最小截集问题。这里的Ei即截集。寻找运输网络中的薄弱环节问题，常常可归结为求最小截集问题。

（5）在一个网络中，寻求一条能经过网络中各个点恰好一次而后回到出发点的路线，使其全程最短。这就是所谓推销员问题。寻求一条能经过网络中各边而后回到出发点的路线，使其全程为最短。这就是所谓中国邮递员问题。这里的Ei是各条路线上的边的集合。这两个问题在本质上有差别，中国邮递员问题可以归结为最优边无关集问题。

上述的各问题，除推销员问题外，都已分别找到了有效的特殊算法。这些算法大致可以分为四类。

（1）利用动态规划方法，建立递推公式。如求最短路的迪克斯特拉算法。

（2）最大流方法，如求最小截集的算法。

（3）贪心(Greedy)算法， 如求最优支撑树的克鲁斯卡尔算法。

（4）交错链方法，如求最优边无关集的匈牙利算法和J.埃德蒙兹的“花”算法等。

E的一个子集簇F，若具有如下的性质:对于F中的任一元素Ei，当S是Ei的子集时S也是F中的元素，即则F称为独立系统，其元素称为独立集。在独立系统上定义的组合最优化问题，称为最优独立集问题。求最优支撑树、最优边无关集等问题，都是求最优独立集问题。又如，装箱问题：

求，满足条件

式中αij的值是0或1;变量x1，x2，…，xm取0或1， 也是求最优独立集问题。如果子集Ei是装箱问题的某个可行解中，取值为1的分量的指标所成之集合，那么所有这样的Ei构成了一个独立系统。

所谓拟阵，是指一个独立系统F满足下述的可扩充条件:对任意两个独立集I、I┡，若I┡中的元素个数大于I中的元素个数，则I┡中必存在一个不属于I的元素e，使将e加进I时，它仍是一个独立集。例如，在有限维的线性空间中，所有由线性独立的向量所构成的集合组成了一个拟阵。在一个图中，由不含圈的子图的边集所构成的子集簇，也是一个拟阵。许多组合问题可化成拟阵问题。

一种求拟阵的最优独立集的简单算法。先将E中的元素按权由大到小排出，去掉权为负数的元素之后，再依次考虑剩下的每一个元素。开始时取I*为空集，若将某一元素添入I*中，I*仍保持为独立集，则该元素就加入I*。否则，就抛弃该元素，依此考虑下一个元素，直到所有的元素考虑完毕为止。最后得到的子集I*就是拟阵的最优独立集。埃德蒙兹证明了一个重要的结果即对任何一个独立系统上的组合最优化问题，贪心算法能求得最优独立集的充分必要条件是该独立系统是一个拟阵。

用贪心算法求最大支撑树问题的步骤是，先将图中的边按权由大到小排列，开始时取I*为空集，依次考虑每一条边，若某一条边加入I*中所构成的子图不含圈，则将此边放入I*。否则舍去这个边。再考虑下一边，直到I*生成一个支撑树为止。I*就是一个最大支撑树。

设F1、F2是两个定义在集合E上的拟阵。若子集I是F1和F2的公共的独立集，则子集I称为F1和F2的一个交集。由所有的交集构成的独立系统，称为拟阵的交簇。

交簇上的组合最优化问题称为最优交问题。它的最优解称为最优交集。最优匹配问题是一个最简单的最优交问题。此外，如最短路、网络流等问题，都可归结为两个拟阵的最优交问题。

对给定的独立集I，不同元素的序列

称为关于I的交错链，如果它满足以下三个条件：

（1）p中所有的ei都属于I，所有的e媴都不属于I；

（2）对任意的指标i(i≤k)，在I中，用去替换e1，e2，…，ei后，I 仍保持为独立集；

（3）在I中，用去替换e1，e2，…，ek后，仍然是独立集，且多了一个元素。

交错链p的权定义为。权大于零的交错链称为增广链。使权达到最大值的增广链，称为最优增广链。

两个拟阵的最优交问题有以下基本结果。交集I*是最优交集的充分必要条件为：不存在关于I*的增广链。借助于最短路算法可求出关于I 的最优增广链。利用最优增广链，逐次改进交集，使之最终达到最优交集。这就是交错链算法。

对于组合最优化问题，由于子集簇F是有限的，可以用一一列举法来求它的最优解。但是，这种方法在实际上往往是不可行的。例如推销员问题，在有n个点的网络中，就有(n－1)!/2条路线可供选择。设n=20，那么即使以每秒可作1亿次算术运算的速度来选择最优路线，大约也要800年才能完成。因此，判定一个算法的好坏，主要的标准是运算次数。对同一类问题，规模愈大则所需运算次数也愈大。用n表示某一组合最优化问题的规模，例如元素的数目、图中的点数、初始数据写成二进制数码的长度等。对规模为 n的同一类型问题，也会由于具体的数据不同而计算量也不同。以给定的算法求解规模为n的某一问题时，用ƒ(n)表示在数据对算法影响最坏的情况下所需的运算次数。若ƒ(n)是n的多项式函数，则该算法称为多项式算法，也称为有效算法。贪心算法、最大流算法和交错链算法都是多项式算法。若ƒ（n）是指数函数，则该算法称为指数算法。一般认为，多项式算法是好算法，而指数算法是不好的算法。

凡能用多项式算法求解的问题，均称为P问题。上述问题中，除推销员问题和装箱问题外，都是P问题。一般地，凡是属于两个拟阵的最优交的问题，都是P问题。线性组合最优化问题，大都可以归结为线性整数规划问题，多面体组合理论，就是在利用线性规划对偶理论来处理这类问题时建立起来的。

在寻求多项式算法的过程中，S.A.库克和R.M.卡普首先发现，有一类问题，从求解的计算量的角度来看，有如下的共性。

（1）它们都还未找到多项式算法。

（2）若对其中的某一个问题存在多项式算法，则这一类中的所有问题也都有多项式算法，换言之，这些问题，关于多项式算法，是互相等价的。由这些问题所组成的等价类，称为 NP 完全类。P 问题和 NP 问题都是计算机科学中的基本概念。推销员问题、装箱问题以及求图的点无关数、色数等问题都属于 NP 完全类。已证明有成千的组合问题属于这一类。人们在求解 NP 完全类中的问题时，往往采用“启发式”方法，这类算法虽不能保证求得问题的最优解，但常常能求得较好的近似解，有时还能事先估计出误差范围。

参考书目

1. C.H.Papadimitriou and K.Steiglitz，Combinatorial Optimization: Algorithms and Complexity， Prentice-Hall， Englewood Cliffs，New Jersey，1982.
2. E.L.Lawler，Combinatorial Optimization:Networks and Matroids， Holt， Rinehart & Winston， New York，1976.