前提：
拉斯维加斯属于概率算法的⼀种，那么对于概率算法就需要了解概率算法的特点和概率算法和确定性算法的区别。 我理解的概率算法和确定性算法的区别：
确定性算法对于每个输⼊实例的执⾏步骤，执⾏结果都是⼀定的。但概率算法是不定的。对于确定性算法有“平均执⾏时间”，对于概率算法有“期望执⾏时间”。 平均执⾏时间：输⼊规模⼀定的所有输⼊实例是等概率出现时，算法的平均执⾏时间。
数字监控系统
期望执⾏时间：反复解同⼀个输⼊实例所花的平均时间。
tl
概率算法的特点：
1.不可再现性：在同⼀个输⼊实例上，每次执⾏结果不尽相同。
2.分析困难：要求⼜概率论，统计学和数论的知识。
Las Vegas算法是概率算法的⼀种。
特点：算法获得的答案必定正确，但有时它仍根本就不到答案。不到答案时或者说陷⼊僵局时，可以重复运⾏算法，每次都有独⽴的机会求出解。所以成功的概率随着执⾏时间的增加⽽增加。
嘌呤核苷酸Las Vegas算法⼀般能⽐确定性算法更有效率，夸张的时候甚⾄是对于每⼀个输⼊实例都是如此。但它⼤的缺点是：算法的时间上界可能不存在，并且是在排除较⼩实例和特别好使的实例概率很⼩从⽽忽略不计的这两情况下，算法的时间上界不存在。
可以采⽤LV(x,y,success)来表⽰算法运⾏。
x：输⼊实例;
y：返回参数;
success：布尔值，true表⽰成功，false表⽰失败。
里斯本战略对于LV算法有如下定义：
p(x)：对于实例x，算法成功的概率
美的电磁炉电路图
s(x)：算法成功时的期望时间
网络巡警e(x)：算法失败时的期望时间
由于LV算法并不是每次都能求解出解。所以有顽固算法，知道求解出解为⽌，该算法如下：
Obstinate(x){
repeat LV(x,y,success);
until success;
return y;
}
那么如果⽤t(x)来表⽰Obstinate算法到⼀个正确解的期望时间。则
解释⼀下就是：t(x)：到正确解的期望时间，但是LV算法会有概率失败，那么到正确解的期望时
间就等于成功的概率乘以成功的期望时间+失败的概率乘（失败的期望时间+下⼀次正确解的期望时间）。由于下⼀次正确解的期望时间和这⼀次之间时完全独⽴的，所以也是
t(x)。
Las Vegas算法的应⽤：皇后问题。
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议