多数问题求解之蒙特卡洛与分治法

这篇具有很好参考价值的文章主要介绍了多数问题求解之蒙特卡洛与分治法。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

多数问题(Majority Problem)是一个有多种求解方法的经典问题,其问题定义如下:

给定一个大小为 n n n的数组,找出其中出现次数超过 n / 2 n/2 n/2的元素

例如:当输入数组为 [ 5 , 3 , 5 , 2 , 3 , 5 , 5 ] [5, 3, 5, 2, 3, 5, 5] [5,3,5,2,3,5,5],则 5 5 5是多数(majority)。

本文将介绍该问题的多种求解方法,重点介绍蒙特卡洛与分治法2种。

1. 解决思路

面对一个未知的算法问题,我们最开始很自然地会使用简单粗暴的方法。

1.1 暴力解法

暴力解法就是遍历整个数组,依次判断每个元素是否是多数。其伪代码如下:

Majority(A[1, n])
for(i = 1 to n)
	cnt = 1
	for(j = 1 to n)
		if (i != j and A[i]==A[j])
			cnt++
	end
	if (cnt > n/2) 
		return "A[i] is the majortiy"
 end
 return "No majority"

暴力算法的缺点就是费时间,时间复杂度为 O ( n 2 ) O(n^2) O(n2)。那有什么办法能少一些遍历的时间代价呢?哈希表就是一种用空间换时间的方法。

1.2 哈希表

上面的暴力解法中,我们在循环遍历中更新元素出现的次数,然后再判断是否是多数。可以改为只遍历数组一次,用哈希表记录每个元素出现的次数,然后再遍历哈希表找到出现次数最大的元素,判断其出现次数是否超过 n / 2 n/2 n/2

这样时间复杂度降为了 O ( n ) O(n) O(n),空间复杂度为 O ( n ) O(n) O(n)。时间复杂度还能更优化一点吗?下面让我们来看下分治法的求解思路。

1.3 分治法

我们把原始数组分为两半:在前一半子数组中,找到多数 A A A;在后一半子数组中,找到多数 B B B。那么原始数组的多数一定在 A A A B B B之间,当二者相等时,原始数组的多数就已经找到了;当二者不等时,比较 A A A B B B出现的次数哪个大于 n / 2 n/2 n/2即可。

算法的时间复杂度 T ( n ) = T ( n / 2 ) + 2 n = O ( n log ⁡ n ) T(n)=T(n/2)+2n=O(n\log{n}) T(n)=T(n/2)+2n=O(nlogn)。具体的C语言代码实现可参见第2节。

1.4 蒙特卡洛法

蒙特卡罗(Monte Carlo)算法是一种随机算法,在一般情况下可以保证对问题的所有实例都以高概率给出正确解,但是通常无法判定一个具体解是否正确。

在多数问题中,蒙特卡洛法的思想是随机从数组中选择一个元素,判断是否是多数。如果不是多数的话,再随机选择一个。在存在多数的情况下,因为随机选择到多数的概率超过 1 2 \frac{1}{2} 21,算法找不到多数的概率小于 1 2 \frac{1}{2} 21

该算法的平均时间复杂度为 O ( n ) O(n) O(n)

2. 代码

以下C语言代码依次实现了Monte Carlo以及分治法求解多数问题,并比较了两种算法的运行时间。

  1. 首先用户需输入测试数据的文件路径,按下回车键。
  2. 然后进入Monte Carlo模式需输入重复的次数。
  3. 待用户输入完成,按下回车键后,对Monte Carlo算法求解多数问题计时开始,直至输出多数问题的结果计时结束,打印输出运行时间(ms)。
  4. Monte Carlo结束后直接进入分治法求解,开始计时,直至分治法输出多数问题的结果计时结束,打印输出运行时间(ms)。
#include <iostream>
#include <cstdlib>
#include <ctime>
#include <windows.h> 

using namespace std;

const int N = 2000000;        //定义数组的最大长度 

int a[N];

bool majorityMC_once(int a[], int len, int *result) { //对长度为len的数组a[]进行一次蒙特卡洛寻找多数 
	int rnd = rand() % len;  //生成[0, len-1)的一个随机下标 
	int x = a[rnd];
	int count = 0;           //记录 x 在数组a[]中出现的次数 
	for (int i = 0; i < len; i++) { 
		if (a[i] == x) {
			count++;
		}
	}
	if (count > (len / 2)) { //若 x 出现次数超过数组长度的一半,则一次蒙特卡洛找到多数,返回true 
		*result = x;         //将找到的多数的值传给result 
		return true;
	} 
	else {                   //否则,一次蒙特卡洛未找到多数,返回false 
		return false;
	}
}

