累积网新闻资讯
拉斯维加斯算法不会得到不正确的解。一旦用拉斯维加斯算法找到一个解，这个解就一定是正确解。但有时用拉斯维加斯算法找不到解。与蒙特卡罗算法类似，拉斯维加斯算法找到来自正确解的概率随着它所用的计算时间的增加而提高。对于所求解问题的任一实例，用同一拉斯维加斯算法反复对该实例求解足够多次，可使求解失败的概率任意小。
- 中文名 拉斯维加斯算法
- 优点 得到的解一定是正解
- 缺点 有时候找不到解
- 效果 求解失败的概率小
简介
在电脑运算中，拉斯维加斯算法是一种永远给出正确解的随机化算法;也就是说，它总是给出正确结果，或是返回来自失败。 换言之，拉斯维加斯算法不赌结果的正确性，而是赌运服写毫雷西握亲掌算所用资源。一个简单的例子是随机快速排序，他的中心点虽然是随机选择的，但排序结果永远一致。
算法
算法如下:
GSAT(Γ∈CNF)
begin
1. for i=1 to Max-tries
2. S=random(360百科Γ); // random assignment
3. for j=1 to Max-moves;
4. if S satisfies Γ then return(Yes);
5. else S=S with some v县压深举微ariable flipped to minimize the
number of unsatisfied clauses;
6. end;
7. end;
8. return (No satisfying truth assignm础酸班表ent found)
end
随机化算法
随机化算法(rando汉别例回项致坚微配mized algorithm)，是这样一种算法，在算法中使用了随机函数，且随机函数的返回值直接或者间接的影响了算法的执行流程或执行结果。就是将算法的某一步或某几步置于运气的控制之下，即该算法在运行的过程来自中的某一步或某几步涉良及一个随机决策，或者轮红孔班考问说其中的一个决策依赖于某种随机事件。
快速排序
快速排序使侵继亮左课价他用分治法(Divide 停视被and conquer)策略来继责把一个序列(list)分为两个子序列(sub-lists)。
步骤为:
- 叶油境烈从数列中挑出一个元素，称为"基准"(pivot)，
- 重新排序数列，所有先往宗台又比基准值小的元素摆360百科放在基准前面，所有比基准值大的元素摆在基准后面(相同的数可二落位获明穿独损盐至占以到任何一边)。在这个分割结束之后，该基准就处于数列的中间位置。这个称为分割(partition)操作。
- 递归地(recursively)把沉调谁秋乡甲经小于基准值元素的子数列和大于基准值元素的子数列排序。
递归到最底部时，数列的大小是零或一，也就是既则话亮证已经排序好了。这个算法一定会结束，因为在每果做次的迭代(iteration)中，它至少会把一个元素摆到它最后的位置去。