1700496458
算法之美：指导工作与生活的算法 只是一张超速罚单：拉格朗日松弛算法
1700496459
1700496460
《公主新娘》
1700496461
1700496462
维齐尼：不可思议！
1700496463
1700496464
伊尼戈·蒙托亚：你一直用这个词。我认为这个词的真正意思可能和你想表达的不太一样。
1700496465
1700496466
有一天，当布莱恩还是个孩子的时候，他向他母亲抱怨他必须做的事情：他的家庭作业、他的家务……“从技术上讲，你做任何事情都不是必需的，”他的母亲回答道，“你不必按照老师说的去做。你不必按我说的去做。你甚至不必遵守法律。所有事情都会产生后果，你要想好你是否愿意承担这些后果。”
1700496467
1700496468
布莱恩的童心被打击了。这是一种强有力的信息，是一种意识、责任、道德判断的觉醒。这也是另一种东西：一种强大的计算技术，被称为拉格朗日松弛算法。拉格朗日松弛算法背后的理念很简单。优化问题有两个部分：规则和计分。在拉格朗日松弛法中，我们采用一些问题的约束并将它们放入计分系统中。也就是说，我们采用那些看似不可能的方法，然后将其降级为高昂代价。（例如，在婚礼座位最优化问题中，我们可能会放松对每桌最多10人的限制，这样可以让桌子上的人坐得满满的，但也会有一些空间上的弊端）当一个优化问题的约束说：“做这个，或者其他！”拉格朗日松弛会回答：“如果不做又会怎样呢？”一旦我们可以越界，哪怕只是一点点，甚至付出高昂的代价，那么原先无法处理的问题就会变得可以处理了。
1700496469
1700496470
拉格朗日松弛算法是关于旅行销售员问题和计算机科学中的其他难题的理论文献的重要组成部分。它们也是许多实际应用程序的关键工具。举个例子，想想卡内基-梅隆大学的迈克尔·特里克（我们在第3章中提到过他），他负责美国职业棒球大联盟和美国大学生篮球联赛的很多日程安排。我们没有提到过他是如何做事的。每年的时间表的组成都是一个巨大的离散优化问题，因为过于复杂，任何计算机都无法直接解决。所以每年特里克和他在体育日程安排组的其他同事们都用拉格朗日松弛算法来完成任务。每次你打开电视或在体育场坐下时，你都知道当晚的球场上有哪些球队要打比赛。这并不一定是最优匹配，但已经非常接近最优了。为此，我们不仅要感谢迈克尔·特里克，更要感谢18世纪法国数学家约瑟夫·路易斯·拉格朗日。
1700496471
1700496472
在安排一个体育赛季的赛事时，特里克发现我们之前所讨论的连续松弛并不一定会让他的生活变得更轻松。“如果游戏玩了一半就结束，你便没有得到任何有用的东西。”最终得到多少派对邀请或消防车的分配结果是一回事，如果有必要的话，这些数字都可以被四舍五入。但是在体育运动中，整数限制——有多少个队打一场比赛，总共有多少场比赛是在进行中，以及每支球队会和其他队交手多少次，在这些情况下都太强大了。“所以我们不能在这个方向上松弛，我们必须保持模型的基本（离散）部分。”
1700496473
1700496474
尽管如此，我们必须做一些事情来处理这个问题的复杂性。因此，“我们必须与联盟合作，松弛他们可能想拥有的一些约束”，特里克解释说。在一个体育赛季中，这种约束的数量是巨大的，它不仅包括来自联盟基本结构的要求，还包括各种各样的特殊要求和道德准则。联赛乐于接受赛季后半段与前半段是完全一致的，只是主场和客场的比赛是相反的。某些联赛不想要这样的结构，但仍然要求在第一轮对阵完所有其他球队之前不要跟一个队交手第二次。一些联赛坚持让最著名的球队在决赛阶段才出场，一些球队不能在特定的时间进行主场比赛，因为他们的球场上还有其他比赛有冲突。在美国大学生篮球联赛的例子中，特里克还必须考虑来自转播比赛的电视网络的限制。电视频道早就提前决定好一年里转播什么样的节目，并将之定义为“A类比赛”和“B类比赛”（也就是能吸引最多观众的比赛）。例如，杜克大学对阵北卡罗来纳大学的比赛一直是A类比赛。各频道随之安排每周有一场A类比赛和一场B类比赛，但这两场比赛也不能同时进行，以免分散收视率。
1700496475
1700496476
不出意料，考虑到所有这些要求，特里克便发现，只要通过软化这些严格的约束条件就能使计算体育赛程成为可能。
1700496477
1700496478
一般来说，当人们第一次拿一份体育活动安排给我们时，他们会说：“我们从不做x，也从不做y。”然后我们看了他们的日程安排，我们说：“嗯，去年你做过两次x，做过三次y。”然后对方会说：“哦，是啊，好吧。除此之外，我们从来没有这样做过。”然后我们再看回前年……我们通常会意识到有些事情是他们认为永远不会做的。棒球界的人认为，扬基队和大都会队从来都不同时进行主场比赛。但这并不是真的，从不是真的。他们也许在一年的同一天里会有3场，或许是6场比赛同时进行。但是对于整个赛季，每个球队都有81场主场比赛，这又是相当罕见的，人们可能就会忘了这回事。
1700496479
1700496480
有时，需要一些外交手腕，但拉格朗日松弛算法通过让一些不可能的事情被降级为惩罚，将匪夷所思的变成不可取的，使我们取得进步。正如特里克所说，与其花费时间去寻找一个无法达到的完美答案，使用拉格朗日松弛法可以让他问一些问题，比如“你的答案能怎样的接近”。事实证明，如果已经足够接近了，就足以让每个人都快乐，比如联盟、学校、网络，以及点燃每年3月疯狂的炙热火焰（即美国大学篮球繁忙冠军赛季）。
1700496481
1700496482
1700496483
1700496484
1700496486
算法之美：指导工作与生活的算法 学会松弛
1700496487
1700496488
在计算问题展现给我们的各种方式中，优化问题（一部分是目标，一部分是规则）仍可以说是最常见的。而离散优化问题，我们的选择是二选一，没有中间地带，这是最典型的选择。在这里，计算机科学做出了一个令人沮丧的结论。许多离散优化问题确实很难。该领域最杰出的人物都想不出一个得到完美答案的方法，而他们实际上是更致力于证明不存在这样的方法，而不是寻找方法。
1700496489
1700496490
如果没有其他的事情，这应该会让我们感到些许安慰。如果我们面对的问题看起来粗糙、棘手、无法处理——好吧，那我们可能是对的。拥有一台电脑也未必能帮上忙。
1700496491
1700496492
至少，除非我们能学会松弛才能有所进展。
1700496493
1700496494
有很多方法可以对一个问题进行松弛，我们已经看到了三个最重要的问题。首先，约束松弛，简单地消除一些约束，在回到现实之前，先在更宽松的问题上取得进展。第二，持续松弛，将离散的或二进制的选择变成连续体：当决定是选冰红茶还是柠檬水时，先想象一个50：50的“阿诺德·帕尔默”混合，然后再向上或向下延展。第三，拉格朗日松弛，把不可能的变成仅仅是惩罚，要学会扭曲规则的艺术（或打破规则，并接受后果）。例如，摇滚乐队在决定将哪些歌曲放入一个有限的专辑中时，就要面对计算机科学家称之为的“背包问题”——将一组不同大小和重要性的项目装进一个有限的集合中的难题。在严格的公式中，背包问题是众所周知的棘手问题，但这并不妨碍我们松弛的摇滚明星们做决定。正如几个著名的例子所证明的那样，有时候稍微超过城市的宵禁，并付出相应的惩罚，好过把节目限制在适当的时间内。事实上，即使你没有违规，你也可以想象它具有启发性。
1700496495
1700496496
保守的英国专栏作家克里斯托弗·布克说，“当我们无意识地受到想法的驱动开始行动时，一段时间里似乎一切顺利”，但因为“这虚幻永远不可能成为现实”，它将不可避免地导致一个多阶段崩溃：“梦”“挫折”“梦魇”“爆炸”。“计算机科学描绘了一个戏剧性的乐观看法。再说一遍，作为一种最优化技巧，松弛就是被个人想法所驱使。也许这是造成这种差异的部分原因。
1700496497
1700496498
松弛给我们带来了许多好处。首先，它保证了真正解决方案的质量。如果我们在制定日程，想象我们可以神奇地在镇上随意穿梭，这将会让我们瞬间明白，每天只能安排8个时长为一小时的会议。这样一个固定的设置预期可能在我们面对完整的问题时十分有用。第二，松弛方式的设计是为了与现实相匹配，这给了我们从另一个方向解决问题提供了范围。当连续松弛告诉我们给某些人打半支疫苗时，我们可以给那些人直接注射一支或多支疫苗，最终获得一个容易计算的解决方案——最多需要接种两次疫苗。也许我们可以接受这一点。
1700496499
1700496500
每当我们遇到一个故障时（除非我们愿意花无数时间去追求完美），难题就会要求我们不许躲避，想象更简单的版本，并首先解决这些问题。当应用正确时，这不仅是一种个人想法，也不是幻想或白日梦。这是我们取得进步的最好方法之一。
1700496501
1700496502
1700496503
1700496504
1700496506
算法之美：指导工作与生活的算法 09 随机性 何时应用随机？
1700496507
[
上一页 ]
[ :1.700496458e+09 ]
[
下一页 ]