bool majorityMC_k_times(int a[], int len, int *result, int k) { //k次蒙特卡洛 
	for (int i = 1; i <= k; i++) {
		if(majorityMC_once(a, len, result)) { //只要有一次蒙特卡洛找到多数,则返回true              
			return true;
		}
	} 
	return false;                             //k次蒙特卡洛均未找到多数,则返回false 
}

bool majorityDC(int a[], int start, int end, int *result) { //分治法求解多数问题,数组下标区间为[start, end] 
	if (start == end) {
		*result = a[end];
		return true;
	}
	else {
		int m1, m2;
		majorityDC(a, start, (start + end) / 2, &m1);    //m1为前半区间[start, (start + end) / 2]的多数 
		majorityDC(a, (start + end) / 2 + 1, end, &m2);  //m2为后半区间[(start + end) / 2 + 1, end]的多数 
		int count1 = 0, count2 = 0;
		for (int i = start; i <= end; i++) {
			if (a[i] == m1) {     //count1记录m1在数组a[]中出现的次数 
				count1++;
			}
			if (a[i] == m2) {     //count2记录m2在数组a[]中出现的次数 
				count2++;
			}
		}
		if (count1 > ((end - start + 1) / 2)) { //m1在数组a[]中出现的次数大于数组长度的一半,则m1为多数 
			*result = m1;
			return true;
		} 
		else if (count2 > ((end - start + 1) / 2)) { //m2在数组a[]中出现的次数大于数组长度的一半,则m2为多数 
			*result = m2;
			return true;
		}
		else {  
			return false;         //m1, m2均不是多数,则数组a[]的多数不存在
		}
	}
}

int main() {
	srand(time(NULL));  //设置时间函数time(NULL)为随机数种子 
	char s[100];
	cout << "请输入测试数据文件路径:" << endl;
	cin >> s; 
	FILE *fp;
	fp = fopen(s, "r");
	if (fp == NULL) {
		cout << "Can not open the file!" << endl;
		exit(0);
	}
	int i = 0;
	while (fscanf(fp, "%d\n", &a[i]) != EOF) {  //读取文件中的数据到数组a[]中 
		i++;
	}
	fclose(fp); 
	cout << "********************** Monte Carlo *********************" << endl;
	int k;
	cout << "请输入 Monte Carlo 重复的次数: ";
	cin >> k;
	LARGE_INTEGER nFreq;
	LARGE_INTEGER nBeginTime;
	LARGE_INTEGER nEndTime;
	QueryPerformanceFrequency(&nFreq);
	QueryPerformanceCounter(&nBeginTime);  //Monte Carlo计时开始 
	int resultMC;
	if (majorityMC_k_times(a, i, &resultMC, k)) {
		cout << resultMC << " is the majority" << endl;
	} 
	else {
		cout << "Can not find the majority!" << endl;
	}
	QueryPerformanceCounter(&nEndTime);  //Monte Carlo计时结束 
	double time = (double)(nEndTime.QuadPart - nBeginTime.QuadPart) / nFreq.QuadPart * 1000;
	cout << "Running time: " << time << "ms" << endl;
	cout << endl;
	cout << "****************** Divide and Conquer ******************" << endl;
	QueryPerformanceFrequency(&nFreq);
	QueryPerformanceCounter(&nBeginTime);  //分治法计时开始 
	int resultDC;
	if (majorityDC(a, 0, i - 1, &resultDC)) {
		cout << resultDC << " is the majority" << endl;
	} 
	else {
		cout << "Can not find the majority!" << endl;
	}
	QueryPerformanceCounter(&nEndTime);    //分治法计时结束 
	time = (double)(nEndTime.QuadPart - nBeginTime.QuadPart) / nFreq.QuadPart * 1000;
	cout << "Running time: " << time << "ms" << endl;
	return 0;
}

3. 运行结果

基于测试数据,求解得到如下结果:

  • dataset1.txt:none
  • dataset2.txt:991
  • data_1015.txt:none
  • data_1015l.txt:none

多次运行程序发现,在多数问题有解时,采用Monte Carlo算法求解效率普遍比分治法高,但是在Monte Carlo算法重复次数较少时,它在实际中并不总是返回正确结果。如测试数据为dataset2.txt,Monte Carlo重复1次时,可能会找不到多数问题的解,如下图。

多数问题求解之蒙特卡洛与分治法,算法,算法,数据结构,C语言

其他运行示例:

(1)dataset1.txt,Monte Carlo重复次数1000:

多数问题求解之蒙特卡洛与分治法,算法,算法,数据结构,C语言

(2)dataset2.txt,Monte Carlo重复次数20:

多数问题求解之蒙特卡洛与分治法,算法,算法,数据结构,C语言

(3)data_1015.txt,Monte Carlo重复次数1000:

