-
拉斯維加斯算法
鎖定
拉斯維加斯算法不會得到不正確的解。一旦用拉斯維加斯算法找到一個解，這個解就一定是正確解。但有時用拉斯維加斯算法找不到解。與蒙特卡羅算法類似，拉斯維加斯算法找到正確解的概率隨着它所用的計算時間的增加而提高。對於所求解問題的任一實例，用同一拉斯維加斯算法反覆對該實例求解足夠多次，可使求解失敗的概率任意小。
- 中文名
- 拉斯維加斯算法
- 優 點
- 得到的解一定是正解
- 缺 點
- 有時候找不到解
- 效 果
- 求解失敗的概率小
拉斯維加斯算法簡介
在電腦運算中，拉斯維加斯算法是一種永遠給出正確解的隨機化算法；也就是説，它總是給出正確結果，或是返回失敗。 換言之，拉斯維加斯算法不賭結果的正確性，而是賭運算所用資源。一個簡單的例子是隨機快速排序，他的中心點雖然是隨機選擇的，但排序結果永遠一致。
[1]
拉斯維加斯算法算法
算法如下：
GSAT(Γ∈CNF)
begin
1. for i=1 to Max-tries
2. S=random(Γ); // random assignment
3. for j=1 to Max-moves;
4. if S satisfies Γ then return(Yes);
5. else S=S with some variable flipped to minimize the
number of unsatisfied clauses;
6. end;
7. end;
8. return (No satisfying truth assignment found)
end
拉斯維加斯算法隨機化算法
隨機化算法（randomized algorithm），是這樣一種算法，在算法中使用了隨機函數，且隨機函數的返回值直接或者間接的影響了算法的執行流程或執行結果。就是將算法的某一步或某幾步置於運氣的控制之下，即該算法在運行的過程中的某一步或某幾步涉及一個隨機決策，或者説其中的一個決策依賴於某種隨機事件。
[2]
拉斯維加斯算法快速排序
步驟為：
- 從數列中挑出一個元素，稱為“基準”（pivot），
- 重新排序數列，所有比基準值小的元素擺放在基準前面，所有比基準值大的元素擺在基準後面（相同的數可以到任何一邊）。在這個分割結束之後，該基準就處於數列的中間位置。這個稱為分割（partition）操作。
- 遞歸地（recursively）把小於基準值元素的子數列和大於基準值元素的子數列排序。
