计算机科学家说的“难题”是真正的难题,老百姓说的难题
当一个计算机科学家说“难题”的时候,他说
的可是真正的难题。
老百姓说的难题,通常都不是真的难题。比
如你让一个小学生做一道高中数学题,他会
说这是一道难题
旦这个难度是相对而
言的,换个数学家来,高中数学题根本不叫
事儿。老百姓爱说“难者不会会者不难”,其
实具有这个性质的事儿都不是真的难题
真正的难题,得是绝对意义上的难。哪怕有
道题,现在活着的所有人都不会做,你也
很难说将来会不会有人找到一个巧妙地解
法,他一说那个解法大家都会觉得很简单
所以那还不能算“绝对意义上的难
而计算机科学家,找到了一种绝对意义上的
难题。术语叫“NP困难(NP-hard)”。如
果再强行翻译一下,大约叫“非确定性多项
式困难”不过你不必在意这个术语,你
只需知道,凡是“NP困难”的问题,都是绝
对的难题就行
为了理解这一点,咱们先看看什么是简单的
问题
比如现在给你一份学生名单,让你找一找,
其中有没有一个叫“王小二”的学生,这就是
个简单问题。简单体现在计算时间短。你
只需要把名单上的名字过一遍就行。对计算
机来说,这是最简单的搜索。我们容易理
解,如果名单上有N个名字,那么搜索时
间将会和N成正比。
好,再看第二个问题。还是N个学生,现
在让你按照考试分数给他们排个名次。如果
你手动,先挑最高分,再挑第二高的分这么
排,你就太慢了。如果你对计算机算法有
定了解,你大概知道有一些特别聪明的排序
算法。其中最快的排序算法所需要的运行l
间,大约和Nog(N)成正比。排序比搜索
要慢一些,但是这个时间也还可以,我们仍
然可以说这是一个简单问题。
什么叫“困难问题”呢?请看第三题
在一张地图上有N个城市,想象你是一
推销员,你能不能找到一条最短的路线,不
重不漏地经过所有这些城市去做推销,然后
回到起点。比如像下面这条路线
这个问题听起来很直观,好像挺简单,这不
就是快递员每天都面对的问题吗?但是,这
是一个非常难的问题。上面图中就是一条看
起来不错的路线,但是你怎么知道它是不是
有可能路线中*最短的*一条呢
这个问题叫做“旅行推销员问题( Traveling
Salesman Problem)”。这是一个最著名的
组合优化问题。这是一个“NP困难”问题。
解决这个问颎没有什么特别聪明的计算机算
法
你几乎就是只能把这些城市的所有
排列组合都计算一遍,看看其中哪个最短。
你所需要的计算时间,不是跟N成正比
如果是10个城市,你得尝试超过36万种
路线。如果是15个城市,你得尝试超过
871亿种路线
