主题：【原创】ｐ（多项式算法）问题对ｎｐ（非多项式算法）问题　 -- 香山居士

共:💬18

老大河待整

【原创】ｐ（多项式算法）问题对ｎｐ（非多项式算法）问题　

这个正好撞到我的专业上了,写一些让大家了解一下.由于我在国内不是学计算机的,出国以后转的行,文中我会用一些英文专业术语.

1. 算法的Complexity

一般一个算法的Complexity包括两个方面:一个是时间Complexity,就是解决一个问题要花多少时间;另一个是空间Complexity,考虑的是解决这个问题要用多少计算机资源,如内存等.在本文中我们只考虑时间Complexity.实际上,一般情况下p和np指的就是时间Complexity.

首先举一个例子:我们要做以下的一个矩阵-向量乘法:

y=Ax

其中A是一个n*n矩阵,x,y都是n*1的向量.如果我们直接按照矩阵乘法的定义计算,我们需要花多少时间?

让我们来算算.假设A,x,y全是实数那么按照定义,计算每一个元素要做n次乘法和n-1加法,即2n-1次基本运算(在次我们认为实数的加法和乘法都是计算机的基本运算).那么计算出整个y就需要n*(2n-1)=2n^2-n次基本运算.

同时假设在计算机运算中,每次基本运算需要相同的时间,把这个时间设为单位时间,那么前面的算法就需要花(2n^2-n)的时间来计算.

在计算机科学中,我们通常只取最高次项,同时忽略常数系数.这是因为当n很大时,低次项的贡献就可以被忽略了.回到我们前面的例子,矩阵-向量乘法的运行时间就是n平方量级,记为O(n^2).

2. p（多项式算法）问题

对于一个给定问题,如果我们可以找到一个算法在O(n^C)(C可以是任何常数)的时间内解决,那么我们称这个问题属于P问题.一般认为在实际应用中,P问题是可以解决的,无论n(输入)有多大.

如果我们找到的算法大于O(n^C),比如说O(2^n)(指数函数)和O(n!)(阶乘函数),虽然理论上这个问题可解,但实际应用中只要输入量(n)大一点,就没办法了.

假设有两个算法,一个O(n^2)另一个O(2^n).同时有一台计算机的速度是一秒钟一百万次运算.当n=1时算法1需要1微秒,算法2需要两微秒,没什么差别.但是当n=1,000,000时算法1需要一百万秒,大约是十一天半,虽然很长但还能等.算法2就需要大约(10^29994)秒,而一年不过3.15*10^8秒!

3. ｎｐ（非多项式算法）问题　

很不幸,现在我们有很多问题,没有一个人可以找到O(n^C)的算法,但又没有一个人可以证明这个问题不存在O(n^C)的算法.这一类问题统称为NP问题.

已知的著名NP问题包括SAT Problem,TSP(Travelling Salesman Problem),Clique Problem, Subset Sum Problem 等.我不想在这说太多细节.但是有一点一定要提的就是,所有的NP问题都可以互相推倒出来.也就是说:

如果你解决了一个NP问题,你就解决了所有的NP问题!

记得我老师上课时说:"If you solve this problem, you will be the most famous guy in computer science."

4. 近似算法

好,现在我有一堆NP问题,我不知道如何找到最佳答案,但这些问题又太重要而无法置之不理,怎么办?别着急,人们已经找到了一些近似算法.

所谓近似算法,就是一些算法在O(n^C)时间内,给出了离最佳值"差不多"的结果.注意:在这个过程中我不知道最佳值是多少,但我知道我的结果和最佳值的差别不会太大!

这里好象有点悬,这正是近似算法最难的地方.以下以 Knapsack 问题为例简单说一下近似算法:

我有一条船,载重量100吨,有一大堆箱子,里面放满了各种金银珠宝.每个箱子有自己的重量和价值.我当然想能拿多少拿多少,但很可惜,我的船只能运100吨,多了要沉船.问题是:给定每个箱子的重量和价值,我最多能拿多少?

这是一个NP问题,我们没有办法知道最佳值--我最多能拿多少,但现在已经有了近似算法可以确切地告诉我:你按我的方法选箱子,我保证你拿的多于最佳值的一半. 那么,两倍,就是这个算法的"近似程度".

本帖一共被 4 帖引用 (帖内工具实现)