□李曉亞

(中國科學院數(shù)學與系統(tǒng)科學研究院應用數(shù)學研究所，北京 100190)

最優(yōu)化、人工智能、組合數(shù)學、邏輯以及其它領域中提出的許多最基本的離散計算問題，屬于一類被稱為NP難問題。我們既不知道這些問題的多項式時間算法，也不能證明這些問題不存在多項式時間算法。設計快速實時而又有效的算法策略的初衷，是為了提高解決這些實際問題的效率。其中大多數(shù)問題都是半結構化甚至是非結構化，因此要面臨的一個主要障礙是，目前從理論上還沒有一個廣泛的通用的架構可以分析這類問題的復雜性本質(zhì)。以我們通常面臨的組合優(yōu)化問題為例，其中絕大部分都是NP難問題，這類問題暫時無法找到多項式時間算法來求得其精確解。至今，理論工作者已經(jīng)發(fā)現(xiàn)了成千上萬個NP完全問題，但卻沒有對實際應用當中的解決方式給出一個系統(tǒng)的指導，而只是針對問題零散地設計各種近似算法、啟發(fā)式算法等來求得問題的解。當問題規(guī)模很大時，直接求解其精確解是不可行的，那么應該采取怎樣的算法或策略來求解這類NP難問題呢?

另一方面，考察問題的需求主要是以下幾個方面:如果想要快速得到一個大規(guī)模問題的精確解，需要付出多大的代價呢?需要什么樣的計算機資源呢?或者說，如果想要幾分鐘得到一個調(diào)度方案，那么能得到一個什么樣的方案，即所得方案與最理想方案的近似程度或者精確程度最高能達到多少?在這類問題中，很多實例只有在最壞情況下或從理論層面看才是難解的，而實際中出現(xiàn)大部分情況都可用有效的算法求得較滿意的解，并且問題實例的復雜程度與問題條件結構之間具有比較強的相關性。問題的結構越有序即不確定性越小，則問題計算難度越低;問題的結構越混亂即不確定性越大，則計算難度越高。而問題條件一旦確定，我們就可以按照決策者對計算時間和計算精度的需求匹配最佳算法，從而確定出至少需要什么樣的計算資源。反過來，已知計算時間的需求和計算資源，從而確定能得到多高精度的解。決策者確定出解的近似度和已有的計算資源，從而確定至少需要多長時間求出符合該目標的解。［1，2］在以往的研究中，學者們或者注重于理論，希冀給出最優(yōu)算法或證明近似算法的最壞情況;或者偏重于應用，通過模擬找到具有很好的實際效果的啟發(fā)式算法。這兩種思路各有所長，但也均有不足之處。在實際生活生產(chǎn)當中，很多問題往往不是靠單一類算法求解就能得到最滿意的答案，目前也很少見到將理論與應用兩種算法設計思路結合起來使用的例子?；诖?，為了系統(tǒng)化地求解這類組合優(yōu)化問題，我們首次提出按需最優(yōu)計算方法，綜合考慮可用的計算機資源、數(shù)據(jù)資源和模型資源的性能、問題實例的復雜程度，以及用戶對計算時間以及計算精度的具體要求等參數(shù)因素，通過比較匹配，依策略選擇精確算法、近似算法以及不同計算規(guī)模的啟發(fā)式算法來對問題進行求解。

一、按需最優(yōu)計算方法的提出

在當今競爭局勢日益激烈、可用資源日益緊缺、信息知識不斷膨脹的環(huán)境下，如何滿足來自于外界以及內(nèi)部的各種需求，實現(xiàn)高效管理、有效決策就顯得意義重大。同時，人們對這類問題解決模式的需求巨大，并且一旦模式有效，由此產(chǎn)生的社會影響、科學影響也會是十分深遠的。Holland在《隱秩序－適應性造就復雜性》書中，強調(diào)了在尋找支配復雜適應系統(tǒng)行為的一般原理中，數(shù)學扮演著一個非常重要的角色，并預言在復雜自適應系統(tǒng)的研究中，只有數(shù)學才能帶我們走完全程。［3］Holland的預言是有依據(jù)的，因為復雜自適應系統(tǒng)(CAS)中面臨的大量問題往往都是NP難或NP完全的，卻要面對快速計算和高效決策之間的矛盾，也就是求解時間與求解精度之間的矛盾，要緩解這種矛盾，采用以往的通過建立數(shù)學模型庫和方法庫來實現(xiàn)決策支持功能的模式已經(jīng)難以實現(xiàn)，這對科學界尤其是算法界提出了新的挑戰(zhàn)。解決此類問題，由于其復雜性特點，通過某一方案是很難系統(tǒng)解決的，這就需要構建決策支持系統(tǒng)來輔助決策;并且，由于問題的不確定性，根據(jù)問題條件變化和決策者的需求變化，該系統(tǒng)需要具有設計個性化方案模式的功能;而由于問題本身開放性特點，隨著時間變化和周圍環(huán)境變化，具有動態(tài)演化的特點，因此所構建的決策支持系統(tǒng)要能實時自適應。基于這種更好地求解問題的需求，我們提出一種新的模式，即:按需最優(yōu)計算方法，通過設計一種新的基于優(yōu)化算法思想的決策模式，以期對客觀世界中普遍具有開放性、不確定性和復雜性特點的熱點問題進行深入探討，以滿足實時高效的決策需求。

