1.11 几点注记

    多项式算法有较好的“封闭性”，即几个多项式算法可以结合起来解同一个实例的某些特殊情形。一个多项式算法可以利用另一个多项式算法作为其“子程序”，并且最后的结果仍是一个多项式算法。

    经验表明，对于大多数问题而言，一旦找到了多项式算法，那么经过研究者的努力，很快就会发现新的多项式算法，对比两种算法实际所用的时间，从理论上讲相当于降低了多项式的阶数，并且常常可以降到3次甚至更低。相反，指数算法，如果有同次数的两个算法，还要讨论最高次数的系数的大小，以区别算法的优劣。而在比较多项式型和指数型的算法时，一般对多项式的次数不再细分。

    一旦找到了多项式算法，那么所论实例的一切指数型算法很快就会被抛弃。

    本书将讨论若干个多项式问题，但是不为追求阶数细微减小的算法而占用太多的篇幅。可能那些阶数更低的多项式算法的出现有其自身的理由，除非是另一个思路所得的产物，只是为了编写本书的初衷“去小知而大知明，汇众知以明其道”不顾及这方面的工作了。

    本书的目的在于把组合最优化这门数学分支的基础部分作一番整理，对有些概念、术语和方法给以明确的界定。有的和某些著作的见解不尽相同。

    第一点, 关于学科的定义：每门学科以及属于该学科的各种概念都有各自的定义。由于历史发展的阶段不同，人们认识事物的侧面不同，甚至个人的偏好不同，同一个学科或概念，有几种不同的定义是常见的事。选定其中的一个，有时相比于别的定义，会被认为有片面性。但是，这样做，比不加定义要好。

    本来我们已经有了组合数学的定义，例如，[孙 1] 中提到：“组合数学研究的对象泛称格局。所谓格局包括图、设计、算法过程、数学系统、工作程序等。” 因此也可以把组合最优化定义为研究、求解最优格局问题的学问。

    又有学者说：“组合最优化是通过对数学方法的研究去寻找离散事件的最优编排、分组、次序或筛选等。”

    更有学者说：“在组合（最优化）问题里，是从一个无限集或者可数无限集里寻找一个对象——典型地是一个整数，一个集合，一个排列，或者一个图。”

    [林 11]中讲得更为广阔而清楚：“亦称离散最优化（discrete optimization），它是组合数学（离散性数学）与最优化理论的交叉学科，研究对象是各种组合构形的最优化问题。所谓组合构形是指有限个事物的配置方式，包括集合选取、位置安排、连接结构、作业布局、资源分配以及排序、划分、装填、覆盖、染色等。概括地说，有一个基础集 表示事物之集和一个状态集 表示事物呈现的状态（如位置、颜色、标号）；一个组合构形就定义为从 到 的映射 表示每一个元素处于一个状态，构成一种配置方式。一种组合构形的优劣往往用它的某个参数 来衡量，如某种特定元素的个数或权重，或时间、长度、费用等性能指标。组合最优化问题的一般形式是求一个满足一定条件的组合构形 ，使其目标参数 达到最大（小）值。”

    它们都比定义1.1要宽得多。

    给一个学科下定义， 往往要求这个定义最好能够清楚地界定讨论的范围涵盖众多的、熟知的、公认应属于此的问题， 还要求理论研究和算法发现时，这个定义本身更易于操作， 更具有一定的构造性。

    像组合最优化，其诞生不久，正处于发展阶段，今日选择了一个定义， 只是立此照存， 便于探讨问题。将来随着出现众多新的题目，积累大量新的研究和应用成果，产生了新的思路，会产生新的定义。这该是科学发展中正常规律的事。《礼记》有一句话：“止，而后能观”。确定定义是研究学问的一种科学方法。

    我们之所以宁愿采用定义 1.1 作为编写本书的一个出发点，一是许多著名学者采用这个定义，二是定义具有有限性、可操作性和子集型，它和几个子集型最优化原理能够配伍，开展工作。当然这样的定义与上述学者的定义相比要狭窄得多，譬如例 1.7 的 Steiner 树问题就不在本书范围之内。

    第二点, 关于求解题目的工具问题：组合最优化问题的一个数字例，如果它的规模很小，往往仅靠纸上笔算，无须理论也能得到答案。大量的生产实际任务，归结为某个问题的实例，其规模往往是巨大的，而理论的研究更是注意一般性，也是以大规模为前提的。如何合理组织有关数据，更易于获得题目的理论和答案，发现新的推理和计算工具是有积极意义的。一般而言，有两个方面：一种是或者从数学宝库中发现合用的工具，或者发现崭新的数学系统；另一种是有效地编制各种程序，甚至软件包，让计算机进行计算。

    第三点, 关于术语的使用：人们常常把某些生活和工程名词转化为自己学科的专业术语，给出明确的定义，有时甚至和本学科的有些论著也不一致。例如，问题、方法和算法等；又如，树、路等。但是，在一般讨论或行文时又很难进一步严格区分。请读者注意上下文和严格的定义，以区分它们的实际意义。

科学成就的重要性往往并不只是表现为在已有的材料上添加新东西，对于科学的进步来说，使已有的但是烦难的研究领域条理化、简单化和明确化，这样一种探讨绝不是次要的。通过这样的探讨，有助于（或至少有可能）从整体上来观察、理解和把握这门科学……即在解决新问题的同时寻求使老问题化难为易的方法，在已有的材料之间建立新的联系，同时使许多个别研究的分散支流汇入一条统一的河道。
– 库朗《希尔伯特》

引用国内学者文献

[孙 1] 温一慧，孙述寰。组合数学 [M]。兰州: 甘肃文化出版社，1994

[林 11] 林诒勋。条目 “组合最优化”- 《中国百科全书》编委会，中国大百科全书 数学卷，2版。 北京: 中国大百科全书出版社，2009