1700496357
算法之美：指导工作与生活的算法 08 松弛 顺其自然
1700496358
1700496359
2010年，梅根·贝洛斯正在普林斯顿大学攻读化学工程博士学位，她的研究围绕着如何将氨基酸放入蛋白质链中，以产生具有特殊特征的分子。（“如果你能最大限度地发挥两种蛋白质的结合能，就能成功地设计出一种生物功能的多肽抑制剂，这样你就能真正抑制疾病的进展。”）当时她也在为自己的婚礼做准备。在婚礼前，她为安排座位而苦恼。
1700496360
1700496361
现在已经有9个大学朋友坐在一起，贝洛斯正在发愁再让谁加入才能让这样一个小小的团体凑够10个人一桌。更糟糕的是，她数了数发现自己有11位亲戚。将谁从尊敬的父母席上分出去呢，她又该怎么向他们解释呢？还有像她的童年邻居和保姆，或者她父母的同事，他们在婚礼上根本不认识什么人怎么办？
1700496362
1700496363
这个问题似乎和她在实验室里研究的蛋白质问题一样困难，她被问题打败了。一天晚上，当她盯着座位图时，“我意识到我博士论文中的氨基酸和蛋白质跟我的婚礼上人们的座位之间确实存在着一对一的关系。”贝洛斯向她的未婚夫喊了一声，便开始写方程式。氨基酸变成了客人，结合能变成了相互关系，而分子之间所谓的“紧邻相互作用”就是邻近的相互作用。她可以利用自己研究中的算法来安排自己的婚礼。
1700496364
1700496365
贝洛斯想出一个用数字来定义所有宾客之间关系的方法。如果某个人不认识另一个人，他们会得到0分，如果他们认识，会得到1分，如果他们是夫妻，会得到50分。（新娘的妹妹给所有想坐在一起的人打10分，作为一种特殊的特权。）然后，贝洛斯指定了一些约束条件：例如最大桌容量和每桌的最低分值，这样就不会有一桌变成“混杂”组，坐的都是陌生人。她还整理了这个项目的目标：最大限度地提高每桌客人之间关系的得分。
1700496366
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
[
上一页 ]
[ :1.700496356e+09 ]
[
下一页 ]