按需最優(yōu)計算算法設計的理論框架綜合了“運籌學”、“按需計算”、“連續(xù)管理”、“復雜自適應系統(tǒng)”理論。在信息技術行業(yè)，“按需計算”指根據(jù)用戶的需求，動態(tài)地提供相應的IT資源。這種按需服務具有兩種特點:“動態(tài)”和“適量”。“動態(tài)”表示隨時汲取，“適量”表示不會因買多了而產(chǎn)生不必要的浪費。復雜自適應系統(tǒng)理論是遺傳算法之父Holland提出來的，其理念在于提出具有適應能力的、主動的個體，可以根據(jù)環(huán)境的變化改變自己的行為規(guī)則，以求生存和發(fā)展。這里的每一個獨立的個體在系統(tǒng)中都在探索一種個體最優(yōu)的策略，從系統(tǒng)整體的角度，如何設計競爭規(guī)則，使每個獨立體的最優(yōu)選擇的結果“加和”，得到對整體優(yōu)化更好的策略。這一思想與算法博弈論的主旨相似，算法博弈論的核心目標是為策略環(huán)境下的問題設計算法，將問題所研究系統(tǒng)的形成與運作視為一個博弈過程:由眾多的尋求自身利益極大化的參與者通過相互作用實現(xiàn)。［4］

二、算法設計策略

具體來講，目前已有的各種算法設計技術或策略涉及到啟發(fā)式算法、分治策略、動態(tài)規(guī)劃、近似算法、算法復雜性理論等，分為以下四類:1)基于貪心策略的啟發(fā)式算法研究:一個算法是貪心的，如果它是通過一些小的步驟來建立一個解，在每一步根據(jù)局部情況選擇一個決定使得某些主要的指標能得到優(yōu)化。［5］由于在實際中常常面臨的是大規(guī)模問題，設計的各種近似算法速度很可能達不到要求。Holland提出的遺傳算法理論，［6］以及模擬退火算法，人工神經(jīng)網(wǎng)絡，禁忌搜索算法，演化算法，蟻群算法，量子算法等等，都是比較流行的啟發(fā)式算法。啟發(fā)式算法雖然并未有理論證明其與最優(yōu)解之間的差異程度，但在工程應用中，很多時候要找到一個有效算法并嚴格地證明其近似程度，也是比較困難的，因此啟發(fā)式算法在實踐中被廣為應用。［7］2)近似算法研究:組合優(yōu)化中的絕大部分問題都是NP難問題。NP難問題的精確算法的計算時間復雜度常常是指數(shù)級別的，即求得問題精確解所花費的時間隨著問題規(guī)模的增長而指數(shù)式增加。由于NP完全問題的難于求解性，一種可行而實用的策略是在有限或允許的時間內(nèi)尋找問題盡可能好的近似解。近似算法可以快速有效地得出一個問題的次優(yōu)解，且提供一個估計出計算結果與真正最優(yōu)解之間的差異程度的數(shù)量表示，因此，在沒有多項式算法的情況下，近似算法也是一種比較好的選擇。近似算法是處理難解的組合優(yōu)化問題的一個非常重要和有效的方法。它可以在多項式時間內(nèi)求得問題的一個解，并使其目標函數(shù)值與最優(yōu)解的目標函數(shù)值之比不超過一個常數(shù)。［8］3)動態(tài)規(guī)劃算法研究:動態(tài)規(guī)劃算法的基本思想是將問題分解為一系列子問題，通過一種類似于蠻力搜索的迭代過程得到子問題的最優(yōu)解，然后通過重新解釋這個過程，把它作為由建立越來越大的子問題的解而工作的迭代算法。［5］4)復雜性研究:應用數(shù)學面臨的一個重大問題就是如何理解復雜性。傳統(tǒng)的科學研究所采用的自上而下(Top－down)的方式并不總能解釋自然界中的現(xiàn)象，取而代之的是自組織、自適應和涌現(xiàn)等新的復雜現(xiàn)象。［9］Feldman分析了動態(tài)系統(tǒng)是如何處理信息的，并引入無序性的概念，認為一個系統(tǒng)的復雜性體現(xiàn)在以下方面:組織，結構，記憶，規(guī)則，以及模式等。通過運用復雜熵的概念，利用信息論中的熵的概念來反映問題結構的無序程度，并分析仿真了其變化特征。［10］

