|
|
知识路径： > 计算机系统基础知识 > 计算机软件知识 > 数据结构与算法知识 > 算法设计与分析 > 概率算法 >
|
|
相关知识点：1个
|
|
|
|
|
一般情况下，可将概率算法大致分为数值概率算法、蒙特卡罗算法、拉斯维加斯算法和舍伍德算法4类。
|
|
|
|
（1）数值概率算法常用于数值问题的求解。这类算法得到的往往是近似解，且近似解的精度随计算时间的增加不断提高。在多数情况下，要计算出问题的精确解是不可能的或没有必要的，因此数值概率算法可得到相当满意的解。
|
|
|
|
（2）蒙特卡罗算法用于求问题的精确解。用蒙特卡罗算法求得问题的一个解，但这个解未必是正确的。求得正确解的概率依赖于算法所用的时间。算法所用的时间越多，得到正确解的概率就越高。蒙特卡罗算法的缺点也在于此。一般情况下，无法有效地判定所得到的解一定正确。
|
|
|
|
（3）拉斯维加斯算法不会得到不正确的解。一旦用拉斯维加斯算法找到一个解，这个解一定是正确解。拉斯维加斯算法找到正确解的概率随着它所用的计算时间的增加而提高。对于所求解问题的任一实例，用同一拉斯维加斯算法反复对该实例求解足够多次，可使求解失效的概率任意小。
|
|
|
|
（4）舍伍德算法总能求得问题的一个解，且所求得的解总是正确的。当一个确定性算法在最坏情况下的计算复杂度与其在平均情况下的计算复杂度有较大差别时，可在这个确定性算法中引入随机性将它改造成一个舍伍德算法，消除或减少问题的好坏实例间的这种差别。舍伍德算法的精髓不是避免算法的最坏情况行为，而是设法消除这种最坏情形行为与特定实例之间的关联性。
|
|
|
