1700496367
婚礼上有107人，11张桌子，每张可容纳10人。这意味着大约有11107种可能的座位安排：这是一个112位的数字，是一个大于2000亿的天文数字，这个数字在可观测的宇宙中可使原子（仅仅80位数）数目相形见绌。在周六晚上，贝洛斯把这份工作提交到她的实验室电脑里进行处理。当她周一早上来上班的时候，它还在分析。她把迄今为止找到的最好的结果提取出来，然后把它放回到蛋白质设计上。
1700496368
1700496369
即使有一个高性能的实验室计算机集群和整整36小时的处理时间，这个程序也无法评估潜在座位安排的极小部分。可能性是真正能获得最高分的最佳解决方案，从来没有出现在它的排列中。不过，贝洛斯对计算机的分析结果感到满意。“它识别出我们已经遗忘的关系。”她说。计算机提供了令人愉快的、非传统的可能性，人类计划者甚至从来没有考虑过。例如，它提议将她的父母从家庭餐桌上“删除”，以他们多年未见的老朋友代之。计算机的最终建议是一项各方都同意的安排，尽管新娘的母亲忍不住做了一些人为调整。
1700496370
1700496371
就连普林斯顿实验室的总计算能力都无法找到完美的座位分配计划，这一点似乎令人十分惊讶。在我们讨论过的大多数领域中，直接的算法可以保证最佳的解决方案。但是，正如计算机科学家在过去几十年里所发现的那样，无论我们的计算机处理速度有多快，我们如何巧妙地对它们进行编程，一个问题的完美解决方案都是不存在的。事实上，没有人能像计算机科学家那样理解，在面对看似无法控制的挑战时，你既不应该永远辛苦工作，也不应该放弃，但我们将会看到第三种尝试。
1700496372
1700496373
1700496374
1700496375
1700496377
算法之美：指导工作与生活的算法 最优化的难度
1700496378
1700496379
美国内战之前，亚伯拉罕·林肯在起草《解放奴隶宣言》或发表葛底斯堡演说之前，在伊利诺伊州的斯普林菲尔德当过一段时间的“草原律师”，他每年都要去第八巡回审判庭两次，这样坚持了16年。作为一名巡回律师，这意味着要在14个不同郡县的城镇里进行巡回审理，在数周内要骑行数百英里。规划这些线路带来了一个自然的挑战：如何在尽可能少的英里数内到达所有要去的城镇，而不重复经过任何一个城镇。
1700496380
1700496381
这是一个数学家和计算机科学家所熟知的“约束优化”问题：如何找到一组变量的最佳排列，并给出特定的规则和记分法。事实上，这是最著名的优化问题。如果它在19世纪被研究过，它可能会被称为“草原律师问题”，如果它在20世纪初出现的话，它可能会被戏称为“投递无人机问题”。但就像秘书问题一样，它出现在20世纪中期，一个明确的名称是“旅行推销员问题”。
1700496382
1700496383
路线规划问题直到20世纪30年代才得到数学界的关注，但后来发展迅猛。数学家卡尔·门格尔在1930年谈到了“邮政信使问题”，他指出，没有比直接简单地尝试每一种可能性更容易的解决办法了。哈斯勒·惠特尼在1934年的普林斯顿大学演讲中提出了这个问题，当时数学家梅里尔·弗勒德（你可能记得第1章中所提到的，他也被认为是第一个提出解决秘书问题方法的人）已经开始思考这个问题了。20世纪40年代，当弗勒德搬到加州时，他把它介绍给兰德研究所的同事，这个问题的标志性名字最早出现在数学家茱莉亚·鲁宾逊1949年发表的论文中。当这个问题席卷数学圈时，它似乎并不容易普及。虽然许多当时最伟大的人都痴迷于它，但似乎没有人能够真正在这方面取得进展。
1700496384
1700496385
在旅行推销员这一例子中，问题不在于电脑（或数学家）是否能找到最短的路径：理论上，一个人可以简单地列出并测量所有的可能性。更确切地说，问题在于随着城镇数量的增加，连接它们的可能路线也会越来越多。路线仅仅是城镇的一个命令，所以用蛮力去一一尝试是可怕的“阶乘时间”——在计算上相当于把一副牌扔在空中从而进行分类，直到它们按顺序落到地上。
1700496386
1700496387
问题是：是否有希望做得更好？
1700496388
1700496389
几十年的研究几乎都没能很好地解决旅行推销员问题。例如，弗勒德在第一次遇到此问题后的20多年（也就是1956年）写道：“在处理这个问题时，很有可能需要采取一种完全不同的方法。事实上，可能不存在解决这个问题的通用方法，而且那些看似不可能的结果也是有价值的。”10年之后，这种情况更加糟糕。“我猜想，”杰克·埃德蒙兹写道，“对于旅行推销员问题，没有好的算法。”这些话是有预见性的。
1700496390
1700496391
1700496392
1700496393
1700496395
算法之美：指导工作与生活的算法 定义的难度
1700496396
1700496397
20世纪60年代中期，国家标准与技术研究所的埃德蒙兹和IBM（国际商业机器公司）的艾伦·科巴姆一起定义了一个可行的解决方案。他们断言，所谓的科巴姆——埃德蒙兹论断表明：如果一种算法运行在所谓的“多项式时间”，即O（n2）、O（n3），或者n的任意次方，那么该算法应该被认为是“有效的”。如果我们知道如何使用一种有效的算法来解决问题，那么该问题就会被认为是“可处理的”。相反，我们不知道如何解决的问题，被认为是“不可处理的”。“除了最小的尺度以外，最棘手的问题是电脑无法处理的问题，无论电脑多么强大。
1700496398
1700496399
这相当于计算机科学的核心洞察力。量化一个问题的难度是可能实现的。但有些问题就是……很难。
1700496400
1700496401
旅行推销员的问题在哪里？奇怪的是，我们还不太确定。1972年，在伯克利的理查德·卡普证明了旅行推销员问题与一个有争议的边缘性问题有关联，而这个问题还没有被明确证明是可解决的（或者是不可解决的）。但到目前为止，还没有找到解决这些问题的有效方法，大多数计算机科学家认为其中没有什么可找的。因此，在20世纪50年代所设想的旅行推销员问题的“不可能解决的结果”很可能就是它最终的命运。更重要的是，许多其他的寻找最优化问题，从政治战略到公共卫生到火灾安全等，都是同样棘手的问题。
1700496402
1700496403
但是对于那些与此类问题搏斗的计算机科学家来说，这个结论并不是故事的结局。相反，它更像是对武器的召唤。认定一个问题是不可解决的，你不能只是举手投降。正如日程安排专家简·卡雷尔·伦斯特拉告诉我们的：“当问题很困难时，并不意味着你就可以忘记它，这意味着它只是处于不同的状态。即使这是一个很厉害的敌人，你还是要打这场仗。”这就是这个领域所发现的无价之宝，我们也可以从中学到：如何最好地解决那些最佳答案似乎遥不可及的问题，如何学会放松。
1700496404
1700496405
1700496406
1700496407
1700496409
算法之美：指导工作与生活的算法 放松吧
1700496410
1700496411
伏尔泰
1700496412
1700496413
完美就是遇到优秀的敌人。
1700496414
1700496415
当别人告诉你要放松的时候，可能是因为你紧张，对要做的事情过于在意。当计算机科学家们面对一项艰巨的挑战时，他们的头脑也想放松，他们会传阅《放松方法或分散放松技巧介绍》（An Introduction to Relaxation Methods or Discrete Relaxation Techniques）一书。但是他们不会放松自己，他们只能会放松问题本身。
1700496416
[
上一页 ]
[ :1.700496367e+09 ]
[
下一页 ]