数 学 杂 志 (J. of Math. PRC)
Vol.14(1994) No. 3. Page 436-444
收稿日期：1993-01-08

摘要 用 -集合表示具有规定性质的集合。-对象是指具有规定结构的-集合。 -集合本身是具有空结构的-对象。

组合最优化的问题是指: 对于每一个-集合,从其诸-对象中找出-优者。 以最小生成林问题、平面凸壳问题及整序问题（§§2-5）为实践背景,对于问题XYZ的一个实例, 把集合 的-子集合的全体记作簇 , 把这些子集合的-优-对象的全体记作簇 , 把实例 的-对象(可行解)的全体记作。

当问题 是第一类优化问题，规定 则以及是两个具有单位元素构成的带（band）。 把三个簇, 与合在一起，记作，叫做实例的解带（solution band）， 问题 的所有实例 的解带构成这问题的解带簇。

从 到 ，算子 是一个同态映射，当 -对象是空结构时，不但有 而且算子 还是一个投影算子。

利用解带的几何直观，探索实例的精确解，有三种求解思路：添元章法、同解章法与枚举章法。

关键词 第一类优化问题；解带；投影；三种求解章法

组合优化是研究有限集合上各种优化问题的学问。

用 -集合表示具有规定性质 的集合。-对象是指 具有规定结构的 -集合。如把若干个实数排成非减序列就是这实数集合的一种结构。-集合本身是具有空结构的 -对象。

组合优化中的任一问题写作问题 。

定义 1 问题 是指：对于每一个 -集合，从其诸 -对象中找出 -优解。

在一个具体的 集合 中寻找它的 优 对象 的任务叫做问题 的 一个实例 。 叫做集合 (关于问题 )的优化对象、优化解或解。当是空结构时，还叫做优化集合。

能够用以解决每一个实例的、具有准确步骤的方法叫做问题 的一个算法。

对于空结构的 -对象，定义 与组合最优化的定义 (马仲蕃 1988) 相一致。 因此，组合优化包括组合最优化。它还包括计算机科学、计算几何、排序论等等的许多问题。

组合优化的理论研究的中心内容是解问题，包括发现算法、研究问题之间、算法之间以及问题与算法之间的各种关系。

系列文章《论优化问题的公理方法（I）一（V）》(秦裕瑗 1993)讨论了这方面的问题。本系列文章作进一步的探讨， 尤其着重探求所谓的算法的算法，即对于某些问题类，寻求系统的、统一的程序，以发现求解某具体问题的种种方法。

本文将讨论：组合优化的基本特征（§1），从三个具体问题（§§2—5，最小生成林问题、平面凸壳问题与整序问题），引申出解带（solution band）概念（§6）。 从几何直观，提出从 到 的投影概念。导出了求解第一类组合优化问题的三种方法：添元章法、同解章法与枚举章法。 最后，提出一个设想，能否用篇法、章法、法与算法四个层次来系统地整理、概括并发展某些熟知的算法。

基本概念

直接从问题 的定义出发，考察它的实例 的特征。

把 -对象叫做实例 的可行解，其全体叫做可行域，记作 。把每一个可行解看作一个点， 是一个集合，把每一个可行解看作是对象，则 是一个族。

可行解 有一个 值，它常常通过目标函数 算得一个实数值，设 。 那些在集合 上的最优的可行解的全体记作 ，叫做 的优化集合，于是 在条件 规定了 opt 是指取最大或最小，显然有：

：集合 有唯一的子集合 与之对应，写 ： 非空当且仅当 非空。

优化集合 的每一个元素 是 的一个优化解。若 ，还有 。

设目标函数的构成与集合 无关，即无论可行解 在那一个集合 中， 目标函数值 不变，例如 是赋权图中某个边子集合， 是 的基数，或 的诸边的权之和。 确实有不少优化问题的目标函数是随 而改变的，不过本系列文章将不涉及后一种情形。

把 作为整体，它的非空子集合 作为局部，有一个简明直观的经验之谈：

• 整体的最优解在局部也最优。

这是说，若 ，则 。 其实，还有 。因为当 ，竟然有 ，应有： 从而 。矛盾。

把这事实叙述为

