算法知识点总结

NP完全问题


P类问题:
所有可以在多项式时间内求解的判定问题构成P类问题.此类问题的复杂度是此类问题的一个实例的规模n的多项式函数。比如排序问题,求最短路径问题等。
P类问题是NP问题的子集,原因是P类问题既然能在多项式时间内求解,也必然能在多项式时间在验证它的解,满足NP类问题的定义。
NP类问题:
所有的非确定性多项式时间可解的判定问题构成NP类问题.
有些问题很难找到多项式时间的解法(也许根本就不存在),但是如果给出了该问题的一个解,我们可以在多项式时间内判断这个解是否正确,比如对于哈密尔顿回路问题,如果给出一个任意的回路,我们可以很容易的判断出该回路是否是哈密尔顿回路.

著名的NP难问题


最长路径问题:最长路径问题是指在给定的图中找出长度最长的道路.


-------------本文结束感谢您的阅读-------------

万水千山总是情,就给五毛行不行!

相关文章: