书城自然科学必谈的数学趣闻
29540200000032

第32章 怎样才能使线路最短

对于平面上三个点之间的线路最短问题解决以后,人们自然想到,平面上四个点及多于四个点之间的最短线路问题:即对于任意几个点之间的最短线路问题。数学家把它归纳为三个方面的问题:

1.不增加附加点,如何求得最短线路F1?

2.允许增加若干附加点,如何求得最短线路F2?加多少个点最好?加在何处?

3.F2比F1最多能缩短多少?

第1个问题已经圆满解决了。与第1个问题相比较,第2、3个问题有着本质的困难。美国贝尔实验室的亨利·波莱克博士和爱德加·吉尔伯特博士就第3个问题提出猜想:通过附加点得到的最短路线,最多只能比原来的缩短13.4%。他们的猜想在1989年由中国科学院应用数学研究所研究员堵丁柱同美国贝尔实验室的黄光明博士合作成功的给予了证明,从而从理论上彻底解决了第3个问题。这一成果受到国际数学界的广泛关注,并被誉为该领域1989~1990年的两项重大成果之一。

第2个问题至今还没有得到解决。如果这个问题解决了,最短路线问题就彻底解决了。那时,最短路线问题将给现代社会的电子、通讯、交通和能源等领域带来巨大的变化。超大规模的集成电路使得人们在1cm2的硅片上集成数以10万计的元器件,如果能解决好元器件之间的最短连接线的问题,则不仅能简化制造工艺,节约原料。而且能大大提高集成块的运算速度。随着电话的普及,上亿部电话之间的电话线的联网,也是十分复杂的最短路线问题。这个问题解决得好,既可少建很多交换台,又可节约大量的电话线,石油输油管道的分布、高速公路网的修建和民航航线的开辟等等,都亟待解决最短路线问题。我们期待着这一问题的早日解决,更希望将来在同学们中能出现解决这一问题的人。