按需最优计算方法及其算法设计策略研究

□李晓亚

(中国科学院数学与系统科学研究院应用数学研究所，北京 100190)

最优化、人工智能、组合数学、逻辑以及其它领域中提出的许多最基本的离散计算问题，属于一类被称为NP难问题。我们既不知道这些问题的多项式时间算法，也不能证明这些问题不存在多项式时间算法。设计快速实时而又有效的算法策略的初衷，是为了提高解决这些实际问题的效率。其中大多数问题都是半结构化甚至是非结构化，因此要面临的一个主要障碍是，目前从理论上还没有一个广泛的通用的架构可以分析这类问题的复杂性本质。以我们通常面临的组合优化问题为例，其中绝大部分都是NP难问题，这类问题暂时无法找到多项式时间算法来求得其精确解。至今，理论工作者已经发现了成千上万个NP完全问题，但却没有对实际应用当中的解决方式给出一个系统的指导，而只是针对问题零散地设计各种近似算法、启发式算法等来求得问题的解。当问题规模很大时，直接求解其精确解是不可行的，那么应该采取怎样的算法或策略来求解这类NP难问题呢?

另一方面，考察问题的需求主要是以下几个方面:如果想要快速得到一个大规模问题的精确解，需要付出多大的代价呢?需要什么样的计算机资源呢?或者说，如果想要几分钟得到一个调度方案，那么能得到一个什么样的方案，即所得方案与最理想方案的近似程度或者精确程度最高能达到多少?在这类问题中，很多实例只有在最坏情况下或从理论层面看才是难解的，而实际中出现大部分情况都可用有效的算法求得较满意的解，并且问题实例的复杂程度与问题条件结构之间具有比较强的相关性。问题的结构越有序即不确定性越小，则问题计算难度越低;问题的结构越混乱即不确定性越大，则计算难度越高。而问题条件一旦确定，我们就可以按照决策者对计算时间和计算精度的需求匹配最佳算法，从而确定出至少需要什么样的计算资源。反过来，已知计算时间的需求和计算资源，从而确定能得到多高精度的解。决策者确定出解的近似度和已有的计算资源，从而确定至少需要多长时间求出符合该目标的解。［1，2］在以往的研究中，学者们或者注重于理论，希冀给出最优算法或证明近似算法的最坏情况;或者偏重于应用，通过模拟找到具有很好的实际效果的启发式算法。这两种思路各有所长，但也均有不足之处。在实际生活生产当中，很多问题往往不是靠单一类算法求解就能得到最满意的答案，目前也很少见到将理论与应用两种算法设计思路结合起来使用的例子。基于此，为了系统化地求解这类组合优化问题，我们首次提出按需最优计算方法，综合考虑可用的计算机资源、数据资源和模型资源的性能、问题实例的复杂程度，以及用户对计算时间以及计算精度的具体要求等参数因素，通过比较匹配，依策略选择精确算法、近似算法以及不同计算规模的启发式算法来对问题进行求解。

一、按需最优计算方法的提出

在当今竞争局势日益激烈、可用资源日益紧缺、信息知识不断膨胀的环境下，如何满足来自于外界以及内部的各种需求，实现高效管理、有效决策就显得意义重大。同时，人们对这类问题解决模式的需求巨大，并且一旦模式有效，由此产生的社会影响、科学影响也会是十分深远的。Holland在《隐秩序－适应性造就复杂性》书中，强调了在寻找支配复杂适应系统行为的一般原理中，数学扮演着一个非常重要的角色，并预言在复杂自适应系统的研究中，只有数学才能带我们走完全程。［3］Holland的预言是有依据的，因为复杂自适应系统(CAS)中面临的大量问题往往都是NP难或NP完全的，却要面对快速计算和高效决策之间的矛盾，也就是求解时间与求解精度之间的矛盾，要缓解这种矛盾，采用以往的通过建立数学模型库和方法库来实现决策支持功能的模式已经难以实现，这对科学界尤其是算法界提出了新的挑战。解决此类问题，由于其复杂性特点，通过某一方案是很难系统解决的，这就需要构建决策支持系统来辅助决策;并且，由于问题的不确定性，根据问题条件变化和决策者的需求变化，该系统需要具有设计个性化方案模式的功能;而由于问题本身开放性特点，随着时间变化和周围环境变化，具有动态演化的特点，因此所构建的决策支持系统要能实时自适应。基于这种更好地求解问题的需求，我们提出一种新的模式，即:按需最优计算方法，通过设计一种新的基于优化算法思想的决策模式，以期对客观世界中普遍具有开放性、不确定性和复杂性特点的热点问题进行深入探讨，以满足实时高效的决策需求。

