网易首页 > 网易号 > 正文 申请入驻

一个运行了80年的算法,我们现在才真正理解它?

0
分享至


来自Quanta Magazine

作者:Steve Nadis

机器之心编译

从你网购的包裹如何以最快速度送达,到航空公司如何规划数千架飞机的航线以节省燃料,背后都有一个近 80 岁「高龄」的数学方法在默默工作。它被誉为优化领域的基石,高效又令人信赖。然而,一个奇怪的事实是:几十年来,没有人能从理论上完美解释它为何如此高效。现在,这个谜题的最后一块拼图,终于被找到了。

1939 年,当时还是加州大学伯克利分校一年级研究生的乔治·丹齐格(George Dantzig)在一次统计学课上迟到了。他从黑板上抄下了两个问题,以为是家庭作业。他后来回忆说,他发现这次的作业「比平时难得多」,并为自己多花了好几天才完成而向教授道歉。

几周后,他的教授告诉他,他成功解决了统计学领域两个尚待解决的著名问题。

丹齐格的这项成果为他的博士论文奠定了基础,并在几十年后成为了电影《心灵捕手》的灵感来源。

乔治·丹齐格(George Dantzig,1914—2005),美国著名数学家,1947 年提出了单纯形法,被称为线性规划之父。

丹齐格在 1946 年,也就是二战刚结束后不久,获得了博士学位,并很快成为了新成立的美国空军的数学顾问。

与所有现代战争一样,第二次世界大战的胜负取决于对有限资源的审慎分配。但与以往的战争不同,这场冲突的规模是全球性的,其胜利在很大程度上是依靠纯粹的工业实力取得的。当时,美国能够生产比其敌人更多的坦克、航空母舰和轰炸机。

了解到这一点后,军方对优化问题产生了浓厚兴趣,即:在可能涉及成百上千个变量的情况下,如何战略性地分配有限的资源?

美国空军交给丹齐格的任务是,找出解决这类优化问题的新方法。作为回应,他发明了单纯形法 (simplex method),这个算法借鉴了他在近十年前解决黑板问题时所发展出的一些数学技巧。

近 80 年后,当需要在复杂的约束条件下做出后勤或供应链决策时,单纯形法仍然是使用最广泛的工具之一。它高效且行之有效。法国国家科学研究中心 (CNRS) 的 Sophie Huiberts 说道:「它一直运行得很快,没人见过它变慢过。」

与此同时,一个奇特的性质长期以来为丹齐格的方法蒙上了一层阴影。

1972 年,数学家们证明:该算法完成任务所需的时间可能会随着约束条件的数量呈指数级增长。

因此,无论该方法在实践中运行得多快,理论分析始终给出最坏情况下的场景,暗示它可能需要指数级更长的时间。对于单纯形法,「我们研究算法的传统工具并不奏效,」 Huiberts 说。

但在即将于 12 月在计算机科学基础(Foundations of Computer Science)会议上发表的一篇新论文中,Huiberts 和慕尼黑工业大学的博士生 Eleon Bach 似乎已经克服了这个问题。

  • 论文标题:Optimal Smoothed Analysis of the Simplex Method
  • 论文地址:https://arxiv.org/abs/2504.04197

他们不仅使该算法变得更快,还从理论上解释了这一现象:长期以来令人担忧的指数级运行时间在实践中并未出现。

这项成果建立在 Daniel Spielman 和滕尚华 (Shang-Hua Teng) 2001 年里程碑式成果《Smoothed Analysis of Algorithms: Why the Simplex Algorithm Usually Takes Polynomial Time》(arXiv:cs/0111050)之上。滕尚华表示,这项成果「卓越且优美」。

「这是一项非常了不起的技术工作,它巧妙地结合了以往研究中发展的许多思想,同时增加了一些非常好的新颖技术构想,」 波恩大学的数学家 László Végh 说道,他没有参与这项研究。