多数问题求解之蒙特卡洛与分治法,算法,算法,数据结构,C语言

(4)data_1015l.txt,重复次数1000:

多数问题求解之蒙特卡洛与分治法,算法,算法,数据结构,C语言文章来源地址https://www.toymoban.com/news/detail-839573.html

到了这里,关于多数问题求解之蒙特卡洛与分治法的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 16. 蒙特卡洛强化学习基本概念与算法框架

    蒙特卡洛强化学习(简称MC强化学习)是一种 无模型 强化学习算法,该算法无需知道马尔科夫决策环境模型,即不需要提前获得立即回报期望矩阵R(维度为(nS,nA))、状态转移概率数组P(维度为(nA,nS,nS)),而是通过与环境的反复交互,使用统计学方法,利用交互数据直接进行

    2024年01月21日
    浏览(47)
  • 【Python数学建模常用算法代码——蒙特卡洛模型】

    蒙特卡洛方法的理论支撑其实是概率论或统计学中的大数定律。基本原理简单描述是先大量模拟,然后计算一个事件发生的次数,再通过这个发生次数除以总模拟次数,得到想要的结果。下面我们以三个经典的小实验来学习下蒙特卡洛算法思想。 实验原理 在正方形内部有一

    2024年02月02日
    浏览(52)
  • 强化学习9——免模型预测算法介绍(蒙特卡洛方法和时步差分方法)

    对于大部分情况来说,环境是未知的,也就是说状态转移概率未知,对于这种情况的算法称为 免模型预测 算法。免模型算法与环境不断交互学习,但是需要大量的运算。 蒙特卡罗方法通过重复随机抽选,之后运用统计概率此方法来从抽样结果中归纳我们想要得到的数值估计

    2024年02月02日
    浏览(47)
  • 【Python】蒙特卡洛模拟 | PRNG 伪随机数发生器 | 马特赛特旋转算法 | LCG 线性同余算法 | Python Random 模块

          猛戳订阅!  👉 《一起玩蛇》🐍 💭 写在前面: 本篇博客将介绍经典的伪随机数生成算法,我们将  重点讲解 LCG(线性同余发生器) 算法与马特赛特旋转算法,在此基础上顺带介绍 Python 的 random 模块。   本篇博客还带有练习,无聊到喷水的练习,咳咳…… 学完前

    2024年02月04日
    浏览(48)
  • 数学建模-蒙特卡洛模拟

    2024年02月15日
    浏览(54)
  • 强化学习:蒙特卡洛方法(MC)

       以抛硬币为例,将结果(正面朝上或反面朝上)表示为作为随机变量 X X X ,如果正面朝上则 X = + 1 X=+1 X = + 1 ,如果反面朝上,则 X = − 1 X=-1 X = − 1 ,现在要计算 E [ X ] E[X] E [ X ] 。    我们通常很容易想到直接用定义来计算,因为我们知道正面朝上和反面朝上的概率都是

    2024年02月08日
    浏览(49)
  • 蒙特卡洛树搜索(MCTS)详解

    蒙特卡洛树搜索是一种经典的树搜索算法,名镇一时的 AlphaGo 的技术背景就是结合蒙特卡洛树搜索和深度策略价值网络,因此击败了当时的围棋世界冠军。它对于求解这种大规模搜索空间的博弈问题极其有效,因为它的核心思想是 把资源放在更值得搜索的分枝上 ,即 算力集

    2024年01月18日
    浏览(58)
  • 蒙特卡洛方法的数学基础-1

    蒙特卡洛方法的数学基础-1 Bayes 公式 常用分布 Binominal Distribution Poisson Distribution Gaussian Distribution  Exponential Distribution Uniform Distribution 大数定理 均匀概率分布随机地取 N 个数 x i , 函数值之和的算术平均收敛于函数的期望值 算术平均收敛于真值 中心极限定理 n个相互独立分布

    2024年02月07日
    浏览(56)
  • 蒙特卡洛方法的收敛性和误差

    目录 1.收敛性 2.误差 3.减少方差的各种技巧 4.效率 5.优缺点 蒙特卡罗方法作为一种计算方法,其收敛性与误差是普遍关心的一个重要问题。由此可以总结出蒙特卡洛方法的优缺点。

    2024年02月06日
    浏览(40)
  • 蒙特卡洛积分、重要性采样、低差异序列

    渲染的目标在于计算周围环境的光线有多少从表面像素点反射到相机视口中。要计算总的反射光,每个入射方向的贡献,必须将他们在半球上相加: 为入射光线  与法线  的夹角,为方便计算可以使用法线向量和入射向量(单位化)的乘积表示。  对于基于图像的光照,入射

    2024年02月03日
    浏览(62)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包