-
多項式算法
鎖定
多項式算法(polynomial algorithm)亦稱有效算法或好算法，是一類計算時間不超過始數據量的一個多項式的算法，算法滿足以下的條件：存在多項式P，使算法的時間複雜性函數f(n)=O(P(n))，這裏n為問題的輸入規模，換言之，有常量C及多項式P，使|f(n)|≤C|P(n)|。對算法的這種度量，具有如下特點：1.刻畫了算法的內在性質，換言之，若算法是多項式算法，當用來求解該類問題時，對問題P1，P2，雖説相應的輸入規模n1，n2不同，相應的多項式P′(n1)，P″(n2)不同，但是P′和P″均都是多項式，因此，不會因為面對的具體問題不同，而影響對算法這種性質的刻畫；2.漸近性特點，也就是説，當輸入規模n增大時，多項式算法的計算時間要比時間複雜性函數為指數函數情形少得多；3.在實際上，多項式算法並不肯定奏效，如P(n)=n1000，當11000>2n，其中，t=1000logn，其中log為以2為底的對數
[1]
。
- 中文名
- 多項式算法
- 外文名
- polynomial algorithm
- 所屬學科
- 數學
- 別 名
- 有效算法或好算法
多項式算法基本介紹
多項式算法是判斷一個算法“好壞”的 數學概念。當考察解某一類問題(如線性規劃問題)的一種算法時，在計算機上利用這一 算法解這類問題中的每個具體問題所需的計算次數(時間)是不同的。計算步數(時間)一般與具體問題的規模(如線性規劃問題中變量的個數，約束條件的個數等)有關。為了判 斷一個具體問題規模的大小，往往把此問題 需要輸入計算機的有關數據轉化為一個二進制的代碼序列(即只含0或1組成的序列)。 這個序列中所含0或1的個數L就稱為這一具體問題的輸入長度，並用L來代表此問題的規模大小。
如果解某類問題的一個算法，在解規模為L的具體問題時，其計算步數在最壞的情形下不超過L的一個多項式P(L)，則稱這一 算法為多項式算法(或好算法)。
顯然，在實踐中具有多項式算法的問題才能有效地用計算機計算，因為當問題的規模增大時，所需的計算時間增大的速度還不很大。所以，多項式算法的概念給出了理論上可計算與實際可計算的問題的區別。同時，對某類問題的已知算法，來研究它是否是多項式算法，也具有重要的理論意義和實際意義。
例如，在考察解線性規劃的算法時，克里和明特構造了一個具體的線性規劃問題，説明單純形法不是一個多項式算法。那麼，線性規劃問題是否存在多項式算法呢?這一問題首先於1979年由蘇聯的哈奇揚解決。哈奇揚證明了他所提出的橢球算法是一個多項式算法。隨後，在美國工作的印度數學家卡馬卡於1984年又提出了求解線性規劃的另一個多項式算法
[2]
。
1979年，蘇聯數學家哈奇揚在Shor, Levin, Judin等人求解凸規劃方法的思想基礎上，提出了線性規劃中的第一個多項式算法——橢球法， 並且證明：LP可以經多項式次數迭代後找到所求的解，其計算複雜性為
。這一成果很快對組合最優化、計算理論等領域產生了深遠影響，但在實際計算中該方法卻遠不及單純形法有效， 因為橢球法求解相同規模問題在一般情形下所需要的計算量與在最壞情形下的幾乎差不多，而實際應用中象Klee等人構造的例子幾乎從未遇見過。這就向人們提出了強烈的挑戰：能否找到理論上是“好的”而實際上又是確實可行的算法?
於是，在美國貝爾試驗室工作的印度數學家卡馬卡N.Karmarkar (1984) 運用投影變換、勢函數(它是罰函數的變形)等新技巧，創建出一個新的LP多項式算法，其計算複雜性為
，大大改進了哈奇揚的結果，很快引起人們的極大關注，人們希望這種方法能比單純形法更有效地解決經濟、管理、工程及其它領域中實際存在的許多大型複雜問題
[3]
。
多項式算法舉例説明
多項式算法哈奇揚算法
1.(初始準備)
記錄迭代次數，tj為第j次迭代的解，初始解
為分量全為0的n維列向量，取
為n階對角矩陣，其中I為n階單位陣，
為問題的規模，P為矩陣A及向量b中所有非零分量的乘積，在上述數據中，可逆方陣B是構造橢球的關鍵成分，初始橢球
2.(檢驗) 若tj滿足
，則停止迭代，當前解即為所求，若
，則停止迭代，説明問題無解。
3.(迭代) 任選一個不滿足
的不等式，例如
，並記
，設
多項式算法卡馬卡算法
1984年，印度數學家N.Karmarkar針對線性規劃問題提出了一種新的多項式時間算法，在實際計算效率方面，Karmarkar算法顯示出可與單純形法競爭的巨大潛力，Karmarkar算法的提出是線性規劃理論研究的突破，而且對於處理非線性優化問題也顯示出強大的生命力和廣闊的應用前景。
單純形法是通過檢查可行域邊界上的極點的方法來求解(LP)問題，而Karmarkar算法則是建立在單純形結構之上的，該算法從初始內點出發，沿着最速下降方向，通過可行域內部直接達到最優解，因此，Karmarkar算法也被稱為內點法，由於是在可行域內部尋優，故對於大規模線性規劃問題，當約束條件和變量數目增加時，內點算法的迭代次數變化較少，收斂性和計算速度均優於單純形法。
卡馬卡算法考慮如下標準形式的線性規劃問題
1.在上述約束條件下
；
2.
；
3.對於給定精度
，當可行解
滿足條件