从几何角度来看,单纯形算法的整个执行过程,就是寻找一条路径(比方说,从底部顶点到最高点),并且这条路径包含的步骤最少,或者说,经过的边最少。总步数则与算法的运行时间(或「复杂度」)相关,目标是在最少的步数内解决问题。在这张图中找出从底部到顶部的最短路线,就相当于找出了这类算法所能采取的最有效形式。

如果不是因为以下两个问题,找到一条快速直接的路径可能会很容易:

  • 第一,原始形状可能比我们的例子复杂得多,有更多的面、顶点和边。
  • 第二,没有地图可以引导你。你无法看到你试图导航的整个物体。相反,你从一个顶点开始,选择要先沿着哪条边走。在下一个顶点你做同样的事情,依此类推,并不确定你选择的边会将你带到哪里。

如果你运气特别差,你可能会在每个顶点都走错方向,最终陷入迷宫。「你可能会走上从 A 点到 B 点的最长路径,」 Bach 说,「因为在每个拐角处,都有人告诉你该走向错误的方向。」 正是这种情况可能导致需要指数级时间才能完成的最坏情况。

2001 年,Spielman 和滕尚华证明:引入一点点随机性可以帮助避免这样的结果。

滕尚华(左)和 Daniel Spielman 在他们 2001 年的里程碑式成果中运用了随机性。

回到前面的例子(注意这里极大地简化了 Spielman 和滕尚华的论证),让我们假设你到达的每个拐角处都有六个选择。如果总是有人告诉你走最差的方向,你就会陷入困境。然而,如果你依靠掷骰子来决定,你将有六分之五的机会避开最差的选择,从而可能避免灾难。在过程中注入随机性和不确定性的元素是合理的,因为在现实世界中,测量永远不是精确的。

当然,Spielman 和滕尚华引入随机性的方式完全不同,但他们证明:运行时间绝不会比约束数量的某个固定次幂更差(例如 n² )—— 这就是所谓的多项式时间 (polynomial time)。这比指数时间(例如 2ⁿ 的形式)要好得多。

最优几何

单纯形法旨在解决这样一类问题:假设一家家具公司生产衣柜、床和椅子。巧合的是,每个衣柜的利润是椅子的三倍,而每张床的利润是椅子的两倍。如果我们想把这写成一个表达式,用 a、b 和 c 分别代表生产的家具数量,那么总利润将与 3a+2b+c 成正比。

为了实现利润最大化,公司应该各种物品各生产多少件呢?

答案取决于它面临的约束条件。比方说,该公司每月最多能生产 50 件产品,因此 a+b+c≤50。衣柜的制造难度更大 —— 假设产量不能超过 20 个,所以 a≤20;椅子需要特殊的木材,而且供应有限,所以 c 必须小于 24。

单纯形法可将这类情况(通常涉及更多变量)转化为一个几何问题。

想象一下在一个三维图表中绘制我们对 a、b 和 c 的约束条件。如果 a≤20,我们可以想象在三维图上有一个垂直于 a 轴的平面,在 a=20 的位置将其切开。我们会规定,我们的解必须位于该平面上或其下方的某个位置。同样,我们可以为其他约束条件创建边界。这些边界组合起来可以将空间分割成一个复杂的三维形状,称为多面体 (polyhedron)。

Sophie Huiberts 手持一个优化问题的几何模型。

然而,这并没有完全解决问题。

Huiberts 指出,他们的多项式时间值仍然相当高,其中包含一个 30 次幂的项,对于指数来说,这是一个相当大的数字。

因此,在过去二十年里,研究人员一直在逐步降低这个数值。

在 Bach 和 Huiberts 的新论文中,他们在算法中应用了更多的随机性,以证明运行时间可以保证远低于先前确立的水平。他们还证明:基于 Spielman 和滕尚华所建立方法的算法,其运行速度无法超越他们获得的值。Huiberts 说,这告诉我们,「我们完全理解了单纯形法的这个模型。」

