斯坦福 算法2 第五周笔记
斯坦福 Algorithms: Design and Analysis 2 第五周笔记
来自斯坦福网站的Algorithms: Design and Analysis，与目前coursera上的版本内容没有变化，不过时间安排略有不同。
1. NPC 问题
这门课里一直讲的都是对于基本计算问题的理论支撑以及相应的实用算法，但是实际上有许多重要的问题甚至是不可能有一个快速的解法的。这里就用NPC理论来定义这种不可解问题（computational intractability）。
1.1 P问题
可解性的定义：
这里的P表示多项式时间。而P问题指的就是能够在多项式时间内解决的问题的集合。
但是实际上我们这门课已经讲了几个不属于P问题的问题，比如在含有负环的图中输出不含负环的最短路径问题以及背包问题，它们都是NPC问题。而旅行商问题是另一个有名的NP问题。
而1965年就有个猜想是说旅行商问题没有多项式解。这就相当于说。
1.2 Reductions and Completeness
如果我们想要证明上面的猜想，也就是TSP问题的不可解，那么一个很好的想法就是通过相对难度来证明，旅行商问题与很多其它的问题一样困难。
于是我们引入规约（Reduction）的定义：
比如将中位数问题规约为排序问题，寻找图中的环规约为DFS等。
有了规约就能得到另一个完全性（Completeness）的定义：
也就是说如果一个集合中所有问题都能规约到，那么这个称谓这个集合完全的。而且这个问题也是这个集合中最难解的问题。
因为我们想要说明的是旅行商问题的难解性，因此需要找到一个集合，这个集合中的问题都能规约到旅行商问题。但这个集合实际上不能是所有计算问题的集合，因为还存在比旅行商问题明显更难的问题比如停机问题（undecidable）。考虑到TSP问题用暴力遍历的方式是可解的，我们可以把这个集合定义为暴力可解的问题集合。
1.3 NPC定义与解释
知道了完全性的定义，那么解释NPC之前需要知道NP问题的定义，NPC问题就是对集合NP有完全性的问题。
在现实生活中许多的重要问题都是NP问题。而通过完全性的定义我们得知，如果一个NPC问题有多项式时间的算法解，那么所有的NP问题都有了多项式解法（所以解这个问题很有难度）。这就是表示。
实际上我们定义NPC问题是想说明一个算法非常难解。因为解这个问题相当于解其它所有的NP问题，所以甚至可以怀疑这种问题是否存在。但是实际上它确实存在，旅行商问题就是其中之一。而如果平时遇到了无论如何也想不到合理解法的问题，可以考虑证明它是NPC问题：
但是对于上面的猜想，也就是P问题与NP问题到底是否相等，至今依然没有得到证明。既没有证明相等，也没有证明不相等。但是我们其实有理由认为它们不相等：
而NP这两个字母表示的并不是not polynominal，而是nondeterministic polynominal，也就是非确定性图灵机在多项式时间可解。这个定义与先前的NP问题的定义等同。
1.4 NPC问题解法
证明了一个问题是NPC问题，说明它确实非常难解。但是实际生活中我们很可能真的遇到任务中某个关键问题就是NPC问题的情况，因此还需要对其求解。可以考虑这些策略：
2. Exact Algorithms for NP-Complete Problems
2.1 The Vertex Cover Problem
这是一个NPC问题，因此上面三条相关解决策略可以应用了：
如果我们想知道，是否存在一个k个点的集合满足顶点覆盖的要求。如果使用暴力解法，那就是遍历图中所有的k个点的集合进行验证。但实际上有更好的解法：
使用类似动态规划中观察解的结构，我们发现如果存在一个k个点的解，那么随机选中图中一条边(u,v)之后，分别去掉u和v的两个子图必然有一个存在k-1个点的顶点覆盖解。
根据这个递推关系，我们就得到了相应的递归解法：
而每次递归需要进行的操作是，共有k层递归，因此整个的复杂度为，比原先的的复杂度要小。能够解决更大规模的问题。
2.2 The Traveling Salesman Problem
如果采用动态规划，它的最优结构很难去表示和递推。可能中间会漏掉某些矛盾的地方比如设计的结构不能解决最后的问题，或者是漏掉可能存在的重复访问等等。
最终将这个结构表示为终点j和已遍历的点集合S表示的问题。
递推关系如下：
它保证了最终的路径中没有重复访问的点，而且花费最小。算法整个流程如下：
这个方法比暴力解好的原因可能就在于问题的表示上。这里用了一个无序的集合S表示已经访问的路径，而暴力解的搜索时路径是有序的。因此暴力搜索时可能会遇到很多搜索到很深的时候需要从头开始，而动态规划的表示大大减少了这一情况。