最优化原理 若整体有若干个最优解在局部之中，则它们是局部所仅有的最优解。

用符号表述为

最优化原理 设 ，且 。若 ，则 。

由这原理，即得(秦裕瑗 1993)：

定理 1（） 若 ，则 。

定理 2（）

定理 3

推论）

定理 4 成立的充要条件为 与 成立。

以上是对实例的可行解集合的情形讨论的。

像(秦裕瑗 1993)中所述，有不少组合优化问题，其实例具有如下性质：

(i) 对于问题 的实例 ，集合 的 -子集合 也能构成一个实例 。

(ii) 集合 及它的 -子集合 总有其唯一的子集合作为它的优化集合，分别记作 或 。

(iii) 非空当且仅当 非空。

若 ，则 。

。

因此，这类优化问题，同样有 ， 与 。

性质 (ii) 有一定的局限性，若优化解 总是唯一的，则说涉及目标函数的参数是规范的。 规范化是一种技术，它能在改变有关参数的值或标记方法之后，使优化解唯一，且这个优化解相当于未改变之前的诸优化解中的一个。 许多优化问题都是能够规范化的。

在讨论-对象时，补充规定：

(iv) 之间进行交、并、补、差等运算时，结果首先是一个集合。如果结果具有明确规定的结构，才具有结构的意义。

例如 都是集合， 则具有结构的意义。

为了统一地讨论这些问题，我们作

定义 2 设 是含有有限个元素的论域，由集合 构成的 -子集合的全集记作 :

: ;

: 若 ，对于任意 ，有 ；

: ，则 ，
则说 是一个 -簇。

定义 3 在 -簇上，算子 满足条件：

公理 1（） 有唯一的（-对象） 与之对应。

公理 2（） 非空当且仅当 非空。

公理 3（）
则说是簇上的第一类优化算子。

定义 4 对于问题的每一个实例，我们把集合的-子集合的全体作为簇， 以及把-对象(可行解)的全体作为簇。 若能把求解实例的任务与簇或集合上的第一类优化算子相对应，则说问题是第一类优化问题。 还把前者说作子集合型的，后者是可行解型的。

当目标函数与可行域所选子集合无关，问题总是可行解型第一类优化问题。

下面讨论三个第一类优化问题。

最小生成林问题的一个提法

最小生成树问题，即问题，是熟知的。它的实例 有赋权连通图 ， 边的权记作 。

首先，最小生成树一般并不唯一，但把权相等的那些边 用三元组作为权， 并以字典序排序，权就规范化了，解是唯一的。

第二，设-图 是赋规范权的简单图，它的连通分枝数为。我们建议，不讨论问题， 而讨论，即最小生成林 (minimum spanning forest) 问题，这是指，实例的-图中， 在诸-生成林中，寻找权和最小者，记作。当然若=1，两个问题一致。 这样解，可以更方便地讨论问题：一个简单图的一个生成子图总有它的， 而连通图的一个生成子图不一定有。

第三，如果给定的图本身就是一个林，那末的-MSF，即，就是本身，即。

现在把问题写成如下形式：实例有-图

: 是简单图，连通分枝数为，

: 边集合 赋有规范权，
在诸 -子图，

: 每一个都是 的 -生成林
中，求-优者:

: 生成林的值等于林的诸边的权之和，

: 值以小为优。
求得的 叫做的最小生成林。

问题 (以及问题 ) 是可行解型第一类优化问题。

对于赋规范权简单图 的一个生成子图 ，如果含有圈，则圈的权最大的诸边中，按 字典序最后一条应予删去，从而不属，即对于，有 于是成立。所以，问题 也是子集合型第一类优化问题。

最小生成林问题的解

对于问题的实例，有三个特征。首先，它是图的一个生成子图，其次，它是一个生成林； 第三，它的连通分枝数等于。因此，涉及到三个图簇，一是图的生成子图的全体，记作簇 ； 二是 中的生成林的全体，即那些满足条件的图，记作簇 ； 第三是是簇 中-生成林的全体，记作簇 。显然有

