企业官网建设流程全解析

邵阳网站建设,网站保定网站建设多少钱,洮南网站建设哪家专业,网站安全建设论文研究人员发现最优化的终极方法 1939年#xff0c;加州大学伯克利分校的一年级研究生乔治丹齐格在迟到后走进统计学课堂#xff0c;从黑板上抄下了两个问题#xff0c;以为那是课后作业。他后来回忆说#xff0c;这次作业“比往常更难”#xff0c;并为此向教授道歉#x…研究人员发现最优化的终极方法1939年加州大学伯克利分校的一年级研究生乔治·丹齐格在迟到后走进统计学课堂从黑板上抄下了两个问题以为那是课后作业。他后来回忆说这次作业“比往常更难”并为此向教授道歉说他多花了好几天才完成。几周后教授告诉他他解决了两道著名的统计学开放性问题。丹齐格的这项工作成为了他博士论文的基础并在几十年后成为了电影《心灵捕手》的灵感来源。丹齐格于1946年获得博士学位当时二战刚刚结束他很快成为了新成立的美国空军的数学顾问。与所有现代战争一样二战的胜负取决于对有限资源的审慎分配。但与以往的战争不同这场冲突是真正全球性的并且在很大程度上是通过纯粹的工业实力赢得的。美国可以简单地生产出比敌人更多的坦克、航空母舰和轰炸机。了解到这一点军方对最优化问题——即如何在可能涉及数百或数千个变量的情况下战略性地分配有限资源——产生了浓厚的兴趣。空军要求丹齐格找出解决此类优化问题的新方法。为此他发明了单纯形法这个算法借鉴了他在大约十年前解决黑板问题时开发出的一些数学技术。近80年后当需要在复杂约束下做出物流或供应链决策时单纯形法仍然是最广泛使用的工具之一。它高效且有效。“它一直运行得很快没人见过它不快”法国国家科学研究中心CNRS的索菲·休伯特斯说。与此同时一个奇特的特性长期以来给丹齐格的方法蒙上了一层阴影。1972年数学家们证明完成一项任务所需的时间可能随着约束数量的增加而呈指数级增长。因此无论该方法在实践中速度有多快理论分析始终提供最坏情况的假设即它可能需要指数级更长的时间。对于单纯形法“我们研究算法的传统工具不适用”休伯特斯说。但在将于12月计算机科学基础会议上发表的一篇新论文中休伯特斯和慕尼黑工业大学的博士研究生埃莱昂·巴赫似乎已经克服了这个问题。他们不仅使算法变得更快还从理论上解释了为什么长期以来担心的指数级运行时间在实践中并未出现。这项工作建立在2001年丹尼尔·斯皮尔曼和腾尚华的一项里程碑式成果之上被腾尚华称为“杰出[且]优美的”。“这是令人印象深刻的技术工作它巧妙地结合了先前研究路线中发展的许多思想[同时加入了]一些真正巧妙的新技术思想”未参与此项努力的波恩大学数学家拉兹洛·韦格说。最优几何单纯形法旨在解决此类问题假设一家家具公司生产衣柜、床和椅子。巧合的是每个衣柜的利润是每把椅子的三倍而每张床的利润是每把椅子的两倍。如果我们想用一个表达式来表示用a、b和c代表生产的家具数量那么总利润与3a 2b c成正比。为了最大化利润公司应该生产每种物品多少个答案取决于其面临的约束条件。假设公司每月最多能生产50件物品所以a b c小于或等于50。衣柜更难制作——最多只能生产20个——所以a小于或等于20。椅子需要特殊木材且供应有限所以c必须小于24。单纯形法将此类情况尽管通常涉及更多的变量转化为几何问题。想象一下在三维图形中绘制a、b和c的约束条件。如果a小于或等于20我们可以想象在三维图形中有一个平面垂直于a轴并在a 20处与之相交。我们会规定解必须位于该平面上或下方。同样我们可以创建与其他约束相关的边界。这些边界结合起来可以将空间分割成一个复杂的三维形状称为多面体。从几何角度看单纯形算法从开始到结束的执行过程涉及找到一条路径——例如从最低顶点到最高点——该路径包含最少的步骤或者等价地经过最少的边。步骤总数反过来与算法的运行时间或“复杂性”相关目标是以最少的步骤解决问题。在此图中找出从底部到顶部的最短路径相当于找出此类算法可以采用的最有效形式。如果不出意外找到一条快速直接的路径可能很容易首先原始形状可能比我们的例子复杂得多有更多的面、顶点和边。其次没有地图引导你。你无法看到要导航的整个物体。相反你从一个顶点开始决定首先沿哪条边前进。你在下一个顶点做同样的事情依此类推但不确定你选择的边将通往何方。如果你运气极差你可能在每个顶点都走错方向并陷入迷宫。“你可能要走最长的路径才能从A到B”巴赫说“因为在每个角落都有人告诉你应该走错误的方向。”这正是可能导致需要指数级时间才能完成的最坏情况。2001年斯皮尔曼和腾证明哪怕一丁点的随机性也有助于防止这种结果。回到之前的例子——冒着极大简化斯皮尔曼和腾论证的风险——假设在你遇到的每个拐角处都有六个选择。如果你总是被告知最差的方向你就会有麻烦。然而如果你依靠掷骰子你将有六分之五的机会避免最差的选择灾难就可能得以避免。在这个过程中引入随机性和不确定性的元素是合理的因为在现实世界中测量从来都不精确。斯皮尔曼和腾以完全不同的方式引入了随机性但他们表明运行时间永远不会比约束数量提高到某个固定幂次——例如n²——更差这是多项式时间的一个例子。这比指数时间例如2ⁿ的形式要好得多。尽管如此这并没有完全解决问题。他们的多项式时间值仍然相当高休伯特斯指出——其中包括一个指数为30的项这对于指数来说是一个相当大的数字。因此在过去的二十年里研究人员一直在逐步降低这个值。巴赫和休伯特斯在他们的新论文中依赖算法中更多的随机性证明运行时间保证远低于先前确定的值。他们还表明基于斯皮尔曼和腾建立的方法的算法不可能比他们获得的值更快。这告诉我们休伯特斯说“我们已经完全理解了[这种]单纯形法的模型。”“这标志着我们对[单纯形]算法的理解取得重大进展”波恩大学计算机科学家海科·罗格林说“首次为该方法在实际应用中的效率提供了真正令人信服的解释。”尽管如此休伯特斯并不认为这是终点。2001年从斯皮尔曼和腾开始的方法展示了如何将运行时间从指数级减少到多项式时间。下一个合乎逻辑的步骤是发明一种方法使其运行时间与约束数量成线性关系。“这是所有这些研究的北极星”她说。但这需要一种全新的策略。“我们短期内没有实现这一点的风险。”虽然巴赫和休伯特斯的努力对他们所在领域的同事具有理论意义但这项工作尚未产生任何直接的实际应用。尽管如此它可能有助于平息人们对当今依赖基于单纯形法的软件的一些担忧。“虽然实践实验表明这些问题总是在多项式时间内解决”设计线性规划软件的爱丁堡大学数学讲师朱利安·霍尔说但巴赫和休伯特斯为这种直觉提供了更强的数学支持。“因此现在更容易说服那些担心指数复杂性的人了。”更多精彩内容 请关注我的个人公众号 公众号办公AI智能小助手或者 我的个人博客 https://blog.qife122.com/对网络安全、黑客技术感兴趣的朋友可以关注我的安全公众号网络安全技术点滴分享