多项式算法

数学术语

多项式算法(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，当12n，其中，t=1000logn，其中log为以2为底的对数。

基本介绍

多项式算法是判断一个算法“好坏”的数学概念。当考察解某一类问题(如线性规划问题)的一种算法时，在计算机上利用这一算法解这类问题中的每个具体问题所需的计算次数(时间)是不同的。计算步数(时间)一般与具体问题的规模(如线性规划问题中变量的个数，约束条件的个数等)有关。为了判断一个具体问题规模的大小，往往把此问题需要输入计算机的有关数据转化为一个二进制的代码序列(即只含0或1组成的序列)。这个序列中所含0或1的个数L就称为这一具体问题的输入长度，并用L来代表此问题的规模大小。

如果解某类问题的一个算法，在解规模为L的具体问题时，其计算步数在最坏的情形下不超过L的一个多项式P(L)，则称这一算法为多项式算法(或好算法)。

显然，在实践中具有多项式算法的问题才能有效地用计算机计算，因为当问题的规模增大时，所需的计算时间增大的速度还不很大。所以，多项式算法的概念给出了理论上可计算与实际可计算的问题的区别。同时，对某类问题的已知算法，来研究它是否是多项式算法，也具有重要的理论意义和实际意义。

例如，在考察解线性规划的算法时，克里和明特构造了一个具体的线性规划问题，说明单纯形法不是一个多项式算法。那么，线性规划问题是否存在多项式算法呢?这一问题首先于1979年由苏联的哈奇扬解决。哈奇扬证明了他所提出的椭球算法是一个多项式算法。随后，在美国工作的印度数学家卡马卡于1984年又提出了求解线性规划的另一个多项式算法。

1979年，苏联数学家哈奇扬在Shor, Levin, Judin等人求解凸规划方法的思想基础上，提出了线性规划中的第一个多项式算法——椭球法，并且证明：LP可以经多项式次数迭代后找到所求的解，其计算复杂性为。这一成果很快对组合最优化、计算理论等领域产生了深远影响，但在实际计算中该方法却远不及单纯形法有效，因为椭球法求解相同规模问题在一般情形下所需要的计算量与在最坏情形下的几乎差不多，而实际应用中象Klee等人构造的例子几乎从未遇见过。这就向人们提出了强烈的挑战：能否找到理论上是“好的”而实际上又是确实可行的算法?

于是，在美国贝尔试验室工作的印度数学家卡马卡N.Karmarkar (1984) 运用投影变换、势函数(它是罚函数的变形)等新技巧，创建出一个新的LP多项式算法，其计算复杂性为，大大改进了哈奇扬的结果，很快引起人们的极大关注，人们希望这种方法能比单纯形法更有效地解决经济、管理、工程及其它领域中实际存在的许多大型复杂问题。

举例说明

哈奇扬算法

哈奇扬方法为考虑如下特征的问题：求x使之满足，其中A为矩阵，其方法步骤为：

1.(初始准备)　记录迭代次数，tj为第j次迭代的解，初始解为分量全为0的n维列向量，取为n阶对角矩阵，其中I为n阶单位阵，为问题的规模，P为矩阵A及向量b中所有非零分量的乘积，在上述数据中，可逆方阵B是构造椭球的关键成分，初始椭球

2.(检验)　若tj满足，则停止迭代，当前解即为所求，若，则停止迭代，说明问题无解。

3.(迭代)　任选一个不满足的不等式，例如，并记，设

转至第2步。

为n维列向量，为n×n矩阵，虽然，哈奇扬方法是求解线性规划的多项式算法，但是其实际迭代上并不产生真实的优越性，这个方法在理论上的影响对线性规划是突破性的，其后产生了一个新方向，即考虑以约束区域的内点为途径，去搜索问题的解，这个方向把线性规划与非线性规划以及组合规划能够更紧密地结合起来。

卡马卡算法

1984年，印度数学家N.Karmarkar针对线性规划问题提出了一种新的多项式时间算法，在实际计算效率方面，Karmarkar算法显示出可与单纯形法竞争的巨大潜力，Karmarkar算法的提出是线性规划理论研究的突破，而且对于处理非线性优化问题也显示出强大的生命力和广阔的应用前景。

单纯形法是通过检查可行域边界上的极点的方法来求解(LP)问题，而Karmarkar算法则是建立在单纯形结构之上的，该算法从初始内点出发，沿着最速下降方向，通过可行域内部直接达到最优解，因此，Karmarkar算法也被称为内点法，由于是在可行域内部寻优，故对于大规模线性规划问题，当约束条件和变量数目增加时，内点算法的迭代次数变化较少，收敛性和计算速度均优于单纯形法。

卡马卡算法考虑如下标准形式的线性规划问题

满足及或者

这里e为分量全为1的n维列向量，并且已知：

1.在上述约束条件下；

2.；

3.对于给定精度，当可行解满足条件

时，即可停止迭代，并认为x即为所求的解。

全国各地天气预报查询

上海市

市辖区

云南省

临沧市