聊聊数据结构与算法:从旅行商问题说起

旅行商问题

旅行商问题,即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个概念:

换句话说,一个问题可以找到一个能在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

https://www.jianshu.com/p/dcb0b52f4935

https://blog.csdn.net/a8082649/article/details/82079779

Table of Contents