按需最优计算算法设计的理论框架综合了“运筹学”、“按需计算”、“连续管理”、“复杂自适应系统”理论。在信息技术行业，“按需计算”指根据用户的需求，动态地提供相应的IT资源。这种按需服务具有两种特点:“动态”和“适量”。“动态”表示随时汲取，“适量”表示不会因买多了而产生不必要的浪费。复杂自适应系统理论是遗传算法之父Holland提出来的，其理念在于提出具有适应能力的、主动的个体，可以根据环境的变化改变自己的行为规则，以求生存和发展。这里的每一个独立的个体在系统中都在探索一种个体最优的策略，从系统整体的角度，如何设计竞争规则，使每个独立体的最优选择的结果“加和”，得到对整体优化更好的策略。这一思想与算法博弈论的主旨相似，算法博弈论的核心目标是为策略环境下的问题设计算法，将问题所研究系统的形成与运作视为一个博弈过程:由众多的寻求自身利益极大化的参与者通过相互作用实现。［4］

二、算法设计策略

具体来讲，目前已有的各种算法设计技术或策略涉及到启发式算法、分治策略、动态规划、近似算法、算法复杂性理论等，分为以下四类:1)基于贪心策略的启发式算法研究:一个算法是贪心的，如果它是通过一些小的步骤来建立一个解，在每一步根据局部情况选择一个决定使得某些主要的指标能得到优化。［5］由于在实际中常常面临的是大规模问题，设计的各种近似算法速度很可能达不到要求。Holland提出的遗传算法理论，［6］以及模拟退火算法，人工神经网络，禁忌搜索算法，演化算法，蚁群算法，量子算法等等，都是比较流行的启发式算法。启发式算法虽然并未有理论证明其与最优解之间的差异程度，但在工程应用中，很多时候要找到一个有效算法并严格地证明其近似程度，也是比较困难的，因此启发式算法在实践中被广为应用。［7］2)近似算法研究:组合优化中的绝大部分问题都是NP难问题。NP难问题的精确算法的计算时间复杂度常常是指数级别的，即求得问题精确解所花费的时间随着问题规模的增长而指数式增加。由于NP完全问题的难于求解性，一种可行而实用的策略是在有限或允许的时间内寻找问题尽可能好的近似解。近似算法可以快速有效地得出一个问题的次优解，且提供一个估计出计算结果与真正最优解之间的差异程度的数量表示，因此，在没有多项式算法的情况下，近似算法也是一种比较好的选择。近似算法是处理难解的组合优化问题的一个非常重要和有效的方法。它可以在多项式时间内求得问题的一个解，并使其目标函数值与最优解的目标函数值之比不超过一个常数。［8］3)动态规划算法研究:动态规划算法的基本思想是将问题分解为一系列子问题，通过一种类似于蛮力搜索的迭代过程得到子问题的最优解，然后通过重新解释这个过程，把它作为由建立越来越大的子问题的解而工作的迭代算法。［5］4)复杂性研究:应用数学面临的一个重大问题就是如何理解复杂性。传统的科学研究所采用的自上而下(Top－down)的方式并不总能解释自然界中的现象，取而代之的是自组织、自适应和涌现等新的复杂现象。［9］Feldman分析了动态系统是如何处理信息的，并引入无序性的概念，认为一个系统的复杂性体现在以下方面:组织，结构，记忆，规则，以及模式等。通过运用复杂熵的概念，利用信息论中的熵的概念来反映问题结构的无序程度，并分析仿真了其变化特征。［10］

