拉斯维加斯算法1979

与拉斯维加斯算法相对的是蒙地卡罗算法。蒙地卡罗算法在一定的概率下可能返回错误的结果，但其运行时间是确定的或有上界的。

特性

随机性：算法在运行过程中使用随机数来影响其行为。

正确性保证：拉斯维加斯算法总是返回正确的结果。也就是说，它不会在计算结果上出错。

运行时间不确定：虽然结果总是正确的，但算法的运行时间是随机的，可能会有很大的波动。

使用拉斯维加斯算法的快速排序代码示例

一个经典的拉斯维加斯算法例子是快速排序的随机化版本。在这个版本中，算法随机选择一个枢轴（pivot）元素进行分区。虽然运行时间的期望值是 O(nlog n)，但实际运行时间会因为随机选择而有所不同。然而，无论运行时间如何，最终排序结果总是正确的。

伪代码示例

解释

randomizedQuickSort：这是主函数，用于对数组 A 的子数组 [low, high] 进行排序。

randomizedPartition：这是随机化的分区函数，它随机选择一个枢轴，并将其与当前子数组的最后一个元素交换，然后调用 partition 函数进行分区。

partition：这是标准的分区函数，使用最后一个元素作为枢轴，将小于等于枢轴的元素移动到枢轴的左边，大于枢轴的元素移动到右边，最后返回枢轴的位置。

swap：这是一个简单的交换函数，用于交换数组中的两个元素。

random：这是一个生成 [low, high] 范围内随机整数的函数。

In computing, a Las Vegas algorithm is a randomized algorithm that always gives correct results; that is, it always produces the correct result or it informs about the failure. However, the runtime of a Las Vegas algorithm differs depending on the input. The usual definition of a Las Vegas algorithm includes the restriction that the expected runtime be finite, where the expectation is carried out over the space of random information, or entropy, used in the algorithm. An alternative definition requires that a Las Vegas algorithm always terminates (is effective), but may output a symbol not part of the solution space to indicate failure in finding a solution. The nature of Las Vegas algorithms makes them suitable in situations where the number of possible solutions is limited, and where verifying the correctness of a candidate solution is relatively easy while finding a solution is complex.

Systematic search methods for computationally hard problems, such as some variants of the Davis–Putnam algorithm for propositional satisfiability (SAT), also utilize non-deterministic decisions, and can thus also be considered Las Vegas algorithms.

History

Las Vegas algorithms were introduced by László Babai in 1979, in the context of the graph isomorphism problem, as a dual to Monte Carlo algorithms. Babai introduced the term "Las Vegas algorithm" alongside an example involving coin flips: the algorithm depends on a series of independent coin flips, and there is a small chance of failure (no result). However, in contrast to Monte Carlo algorithms, the Las Vegas algorithm can guarantee the correctness of any reported result.

Example

As mentioned above, Las Vegas algorithms always return correct results. The code above illustrates this property. The goal is to find an index in the array a that contains the value 1. A variable k is generated randomly; after k is generated, k is used to index the array a. If this index contains the value 1, then k is returned; otherwise, the algorithm repeats this process until it finds 1.

Definition

This section provides the conditions that characterize an algorithm's being of Las Vegas type.

An algorithm A is a Las Vegas algorithm for problem class X, if

whenever for a given problem instance x∈X it returns a solution s, s is guaranteed to be a valid solution of x

on each given instance x, the run-time of A is a random variable RTA,x

There are three notions of completeness for Las Vegas algorithms:

Applications

Analogy

Las Vegas algorithms arise frequently in search problems. For example, one looking for some information online might search related websites for the desired information. The time complexity thus ranges from getting "lucky" and finding the content immediately, to being "unlucky" and spending large amounts of time. Once the right website is found, then there is no possibility of error.

Complexity class

The complexity class of decision problems that have Las Vegas algorithms with expected polynomial runtime is ZPP.

It turns out that （公式略）

which is intimately connected with the way Las Vegas algorithms are sometimes constructed.

Optimal Las Vegas algorithm

In order to make a Las Vegas algorithm optimal, the expected run time should be minimized. This can be done by:

The Las Vegas algorithm A(x) runs repeatedly for some number t1 steps. If A(x) stops during the run time then A(x) is done; otherwise, repeat the process from the beginning for another t2 steps, and so on.

Designing a strategy that is optimal among all strategies for A(x), given the full information about the distribution of TA(x).

Relation to Monte Carlo algorithms

Las Vegas algorithms can be contrasted with Monte Carlo algorithms, in which the resources used are bounded but the answer may be incorrect with a certain (typically small) probability. A Las Vegas algorithm can be converted into a Monte Carlo algorithm by running it for set time and generating a random answer when it fails to terminate.