研究主要结果

尽管如此,Huiberts 并不认为这是终点。

从 2001 年 Spielman 和滕尚华开始的方法展示了如何将运行时间从指数级降低到多项式级。下一个合理的目标是发明一种能够与约束数量成线性关系扩展的方法。「这是所有这项研究的北极星 (North Star),」她说。但这需要一种全新的策略。「我们短期内还不大可能实现它。」

虽然 Bach 和 Huiberts 的努力对他们领域的同行具有理论意义,但这项工作尚未产生任何直接的实际应用。

Eleon Bach 是这项新成果的作者之一。

尽管如此,它可能会平息一些人对于依赖当今基于单纯形法的软件可能产生的担忧。爱丁堡大学数学讲师、线性规划软件设计师 Julian Hall 表示:「虽然实践实验表明这些问题总是在多项式时间内解决」,但 Bach 和 Huiberts 的研究为这一直觉提供了更强的数学支持。「因此,现在更容易说服那些担心指数级复杂度的人了。」

参考链接:https://www.quantamagazine.org/researchers-discover-the-optimal-way-to-optimize-20251013/

特别声明:以上内容(如有图片或视频亦包括在内)为自媒体平台“网易号”用户上传并发布,本平台仅提供信息存储服务。

Notice: The content above (including the pictures and videos if any) is uploaded and posted by a user of NetEase Hao, which is a social media platform and only provides information storage services.

相关推荐
热点推荐
霍啟山未婚妻娜然起底 173cm俄蒙混血名模曾出演周杰倫MV女主

霍啟山未婚妻娜然起底 173cm俄蒙混血名模曾出演周杰倫MV女主

粤睇先生
2026-11-14 20:43:59
男子失业后断供房贷,靠跑外卖维生,法院:他家中有两名未成年子女,涉案房屋是全家唯一住所,暂不拍卖,付清欠付利息,其余部分分期还款

男子失业后断供房贷,靠跑外卖维生,法院:他家中有两名未成年子女,涉案房屋是全家唯一住所,暂不拍卖,付清欠付利息,其余部分分期还款

中国经济网
2026-11-16 11:04:07
中东:川普第一是别打垮伊朗让威胁继续,第二才是让内塔继续干

中东:川普第一是别打垮伊朗让威胁继续,第二才是让内塔继续干

邵旭峰域
2026-11-17 14:08:04
年薪5800万,却拖累全队!詹姆斯压力变大,你或许该被76人送走

年薪5800万,却拖累全队!詹姆斯压力变大,你或许该被76人送走

老梁体育漫谈
2026-11-17 00:14:30
19岁李嫣跟老爸聚餐!手不离烟动作熟练,170cm身材干瘪太像王菲

19岁李嫣跟老爸聚餐!手不离烟动作熟练,170cm身材干瘪太像王菲

一娱三分地
2025-08-14 13:28:27
一个90多岁的老太太,脚上蹬着15块钱的破鞋,住着武汉不起眼的小院,却一口气捐了1000万。

一个90多岁的老太太,脚上蹬着15块钱的破鞋,住着武汉不起眼的小院,却一口气捐了1000万。

回京历史梦
2026-11-10 17:50:30
“吃相和面相一样难看!”那个攥着铁叉护食的小女孩看着让人恶心,家长还发在网上,网友:从小不教就这下场

“吃相和面相一样难看!”那个攥着铁叉护食的小女孩看着让人恶心,家长还发在网上,网友:从小不教就这下场

番外行
2026-11-10 19:50:56
为啥大部分人不愿做肠镜?院士:做一次肠镜,或能保5年不得肠癌

为啥大部分人不愿做肠镜?院士:做一次肠镜,或能保5年不得肠癌

39健康网
2026-11-13 18:02:28
红军过草地其实仅用五六天,巨大非战斗减员源自哪里?有何隐情?