针对NP难问题，传统方法的解决思路一般退而求其次采用设计一个近似算法求出近似解，或者设计一个启发式算法得出一个可行解，甚至也有给问题设计一些加强条件，即问题的一种特殊情形，并证明这种情形下的问题是一个P问题，然后针对该情形设计多项式算法求解。但是，如何系统化地求解这类NP难问题目前仍然没有学者给出思路。我们知道，在实际生活生产当中，很多问题往往不是笼统地靠单一算法求解就能得到满意的答案的。事实上，已经有许多不同的方法或技巧可以用来设计求解NP难问题，特别是某种形式的组合优化问题的不同性能、不同形式的算法，并且在求解NP难问题上已有的方法或思路已初步体现出按需最优计算方法的算法策略设计特点。一般而言，对于一类计算难度大的问题，我们通过寻找统一的启发式算法或近似算法来快速地求解其近似解。［11，12］但是，对于下列类型的问题情形也统一采用启发式算法或近似算法得到近似解是不合理的:一类是具有特殊结构，由多项式时间算法可求解得到精确解的问题情形;另一类是可以直接通过枚举快速得到最优解的小规模问题。Woeginger总结分析了一类超多项式算法的特点，并对不同的超多项式算法技术分类，较为全面地罗列了各种算法设计技术对应的可精确求解的NP难问题。［13］Papadimitriou等探讨了算法有效性设计与问题复杂性之间的关系，指出许多NP难问题未被求解不是因为问题是难的，而是因为人们还未找到合适的可以对它们进行求解的有效算法设计技术。［14］

基于以上分析调研，本文研究了利用按需最优计算方法来设计NP难问题的算法设计方法。其基本策略如下:给定一个NP难问题，通过某种复杂性规律来给出其复杂程度的量化表示，定义为复杂熵E。假设综合考虑了用户对精度的要求、用户对计算时间的要求、可用计算资源的性能等因素以后，得到用户可以承受的计算复杂熵的上界为Q。具体策略为1)若E=0，选择精确算法(枚举算法);2)若0＜E＜Q，建议选择枚举算法或者动态规划算法;3)若E ＞Q，建议选择启发式算法进行求解，也可设计近似算法对其进行求解。这里，按需最优计算体现在:当确定了问题实例的复杂程度以后，决策者或用户可选择最合适的算法，算法的选择取决于实例的复杂熵、计算机的性能、用户对精度以及计算时间的要求。

三、结论

按需最优计算方法旨在针对广泛的NP难问题，设计快速、实时的算法策略，根据用户的计算需求以及问题的复杂程度进行算法设计，满足需求与现实的最佳平衡。按需最优计算方法起源于应用，落足到理论，即考虑系统建模中的优化，又探索算法设计中的新方法，是搭建于理论与应用之间的桥，实现理论与应用的融合。

［1］李文林.数学:新的黄金时代［M］.上海:上海教育出版社，1997.

［2］王晓东.计算机算法设计与分析［M］.北京:电子工业出版社，2004.

［3］霍兰著，陈禹，方美琪，韩晖，周晓牧等译.隐秩序［M］.上海:上海科技教育出版社，2000.

［4］Noam Nisan，Tim Roughgarden，Eva Tardos，Vijay V.Vazirani.Algorithmic Game Theory［M］.Cambridge University press，2007.

［5］Jon Kleinberg，Eva Tardos著，张立昂，曲婉玲译.算法设计［M］.北京:清华大学出版社，2007.

［6］John H.Holland.Genetic Algorithm – Computer programs that“evolve”in ways that resemble natural selection can solve complex problems even their creators do not fully understand［J］.Scientific American，July:66－72，1992.

［7］越民义.组合优化导论［M］.杭州:浙江科学技术出版社，2001.

［8］堵丁柱，葛可一，胡晓东.近似算法的设计与分析［M］.北京:高等教育出版社，2011.

［9］李大潜等.2011－2020年我国数学学科发展战略研究［R］.2010.

［10］D P Feldman，C S McTague，J P Crutchfield.The organization of intrinsic computation:Complexity－entropy diagrams and the diversity of natural information processing［J］.Chaos，18(4)，2008:043106.

［11］C E Moustakas.Heuristic research:design，methodology，and applications［M］.Sage Publications，Inc，1990.

［12］D Pisinger，S Ropke.A general Heuristic for Vehicle Routing Problems［J］.Computers and Operations Research，34(8)，August:2403－2435，2007.

［13］G J Woeginger.Exact Algorithms for NP － Hard Problems:A survey［C］.Combinatorial Optimization(Edmonds Festschrift)，LNCS 2570:185 －207，2003.

［14］H R Lewis，C H Papadimitriou.The Efficiency of Algorithms［J］.Scientific American，238(1)，96－109，Jan 1978.