huangyhg

转载自 http://cs.cuc.edu.cn/linweiguo/archives/000338.html 摘自某BBS：

存在许多还没找到有效算法的问题。也许其中最著名的要数图论中的“旅行推销员问题”，简称“TSP”。即“已给一个n个点的完全图，每条边都有一个长度，求总长度最短的经过每个顶点正好一次的封闭回路”。Edmonds，Cook和Karp等人发现，这批难题有一个值得注意的性质，对其中一个问题存在有效算法时，每个问题都会有有效算法。这些问题称为NP难题（NP-Hard或NPH）。迄今为止，这类问题中没有一个找到有效算法。目前倾向于接受NP完全问题（NP-Complet或NPC）和NP难题不存在有效算法这一猜想，认为这类问题的大型实例不能用精确算法求解，必须寻求这类问题的有效的近似算法。
计算复杂性理论源于对判定问题算法的研究。
判定问题：其答案不是“是”就是“否”的问题。如，一个图的两顶点之间存在路径吗？判定问题有三类：P、NP和NPC。
P类：已有多项式时间算法的判定问题。
NP类：已有指数时间算法的判定问题，包括P类。
NPC类：是NP的一个子集，且其中每一个问题均能由NP中的任何问题在多项式时间内转化而成。问题A能在多项式时间内转化为问题B可理解为，问题A有一个算法以问题B的算法为子程序，当把每次对B算法的调用看作一个基本操作（只花常数时间）时，A的这个算法是多项式时间的。
在NPC问题之外还有一些问题，其难度与NPC相当或难度超出NPC，这就是NPH问题。何谓NPH问题呢？
NPH类：若问题A不属于NP类，已知某一NPC问题可在多项式时间之内转化为问题A，则称A为NP难题。例如，“TSP”是NPH问题。

__________________
借用达朗贝尔的名言：前进吧，你会得到信心!
[url="http://www.dimcax.com"]几何尺寸与公差标准[/url]