1700496506
算法之美：指导工作与生活的算法 09 随机性 何时应用随机？
1700496507
1700496508
迈克尔·拉宾
1700496509
1700496510
我必须承认，在这一领域工作多年之后，许多算法问题的随机性对我来说是非常神秘的。它是有效的，是起作用的。但它为什么是绝对神秘的又是如何保持的？
1700496511
1700496512
随机性似乎与理性相反，它是放弃问题的形式，也是最后一招。实际却远非如此。在计算机科学中，随机性的作用是惊人的且日益重要，这一点告诉我们，利用机遇可以成为解决最困难问题的一个有效的方法。事实上，有时没有任何其他方法是有用的。
1700496513
1700496514
与标准“确定性”算法不同，我们通常想象的电脑使用，每次都以完全相同的方式一个步骤紧随另一个之后，而随机算法是使用随机生成的数字来解决问题。最近，在计算机科学上的研究表明，在某些情况下，随机算法能够比所有已知的确定性算法更快地生成较难问题的答案。虽然它们并不能保证每一次都有最优解决方案，但随机算法可以用很少的时间就得到接近最优化的惊人答案，这都仅仅通过战略性地扔几个硬币就能确定。
1700496515
1700496516
这里有一个深刻的信息是，在某些问题上，随机的方法甚至比最好的确定性的方法都要优秀。有时候，解决问题的最好办法是依靠运气，而不是试图完全地分析出答案。
1700496517
1700496518
但仅知道随机性有用还不够，你需要知道什么时候该依靠运气，以什么方式，以及在什么程度上。最近的计算机科学提供了一些答案，尽管故事在几个世纪前就开始了。
1700496519
1700496520
1700496521
1700496522
1700496524
算法之美：指导工作与生活的算法 抽样
1700496525
1700496526
1777年，乔治-路易斯·雷克勒，布冯伯爵，发表一个有趣的概率分析结果。如果我们把一根针扔到一张画了线的纸上，这根针有多大可能性会和纸上的一条线相交呢？布冯的研究表明，如果针短于两条线之间的距离，答案是2/π乘以针的长度除以两线之间的距离。对于布冯来说，推导出这个公式就已经足够了。但在1812年，皮埃尔-西蒙·拉普拉斯（也就是我们在第6章提到的英雄）指出，这个结果还有另一层含义：一个人可以仅通过针掉在纸上来估计π的值。
1700496527
1700496528
拉普拉斯的提议指出了一个深刻的普遍真理：当我们想要了解一个复杂的量时，我们可以通过抽样来估计它的值。这正是他利用贝叶斯法则帮助我们完成工作的一种计算。事实上，有些人追随拉普拉斯的建议，进行了他所建议的实验，实验证实这是可能的（尽管不是特别有效）——用这个实践的方法去估计π的值。[1]
1700496529
1700496530
将针扔到画了线的纸上几千次是一种有趣的消遣（对一些人来说），但这需要计算机的发展，使取样成为一种实用的方法。之前，当数学家和物理学家们试着用随机性来解决问题时，他们必须辛苦地用手来计算，这就很难产生足够的样本以带来精确的结果。尤其是在第二次世界大战期间，洛斯阿拉莫斯美国国家实验室开发的计算机为计算带来了飞跃。
1700496531
1700496532
斯塔尼斯拉夫·乌拉姆是一位数学家，他曾助力于开发原子弹。他在波兰长大，1939年移居美国，并于1943年加入曼哈顿计划。在短暂回归学术界后，他于1946年回到了洛斯阿拉莫斯，从事热核武器设计。但他患了脑炎并做了脑部急救手术。当他从疾病中恢复过来时，他担心自己是否能恢复数学能力。
1700496533
1700496534
康复期间，乌拉姆玩了很多纸牌，尤其是单人纸牌（也称为克朗代克）。正如任何一个纸牌游戏玩家所知道的那样，某一些洗牌方式就是会让游戏无法获胜。乌拉姆也是这样玩的，他问自己一个自然的问题：洗出能获得胜利的好牌的概率是多少呢？
1700496535
1700496536
在像单人纸牌游戏这样的游戏中，你可以通过各种可能性的空间来推理，这几乎让你无法抗拒。翻第一张牌，还有52种可能的游戏来跟踪。翻第二张，对于第一张有51种可能性。这意味着在我们开始玩之前，已经有了成千上万种可能性。斯科特·菲茨杰拉德曾写道：“一流的智力，就是大脑中能够同时存在两种对立的想法，它们还能同时正常运转。”这或许是真的，但真正一流的智商、人类群者其他任何东西，并不能同时存在80×1067种可能的洗牌方式，且还依然有希望继续正常运转。
1700496537
1700496538
在尝试了一些复杂的组合计算并放弃之后，乌拉姆开始了一种不同的方法，它的优势就是其具有的简单性：去玩游戏就好了。
1700496539
1700496540
我注意到，可能更实用的（尝试）是放下牌，跟着过程发展进行实验，只是注意成功出现的比例，而不是试图计算出所有组合的可能性，这种可能性都是以指数倍递增的，最后的数量大得惊人，除了最基本的情况，没有其他办法估计。这在智力上即使不是完全的羞辱，结果也是惊人的，理性或传统思维的局限会给人一种没那么可怕的感觉。在一个非常复杂的问题中，实际的抽样要好于对所有的可能链都进行检验。
1700496541
1700496542
当他说“更好”时，请注意，他并不一定是指抽样分析比详尽的分析能为你提供更精确的答案：抽样过程中总会有一些错误存在，虽然可以通过确保样品真正的随机性以及提高样品的数量来减少这种错误出现的可能。他说“抽样会更好”的意思是，因为它最终会给你一个答案，而其他方法都无法做到。
1700496543
1700496544
乌拉姆的想法（抽样可以在其他分析方法失败时取得成功）在解决洛斯阿拉莫斯出现的一些困难的核物理问题时也至关重要。核反应是一种分支过程，可能也会像纸牌那样疯狂地增加：一个粒子分裂为两个，每一个都可能会撞击其他的，再导致它们分裂，一直这样发展下去。准确地计算出这一过程中某些特定结果的可能性，在许多粒子的相互作用下，都已经难到几乎不可能的程度。但如果进行模拟，每一次的交互作用就像打开一张新的纸牌，提供了一种选择。
1700496545
1700496546
乌拉姆与约翰·冯·诺伊曼进一步发展了这个想法，并与另一位来自曼哈顿计划的物理学家尼古拉斯·梅特罗波利斯合作，在洛斯阿拉莫斯的计算机上实现了这个方法。梅特罗波利斯将这一方法（将详尽的概率计算用抽样模拟进行代替）命名为蒙特卡罗法，这种方法因摩纳哥的蒙特卡罗赌场而得名，因为该场所同样依赖于变幻莫测的机会与运气。洛斯阿拉莫斯的团队便能够用它来解决核物理中的关键问题。今天，蒙特卡罗方法已经成为科学计算的基石之一。
1700496547
1700496548
许多如计算亚原子粒子的相互作用或在纸牌上的获胜机会这样的问题，是它们内在具有的概率，所以通过像蒙特卡罗法这样随机的方法来解决这些问题很有道理。但关于随机性的作用也许最让人惊讶的是，它可以被用在机会看似发挥不了作用的情况下。即使你想要回答一个只有“是”或“否”，“真”或“假”的答案的问题（其中没有任何其他可能性）掷几个骰子仍然是解决方案的一部分。
1700496549
1700496550
[1]有趣的是，偶然间，其中的一些实验对π值的估计似乎产生了比预期更好的效果，这表明他们可能是故意缩短了最佳停止点，或者干脆伪造。例如，1901年，意大利数学家马里奥·拉扎里尼据说做了3408次实验，并最终估计π≈355/113=3.1415929（π到小数点后7位的实际值是3.1415927）。但如果针与纸上的线相交的机会只有一次，那估计会没那么精准（3.1398或3.1433），这让拉扎里尼的报告显得可疑。拉普拉斯可能已经发现，我们可以使用贝叶斯法则来确认，这个结果不太可能来自一个有效的实验。
1700496551
1700496552
1700496553
1700496554
[
上一页 ]
[ :1.700496505e+09 ]
[
下一页 ]