1,068
个编辑
更改
跳到导航
跳到搜索
第33行：
第33行： − − #Define a domain of possible inputs − − Define a domain of possible inputs − − #Generate inputs randomly from a [[probability distribution]] over the domain − − Generate inputs randomly from a probability distribution over the domain − #Perform a [[Deterministic algorithm|deterministic]] computation on the inputs − − Perform a deterministic computation on the inputs − #Aggregate the results − − Aggregate the results 第60行：
第46行： − Monte Carlo method applied to approximating the value of . − − For example, consider a quadrant (circular sector) inscribed in a unit square. Given that the ratio of their areas is π/4, the value of π can be approximated using a Monte Carlo method:<ref name=":9">Kalos, Malvin H.; Whitlock, Paula A. (2008). ''Monte Carlo Methods''. Wiley-VCH. ISBN <bdi>978-3-527-40760-6</bdi>.</ref> − − #Draw a square, then [[inscribed figure|inscribe]] a quadrant within it − − Draw a square, then inscribe a quadrant within it − #[[uniform distribution (continuous)|Uniformly]] scatter a given number of points over the square − − Uniformly scatter a given number of points over the square − #Count the number of points inside the quadrant, i.e. having a distance from the origin of less than 1 − − Count the number of points inside the quadrant, i.e. having a distance from the origin of less than 1 − #The ratio of the inside-count and the total-sample-count is an estimate of the ratio of the two areas, π/4. Multiply the result by 4 to estimate π. − − <nowiki>The ratio of the inside-count and the total-sample-count is an estimate of the ratio of the two areas, |4}}. Multiply the result by 4 to estimate .</nowiki> − In this procedure the domain of inputs is the square that circumscribes the quadrant. We generate random inputs by scattering grains over the square then perform a computation on each input (test whether it falls within the quadrant). Aggregating the results yields our final result, the approximation of π . − − There are two important considerations: − #If the points are not uniformly distributed, then the approximation will be poor. − − If the points are not uniformly distributed, then the approximation will be poor. − #There are many points. The approximation is generally poor if only a few points are randomly placed in the whole square. On average, the approximation improves as more points are placed. − − There are many points. The approximation is generally poor if only a few points are randomly placed in the whole square. On average, the approximation improves as more points are placed. − − Uses of Monte Carlo methods require large amounts of random numbers, and it was their use that spurred the development of pseudorandom number generators, which were far quicker to use than the tables of random numbers that had been previously used for statistical sampling.
→概述
蒙特卡罗方法各不相同，但趋于遵循一个特定的模式:
蒙特卡罗方法各不相同，但趋于遵循一个特定的模式:
1、定义可能输入的域
1、定义可能输入的域
2、从域上的概率分布随机生成输入
2、从域上的概率分布随机生成输入
3、对输入进行确定性计算
3、对输入进行确定性计算
4、汇总结果[[File:Pi 30K.gif|thumb|right| Monte Carlo method applied to approximating the value of {{pi}}.
4、汇总结果[[File:Pi 30K.gif|thumb|right| Monte Carlo method applied to approximating the value of {{pi}}.
蒙特卡罗方法应用于估计π值。|链接=Special:FilePath/Pi_30K.gif]]
蒙特卡罗方法应用于估计π值。|链接=Special:FilePath/Pi_30K.gif]]
例如，考虑一个单位正方形内嵌的四分之一圆。考虑到它们的面积比是π/4，π的值可以用蒙特卡罗方法来近似：<ref name=":9" />
例如，考虑一个单位正方形内嵌的四分之一圆。考虑到它们的面积比是π/4，π的值可以用蒙特卡罗方法来近似：<ref name=":9" />
1、画一个正方形，然后在其中划出一个四分之一圆
1、画一个正方形，然后在其中划出一个四分之一圆
2、在正方形上均匀散布给定数量的点
2、在正方形上均匀散布给定数量的点
3、计算四分之一圆内的点数，即满足距离原点小于1的
3、计算四分之一圆内的点数，即满足距离原点小于1的
4、四分之一圆内部计数与总样本计数之比是两个区域之比的估计值，π/4。把结果乘以4就可以估算出π的值。
4、四分之一圆内部计数与总样本计数之比是两个区域之比的估计值，π/4。把结果乘以4就可以估算出π的值。
在这个过程中，输入域是限定四分之一圆的正方形。我们通过将颗粒散射到正方形上来产生随机输入，然后对每个输入执行计算(测试它是否在四分之一圆内)。汇总这些结果会产生最终的结果—π的近似值。
在这个过程中，输入域是限定四分之一圆的正方形。我们通过将颗粒散射到正方形上来产生随机输入，然后对每个输入执行计算(测试它是否在四分之一圆内)。汇总这些结果会产生最终的结果—π的近似值。
有两个重要的考虑因素:
有两个重要的考虑因素:
1、如果这些点不是均匀分布的，那么近似效果就会很差。
1、如果这些点不是均匀分布的，那么近似效果就会很差。
2、这一过程需要很多点。如果整个正方形中只有几个点是随机放置的，那么这个近似值通常是很差的。平均而言，随着放置更多的点，近似值精度会提升。
2、这一过程需要很多点。如果整个正方形中只有几个点是随机放置的，那么这个近似值通常是很差的。平均而言，随着放置更多的点，近似值精度会提升。
应用蒙特卡罗方法需要大量的随机数，这也就刺激了'''伪随机数生成器 Pseudorandom Number Generators'''的发展，伪随机数生成器比以前用于统计抽样的随机数表要快得多。
应用蒙特卡罗方法需要大量的随机数，这也就刺激了'''伪随机数生成器 Pseudorandom Number Generators'''的发展，伪随机数生成器比以前用于统计抽样的随机数表要快得多。