本文主要是介绍判断NP完全问题的一些蛛丝马迹，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
一般来说我们没有简单的办法判断问题是不是NP完全问题，但还是有一些蛛丝马迹可寻（来自《算法图解》）
- 元素较少时算法的运行速度非常快，但是随着元素数量的增加，速度会变得非常慢；
- 涉及
所有组合的问题通常都是NP完全问题；- 不能将问题分成小问题，必须考虑各种可能的情况。这可能是NP完全问题；
- 如果问题涉及序列(如旅行商问题中的城市序列)且难以解决，它可能是NP完全问题；
- 如果问题涉及集合（如广播台集合）且难以解决，它可能是NP完全问题；
- 如果问题可转换为集合覆盖问题或旅行商问题，那么它肯定是NP完全问题。
对于NP完全问题，最佳的做法是使用近似算法，贪婪算法易于实现，运行速度快，是不错的近似算法。
典型NP问题——旅行商问题，引自百度百科：
假设有一个旅行商人要拜访N个城市，他必须选择所要走的路径，路径的限制是每个城市只能拜访一次，而且最后要回到原来出发的城市。路径的选择目标是要求得到的路径路程为所有路径之中的最小值。
典型NP问题——集合覆盖问题，引自百度百科：
给定全集
U，以及一个包含n个集合且这n集合的并集为全集的集合S。集合覆盖问题要找到S的一个最小的子集，使得他们的并集等于全集。
这篇关于判断NP完全问题的一些蛛丝马迹的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
