从一个常见而看似简单的数学问题说起:为什么

 新闻资讯     |      2020-06-04 05:21

在数学中有这样一个生活里经常会有的、看起来简单的问题。问题是这样的,假设一个推销员从其起点出发,需要去张三、李四和王五这三个地方推销,然后回到起点。这个问题也可以是一个邮局的邮递员、或快递公司的送货员、或押运公司押送现金员等,需要去此三地后回到起点。所以,可以有下面6种可能的路线:

首先去张三,接下来去李四,然后去王五,首先是张三,其次是王五,然后是李四,首先去李四,接下来去张三,然后去王五,首先是李四,其次是王五,然后是张三,首先去王五,接下来去张三,然后去李四,首先是王五,其次是李四,然后是张三。

在上面示例中共有4个目的地:推销员处、张三、李四和王五,有6个可能的路径。实际上,这些路径中只有3个是唯一的,因为有一半路径与另一半路径是相同的,例如,推销员处张三李四王五推销员处的路径,与推销员处王五李四张三推销员处的路径,方向相反但是路径及其距离相同。

这些路线中哪一条所行进的距离最小?有人会说,这太简单了,只需要根据上面所列出的路线一一比较,就可以得出最佳答案。

问题是,上面的例子只有4个目的地所以只有3条唯一可能的路线。如果有5个目的地,则有12条唯一路径;如果有6个目的地,则有60条唯一路径;以此类推,如果有10个目的地,则有181,440条唯一路径;如果有15个目的地,则有约436亿条独特的路径。一般来讲,对于任意的目的地数量N,可能的唯一路径数量为(N -1)!/ 2,即(N -1)的阶乘的一半。

如果只有4个目的地,那么计算所有12个可能旅行的距离都不会花费那么长的时间,一台典型的现代计算机只需要大约一微秒的时间就可以计算出来。如果是有10个目的地,则花费不到一秒的时间。但是如果是有15个目的地,需要12小时;如果是有20个目的地,则大约需要2000年。如果是有25个目的地时,必须将计算机运行约100亿年才能优化出路径:这大约与我们宇宙的寿命一样长。

不难看出,随着目的地的增加,可能路径的数量就却以数学阶乘式迅速增加,存在着大量可能的解决方案而难以一一枚举比较而得出答案。

这样的问题自古有之,属于现代运筹学、决策论等范畴,古人云:运筹帷幄,方能决胜千里,说的就是这个意思。

在数学上,这样的问题具体地被称为“旅行推销员问题”,英语:Travelling Salesman Problem,简称TSP,一本1832年的旅行推销员手册首次提到这个问题,包括了德国和瑞士的旅行实例。爱尔兰数学家WR Hamilton和英国数学家Thomas Kirkman在1800年代予以数学公式化。该问题的数学一般形式是1930年代在维也纳和哈佛大学首先进行研究,尤其是卡尔·门格(Karl Menger)定义了该问题。1930年代,Merrill M. Flood为寻求解决校车路线问题首次在数学上对其进行实际研究。在1950年代和1960年代,这个数学问题在欧美科学界变得越来越普遍。

在随后的几十年中,许多数学、计算机科学、化学、物理学和其他科学领域的科学家们对这个问题进行了研究。1970年代末期和1980年末取得了长足的进步,科学家们使用切割平面和分支定界方法成功地解决了多达2,392个城市的实例。在2006年,科学家计算了通过芯片布局问题给出的一个85,900个城市实例的最优行程,这是目前解决的最大实例。

在计算机科学中,对于一一枚举或穷举的方式又称为或穷举搜索,或蛮力搜索(brute-force search)。虽然蛮力搜索会找到一个较好的解决方案,但是其成本随着问题规模的增加而迅速爆炸性地增长而难以进行。

这样的问题在社会生活中具有大量的实际应用。这对于优化交货路线和供应链物流最短路径的选择直接相关。如果有前往一系列地址的一系列包裹,则需要采取最佳路线;如果计划行程、从差事旅行到公路旅行,需要不会浪费时间或里程;对于航空业、制造业或运输业,则希望尽快最有效地将旅客和货物送达目的地;等等。

这样的问题不仅仅是一个路径问题,它还体现在科学与技术中的许多组合优化问题中,体现在众多可能的组合中找到最佳解决方案,需要检查可能的每条合理方案,量化该方案所需的距离(或时间),然后选择最短(或最快)的方案。

比如,体现在如DNA测序中,快速的DNA测序方法的出现极大地推动了生物学和医学的研究和发现;出现在如微型芯片的设计和制造中的芯片布局问题;出现在如天文观测中天文学家希望在观察众多星体时减少在观察星体之间转动天文望远镜的时间,等等。

尽管这个问题在社会生活中具有普遍的重要性,但如果可能的目的地或方案太多,问题很快就变得相当复杂,无法确定是否找到了最佳路线,只能提出近似的解决方案。

如上图所示的34节点路径所示,一一枚举的穷举方法不足以解决节点过多的“旅行推销员问题”。但是,存在其他允许找到近似候选解的算法,然后可以检查这些解是否低于某个阈值。

所得到的解决方案将受到计算能力和算法质量的限制。一旦目的地或方案变得太多就很难用经典计算机解决,即使使用有史以来最好的算法,经典计算机也不能很快或很好地解决这个问题:计算机科学家称之为多项式时间(Polynomial time)问题。

幸运的是,使用量子计算机,许多计算上困难的问题,比如上面34节点路径问题,通过运用比如具有34量子位的量子计算机计算,解决难度将要小得多,并且计算所用时间远远地要少得多。量子计算机比传统计算机具有极大的计算优势。

如上图所示谷歌的由54个量子位组成的Sycamore量子处理器,去年在200秒内完成了需要一万台先进的超级计算机才能完成的一项任务。后来,IBM提出反驳,声称在像Summit之类的全球最强大的经典计算机系统上,该任务仅需2.5天。即便如此,量子计算机比传统计算机也已经具有了极为强大的“量子优势”。

当对量子位状态执行量子运算时,不会获得具有均等概率的平坦分布在所有可能的路径中。某些结果将具有异常高的概率,而某些结果将具有极低的概率,量子计算的结果可以预测最佳路径。

诸如“旅行推销员问题”,已经超出了经典计算机可以有效完成的工作范围,在多项式时间内,经典计算机甚至在理论上都无法解决,只能由量子计算机有效解决,量子计算机可以有效解决经典计算机不能解决的某些问题。如果存在经典解,那么量子解也可以。但是,即使不存在经典的解决方案,也可能有一个量子解决方案。

即使不存在这样的解决方案,并且对于经典计算机也可能不存在,量子计算机提供了无与伦比的希望。当用一一枚举的蛮力选择而无法解决诸如旅行推销员太多路径的问题时,不用完全放弃这种解决问题的简单实用的方法,量子计算革命将使之成为可能。