漫画:什么是旅行商问题?

举报
xenia 发表于 2019/10/21 17:39:33 2019/10/21
【摘要】 需要规划出怎样的路线呢?举个例子:有一个快递员,要分别给三家顾客送快递,他自己到达每个顾客家的路程各不相同,每个顾客之间的路程也各不相同。那么,想要把快递依次送达这三家,并最终回到起点,哪一条路线所走的总距离是最短的呢?旅行商问题和小灰所遇到的问题类似,旅行商问题所描述的是这样一个场景:有一个商品推销员,要去若干个城市推销商品。该推销员从一个城市出发,需要经过所有城市后,回到出发地。每个城市...


640?wx_fmt=jpeg&tp=webp&wxfrom=5&wx_lazy=1&wx_co=1

640?wx_fmt=jpeg&tp=webp&wxfrom=5&wx_lazy=1&wx_co=1

640?wx_fmt=jpeg&tp=webp&wxfrom=5&wx_lazy=1&wx_co=1


640?wx_fmt=jpeg&tp=webp&wxfrom=5&wx_lazy=1&wx_co=1


需要规划出怎样的路线呢?举个例子:


有一个快递员,要分别给三家顾客送快递,他自己到达每个顾客家的路程各不相同,每个顾客之间的路程也各不相同。


640?wx_fmt=png&tp=webp&wxfrom=5&wx_lazy=1&wx_co=1


那么,想要把快递依次送达这三家,并最终回到起点,哪一条路线所走的总距离是最短的呢?


640?wx_fmt=png&tp=webp&wxfrom=5&wx_lazy=1&wx_co=1



640?wx_fmt=jpeg&tp=webp&wxfrom=5&wx_lazy=1&wx_co=1


640?wx_fmt=jpeg&tp=webp&wxfrom=5&wx_lazy=1&wx_co=1

640?wx_fmt=jpeg&tp=webp&wxfrom=5&wx_lazy=1&wx_co=1


640?wx_fmt=jpeg&tp=webp&wxfrom=5&wx_lazy=1&wx_co=1

640?wx_fmt=jpeg&tp=webp&wxfrom=5&wx_lazy=1&wx_co=1


640?wx_fmt=jpeg&tp=webp&wxfrom=5&wx_lazy=1&wx_co=1



旅行商问题


和小灰所遇到的问题类似,旅行商问题所描述的是这样一个场景:


有一个商品推销员,要去若干个城市推销商品。该推销员从一个城市出发,需要经过所有城市后,回到出发地。每个城市之间都有道路连通,且距离各不相同,推销员应该如何选择路线,使得总行程最短呢?


640?wx_fmt=png&tp=webp&wxfrom=5&wx_lazy=1&wx_co=1



这个问题看起来很简单,却很难找到一个真正高效的求解算法。其中最容易想到的,是使用穷举法 


把所有可能的路线穷举出来,计算出每一条路线的总行程:


A-B-C-D-E-F-G-H-I  

A-B-C-D-E-F-G-I-H  

A-B-C-D-E-F-H-G-I  

A-B-C-D-E-F-H-I-G  

A-B-C-D-E-F-I-H-G  

A-B-C-D-E-F-I-G-H

......

......


像上面这样排列组合,从所有路线中找出总行程最短的路线。显然,这个方法的时间复杂度是O(n!),随着城市数量的增长,花费的运算时间简直不可想象!


后来,人们想出了许多相对优化的解决方案,比如动态规划法分枝定界法(这个算法很有意思,以后会专门写一篇漫画来详细介绍)......但是,这些算法的时间复杂度仍然是指数级的,并没有让性能问题得到根本的解决。


640?wx_fmt=jpeg&tp=webp&wxfrom=5&wx_lazy=1&wx_co=1


640?wx_fmt=jpeg&tp=webp&wxfrom=5&wx_lazy=1&wx_co=1



P和NP


NP到底是什么意思呢?


我们曾经学习过许许多多的算法,这些算法的时间复杂度都可以用多项式来表示,比如:


