概述
随机算法是当前工业界和学术界都比较热的一个话题，从机器学习、数据挖掘到现在热得发烫的深度学习，无一没有随机算法的影子。随机算法起源于人类天性：赌博，最初用来解决一些不确定问题，现在已逐渐发展为一门独立的学科，深入到工程领域各学科。本文以一个简单的例子对基本的随机算法作简单介绍，深入了解请研读随机算法
寻宝问题
寻宝问题描述如下：
假设有10个山头，其中3个山头里面分别有价值10个金币宝藏，每个山头都有1个精灵守护，要进山寻宝，必须给精灵3个金币，当在一个山头找到宝藏后，精灵不允许继续再寻宝，哪个山头有宝藏未知，是否应该寻宝，采用何种策略寻宝？
因为每个山里面是否有宝藏是未知的，不妨对这10个山里面是否有宝藏进行编号，设为{0, 0, 0, 1, 0, 0, 1, 0, 0, 1}，其中的0表示没有宝藏，1表示有宝藏。
因为宝藏未知，按照什么样的顺序访问山头也是未知的。在这种情况下，有两种方案：
- 情况1: 给山头排个序，然后依次访问；
- 情况2: 随机访问；
对于情况1，假设排序为p=<0, 0, 0, 1, 0, 0, 1, 0, 0, 1>，则挖到宝藏会亏本2个金币。也就是说，一旦确定了访问山头的次序，并且这个次序是一个亏本的次序，则必然亏本。
对于情况2，随机访问有是什么样子呢？在这里不作具体的数学分析（分析也比较简单，利用离散均匀分布，计算期望）。随机访问一般有两种算法，一种是lasvegas算法，一种是monter carlo算法，随机算法的本质是算法的某一步骤中引入随机函数确定的某个值，从而导致不同相同的输入可能得到不同的结果。
lasvegas算法针对寻宝问题的代码为：
func LasVegas(input []int, key int) int {
retCount := 0
r := rand.New(rand.NewSource(time.Now().UnixNano()))
idxs := make([]int, 0)
for i, _ := range input {
idxs = append(idxs, i)
}
for count := 0; count < len(input); count++ {
// 从未选择的山头中选择一个
i := r.Intn(len(idxs))
retCount++
if input[idxs[i]] == key {
fmt.Println("===========")
return 10 - 3*retCount
}
idxs = lefts(idxs, idxs[i])
}
return 0 - 3*retCount
}
分析上面的代码，lasvegas算法的本质是只要存在解（在本例的寻宝中），会一直尝试，直到得到正确解。也就是：只要存在解，lasvegas算法最终一定会得到解。
如果寻宝问题中，山头数量足够多，而宝藏山头特别少，则按照lasvegas算法可能会亏损特别严重，得不偿失，因此，monter carlo算法对尝试的次数作了限制，这本质上就是一种尝试-止损原则，即先确定一个止损位，按照在止损范围内尝试获利。其代码为：
func MC(input []int, upperTryNum int, key int) int {
retCount := 0
r := rand.New(rand.NewSource(time.Now().UnixNano()))
idxs := make([]int, 0)
for i, _ := range input {
idxs = append(idxs, i)
}
for count := 0; count < len(input); count++ {
if retCount <= upperTryNum {
retCount++
i := r.Intn(len(idxs))
if input[i] == key {
return 10 - 3*retCount
}
idxs = lefts(idxs, idxs[i])
}
}
return 0 - upperTryNum
}
其中的upperTryNum就是尝试的次数。
通常情况下，Monte Carlo不一定会得到解，但是其损失是可以预见。针对寻宝这个例子，在本人机器上分别运行10次，其获益金币数结果为（每次运行结果都不同）：
lvs（lasvegas）: [4 1 -2 4 -8 7 7 7 4 1] , mcs（monter carlo）: [4 7 7 7 7 7 7 1 7 7]
大家可以在自己的机器上观测运行结果（ https://github.com/bjutJohnson/Algorithms/tree/master/src/probabilistic ） ，可以把尝试次数设置得更多一些，然后结合数学期望进行分析。
小结
随机算法虽然起源于不确定性问题，但是对于规模庞大的确定性问题如围棋、解密度空间稀疏等，都有与之相应的解决方案，特别是求解次优解的情况。
网友评论