重庆网站设计中心,柳州建设网站经济适用房表格,哈尔滨做网站公司有哪些,一个简单网页的代码目录 一、P类问题与NP类问题的定义二、常见的NP类问题#xff08;一#xff09;旅行商问题#xff08;TSP#xff09;#xff08;二#xff09;哈密尔顿回路问题#xff08;三#xff09;判断回路问题#xff08;四#xff09;图的着色问题#xff08;五#xff09… 目录 一、P类问题与NP类问题的定义二、常见的NP类问题一旅行商问题TSP二哈密尔顿回路问题三判断回路问题四图的着色问题五背包问题 三、P类问题和NP类问题的区别四、NP完全问题 一、P类问题与NP类问题的定义
P类问题与NP类问题是计算机科学和数学中的两类重要问题简单的来说P类问题是较“容易”的问题在计算机中可以在多项式时间内解决而NP类问题是较“复杂”的问题它并不能在多项式时间内解决只能验证是否存在解解是否正确。
常见的P类问题有排序、搜索算法等等但不是所有的排序算法都是P类问题例如下表中快速排序、堆排序和归并排序是P类问题其平均时间复杂度呈多项式由于插入排序、冒泡排序、简单选择排序的平均时间复杂度都呈指数级所以不属于P类问题而是NP类问题。
排序名称平均时间复杂度直接插入排序O(n2)折半插入排序O(n2)希尔排序依赖于增量序列冒泡排序O(n2)快速排序O(nlog2n)简单选择排序O(n2)堆排序O(nlog2n)归并排序O(nlog2n)
二、常见的NP类问题
一旅行商问题TSP
旅行商问题中给定一组城市和每对城市之间的距离寻找一条最短路径使得旅行者能够遍历所有城市并回到起始城市。 由于该问题的复杂度是指数级的所以不存在多项式时间的确定性算法来解决它属于NP类问题。
二哈密尔顿回路问题
对于一个有向图判断是否存在一条回路可以经过图中所有顶点且不重复的问题称为哈密尔顿回路问题。 在遍历图中的顶点时需要经过所有可能的路径从而判断且需要遍历的路径呈指数级增加所以该问题也是个NP类问题。
三判断回路问题
同样对于一个图若要判断图中是否有回路可以通过深度优先搜索DFS和广度优先搜索BFS来判断两种搜索算法都会遍及图中所有的结点所以该问题也是个NP类问题。
四图的着色问题
给定一个无向图和若干种颜色给图中的每个顶点着色使得任意相邻的两个顶点颜色不同即为图的着色问题。 若针对一个顶点涂色则其邻边的顶点与该顶点颜色均不同从而一直进行下去该图中所有的颜色组合数呈指数级增加可以采用贪心算法和回溯算法来解决所以该问题也是个NP类问题。
五背包问题
给定一组物品每个物品都有自己的重量和价值背包的容量有限求如何选择物品放入背包使得背包内的物品总价值最大即为背包问题。 同样物品的选择和组合方式的数量随着物品数量的增加而呈指数级增长所以该问题也是个NP类问题。
三、P类问题和NP类问题的区别
P类问题和NP类问题的区别在于时间复杂度P类问题可以在多项式时间内的确定性算法来进行判定或求解问题且一般P类问题的求解较简单时间复杂度较低而NP类问题可以在多项式时间内的不确定性算法来进行判定或求解问题其求解过程较困难但一般都是去验证问题。
四、NP完全问题
NP完全问题是NP问题的一个子类可以说它是更复杂的问题也是在多项式时间内验证问题的解。例如多项式变换技术问题、布尔可满足性问题以及上面的旅行商问题TSP、哈密尔顿回路问题等等。
