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