簇 含有个生成子图。以子图所含边数为参数，被分成层， 最高层是第层，只有一个元素，就是图。而空图 在最底层，是第0层。根据-生成林的特征， 中每一个图都含有条边。所以它们都在第层，所求的解 就在这一层里。

关于子图间的并运算，如果，定义，则是一个带(band)， 即是一个具有零元素的交换半群，且是-幂等的(即 )。

关于子图间的包含关系，是半序的，称为半序集合 。

从不同的观点考察同一个，可以设簇，集合，半序集合 以及带等等。

簇中的最小元为空图 ，在第0层，而最大元 在的最高层。

关于并运算，不是带的一个子带。然而，对于，我们定义 不难证明，集合是一个带。

簇中每一个元素是赋规范范数的简单图。它唯一地对应中的元素，一个 。而图当然属于。它的(即 )就是本 身，即。这表明，算子具有投影的特征。

因为当，总有 。所以中每一个元素在 带中有相同的投影，即有相同的-最小生成林， 从而集可利用进行划分。

总之，对于问题的实例，图 有带和带， 算子是从 到的一个同态映射： 不仅如此，还是一个投影算子。

平面凸壳问题

凸壳问题是离散型计算几何的中心问题之一，它不仅有广泛的实际应用，也是求解许多表面上互不相关的问题的一个有力工具。

仅是为了达到我们的目的，限于讨论平面凸壳(planar convex hull)问题，即问题。这是指， 求包含平面有限点集的最小凸多边形，叫做凸壳。等价地，在点集合中找出这样的凸子集合 (即以其作为顶点集合能围成一个(闭)凸多边形域)，含有所给的点集合。凸壳是唯一的。

问题的实例可以写成下面形式：设有-集合；

: 是平面点集合，

: 是有限的，
在诸 -子集合

: 是凸集合，
中，求-优者:

: 由-凸集合 围成的凸多边形域记作，规定的值为

：值以小为优。
求得的 叫做的凸壳。

对于点集合，它的子集合的全体记作簇 ，那些凸子集合的全体记作簇 ，而的所有可行解， 即凸集合，记作，显然有

，是一个带， 也是一个带，其中 算子在 与 之间是一个同态映射。

因为 的凸壳为 ，集合 的凸壳就是 本身。因此， 是带 中的 在带 中的投影， 是一个投影像子。

问题显然是可行解型第一类优化问题。它还是子集合型第一类优化问题。因为， 当时，属于的点不会属于，所以有 。

排序问题

排序(sorting)问题同题 ，是指：把有限互异整数排成递增序列。

这是计算科学中应用最广、研究最深的问题之一。

把整数集合排成一个序列，记作【】或 【】。采用符号【 】，以便参加加运算。若是递增的，于 是

例如

问题 的实例 可以写成下面形式：设有 -集合

: 诸元素 为互异整数。

: 为有限。
在诸 -对象

: 它的元素不重复地取尽 ，

: 结构是排成一个序列，
中，求 -优者；

: 序列【】 的目标函数值为

: 值以大者为优，
求得的 【 】 叫做 的整序。

所以，问题 是一个组合优化问题。

把集合 的子集合全体记作簇 ，对于 ，有唯一的整序 (递增序列) 。 这种整序的全体记作簇 ，集合 的所有排列（可行解）记作簇 。

问题 显然是 (上)可行解型的第一类优化问题。它还是子集合型的第一类优化问题。 因为 有唯一的整序 ， 是指两个递增序列 , 合并成一个递增序列，显然有

与 是两个带。 算子 在它们之间是一个同态映射，但是 与 之间没有包含关系，也没有投影概念。

优化问题的解答与求解的三个算法

以上述的三个问题为实践背景，来讨论一般性问题。

设有问题 的一个实例 ，对于集合 ，-集合的全体记作簇 。 -对象的全体记作簇 。的可行解的全体记作簇 。总有

对于(子集合型 \可行解型)第一类优化问题， 与 是两个带。 算子 是从 到 的一个同态映射：

对于非空结构 -对象 (例如整序问题)， 与 之间没有包含关系。对于空结构 -对象 (如最小生成林问题与平面凸壳问题)，则有 这时，同态映射 还是一种投影，即 的解 是带 中的元素 在带 中的投影。因为有。