红军过草地其实仅用五六天,巨大非战斗减员源自哪里?有何隐情?

幻梦人生
2024-12-08 04:05:03
亚足联彻底不管了!东南亚版A3联赛火热进行,中超球队无缘参赛

亚足联彻底不管了!东南亚版A3联赛火热进行,中超球队无缘参赛

湖北的老球迷
2026-11-17 10:51:51
“华系车”赢麻!鸿蒙大涨139%,极狐涨112%,小米大跌11%

“华系车”赢麻!鸿蒙大涨139%,极狐涨112%,小米大跌11%

大厂财经社
2026-11-17 12:19:08
西媒直呼德国队5-0荷兰令人生畏,克洛普羞辱了哈维

西媒直呼德国队5-0荷兰令人生畏,克洛普羞辱了哈维

懂球帝
2026-11-17 18:03:15
浙江队官方:头部遭撞击的U15球员已接受手术,还处于术后监测中

浙江队官方:头部遭撞击的U15球员已接受手术,还处于术后监测中

懂球帝
2026-11-17 17:21:11
被支付宝砸中“一亿好运”的信小呆,8年后的现状,你绝对想不到

被支付宝砸中“一亿好运”的信小呆,8年后的现状,你绝对想不到

青木说
2026-11-17 17:37:54
周鹏火线归位!徐杰领衔广东12人名单曝光,首战死磕山东,这仇必须报!

周鹏火线归位!徐杰领衔广东12人名单曝光,首战死磕山东,这仇必须报!

林子说事
2026-11-17 14:04:17
黄仁勋正在考虑复职!新加坡亿万富豪:没有老黄,不会再有进一步投资

黄仁勋正在考虑复职!新加坡亿万富豪:没有老黄,不会再有进一步投资

新加坡椰子
2026-11-16 18:53:27
砸8亿清退1200名中国工程师,SpaceX强行去中国化,如今怎么样了

砸8亿清退1200名中国工程师,SpaceX强行去中国化,如今怎么样了

南宗历史
2026-09-17 13:38:03
宇树科技跌超10%,领跌物理AI板块

宇树科技跌超10%,领跌物理AI板块

澎湃新闻
2026-11-17 10:29:03
市场部负责人被带走,360证实:涉经济问题

市场部负责人被带走,360证实:涉经济问题

观察者网
2026-11-17 12:18:58
知名男演员凌晨酒驾撞车!警方介入,或面临刑事立案!本人致歉!他因这部经典作品被中国观众熟知↗

知名男演员凌晨酒驾撞车!警方介入,或面临刑事立案!本人致歉!他因这部经典作品被中国观众熟知↗

极目新闻
2026-11-15 09:03:13
2026-11-17 19:03:00
机器之心Pro incentive-icons
机器之心Pro
专业的人工智能媒体
14497文章数 142758关注度
往期回顾 全部

科技要闻

硅谷大佬组局,帮黄仁勋杀回来!

头条要闻

中国女子在希腊失踪半年 保险箱发现10万欧元现金

头条要闻

中国女子在希腊失踪半年 保险箱发现10万欧元现金

体育要闻

伪强队?拥4亿豪阵欧国联6连败+世界杯出局

娱乐要闻

陈晓楠对话厉娜和许飞引全网热议

财经要闻

10万人逼宫英伟达,黄仁勋要复职了?

汽车要闻

更豪华更好开 问界新M8细节升级见真章

态度原创

本地
艺术
教育
时尚
公开课

本地新闻

乌兰察布:以前种土豆,现在种Token

艺术要闻

漫天香氛,秋风醉人~杭州的秋天从不让人失望!13个地方,秒出大片!

教育要闻

济南市历下区燕山小学教育集团将出席2026第四届课博会,解码“做中学”视域下小学科学教育生态构建

自骂“烂人”的黄仁勋,冤不冤?

公开课

李玫瑾:为什么性格比能力更重要?

无障碍浏览 进入关怀版