补充资料：概率算法

概率算法
probabilistic algorithm

gail口suanfa概率算法《p均babilistlc al，dt加m)带有随机操作的一类算法，又称作随机算法。算法在计算的某一步或某些步产生符合规定要求的随机数，然后根据产生出的随机数决定下一步的计算。例如，在计算的某一步有两种选择:执行A或执行B。此时随机产生一个O或1。若产生的是O则执行A，若产生的是1则执行B。这相当于根据掷一枚硬币的结果(正面或反面)决定下一步的计算。 将概率的思想用到算法中始于数值计算，在计算方法中通常称作蒙特卡罗法，是在20世纪40年代中叶提出的。它的基本思想是建立概率模型，通过统计模拟或抽样得到间题的近似解。通常要求计算结果的期望值等于问题的精确解，并且计算误差的期望值随可供使用的时间增加而减小。近20年来概率算法在非数值计算中得到很好的应用。例如，已经设计出关于排序和搜索、素数判定、有限域上的多项式分解和求根、字符申的模式匹配等方面的有效概率算法。概率算法同样也应用到并行计算中，得到概率并行算法。 M.O.F滋bin在1976年提出一个判定素数的概率算法，其理论根据是:当n是合数时，在1到n一1的整数中有一半以上是n为合数的“见证人”。算法的基本做法是:随机地产生一个1与n一1之间的整数b，检查b是否是。为合数的“见证人”。若b是“见证人”，则计算结束，并得出n为合数的结论;否则重复这个过程。至多进行k次，若产生的k个随机数b都不是n为合数的“见证人”，则得出n为素数的结论。算法所需要的时间为O(1褚n)。当计算的结果是n为合数时，结果肯定是正确的。但是，“n为素数”的结果有可能是错误的。此时n为合数的概率，即得出错误结果的概率不超过1/2盛。当k足够大时，这是一个很小的数。譬如，取k二10，错误的概率小于0.001。这已经是在实验中不大可能发生的事件了。实验表明，算法在实际使用中几乎不会给出错误的结论。 这类概率算法对每一个实例的计算时间是确定的，计算结果服从某种概率分布。也就是说，不能保证算法给出的解总是正确的，只能保证得出非正确解的概率足够小。还有一类概率算法给出的解总是正确的，而执行时间服从某种概率分布。算法执行时间的期望值通常是输人规模的多项式，但不能排除运行很长时间的可能性甚至有可能给不出解。当然，出现这种坏情况的概率很小。 概率算法通常能大大地提高效率。但有迹象表明，对于NP完全问题很可能不存在有效的概率算法。用计算机执行概率算法时，要用伪随机数代替随机数。大多数程序设计语言都有伪语言随机数发生器，用来产生伪随机数。

说明：补充资料仅用于学习参考，请勿用于其它任何用途。