np完全算法（np-c问题）

对于NP完全问题的定义，百度百科是这样给出的：NP完全问题(NP-C问题)，是世界七大数学难题之一。

是关于时间复杂度的计算问题，在阅读决策树算法有关知识点的时候遇到的。

NP的英文全称是Non-deterministic Polynomial的问题，即多项式复杂程度的非确定性问题。

简单的写法是 NP=P？，问题就在这个问号上，到底是NP等于P，还是NP不等于P。

例子1 旅行商城市最短路径问题。
遍历下来是就是阶乘问题（考虑有些城市之间是单行道，这回导致路径往返的路径不同）

集合覆盖问题也是一类np完全问题
例子2 橄榄球队挑选球员，一般是擅长球技数从多到少，直至覆盖所有需求。

识别np-c问题

• 元素较少时算法的运行速度非常快，但随着元素数目的增加，速度会变得非常慢。
• 涉及“所有组合”的问题通常是NP完全问题。
• 不能采用分治法的思想将大问题分解成小问题，必须考虑各种可能情况，这很可能是NP完全问题。
• 如果问题涉及“序列”或“集合”，并难以解决，很可能就是NP完全问题。
• 如果问题可转换为旅行商问题或集合覆盖问题，那就肯定是NP完全问题。

原文链接：https://blog.csdn.net/leowinbow/article/details/88187386