归并排序的时间复杂度是O(nlogn)

冒泡排序的时间复杂度是O(n^2)

Floyd算法的时间复杂度是O(n^3)


尽管这些算法的运行时间有数量级上的差别,但是它们的时间复杂度都可以用O(n^k)来表示,k是一个常数。


因此,这些算法都是多项式时间算法,能用多项式时间算法解决的问题被称为P问题( Polynomial)


人们常说,能用钱解决的问题都不是问题,在计算机科学家眼中,能用多项式时间解决的问题都不是问题。


然而,世间还存在许多变态的问题,是无法(至少是暂时无法)在多项式时间内解决的,比如一些算法的时间复杂度是O(2^n),甚至O(n!)。


随着问题规模n的增长,计算量的增长速度是非常恐怖的。这类问题被称为NP问题(Non-deterministic Polynomial),即非确定多项式问题。


有些科学家认为,所有的NP问题终究都可以在多项式时间内解决,只是我们暂时还没有找到方法;也有些科学家认为,某些NP问题永远无法在多项式时间内解决。


这个业界争论可以用一个公式来表达:

NP = P?


640?wx_fmt=jpeg&tp=webp&wxfrom=5&wx_lazy=1&wx_co=1


640?wx_fmt=jpeg&tp=webp&wxfrom=5&wx_lazy=1&wx_co=1


640?wx_fmt=png&tp=webp&wxfrom=5&wx_lazy=1&wx_co=1



归约和NPC


这里所说的NPC问题可不是游戏当中的NPC,它究竟是什么意思呢?要想理解NPC问题,我们需要先了解归约的概念。


归约,可以简单理解成问题之间的转化。例如问题Q是一个一元一次方程的求解问题:3x+6 = 12,这个问题可以转化成一个一元二次问题Q':0x^2+3x+6 = 12。


显然,问题Q并不比问题Q'更难解决,只要有办法解决Q',就一定能够解决Q。对于这种情况,我们可以说问题Q归约于问题Q'


同时,这种归约可以逐级传递,比如问题A归约于问题B,问题B归约于问题C,问题C归约于问题D,那么我们可以说问题A归约于问题D。


在NP问题之间,也可以存在归约关系。我们把众多的NP问题层层归约,必定会得到一个或多个“终极问题”,这些归约的终点就是所谓的NPC问题(NP-complete),也可以翻译成NP完全问题。上面所讲的旅行商问题,被科学家证明属于NPC问题。


640?wx_fmt=png&tp=webp&wxfrom=5&wx_lazy=1&wx_co=1


就数量上而言,NP问题远比P问题要多,而NP之中的NPC问题也仅占极少数,所以P、NP、NPC之间的关系可以用下图来表示:


640?wx_fmt=png&tp=webp&wxfrom=5&wx_lazy=1&wx_co=1


俗话说擒贼先擒王,只要有朝一日,我们能够找到NPC问题的多项式时间算法,就能够解决掉所有的NP问题!但遗憾的是,至今还没有人能够找到可行的方法,很多人认为这些问题是无解的。



640?wx_fmt=jpeg&tp=webp&wxfrom=5&wx_lazy=1&wx_co=1

640?wx_fmt=jpeg&tp=webp&wxfrom=5&wx_lazy=1&wx_co=1


640?wx_fmt=jpeg&tp=webp&wxfrom=5&wx_lazy=1&wx_co=1


640?wx_fmt=jpeg&tp=webp&wxfrom=5&wx_lazy=1&wx_co=1


640?wx_fmt=jpeg&tp=webp&wxfrom=5&wx_lazy=1&wx_co=1640?wx_fmt=jpeg&tp=webp&wxfrom=5&wx_lazy=1&wx_co=1


640?wx_fmt=jpeg&tp=webp&wxfrom=5&wx_lazy=1&wx_co=1

本文转载自公众号【程序员小灰】

原文链接:https://mp.weixin.qq.com/s/bSF0OntNwPRusIgGOpZuVg

【版权声明】本文为华为云社区用户转载文章,如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。