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
1700496508
迈克尔·拉宾
1700496509
1700496510
我必须承认，在这一领域工作多年之后，许多算法问题的随机性对我来说是非常神秘的。它是有效的，是起作用的。但它为什么是绝对神秘的又是如何保持的？
1700496511
1700496512
随机性似乎与理性相反，它是放弃问题的形式，也是最后一招。实际却远非如此。在计算机科学中，随机性的作用是惊人的且日益重要，这一点告诉我们，利用机遇可以成为解决最困难问题的一个有效的方法。事实上，有时没有任何其他方法是有用的。
1700496513
1700496514
与标准“确定性”算法不同，我们通常想象的电脑使用，每次都以完全相同的方式一个步骤紧随另一个之后，而随机算法是使用随机生成的数字来解决问题。最近，在计算机科学上的研究表明，在某些情况下，随机算法能够比所有已知的确定性算法更快地生成较难问题的答案。虽然它们并不能保证每一次都有最优解决方案，但随机算法可以用很少的时间就得到接近最优化的惊人答案，这都仅仅通过战略性地扔几个硬币就能确定。
1700496515
1700496516
这里有一个深刻的信息是，在某些问题上，随机的方法甚至比最好的确定性的方法都要优秀。有时候，解决问题的最好办法是依靠运气，而不是试图完全地分析出答案。
1700496517
1700496518
但仅知道随机性有用还不够，你需要知道什么时候该依靠运气，以什么方式，以及在什么程度上。最近的计算机科学提供了一些答案，尽管故事在几个世纪前就开始了。
1700496519
1700496520
1700496521
1700496522
[
上一页 ]
[ :1.700496473e+09 ]
[
下一页 ]