随机算法 通俗滴介绍随机算法思维

本人参考很多资料所做的研究生课件,转载可以,杜绝归为己有

随机算法介绍主讲 人：XXX

本人参考很多资料所做的研究生课件,转载可以,杜绝归为己有

什么是随机化 拉斯维加斯算法 蒙特卡洛算法 舍伍德算法 随机算法小结

本人参考很多资料所做的研究生课件,转载可以,杜绝归为己有

1.1 为什么随机化

第一章 什么是随机化算法第一节 为什么要随机化大部分算法都是确定性的，其确定性体现在以下几方面： 1.每个步骤都是确定的，即在某一步到底该做什么是确定的； 2.算法的结果是确定的，即输出地东西是什么事先是知道的； 3.步骤的数量是确定的，即算法的时间复杂性是确定的。 在此，要明白，确定性不是指你作为一个用户对一切事物都完全 掌控，而是指一旦输入确定，一切都已经确定，只不过你不知道而已。

本人参考很多资料所做的研究生课件,转载可以,杜绝归为己有

1.1 为什么随机化

比如说，一个学生考研面试完成后，我们已经做出了是否录取的 决定，只不过学生自己尚不知道而已，因而还会忐忑不安。 但是，确定性不一定是所有算法必须具备的一个特性。事实上， 我们有时候需要一些随机性。 在生活中需要随机的时候很多。在晚会上进行抽奖是随机抽奖， 彩票的号码是随机产生。如果抽奖和中奖是事先确定的，很多人会不 高兴(被安排中奖的人例外)。在操作系统中，其调度策略也有一个伪 随机调度策略。 因此，随机化所取得的作用是防止某种特别令人不满的结果出现。

本人参考很多资料所做的研究生课件,转载可以,杜绝归为己有

1.1 为什么随机化

面对考试，部分不知道如何解答的问题时，胡乱地写一通货任意选 择一个答案就是随机策略。随机策略是我们不知所措的时候所采取的 一种策略。 古人在面对疑难问题时的会采取占卜， 而占卜本身不会启示将 来发生的问题，它起的作用就是帮助占卜者作出决定。 因此，这里随机化有有了它的另一个用途：解答我们解答不了的问 题，虽然这个解答不一定正确。

本人参考很多资料所做的研究生课件,转载可以,杜绝归为己有

1.1 为什么随机化

将结论推广至算法： 随机化就是用来解答我们不能确定性解答的问题。

本人参考很多资料所做的研究生课件,转载可以,杜绝归为己有

1.1 为什么随机化

关于随机有两种针锋相对的观点： 1.一种认为，随机在这个世界上并不存在，一切都是冥冥之中自 有天意，或者说万事有因果联系； 2.另一种观点认为，这个世界本来就是随机的，从来不存在任何 因果联系，一个人的成功纯属运气，与能力无关。(还有第三派认为 既有随机又有因果) 在此，仅供大家思考，更加清晰认识随机思想。

本人参考很多资料所做的研究生课件,转载可以,杜绝归为己有

1.2 什么是随机化

第二节 什么是随机化算法随机化算法通俗来讲，就是将算法的某一步或某几步置于运气 的控制之下，即该算法在运行过程中的某一步或者某几步涉及一个随 机数，或者说其中的一个决策依赖于某种随机事件。 正如抛硬币，抛出一个正面执行一个操作，抛出反面执行另一个 操作。

本人参考很多资料所做的研究生课件,转载可以,杜绝归为己有

1.2 什么是随机化

从某种程度上看，随机 化算法就是跑硬币算法：在

某一步通过抛硬币来决定下 一步行动的方向

本人参考很多资料所做的研究生课件,转载可以,杜绝归为己有

1.2 什么是随机化

关于随机化目的，前面已经说过，主要有两个： 1)防止对手破坏，防止好人吃亏； 2)解决确定性算法不能解决的问题。 为第一种目的设计的随机化算法称为拉斯维加斯算法(Las Vegas Algorithms)。

本人参考很多资料所做的研究生课件,转载可以,杜绝归为己有

1.2 什么是随机化

拉斯维加斯是美国著名 赌城，对于一个赌徒来说， 什么最重要？当然是公平。 即需要防止赌场暗中做手脚， 以免赌徒吃亏。而随机化恰 恰是保证公平的重要手段。

Las Vegas

本人参考很多资料所做的研究生课件,转载可以,杜绝归为己有

1.2 什么是随机化

对拉斯维加斯算法而言，虽然使用了随机策略，但这个策略为的是 保证公平，因而计算结果仍然是正确的。而为了保证公平，就不免要费 点时间。因此，拉斯维加斯算法保障计算结果的正确性，但不保证算法 的时间效率。

本人参考很多资料所做的研究生课件,转载可以,杜绝归为己有

1.2 什么是随机化

为第二种目的设计的随机化算法称为蒙特卡罗算法(Monte Carlo Algorithms)。 不过，这里的蒙特卡罗与摩洛哥的赌场蒙特卡罗并无关系，发明算法的人是为了 纪念抚养过他的叔叔而命名的。(也许，他的叔叔名字含有蒙特卡罗。 ) 蒙特卡罗算法的主要目的是用来解决难解即复杂性很高的问题，其主要追 求的是算法的时间效率。为了这个效率，不得不牺牲准确性甚至是正确性。 因此，蒙特卡罗算法保证算法的运行时间，但不保证算法结果的正确性。

本人参考很多资料所做的研究生课件,转载可以,杜绝归为己有

第二章 拉斯维加斯算法拉斯维加斯算法的目的是保障公平，或者说不让最坏的情况产生， 我们增加一个随机步骤，而增加的随机步骤增添了成本，因此拉斯维加 斯算法是以牺牲效率来获取公平。 拉斯维加斯算法的特点是： 1)永远产生正确答案，即从不给出错误答案； 2)通常情况下算法的效率很好，但有时候会慢。 使用拉斯维加斯算法的基本思路是：产生一个合适的随机数，然后根 据随机数的取值决定下一步的行动。

本人参考很多资料所做的研究生课件,转载可以,杜绝归为己有

2 拉斯维加斯算法

一、一般概念拉斯维加斯算法有时运行成功，有时失败，需要反复运行同 一实例，直到成功为止。 BOOL las_vegas():解问题的某个实例的代码段。运行 成功 返回 true,否则返回false。

本人参考很多资料所做的研究生课件,转载可以,杜绝归为己有

2 拉斯维加斯算法

拉斯维加斯算法反复地运行下面的代码段： while (! las_vegas ( P (x))) ; 直到运行成功返回为止。

1. 2.

p(x):对输入实例成功地运行las_vegas的概率 若存在常数δ>0,使得对的所有实例p,都有p(x)>= δ ,则 失败的概率小于1- δ 。 3. 连续运行k次，失败的概率降低为(1- δ )k。 4. k充分大， (1- δ )k趋于0。