无论 -对象的结构是否非空，把三个簇与合并， 记作 。叫做实例 的解带 (solution band)。

问题 的每一个实例有一个解带，所有实例的解带构成问题 的解带簇。

求解实例 ，即求出 ，是我们目的。解带的几何直观性提供了几个求解的思路，称为章法。

第一种算法是在带 中如何从确定的、已知的空集合 出发找出 。在(秦裕瑗 1993)的文 (II)等中已讨论过：若，记作 则 利用公式右端，有多种方法来求解 。所有这些统称为添元章法，最基本的一种是生成法：作 于是 及 针对§§2-5的三个问题，对于集合（依次当作赋规范权简单图/平面有限点集合/有限互异整数集合）， 作出含有个元素的子集合 （生成子图/点子集合/数的集合）的优的 的-对象(-/凸壳/递增数列)， 于是 是所求的优化解（的凸壳/的递增数列）。 具体化到这三个问题，得到相应的生成算法。

对于问题 的实例 ，如果把诸边按其权的递增性先排成一列。再用生成法，得到一种改进，是熟知的 Kruskal 算法（1936）。

把的右端两两相加，而得分治法，也不难应用来求解上述三个问题。

第二种算法是从确定的、已知的集合 出发。沿着什么途径到达 。 第一种仅限在带之中，这时 只能是空结构。

簇 是带 的一个子带， 只是它的零元素是 。这时，即簇 中每一个集合 都与 有同解。

一种求解 的方法是在簇 中设计一个序列 其中

问题 与 的破圈法 (管梅谷，1975)，问题 的 Hadwiger-Debrunner算法 (1984) 都属于这一类。

对于问题 的一个实例 ，除了 之外，还可能有众多的实例与实例 有相同的解 。 把所有这种实例记作 ，叫做实例 的同解实例簇。 实例 与实例 都在其中。于是可以像那样， 在 内设计出求解方法。这时无需有与/或。 这两种方法统称为同解章法，在(秦裕瑗 1993)中已经作了初步讨论。几种叠代法以及离散型动态规划方法都属于此。

第三种是在可行解集合 中找出优化解 ，即求解 求解的基本方法是枚举，以及由之发展起来的隐枚举法、分枝定界法，规划论法、凸多面体法以及本系列文章将介绍的对称差（的）分解法等等， 这里统称为枚举章法。

以上讲的三种章法都是求精确解的，统称为精确篇法。

写一本内容丰富的书，总纲之下，分篇、章、节、段、句，以示层次，并以节为基本单位。 组合优化涉及面很广，有众多的求解方法。为了表达这些方法清楚些，有必要在总纲之下，也分层别类。 我们建议，分四个层次；篇法，章法、法和算法，而以法作为基本单位。 对于第一类优化问题的求解方法，至少有四个篇法。精确篇法、近似篇法、启发篇法和随机篇法。 在精确篇法下，至少有三个章法：添元章法、同解章法和枚举章法。 添元章法又有生成法、分治法、层次法等等。 一个具体的优化问题，它本身有其具体的术语，概念与表达形式，有其特征（如平面性、欧氏距离、非负性等）， 还有相应的计算方法，数据结构的成果等。 借助所有这些，把上面讲的篇法、章法与法应用过来而得到的方法以及其改进，统称为求解这问题的算法。

本系列文章中，把篇法、章法、法与算法作为专门术语，而把方法、解法这两个词作为一般名词。 让它们带有某些含糊之处，便于行文。至于问题这个词既是专门的又是一般的。

事情发展到某种程度以后，人们也许有一天手边开始有一个不断需要完善的“提纲”。 用它来帮助人们判断一个崭新的组合优化问题属于那一类。 果然在“提纲”之内，人们就可以按部就班地探求各种算法。 还用它来帮助人们整理熟知的问题的许多算法。 “提纲”可收到纲举目张的效果，“提纲”成了“算法的算法”。这也许是一个梦思，却是值得追求的。

致谢 1993年5月作者访问新疆大学与兰州大学教学系，与张福基、郭韦琦两教授讨论过程中得到启发， 从而建立了解带和投影这两个概念，引发了这篇文章，特此致谢。