Workflow
多项式时间
icon
Search documents
一个运行了80年的算法,我们现在才真正理解它?
机器之心· 2025-10-19 03:48
来自 Quanta Magazine 作者: Steve Nadis 机器之心编译 从你网购的包裹如何以最快速度送达,到航空公司如何规划数千架飞机的航线以节省燃料,背后都有一个近 80 岁「高龄」的数学方法在默默 工作。它被誉为优化领域的基石,高效又令人信赖。然而,一个奇怪的事实是:几十年来,没有人能从理论上完美解释它为何如此高效。现 在,这个谜题的最后一块拼图,终于被找到了。 1939 年,当时还是加州大学伯克利分校一年级研究生的 乔治·丹齐格(George Dantzig)在一次统计学课上迟到了。他从黑板上抄下了两个问题,以为是家庭作 业。他后来回忆说,他发现这次的作业「比平时难得多」,并为自己多花了好几天才完成而向教授道歉。 几周后,他的教授告诉他,他成功解决了统计学领域两个尚待解决的 著名 问题。 丹齐格 的这项成果为他的博士论文奠定了基础,并在几十年后成为了电影《心灵捕手》的灵感来源。 乔治 · 丹齐格( George Dantzig , 1914—2005 ),美国著名数学家, 1947 年提出了单纯形法,被称为线性规划之父。 丹齐格 在 1946 年,也就是二战刚结束后不久,获得了博士学位,并很 ...