Randomized Algorithms¶
Intro¶
-
Deterministic Algorithms: 确定输入输出
-
Randomized Algorithms: 给定固定输入 随机输出
Example¶
Hiring Problem¶
Hiring condition
有n个候选人,在结束每一次面试的时候必须立即决定是否录用并且不能反悔
- 选择最好的candidate
- 在能够保证选出最好的candidate的情况下,尽可能介绍雇佣的次数
很简单直接的思路就是每次面试到了一个在已经面试结束的candidate中最好的,然后录用,也就是一个deterministic算法。
- 但是显然可以发现,如果candidate评估是递增的,那么这个算法会录用所有candidate,显然不是最优的。
Randomly Permute
对candidate进行随机排列后再采用确定算法,这样在期望下可以保证hire不超过
Prove
设定一个事件
对每个候选者
对
对所有
Variant
现在问题的变体是,如果成本有限,我们只能雇佣一个candi,这时怎样做才能最大化选到最好candi的概率
解决:
- Randomly Permute
- 面试前
个candidate,但是不雇佣 -
for i = k+1 to n:
如果第
个candidate比前 个candidate中最好的还要好,那么就雇佣
我们要计算选到最好candi的概率:
我们记等号右侧前面的事件为
A事件的概率比较好计算,对于A发生时B的概率,就是指第
求导可以得到当
3SAT Problem¶
对于一个给定的布尔公式是否存在一种赋值,使得该公式为真,例如:
其中
Monte Carlo
对于一个变量
可以计算出在期望下,随机赋值使得3SAT问题为真的概率为
定义:
我们知道
这个算法在时间复杂度上可以保证在
这种算法称为Monte Carlo算法
Las Vegas
我们现在想知道一个概率,就是每跑一次算法,满足条件的子句个数大于等于
大体的思路是:
取整数
所以
取
所以也就是说在期望下,我们需要跑
这种算法称为Las Vegas算法
QuickSort¶
A Pivot is good if: 能均使得分出的两个子集大小大于原数组的
-
Idea 1:randomly pick pivot,如果是好的就用,不是就重选
有
,期望下每一层递归需要 时间,所以总时间复杂度为 -
Idea 2:randomly pick pivot,use it anyway
同样有时间复杂度是
,
Implementation¶
程序中的random permutation方法:
- 设置随机键值
在
键值相同的概率不会超过$\frac{1}{n}
- Random Shuffle
留言