精华内容
下载资源
问答
  • 概率算法

    万次阅读 2019-06-24 13:36:39
    1、数值概率算法:常用于解决数值计算的问题。该算法往往只能得到问题的近似解,并且该计算解的精度一般随着计算时间的增加而不断提高。 例:设f(x)=1-x^2,计算定积分的值。 分析:要计算定积分的值的几何含义...

    概率算法大致分为4类:数值概率算法,蒙特卡洛算法,拉斯维加斯算法,舍德伍算法。

    1、数值概率算法:常用于解决数值计算的问题。该算法往往只能得到问题的近似解,并且该计算解的精度一般随着计算时间的增加而不断提高。

    例:设f(x)=1-x^2,计算定积分的值。

    分析:要计算定积分的值的几何含义就是f(x)与x轴y轴所围得面积(设为阴影)。又因为x,y轴所围的面积为1,所以随机点落入阴影的概率(在上下线所围成的区域内)即为定积分的近似解。 
    假设向单位正方形中随机投入n个点(xi,yi)i=1,2,3,…n。随机点是否落入阴影区域内,可由yi<=f(xi)=1-xi2来判断。如果有m个点落入阴影,则概率p=m/n。

    2、蒙特卡洛算法:当所求解问题是某种随机事件出现的概率,或者是某个随机变量的期望值时,通过某种“实验”的方法,以这种事件出现的频率估计这一随机事件的概率,或者得到这个随机变量的某些数字特征,并将其作为问题的解。

    3、拉斯维加斯算法:算法是一个能够保证输出结果为正确的随机化算法,因为它的正确性,使它成为适用情况下的首选算法。Las Vegas算法模型不允许错误的输出,但是它可以允许程序输出“?”结果,即“不知道结果正不正确”

    4、舍德伍算法:舍伍德算法总能求得问题的一个解,且所求得的解总是正确的。当一个确定性算法在最坏情况下的计算复杂性与其在平均情况下的计算复杂性有较大差别时,可以在这个确定算法中引入随机性将它改造成一个舍伍德算法,消除或减少问题的好坏实例间的这种差别。舍伍德算法精髓不是避免算法的最坏情况行为,而是设法消除这种最坏行为与特定实例之间的关联性。

    展开全文
  • 基本算法之概率算法

    2020-04-19 00:02:08
    基本算法之概率算法 一.概率算法的基本思想 大致执行步骤如下: 1.将问题转化为相应的几何图形S,S的面积容易计算,问题的结果往往对应几何图形中的某一部分。 2.然后,向几何图形中随机撒点。 3.统计几何图形S和S1...

    基本算法之概率算法

    一.概率算法的基本思想

    大致执行步骤如下:
    1.将问题转化为相应的几何图形S,S的面积容易计算,问题的结果往往对应几何图形中的某一部分。
    2.然后,向几何图形中随机撒点。
    3.统计几何图形S和S1中的点数,根据S和S1面积的关系及图形中的点数来计算得到的结果。
    4.判断上述结果是否在需要的精度之内,如果未达到精度则执行步骤2;如果达到精度,则输出结果。
    概率算法大致分为4种形式:
    1)数值概率算法;
    2)蒙特卡罗(Monte Carlo)算法;
    3)拉斯维加斯(Las Vegas)算法;
    4)舍伍德(Sherwood)算法;

    二.典型实例

    蒙特卡罗算法是一个典型的应用,用来计算圆周率π。下面就通过一个实例来分析蒙特卡罗概率算法的应用。
    1.分析
    使用蒙特卡罗算法计算圆周率π的思想其实很简单,首先分析一个半径为1的圆,如下图所示:
    在这里插入图片描述
    图中的面积的计算公式如下:
    S圆=πr^2
    图中阴影部分是一个圆的1/4,因此阴影面积的计算公式如下:
    S阴影=S圆/4=(π
    r^2)/4=π/4
    图中的正方形的面积为:
    S正方形=r^2=1
    按照图示建立一个坐标系。如果均匀地向正方形内撒点,那么落入阴影部分的点数与全部的点数之比为:
    S阴影/S正方形=π/4
    根据概率统计的规律,只要撒点数足够多,那么将得到近似的结果。通过这个原理可以计算圆周率π的近似值,这就是蒙特卡罗π的算法。
    2.参考代码

    import java.util.Scanner;
    
    public class PI {
    	static double MontePI(int n) {
    		double PI;
    		double x,y;
    		int i,sum;
    		sum = 0;
    		for(i=1;i<=n;i++) {
    			x=Math.random();
    			y=Math.random();
    			if(x*x+y*y <= 1) {
    				sum++;
    			}
    		}
    		PI=4.0*sum/n;
    		return PI;
    	}
    
    	public static void main(String[] args) {
    		// TODO Auto-generated method stub
    		int n;
    		double PI;
    		System.out.println("蒙特卡罗概率算法计算π:");
    		System.out.println("输入点的数量:");
    		Scanner input = new Scanner(System.in);
    		n=input.nextInt();
    		PI=MontePI(n);
    		System.out.println("PI="+PI);	
    	}
    
    }
    

    3.结果展示
    在这里插入图片描述

    展开全文
  • 算法设计之概率算法

    千次阅读 2018-11-19 13:16:38
    算法设计之概率算法 1.为什么需要概率算法? 与确定性算法相比,若冒险,可能做得更好! 概率算法的分类? 数字算法。 求数字问题的近似解求数字问题的近似解 Monte Carlo算法 (MC算法) 这里我们指的MC算法是:...

    算法设计之概率算法

    • 1.为什么需要概率算法?

    与确定性算法相比,若冒险,可能做得更好!

    • 概率算法的分类?
    1. 数字算法。
      求数字问题的近似解求数字问题的近似解
    2. Monte Carlo算法 (MC算法)
      这里我们指的MC算法是: 若问题只有1个正确的解,而无近似解的可能时使用MC算法。
      特点:MC算法总是给出一个答案,但该答案未必正确,成功(即答案是正确的)的概率正比于算法执行的时间。
      缺点:一般不能有效地确定算法的答案是否正确。

      常见的场景:素数测定
      在这里插入图片描述

    所以MC算法的基本思想是:为了增加一个一致的、p-正确算法成功的概率,只需多次调用同一算法,然后选择出现次数最多的解。

    在这里插入图片描述

    在这里插入图片描述
    在这里插入图片描述
    3. Las Vegas(LV)
    LV算法绝不返回错误的答案。
    特点:获得的答案必定正确,但有时它仍根本就找不到答案。
    与MC算法一样,成功的概率正比于算法的执行时间。
    常见问题:N皇后问题。
    4.Sherwood算法
    当某些确定算法解决一个特殊问题平均的时间比最坏时间快得多时,我们可以使用Sherwood算法来减少,甚至是消除好的和坏的实例之间的差别。
    常见的场景: 离散对数计算,搜索有序表
    将输入实例随机化,从概率上消除实例的差异:
    可将随机预处理使用到f的计算上:
    ① 使用函数u将x加密为某一随机实例y
    ② 将y提交给f计算出f(y)的值
    ③ 使用函数v转换为f(x)

    展开全文
  • 概率算法依照概率统计的思想来求解问题,其往往不能得到问题的精确解,但是在数值计算领域得到了广泛的应用。因为很多数学问题,往往没有或者很难计算解析,此时便需要通过数值计算来求解近似值。概率算法执行的基本...

    1、什么是概率算法?

    概率算法依照概率统计的思想来求解问题,其往往不能得到问题的精确解,但是在数值计算领域得到了广泛的应用。因为很多数学问题,往往没有或者很难计算解析,此时便需要通过数值计算来求解近似值。概率算法执行的基本过程如下:

      (1). 将问题转化为相应的几何图形S,S的面积容易计算,问题的结果往往对应几何图形中某一部分S1的面积。

      (2). 然后,向几何图形中随机撒点。

      (3). 统计几何图形S和S1中的点数。根据S和S1面积的关系及各图形中的点数来计算得到结果。

      (4). 判断上述结果是否在需要的精度之内,如果未达到精度则执行步骤(2)。如果达到精度,则输出近似结果。

    概率算法大致分为如下4种形式:数值概率算法;蒙特卡罗(Monte Carlo)算法;拉斯维加斯(Las Vegas)算法;舍伍德(Sherwood)算法;

    2、概率算法的应用

    计算π的近似值

    圆周率π是一个非常重要的常数,无论在数学还是在物理学上都有很广泛的用途。π的值直接关系到计算圆周长、圆面积、球体积等。π一般定义为圆周长与圆直径之比。在数学分析学中,圆周率π被严格定义为满足如下等式的最小正实数:sin(x) = 0{\color{Red} },圆周率 π=3.141592653589793…… ,其是一个无限不循环实数,即所谓的无理数。圆周率π的精确计算,从古至今都非常重要。

    蒙特卡罗(Monte Carlo)算法是一种以概率为基础的、非常重要的数值计算方法,在工程、金融、计算物理学等领域都有着重要的应用。蒙特卡罗算法是如何计算圆周率π的呢?我们先画一个半径为1的圆,如图所示:

    先来推算图中阴影部分的面积,阴影部分是一个圆的1/4,因此有如下计算公式:S阴影 = S圆 /4 = (1/4)π*r^2 = π/4 ,而图中正方形的面积则为:S正 = r^2 = 1,这样,按照图示建立一个坐标系。如果均匀地向正方形内撒点,那么落入阴影部分的点数与全部的点数之比就是S阴影/S正方形=π/4。根据概率统计的规律,只要撒的点足够多,就会得到近似的结果。通过这个原理便可以计算圆周率π的近似值,这就是蒙特卡罗算法。

    蒙特卡罗算法有几个关键点:

    • 均匀撒点:使用随机方法来实现,产生[0,1]之间随机的坐标值[x,y]。
    • 区域判断:图中阴影部分的特点是距离坐标原点的距离小于等于1,这样,可以通过计算判断x^2+y^2≤1来实现。

    通过蒙特卡罗算法计算π的近似值,Java实现demo演示如下:

    public class Test {
        /**
         * 打印结果:
         *  n = 6000 ------> π = 3.1466666666666665
         *  n = 600000 ------> π = 3.1464866666666667
         *  n = 60000000 ------> π = 3.1413683333333333
         *  n = 600000000 ------> π = 3.1415774266666667
         **/
        public static void main(String[] args) {
            int n = 6000;
            System.out.println("n = " + n + " ------> π = " + getMontePI(n));
        }
    
        public static double getMontePI(int amount) { // amount为阴影区域的撒点数
            int cnt = 0; // 统计落在阴影区域的点
            Random random = new Random();
            for (int i = 1; i < amount; i++) {
                // 阴影区域范围:x^2+y^2≤1
                if (Math.pow(random.nextDouble(), 2) + Math.pow(random.nextDouble(), 2) <= 1)
                    cnt++;
            }
            return 4.0 * cnt / amount; // π概率计算公式
        }
    }

    从测试结果可知:撒点数n越多,概率统计得到π的值越精确。同时,由于概率算法的随机性,在不同的运行时间,即使输入同样的撒点数,得到的结果也是不相同的。

    参考书籍:《Java常用算法手册(第3版)》

    展开全文
  • 概率算法(随机化算法)

    千次阅读 2019-07-27 13:46:19
    概率算法允许算法在执行过程中随机地选择下一个计算步骤。在很多情况下,算法在执行过程中面临选择时,随机性选择比最优选择省时,因此概率算法可以在很大程度上降低算法的复杂度。概率算法的一个基本特征是对所求解...
  • 隐马尔可夫链概率计算方法 直接计算法 前向算法 后向算法
  • 舍伍德类型概率算法

    千次阅读 2020-10-25 20:53:38
    舍伍德类型概率算法 舍伍德类型概率算法的特点:总能求得问题的一个解,且所求得的解总是正确的。 【问题描述】设计一个快速排序的舍伍德类型概率算法。 【问题解答】快速排序算法的关键在于一次划分中选择合适的...
  • 数值概率算法

    千次阅读 2018-01-09 10:26:47
    概率算法允许在执行过程中随机的选择下一步的计算步骤。又是可使算法大大降低复杂度,提高算法效率,但有时也可能得不到问题的全部答案。基本概念概率算法大致分为4类:熟知概率算法,蒙特卡洛算法,拉斯维加斯算法...
  • 概率算法大致可分为4种形式: 数值概率算法; 蒙特卡罗算法; 拉斯维加斯算法; 舍伍德算法; 计算蒙特卡罗概率的算法实现: 1 #include "stdio.h" 2 #include "time.h" 3 #include "stdlib.h" 4 ...
  • 概率算法总结

    千次阅读 2016-11-22 09:51:27
    利用随机性求数字问题的近似解,概率算法获得的答案是近似的,通常执行时间越长,精度就越高,误差就越小。 举例:Pi值的估计;数字积分(计算定积分的值);概率计数(求集合X的势) 2)Sherwood算法 总是给出...
  • PHP指定概率算法

    千次阅读 2017-02-11 10:05:02
    PHP指定概率算法,可用于刮刮卡,大转盘等抽奖算法。
  • 中奖概率算法

    千次阅读 2018-01-23 17:33:37
    在此分享一个高效、好用、易懂的中奖概率算法。算法源代码出自网络,不过我加之修改,为我所用啦!哈哈哈...嗝~ 前阶段出于工作需要,写了一个发红包的微擎模块,根据公司的运营人员的要求: 1.红包取自红包池...
  • 概率算法1-应用定积分计算

    千次阅读 2018-01-14 22:07:14
     概率算法的特性:使用概率算法去处理同一个问题,计算两次会得到不同的计算结果。概率算法是对于我们在现实社会中是非常有效的,大家都是学理工科的,知道这里世界上是没有绝对的事情,也没有绝对发生的事情。我们...
  • 经典抽奖概率算法

    千次阅读 2018-12-31 17:05:32
    * 经典的概率算法, * $proArr是一个预先设置的数组, * 假设数组为:array(100,200,300,400), * 开始是从1,1000 这个概率范围内筛选第一个数是否在他的出现概率范围之内, * 如果不在,则将概率空间,也...
  • 这篇文章主要介绍了Python计算斗牛游戏概率算法,简单介绍了斗牛游戏的原理并结合具体实例形式分析了相关的游戏概率算法,需要的朋友可以参考下本文实例讲述了Python计算斗牛游戏概率算法。分享给大家供大家参考,具体...
  • 概率算法允许算法在执行过程中随机地选择下一个计算步骤。在很多情况下,算法在执行过程中面临选择时,随机性选择比最优选择省时,因此概率算法可以在很大程度上降低算法的复杂度。 概率算法的一个基本特征是对所...
  • 游戏掉落概率算法

    万次阅读 2017-05-10 10:40:27
    并且,抽奖系统的概率可能还会随着抽奖人数的变化而不断调整,这个虽然看起来有点复杂,其实只是多了逻辑,如果知道普遍的掉落概率算法,那么我相信这种可控的概率算法也是很简单的。掉率概率的原理很简单,就是基本...
  • 所以人们发展了各种工具来避开它们,最常用的两种方法是使用概率算法和近似算法,这两种方法也符合实际需要:在解决实际问题中,我们不需要结果绝对正确,也不需要结果绝对精确。 所谓概率算法,就是在算
  • 经典概率算法讲解

    千次阅读 2016-12-28 10:24:22
    首先来看一个经典的概率算法: function get_rand($proArr) { $result = ''; //概率数组的总概率精度 $proSum = array_sum($proArr); //概率数组循环 foreach ($proArr as $key => $proCur) { $randNum...
  • 经典的概率算法

    千次阅读 2018-04-24 10:41:06
    * 经典的概率算法, * $proArr是一个预先设置的数组, * 假设数组为:array(100,200,300,400), * 开始是从1,1000 这个概率范围内筛选第一个数是否在他的出现概率范围之内, * 如果不在,则将概率空间,也...
  • 经典的概率算法函数

    千次阅读 2019-09-12 03:36:29
    这是一个很经典的概率算法函数: function get_rand($proArr) { $result = ''; //概率数组的总概率精度 $proSum = array_sum($proArr); //概率数组循环 forea...
  • 概率算法简介

    千次阅读 2006-03-18 17:29:00
    概率算法简介 很多算法的每一个计算步骤都是固定的,而在下面我们要讨论的概率算法,允许算法在执行的过程中随机选择下一个计算步骤。许多情况下,当算法在执行过程中面临一个选择时,随机性选择常比最优选择省时。...
  • php 中奖概率算法

    千次阅读 2015-05-13 21:38:22
    我们先完成后台PHP的流程,PHP的主要工作是负责配置奖项及对应的中奖概率,当前端页面点击翻动某个方块时会想后台PHP发送ajax请求,那么后台PHP根据配置的概率,通过概率算法给出中奖结果,同时将未中奖的奖项信息...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 421,454
精华内容 168,581
关键字:

概率算法