# 拉斯维加斯算法

> 在电脑运算中，拉斯维加斯算法（Las Vegas algorithm）是一种永远给出正确解的随机化算法；也就是说，它总是给出正确结果，或是返回失败。 换言之，拉斯维加斯算法不赌结果的正确性，而是赌运算所用资源。一个简单的例子是随机快速排序，他的中心点虽然是随机选择的，但排序结果永远一致。与拉斯维加斯算法相对的是蒙地卡罗算法。

- ID: m04306
- 分类: decide
- 领域: 决策科学

## 定义

一类随机化算法，它总是给出正确的结果，但运行时间是不确定的（可能很快，也可能很久）。与之相对的是蒙特卡罗算法（运行时间确定，但结果可能出错）。脚手架作用： 定义了时间与确定性的权衡。在决策中，如果你追求绝对的正确（拉斯维加斯），你就必须容忍时间的不确定性；如果你必须在截止日期前给出方案（蒙特卡罗），你就必须容忍结果可能包含误差。

## 机制

拉斯维加斯算法是一种随机算法，其运行时间随机但结果永远正确，必要时靠随机重试保证正确。它与蒙特卡洛算法（结果可能错但时间固定）相对。

## 练习

把随机性引入搜索或选择步骤，若未得正确解就重采样直到成功。用期望时间分析其效率并设重试上限。

## 脚手架用法

定义了时间与确定性的权衡。在决策中，如果你追求绝对的正确（拉斯维加斯），你就必须容忍时间的不确定性；如果你必须在截止日期前给出方案（蒙特卡罗），你就必须容忍结果可能包含误差。

[阅读网页](https://thinkingmodels.site/entries/detail/m04306)