1700496435
1700496436
1700496438
算法之美：指导工作与生活的算法 无数灰色地带：持续的松弛
1700496439
1700496440
旅行推销员问题，就像梅根·贝洛斯寻找最佳座位安排的问题一样，是一种特殊的最优化问题，称为“离散优化”，即在解决方案中没有平滑的连续统一体。推销员要么到这个镇子，要么到那个镇，你要么在5号桌，要么在6号桌。两者之间没有灰色地带。
1700496441
1700496442
这样的离散优化问题就在我们身边。例如，在城市里，规划者试图把消防车放置在一个能在同样固定时间内（比如5分钟），到达区内不同住宅的地方。从数学上讲，每辆消防车都能在5分钟内从所处位置到达任何可以到达的区内住宅。挑战在于找到最小的地点集合，这样所有的房子都能被覆盖。威斯康星大学麦迪逊分校的劳拉·艾伯特·麦克莱说：“整个火灾和紧急情况领域都采用了这种覆盖模型，而且效果很好。”“这是一个很好的、很清晰的模型。”但由于一辆消防车要么存在于某个地点，要么不在这个地方，因此计算最小集就涉及离散优化。正如麦克莱所指出的，“这就是很多问题在计算上变得困难的地方，因为你不能这样做一半，那样做一半”。
1700496443
1700496444
离散优化的挑战也出现在社会环境中。想象一下，你想为你所有的朋友和熟人举办聚会，却不想花邀请信所需要的信封和邮票的钱。因此，你可以决定向几位关系好的朋友发出邀请，告诉他们“把我们认识的人都带过来”。你最理想的发现是，你的最小朋友圈认识你社交圈子里的所有人，这可以让你“舔”最少的信封，还能让每一个人都能参加。当然，这听起来似乎是为了省买邮票的几块钱，但这恰恰是政治竞选活动经理和企业营销人员想要解决的问题，即最有效地传播他们的信息。这也是流行病学家研究的问题，例如，给人口中最低数量的人接种疫苗，以保护整个社会免受传染病的威胁。
1700496445
1700496446
正如我们所指出的，离散优化对整数的要求（例如一个消防部门只可以有一辆、两辆、或三辆车在车库里，而不是两辆半或π辆消防车）使离散优化问题难以解决。事实上，消防车问题和派对邀请问题都是难以解决的：没有普遍有效的解决方案。但是，事实证明，确实存在许多有效的策略来解决这些问题的连续版本，其中任何分数或小数都是可能的解决方案。研究人员面对一个离散优化问题，可能会很羡慕地盯着这些策略，但他们可以做的还很多。他们可以试着把离散问题放宽到一个连续问题，然后看看会发生什么。
1700496447
1700496448
在邀请问题上，将其从离散优化松弛到连续优化，意味着一个解决方案可能会告诉我们向某一人发送一个1/4的邀请，问另外一个人发2/3。这到底是什么意思？很明显，这不是最初问题的答案，但是，就像最小生成树一样，它确实给了我们一个起点。有了轻松的解决方案，我们可以决定如何将这些分数转换回现实。例如，我们可以选择在必要的时候简单地把它们围起来，向每个收到“半个邀请”或以上的人发出邀请。我们也可以把这些分数当作概率来解释，例如在松弛的解决方案告诉我们要放半辆消防车的地方分别扔硬币，然后实际上，只在最后扔出硬币头像一面的地方放置消防车。在这两个例子中，随着这些分数转化为整数，在原始的离散问题中，我们便会有一个有意义的解决方案。
1700496449
1700496450
最后一步，和任何松弛方式一样，那就是问自己，与我们可能想出的最好的解决方案相比，这个解决方案有多好，我们可能会用详尽的方法检查每一个可能的答案。事实证明，对于邀请函问题，连续松弛与凑整将给我们一个容易计算的不错的解决方案：数学保证你能邀请到所有你想要邀请的人，而最多发出计算机通过直接计算所给出的最佳解决方案两倍的邀请。同样，在消防车问题上，连续松弛问题很可能很快地让我们在一个舒适的范围内得到最佳答案。
1700496451
1700496452
持续松弛并不是一颗神奇的子弹：它仍然没有给我们提供有效的方法以得到真正的最佳答案，只能得出它们的近似值。但是，提供最佳邮寄或接种方案的两倍选择仍远比未优化的选择要好。
1700496453
1700496454
1700496455
1700496456
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
[
上一页 ]
[ :1.700496435e+09 ]
[
下一页 ]