“四十不惑”　困扰科学家四十年的数学难题一朝得解

【美国《科学日报》网站10月15日报道】艾奥瓦大学（UI）的一名研究人员帮助解决了一个困扰计算机科学家40年之久的应用数学问题。仅在1年前，他还帮助解决了一个困扰科学家32年之久的问题。
UI亨利·B·蒂皮商学院管理科学教授库尔特·安施特赖歇尔与UI文理学院2000年计算机科学博士毕业生内森·布里克修斯合作，找到了用尽可能短的线路架在9＊4规格的栅格上把34个计算机部件连接起来的方法。该问题的正式名称是“ste36a”，建立在通用自动计算机设计的基础之上，由研究人员利昂·斯坦伯格于1961年提出。
安施特赖歇尔说，由于部件（它们之间总共有2625条连线）的可能位置只有36处，因此该接线问题似乎没有那么难。但是，可能的解决办法大约有“5E40”个，即5后面加上40个零。解决该问题的算法要考虑约18亿个子问题，因此在一台800兆赫的个人计算机上大约需要运算18天。
安施特赖歇尔说：“听起来似乎很长，但其实比所有人想到的可能需要的时间要短得多。”2000年夏天，安施特赖歇尔、布里克修斯和来自阿尔贡国家实验所的同行平均利用650台计算机，耗时1周，解决了1968年提出的“nu g 30”问题。
安施特赖歇尔说：“研究这类问题的人认为，该接线问题要比解决nu g 30问题困难，结果却简单得多。在解决nu g 30问题的过程中，我们学到了非常有效地加快解决斯坦伯格问题的技巧。”
该接线问题与nu g 30问题一样，是一个“二次分配问题”，或称QAP.这类问题出现在选址论领域，而且众所周知，极难解决。QAP的其他应用包括设计计算机芯片，安排医院内各科室的位置，以便使患者在科室之间行走的总距离最短。
现就职于微软公司的布里克修斯说，他在这类项目中获得的知识有助于自己在项目管理规划和程序调度方面的工作。他说：“微软没有参与解决该问题，但是ste36a和很多调度问题之间有内在的相似性。我们用来解决斯坦伯格问题的技巧也适合解决我在日常工作中遇到的问题。”