NP完全性和近似算法

NP完全性

P类问题：P类问题就是在多项式时间内可以解决的问题。
NP类问题：NP类问题是指那些在多项式时间内可以被证明的问题。
NP完全性：如果一个问题L满足：1. L在NP中；2. 对于NP中的任意问题L’，L’可以多项式时间归约到L；则说L是NP完全(NP-Complete)的。

典型的NP完全性问题

电路满足问题：给定一个只由AND，OR和NOT组成的n输入-单输出布尔组合电路，是否存在一个输入指派，使得电路输出为1？一个布尔组合电路不能包含有向环。

最优顶点覆盖问题：在一个给定的图中，找到具有最小规模的顶点覆盖（所有的边至少有一点是和集合中的顶点相连的）。

子集和问题：给定一个数组，判断是否存在一个子集合，使得其中的数加起来恰好为目标值t。

固定参数算法

如果我们知道一个问题是NP完全性的，那么我们就不必去寻找多项式时间的解法，转而寻找一种其他的解决方案。

固定参数是对原问题添加了一个参数k，并且使得算法的复杂度的指数部分只和这个参数k相关，而其他部分为多项式，使得在问题规模较小的时候，可以得到解决。

在顶点覆盖问题中，固定参数算法增加了一个参数，能否在k个顶点内覆盖所有的边。这里，有一种算法的复杂度为，这样，在k较小时，问题可以得到解决。

近似算法

最优解问题，如果对规模为n的任意输入，近似算法产生的近似解的代价与最优解的代码只差一个一个因子，这称该算法为近似算法。

对于顶点覆盖问题，有这样一个算法：

C=空
E = 图中所有的边
while(E不为空)
    选择E中任意一边
    将和边相连的两个顶点加入到C，去重
    将和两个顶点的相连的边从E中移除
return C

这个算法产生的解法产生的顶点最多为最优解的两倍（具体的说明见算法导论相关章节）。

近似模式

近似模式和近似算法不同的是，近似模式有一个参数，可以通过调节这个参数调节和最优解的差距，当然，越精确，复杂度就越高。下面是一个子集和问题的精确解法，当不能等于t时，会输出最接近的那个数。

#include<bits/stdc++.h>
using namespace std;

int subsetSum(vector<int> &arr, int target){
    vector<int> v;
    v.push_back(0); // 一个都不选
    for(int i=0;i<arr.size();i++){
        int len = v.size();
        for(int j=0;j<len;j++){
            v.push_back(v[j] + arr[i]); //枚举所有可能
        }
        sort(v.begin(),v.end());
        auto ret = unique(v.begin(),v.end()); //去重
        v.erase(ret,v.end());
        //可以对数组进一步处理，对于相近的值，去掉相似的值，如101 102 103 可以去掉后两个，相当于使用101替代了后两个
        len = v.size();
        while(v.back() > target){ //去掉大于target的部分
            v.pop_back();
        }
    }
    return v.back();
}

int main(int argc, char const *argv[])
{
    int n,target;
    cin>>n>>target;
    vector<int> arr(n,0);
    int sum = 0;
    for(int i=0;i<n;i++){
        scanf("%d",&arr[i]);
        sum += arr[i];
    }
    cout<<subsetSum(arr,target)<<endl;
    system("pause");
    return 0;
}

这里近似的一个参数是替代值，如果把相近的值都用一个值来替代，这样可以减少数组中元素，提高速度。

总结

对于NP完全性问题，在问题规模较小时，我们可以考虑指数时间的精确解，问题规模较大时，我们可以使用近似算法，使用一种启发性的算法来得到近似解。启发式的策略有点像贪婪算法，想到某种策略并不难，难的是说明这种算法和最优解的差距。至于近似模式，感觉并不是所有的问题都能有这样一种方法。

感觉比较难，但还是做个笔记吧，还是开了一点眼界。