針對NP難問題，傳統(tǒng)方法的解決思路一般退而求其次采用設計一個近似算法求出近似解，或者設計一個啟發(fā)式算法得出一個可行解，甚至也有給問題設計一些加強條件，即問題的一種特殊情形，并證明這種情形下的問題是一個P問題，然后針對該情形設計多項式算法求解。但是，如何系統(tǒng)化地求解這類NP難問題目前仍然沒有學者給出思路。我們知道，在實際生活生產(chǎn)當中，很多問題往往不是籠統(tǒng)地靠單一算法求解就能得到滿意的答案的。事實上，已經(jīng)有許多不同的方法或技巧可以用來設計求解NP難問題，特別是某種形式的組合優(yōu)化問題的不同性能、不同形式的算法，并且在求解NP難問題上已有的方法或思路已初步體現(xiàn)出按需最優(yōu)計算方法的算法策略設計特點。一般而言，對于一類計算難度大的問題，我們通過尋找統(tǒng)一的啟發(fā)式算法或近似算法來快速地求解其近似解。［11，12］但是，對于下列類型的問題情形也統(tǒng)一采用啟發(fā)式算法或近似算法得到近似解是不合理的:一類是具有特殊結構，由多項式時間算法可求解得到精確解的問題情形;另一類是可以直接通過枚舉快速得到最優(yōu)解的小規(guī)模問題。Woeginger總結分析了一類超多項式算法的特點，并對不同的超多項式算法技術分類，較為全面地羅列了各種算法設計技術對應的可精確求解的NP難問題。［13］Papadimitriou等探討了算法有效性設計與問題復雜性之間的關系，指出許多NP難問題未被求解不是因為問題是難的，而是因為人們還未找到合適的可以對它們進行求解的有效算法設計技術。［14］

基于以上分析調(diào)研，本文研究了利用按需最優(yōu)計算方法來設計NP難問題的算法設計方法。其基本策略如下:給定一個NP難問題，通過某種復雜性規(guī)律來給出其復雜程度的量化表示，定義為復雜熵E。假設綜合考慮了用戶對精度的要求、用戶對計算時間的要求、可用計算資源的性能等因素以后，得到用戶可以承受的計算復雜熵的上界為Q。具體策略為1)若E=0，選擇精確算法(枚舉算法);2)若0＜E＜Q，建議選擇枚舉算法或者動態(tài)規(guī)劃算法;3)若E ＞Q，建議選擇啟發(fā)式算法進行求解，也可設計近似算法對其進行求解。這里，按需最優(yōu)計算體現(xiàn)在:當確定了問題實例的復雜程度以后，決策者或用戶可選擇最合適的算法，算法的選擇取決于實例的復雜熵、計算機的性能、用戶對精度以及計算時間的要求。

三、結論

按需最優(yōu)計算方法旨在針對廣泛的NP難問題，設計快速、實時的算法策略，根據(jù)用戶的計算需求以及問題的復雜程度進行算法設計，滿足需求與現(xiàn)實的最佳平衡。按需最優(yōu)計算方法起源于應用，落足到理論，即考慮系統(tǒng)建模中的優(yōu)化，又探索算法設計中的新方法，是搭建于理論與應用之間的橋，實現(xiàn)理論與應用的融合。

［1］李文林.數(shù)學:新的黃金時代［M］.上海:上海教育出版社，1997.

［2］王曉東.計算機算法設計與分析［M］.北京:電子工業(yè)出版社，2004.

［3］霍蘭著，陳禹，方美琪，韓暉，周曉牧等譯.隱秩序［M］.上海:上?？萍冀逃霭嫔纾?000.

［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］越民義.組合優(yōu)化導論［M］.杭州:浙江科學技術出版社，2001.

［8］堵丁柱，葛可一，胡曉東.近似算法的設計與分析［M］.北京:高等教育出版社，2011.

［9］李大潛等.2011－2020年我國數(shù)學學科發(fā)展戰(zhàn)略研究［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.