聊聊数据结构与算法：从旅行商问题说起
旅行商问题
旅行商问题，即TSP问题（Travelling salesman problem），假设有一个旅行商人要拜访n个城市，给定一系列城市和每座城市之间的距离，求解访问每一座城市一次并回到起始城市的最短回路。
为了解决这个问题，我们可以遍历每一条路线并计算路程，最后挑选出最短的路线。但是这个算法的时间复杂度是O(n!)，是一个阶乘函数，这意味着5个城市就有120条路线，6个城市就有720条路线，7个城市就有5040条路线，如果是100个城市就是一个天文数字，几乎不可能计算出结果。
迄今为止，这类的问题并没有一个更快的算法，这类问题一般称之为NP-C问题，为了理解什么是NP-C问题，我们需要先理解几个概念。
P类问题、NP类问题和NP-C问题
P类问题
所有可以在多项式时间内求解的判定问题构成P类问题（Polynomial problem）。
这句定义包含了2个概念：
-
多项式时间（Polynomial time）
在数学中，多项式是由若干个单项式相加组成的代数式。单项式则是由数或字母的积组成的代数式。而多项式时间则表示不超过多项式O(n^k)的时间复杂度。
-
判定问题
判断是否有一种能够解决某一类问题的能行算法的研究课题。
换句话说，一个问题可以找到一个能在O(1)、O(log(n))、O(n^2)等多项式时间解决的算法，那么这个问题就属于多项式问题，即P类问题。这类多项式级别的问题是计算机可以解决的，而像O(2^n)、O(n!)这类非多项式级别的问题，其复杂度往往已经到了计算机都接受不了的程度。
NP类问题
所有的非确定性多项式时间可解的判定问题构成NP类问题（Non-deterministic Polynomial problem）。
NP类问题将问题分为求解和验证两个阶段，问题的求解是非确定性的，无法在多项式时间内得到答案，而问题的验证却是确定的，能够在多项式时间里确定结果。
比如：是否存在一个公式可以计算下一个质数是多少？这个问题的答案目前是无法直接计算出来的，只能通过间接的“猜算”来得到结果，这就是非确定性问题。但是如果某人给（猜）出了一个公式，我们却可以在多项式时间里对这个公式进行验证，这就是非确定性多项式问题，即NP类问题。
所有的P类问题都是NP问题，也就是说，能多项式地解决一个问题，必然能多项式地验证一个问题的解。反过来人们想知道，是否所有的NP类问题都是P类问题，也就是NP类问题是否存在一个算法，可以在多项式时间内计算出答案？这就是著名的NP=P?，目前仍无法被证明成立或不成立，但人们普遍倾向于相信NP≠P。
NP-C问题
NP中的一类比较特殊的问题，这类问题中每个问题的复杂度与整个类的复杂度有关联性，假如其中任意一个问题在多项式时间内可解的，则这一类问题都是多项式时间可解。这些问题被称为NP完全问题，或NP-C问题（Non-deterministic Polynomial complete problem）。
人们在研究NP问题的过程中找出了一类非常特殊的NP类问题叫做NP完全问题，即NP-C问题。任何一个NP类问题都可以归约为更复杂的NP-C问题，只要能够解决任何一个NP-C问题，那一定能解决所有的NP类问题。
以旅行商问题举例，我们可以改一下将其变成判定问题，问能否找到一条路线，使得路程小于1000公里？问题同样难以求解，但是却很容易验证，只要猜到了一条小于1000公里的路线，照路线走计算总路程便知，这就是NP类问题。把这个问题归约为原问题，便是一个NP-C问题，既难以求解，又难以验证，因为即使猜了一条“最短”路线，要验证也要遍历所有路线才能证明这是最短路线。
因此学会了如何识别NP-C问题，当我们在遇到NP-C问题时，就可以避免浪费时间去寻找解决它们的快速算法。
贪心算法
贪心算法（又称贪婪算法）是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，所做出的是在某种意义上的局部最优解。贪心算法适用的前提是：局部最优策略能导致产生全局最优解。
贪心算法适用的情况很少，因此不是对所有问题都能得到整体最优解，往往得到的是近似最优解。贪心算法没有固定的算法框架，算法设计的关键是贪心策略的选择。必须注意的是，贪心算法不是对所有问题都能得到整体最优解，选择的贪心策略必须具备无后效性，即某个状态以后的过程不会影响以前的状态，只与当前状态有关。所以对所采用的贪心策略一定要仔细分析其是否满足无后效性。
解决最短路径问题的广度优先搜索算法、Dijkstra算法都属于贪心算法，只是在其问题策略的选择上，刚好可以得到最优解。
我们知道，对于NP-C问题，无法快速找到最优解，但是利用贪心算法作为近似算法，我们就可以快速找到旅行商问题的近似最优解，做法是这样：在每次选择要去的下一个城市时，都选择还没去过的最近的城市。我们就可以找一条相对比较短的路径，虽然不是最短的路径，不完美，但在现实中近似最优解有时也是可以接受的。
参考文档
http://www.matrix67.com/blog/archives/105