随机算法的基本概念 例子 o判断函数f(x1,x2X)在区域D中是否恒为0, 2 f很复杂,不能数学化简,如何判断就很麻烦 o若随机产生一个n维坐标(r2)D,代入 得f(r,2rn)≠0,则可判定区域D内f不恒为0 o若对很多个随机产生的坐标进行测试,结果次 次均为0,则可说f0的概率是非常小 有不少问题,目前只有效率很差的确定性求解 算法,但用随机算法去求解,可以很快地获 得相当可信的结果 3随机算法的基本概念 ◼ 例子  判断函数 f(x1 ,x2 ,…xn )在区域 D中是否恒为0， f 很复杂，不能数学化简，如何判断就很麻烦  若随机产生一个n维坐标(r1 ,r2 ,… rn )D，代入 得f(r1 ,r2 ,… rn )≠0，则可判定区域D内f不恒为0  若对很多个随机产生的坐标进行测试，结果次 次均为0，则可说f≠0的概率是非常小 ◼ 有不少问题，目前只有效率很差的确定性求解 算法， 但用随机算法去求解，可以很快地获 得相当可信的结果 3