文档介绍：凸包问题简介
算法设计随机算法NP问题
2021/10/5
1
凸包（convex hull）
算法设计随机算法NP问题
2021/10/5
2
随机算法简介
算法设计随机算法NP问题
2021/10/5
3
定义：在算法中引入随机因素, 即通过随机数选择算法的下一步操作。
特点：简单、快速
一种平衡：随机算法可以理解为在时间、空间和随机三大计算资源中的平衡
算法设计随机算法NP问题
2021/10/5
4
计算机产生随机数的方法
d0=d
dn=bdn-1+c
an= dn % 65536
算法设计随机算法NP问题
2021/10/5
5
1、数值概率算法：用于数值问题的求解
2、Sherwood算法一定能得到问题的正确解
常见的四类随机算法：
算法设计随机算法NP问题
2021/10/5
6
3、Las Vegas算法或者得到正确的解，或者得不到解。
4、Monte Carlo算法一定能得到解，但是得到的解可能不正确，然而这种概率是小的且有界的。
常见的四类随机算法：
算法设计随机算法NP问题
2021/10/5
7
重复性定律
设 是一次随机试验的成功概率，则N次独立随机试验的成功概率为
P = 1-(1- )N N
例如： =, N=20, P 1
算法设计随机算法NP问题
2021/10/5
8
一种重要让步策略：
传统算法: 以100％成功概率求解
确定的 问题的最优解
近似算法: 一种对解质量的让步
算法 随机算法: 一种对求解成功概率和
非确定的 解质量的让步
智能算法: 遗传算法、模拟退火法、
拟人拟物算法等
算法设计随机算法NP问题
2021/10/5
9
用随机投点法计算值
设有一半径为r的圆及其外切四边形。向该正方形随机地投掷n个点。设落入圆内的点数为k。由于所投入的点在正方形上均匀分布，因而所投入的点落入圆内的概率为 。所以当n足够大
时，k与n之比就逼近这一概率。从而 。
double darts(int n)
{ // 用随机投点法计算值
int k=0;
for (int i=1;i <=n;i++) {
double x=Random();
double y=Random();
if ((x*x+y*y)<=1) k++;
}
return 4*k/(double)n;
}
算法设计随机算法NP问题
2021/10/5
10