精华内容
下载资源
问答
  • n皇后问题 随机算法 高级算法 研究生算法课程作业 c++
  • 随机算法实现N皇后问题,所用随机算法是Las Vegas随机算法
  • 线性同余产生伪随机数 ...X(n+1) = (a * X(n) + c) % m这样的公式,其中:  模m, m > 0 系数a, 0  增量c, 0  原始值(种子) 0  其中参数c, m, a比较敏感,或者说直接影响了伪随机数产生的质量

    本系列所有代码https://github.com/YIWANFENG/Algorithm-github

    四中随机化算法

    数值随机化算法:

    1..这类算法所得到的往往是近似解。

    2.近似解的精度随着计算时间的增加而不断提高。

     

    蒙特卡罗算法:

    1.求问题的准确解,但得到的解不一定正确。

    2.计算时间越长,解的正确性越高。

     

    拉斯维加斯算法:

    1.求正确解,但可能得不到任何解。

    2.计算时间越长,得到正确解几率越高。

     

    舍伍德算法:

    1.总可求的一解,且所求解一定正确。

    2.非避免算法最坏,而是消除最坏与特定实例之间的关联。

    线性同余产生伪随机数

    算法思路分析以及相关数学公式:

    X(n+1) = (a * X(n) + c) % m这样的公式,其中:

     模m, m > 0

    系数a, 0 < a < m

    增量c, 0 <= c < m

    原始值(种子) 0 <= X(0) < m

    其中参数c, m, a比较敏感,或者说直接影响了伪随机数产生的质量。

    由上述公式得出xn+1)后右移16位即得到一个0-65535之间的随机数。

    (高16位随机性较低16位好)

    #include <iostream>
    #include <time.h> 
    
    //线性同余产生伪随机数 
    using namespace std;
    
    class CRandom
    {
    private:
    	unsigned long rand_seed; //随机数种子
    
    public:
    	CRandom(unsigned long s = 0)
    	{
    		if(!s) rand_seed = time(0);
    		else rand_seed = s; 
    	}
    	
    	unsigned long Random(unsigned long n) 
    	{
    		//0-n-1之间的随机数 
    		const unsigned long multiplier = 1194211693L;
    		const unsigned long adder = 15465L;
    		
    		rand_seed = multiplier*rand_seed + adder;
    		
    		return (rand_seed>>16) % n;
    	} 
    	
    	double fRandom(void) 
    	{
    		//产生0-1之间的随机实数 
    		const unsigned long large_number =  0x10000;
    		return Random(large_number) / double(large_number);
    	}
    	
    };
    
    int main()
    {
    	CRandom rnd;
    	
    	int i,n=100000;
    	int m[10];
    	for(i=0;i<10;++i) m[i]=0;
    	//查看生成随机数的分布 
    	for(i=0;i<n;i++) 
    		m[rnd.Random(1000)/100]++;
    	for(i=0;i<10;++i)	
    	 	cout<<m[i]/(double)n<<endl;
    	cin.get();
    	
    	return 0;
    }

    主元素问题

    题目:

    T[1:n]是一个含有n个元素的数组(集合)。当 | {i | T[i]=x} | > n/2 时,称元素x是数组T的主元素。判断一数组是否含有主元素。

     

    算法思路分析以及相关公式:

    蒙特卡洛算法,随机从数组中取一个数来测试其是否是该数组的主元素。

    一次随机测试很可能出错,在这里我们采用多次取样判断来减小误差。

     

    若数组含有主元素,则返回true的概率是p (p>1/2)2次调用返回true的概率是

    P+(1-P)*P, = (1-P)^2 > 3/4,如果需要更高准确度则重复更多次数。

    #include <time.h> 
    #include <stdlib.h>
    #include <math.h>
    
    #include <iostream>
    
    
    //主元素问题-- 蒙特卡洛算法
    using namespace std;
    
    template <class T_>
    bool Majority(const T_ *t,int n)
    {
    	srand(time(0));//取消后正确几率下降
    	int i = rand()%n;
    	T_ x = t[i];
    	int k =0;
    	for(int j=0;j<n;++j) {
    		if(t[j]==x) k++;
    	}
    	return (k>n/2);
    }
    
    template <class T_>
    bool MajorityMC(const T_*t,int n,double e)
    {
    	//e允许的最大错误几率 
    	int k =ceil(-log(e)/log(2.0));
    	for(int i=1;i<=k;++i) {
    		if(Majority(t,n)) return true;
    	}
    	return false;
    }
    
    
    
    int main()
    {
    
    	srand(time(0));
    	int i,n  = 10000;
    	int *a = new int[n];
    	for(i=0;i<n;++i) a[i] = i+1;
    	int counter = 0 ;
    	while (counter<n/2+1) {
    		i = rand()%n;
    		if(a[i]!=0) {
    			a[i]=0;
    			++counter;
    		}
     	}
     	
     	for(i = 0;i<40;++i) {
     		if(MajorityMC(a,n,0.1)) 
     			cout<<true<<endl;
     		else
     			cout<<false<<endl;
        }
        
    	cin.get();
    	delete []a;
    	return 0;
    }

    N皇后问题

    N皇后问题,Las Vegas 算法。

    算法分析与相关公式:

     对于n后问题的任何一个解而言,每一个皇后在棋盘上的位置无任何规律,不具有系统性,而更象是随机放置的。在棋盘上相继的各行中随机地放置皇后,并注意使新放置的皇后与已放置的皇后互不攻击,直至n个皇后均已相容地放置好,或已没有下一个皇后的可放置位置时为止。

    #include <time.h> 
    #include <stdlib.h>
    #include <math.h>
    #include <iostream>
    
    
    //nqueue - Las Vegas
     
    using namespace std;
    
    class NQueue_Las_Vegas
    {
    private:
    	int *y;  //当前行上皇后可放置的位置
    	
    	bool Place(int k)		
    	{ 
     		//验证第k行皇后位置是否合理 
     		for(int i=1; i<k; ++i) { 
     			if((k-i)==abs(x[i]-x[k]) || x[i]==x[k]) 
     				return false; 
     		} 
     		return true; 
     	} 
    
    	
    	bool Backtrack(int t)	
    	{
    		//回溯法
    		if(t>n) return true;
    		else {
    			for(int i=1;i<=n;++i)
    			{
    				x[t] = i;
    				if(Place(t) && Backtrack(t+1))
    					return true;
    			}
    		}
    		return false;
    	}
    	
    	bool QueuesLV(int m)	
    	{
    		//随机放置m个皇后的Las Vegas算法
    		int k = 1;
    		int count = 1;
    		while(k<=m && count>0) {
    			count=0;
    			for(int i=1;i<=n;++i) {
    				x[k]=i;
    				if(Place(k)) y[count++] = i;
    			}
    			if(count>0) 
    				x[k++] = y[rand()%count];
    			
    		}
    		return count>0;
    	}
    	
    public:
    	int n;
    	int *x;
    	
    	void Solve(int num_loops)
    	{
    		y = new int[n+1];
    		int m = 5;
    		if(n>15) m = n-15;
    		bool found = false;
    		for(int i=1;i<num_loops;++i) {
    			if(QueuesLV(m)) {
    				if(Backtrack(m+1)) {
    					found = true;
    					break;
    				}
    			}
    		}
    		if(found) {
    			for(int i=1;i<=n;++i) 
    				cout<<x[i]<<' ';
    			cout<<endl;
    		} else {
    			cout<<"No Answer"<<endl;
    		}
    		delete [] y;
    	}
    };
    
    
    int main()
    {
    	NQueue_Las_Vegas nq;
    	nq.n = 8;
    	nq.x = new int[nq.n+1];
    	for(int i=0;i<20;++i)
    		nq.Solve(10) ;
    		
    	cin.get();
    	delete [] nq.x;
    	return 0;
    }

    素数测试

     --蒙特卡洛算法  

    算法思路分析以及相关公式:

     Wilson定理:对于给定的正整数n,判定n是一个素数的充要条件是(n-1)! -1(mod n)

     费尔马小定理:如果p是一个素数,且0<a<p,则a^(p-1)(mod p)。 

     二次探测定理:如果p是一个素数,且0<x<p,则方程x^21(mod p)的解为x=1p-1

     Carmichael数:费尔马小定理是素数判定的一个必要条件。满足费尔马小定理条件的整数n未必全是素数。有些合数也满足费尔马小定理的条件,这些合数称为Carmichael数。前3Carmichael数是561,11051729Carmichael数是非常少的,在1~100000000的整数中,只有255Carmichael数。

     

    #include <time.h> 
    #include <stdlib.h>
    #include <math.h>
    #include <iostream>
    
    
    //素数测试 --蒙特卡洛算法  
    using namespace std;
    
    void PowerAndPrimeTest(unsigned int a,unsigned int p,unsigned int n,
    		unsigned int &result,bool &composite)
    {
    	//计算power(a,p) mod n ,同时实施对n的二次探测 
    	//result计算结果		composite是否为合数 
    	unsigned int x;
    	if(p==0) result = 1;
    	else {
    		PowerAndPrimeTest(a,p/2,n,x,composite);
    		
    		result = (x*x)%n;
    		if(result==1 && x!=1 && x!=n-1)
    			composite = true; 
    		//计算结果 
    		if(p%2==1) //p是奇数 
    			result = (result*a)%n;
    	}
    	
    }
    
    bool PrimeTestMC(unsigned int n,unsigned int k)  
    {
    	//检测n是否为素数
    	//重复调用k次蒙特卡洛算法  
    	unsigned int a,result;
    	bool composite  = false;
    	if(n<5) {
    		if(n==2 || n == 3) return true;
    		return false;
    	} 
    	for(int i=1;i<=k;++i) {
    		//下面这句决定5以下素数测试有问题 
    		a = rand()%(n-3)+2 ;
    		PowerAndPrimeTest(a,n-1,n,result,composite);
    		if(composite || (result!=1)) return false;
    	}
    	return true;
    }
    
    bool PrimeTest(unsigned int n)   
    {
    	if(n==1) return false;
    	else if(n==2) return true;
    	unsigned int i,m = sqrt(n);
    	for(i=2;i<=m;++i) 
    		if(n%i==0) return false;
    	return true;
    }
    
    int main()
    {
    	unsigned int n = 1194211693L;
    	for(int i=2000;i<5000;++i) 
    		if(PrimeTest(i)) {
    			cout<<i<<endl;
    			n=i;
    			break;
    		}
    	
    	for(int i=0;i<20;++i) {
    		if(PrimeTestMC(n,4)) cout<<true<<endl;
    		else cout<<false<<endl;
    	}
    	
    	
    	cin.get();
    	return 0;
    }





    展开全文
  • 随机化算法

    千次阅读 2019-01-12 22:24:52
    随机化算法 百科的介绍: 随机化算法(randomized algorithm),是这样一种算法,在算法中使用了随机函数,且随机函数的返回值直接或者间接的影响了算法的执行流程或执行结果。就是将算法的某一步或某几步置于运气的...

    随机化算法

    百科的介绍:
    随机化算法(randomized algorithm),是这样一种算法,在算法中使用了随机函数,且随机函数的返回值直接或者间接的影响了算法的执行流程或执行结果。就是将算法的某一步或某几步置于运气的控制之下,即该算法在运行的过程中的某一步或某几步涉及一个随机决策,或者说其中的一个决策依赖于某种随机事件。

    算法课本:

    在许多情况下,当算法在执行过程中面临一个选择时,随机化选择常比最优选择省事。因此随机化算法在很大程度上降低算法的复杂度。随机化算法的一个基本特征是对所求问题的同一实例用同一随机化算法求解两次可能得到完全不同的效果。不仅是结果,甚至是时间都有可能相差很大。一般情况下,将随机化算法大致分为四类:

    • 数值随机化算法
    • 蒙特卡罗算法
    • 拉斯维加斯算法
    • 舍伍德算法

    数值化随机算法常用于数值问题求解。这类算法得到的往往是近似解,且近似解的精度随着计算时间的增加而不断提高。在许多情况下,要计算出问题的精确解是不可能的或没有必要的,用数值化税基算法可得到相当满意的解。

    数值类问题常用,多见于MATLAB , 各种积分微分,数学计算中。

    蒙特卡罗算法用于求问题的准确解。对许多问题,近似解是毫无意义的。用蒙特卡罗算法能求得问题的一个解,但这个解未必是正确的。其求得正确解的概率依赖算法所用的时间。算法所用时间越多,得到正确解的概率就越高。蒙特卡罗算法的主要缺点也在于此。一般情况下,无法有效的判断所得到的解是否可定正确。(非一般情况是可以判定的!)

    设p为实数,且1/2<p<1。如果一个蒙特卡罗算法对于问题的任一实例得到正确解的概率不小于p,则称该蒙特卡罗算法是p正确的,且称p-1/2是该算法的优势。按照这种情况,只要执行次数足够多,则可以得到正确解。不过当p小于1/2的时候就无能为力了。不过大多数蒙特卡罗算法经重复调用之后正确率快速上升。

    拉斯维加斯算法不会得到不正确的解。一旦用拉斯维加斯算法找到一个解,这个解就一定是正确解。但有时用拉斯维加斯算法会找不到解。拉斯维加斯算法找到正确解的概率会随着它所用的计算时间的增加而提高。位于所求解问题的任一实例,用同一拉斯维加斯算法反复随该实例求解足够多次,可使解失效的概率任一小。

    它可以显著地改进算法的有效性,甚至对某些迄今为止找不到有效算法的问题,也能得到满意的结果。n皇后问题利用此算法可以有效的解决,算法的思路是每次放置保证不跟已经放入的起冲突即可,直到无法放入或者皇后已经放完为止。

    舍伍德算法总能求得问题的一个解,而且所得的解总是正确的。当一个确定性算法在最坏情况下的计算复杂性与其平均情况下的计算复杂性有较大差别时,可在这个确定性算法中引入随机性将它改造成一个舍伍德算法,消除或减少问题的好坏实例间的这种差别。舍伍德算法的精髓不是避免算法的最坏情形,而是设法消除这种最坏情形行为与特定实例之间的关联性。当出现这种情况时,在算法中增加随机性处理,只要随机性处理和当前确定性算法时间相比远低于它的时间复杂度数量级就可以。快速排序就是它的一个实例。舍伍德算法并不能改变算法的时间复杂度,但算法的时间复杂性相对均匀。

    基于舍伍德算法的设计思想还可以设计高效的数据结构,跳跃表就是其中一例。具体跳跃表的实例可以从网上搜索。私下在阅读相关资料的时候,觉得跳跃表的实例应该可以在数据库的索引设计底层中出现,它是一种牺牲空间增加跳跃索引换取查询速度的,查询算法的效率可以参考快速排序,不过增加和删除的效率有点低。

    展开全文
  • 1、拉斯维加斯(Las Vegas)算法  拉斯维加斯算法不会得到不正确的解。一旦用拉斯维加斯算法找到一个解,这个解就一定是正确解。但有时用拉斯维加斯算法找不到解。...拉斯维加斯算法的一个显著特征是它所作的随机

          1、拉斯维加斯(Las Vegas)算法

         拉斯维加斯算法不会得到不正确的解。一旦用拉斯维加斯算法找到一个解,这个解就一定是正确解。但有时用拉斯维加斯算法找不到解。与蒙特卡罗算法类似,拉斯维加斯算法找到正确解的概率随着它所用的计算时间的增加而提高。对于所求解问题的任一实例,用同一拉斯维加斯算法反复对该实例求解足够多次,可使求解失败的概率任意小。拉斯维加斯算法的一个显著特征是它所作的随机性决策有可能导致算法找不到所需的解。

    void obstinate(Object x, Object y)
    {// 反复调用拉斯维加斯算法LV(x,y),直到找到问题的一个解y
        bool success= false;
        while (!success) success=lv(x,y);
    }
    

          设p(x)是对输入x调用拉斯维加斯算法获得问题的一个解的概率。一个正确的拉斯维加斯算法应该对所有输入x均有p(x)>0。设t(x)是算法obstinate找到具体实例x的一个解所需的平均时间 ,s(x)和e(x)分别是算法对于具体实例x求解成功或求解失败所需的平均时间,则有。解此方程得:


         2、n后问题

         问题描速:在n×n格的棋盘上放置彼此不受攻击的n个皇后。按照国际象棋的规则,皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。n后问题等价于在n×n格的棋盘上放置n个皇后,任何2个皇后不放在同一行或同一列或同一斜线上。


         1)纯拉斯维加斯随机算法求解思路

          对于n后问题的任何一个解而言,每一个皇后在棋盘上的位置无任何规律,不具有系统性,而更象是随机放置的。在棋盘上相继的各行中随机地放置皇后,并注意使新放置的皇后与已放置的皇后互不攻击,直至n个皇后均已相容地放置好,或已没有下一个皇后的可放置位置时为止。

          具体实现代码如下:

         1、RandomNumber.h

    #include"time.h"
    //随机数类
    const unsigned long maxshort = 65536L;
    const unsigned long multiplier = 1194211693L;
    const unsigned long adder = 12345L;
    
    class RandomNumber
    {
    	private:
    		//当前种子
    		unsigned long randSeed;
    	public:
    		RandomNumber(unsigned long s = 0);//构造函数,默认值0表示由系统自动产生种子
    		unsigned short Random(unsigned long n);//产生0:n-1之间的随机整数
    		double fRandom(void);//产生[0,1)之间的随机实数
    };
    
    RandomNumber::RandomNumber(unsigned long s)//产生种子
    {
    	if(s == 0)
    	{
    		randSeed = time(0);//用系统时间产生种子
    	}
    	else
    	{
    		randSeed = s;//由用户提供种子
    	}
    }
    
    unsigned short RandomNumber::Random(unsigned long n)//产生0:n-1之间的随机整数
    {
    	randSeed = multiplier * randSeed + adder;//线性同余式
    	return (unsigned short)((randSeed>>16)%n);
    }
    
    double RandomNumber::fRandom(void)//产生[0,1)之间的随机实数
    {
    	return Random(maxshort)/double(maxshort);
    }
         2、7d4d1.cpp

    //随机化算法 拉斯维加斯算法 n后问题
    #include "stdafx.h"
    #include "RandomNumber.h"
    #include <cmath>
    #include <iostream>
    using namespace std;
    
    class Queen
    {
    	friend void nQueen(int);
    	private:
    		bool Place(int k);		//测试皇后k置于第x[k]列的合法性
    		bool QueensLv(void);	//随机放置n个皇后拉斯维加斯算法
    		int n;					//皇后个数
    		int *x,*y;				//解向量
    };
    
    //测试皇后k置于第x[k]列的合法性
    bool Queen::Place(int k)
    {
    	for(int j=1; j<k; j++)
    	{
    		if((abs(k-j)==abs(x[j]-x[k]))||(x[j]==x[k]))
    		{
    			return false;
    		}
    	}
    	return true;
    }
    
    //随机放置n个皇后的拉斯维加斯算法
    bool Queen::QueensLv(void)
    {
    	RandomNumber rnd;		//随机数产生器
    	int k = 1;				//下一个皇后的编号
    	int count = 1;			//在一列中,可以放置皇后的个数
    
    	while((k<=n)&&(count>0))
    	{
    		count = 0;
    		for(int i=1; i<=n; i++)
    		{
    			x[k] = i;//位置
    			if(Place(k))
    			{
    				y[count++] = i;
    			}
    		}
    		if(count>0)
    		{
    			x[k++] = y[rnd.Random(count)];		//随机位置
    		}
    	}
    
    	return (count>0);		//count>0 表示放置成功
    }
    
    //解n后问题的拉斯维加斯算法
    void nQueen(int n)
    {
    	Queen X;
    	X.n = n;
    
    	int *p = new int[n+1];
    	for(int i=0; i<=n; i++)
    	{
    		p[i] = 0;
    	}
    	X.x = p;
    	X.y = new int[n+1];
    
    	//反复调用随机放置n个皇后的拉斯维加斯算法,直到放置成功
    	while(!X.QueensLv());
    
    	for(int i=1; i<=n; i++)
    	{
    		cout<<p[i]<<" ";
    	}
    	cout<<endl;
    	delete []p;
    }
    
    int main()
    {
    	int n=8;  
        cout<<n<<"皇后问题的解为:"<<endl;  
        nQueen(n);  
        return 0;  
    }
         程序运行结果如下:


         2)与回溯法结合的拉斯维加斯随机算法求解思路

         如果将上述随机放置策略与回溯法相结合,可能会获得更好的效果。可以先在棋盘的若干行中随机地放置皇后,然后在后继行中用回溯法继续放置,直至找到一个解或宣告失败。随机放置的皇后越多,后继回溯搜索所需的时间就越少,但失败的概率也就越大。 

      算法具体代码如下:

        1、RandomNumber.h如上

        2、7d4d1-2.cpp

    //随机化算法 拉斯维加斯算法 n后问题
    #include "stdafx.h"
    #include "RandomNumber.h"
    #include <cmath>
    #include <iostream>
    using namespace std;
    
    class Queen
    {
    	friend bool nQueen(int);
    	private:
    		bool Place(int k);					//测试皇后k置于第x[k]的合法性
    		bool Backtrack(int t);				//解n后问题的回溯法
    		bool QueensLV(int stopVegas);		//随机放置n个皇后拉斯维加斯算法
    		int n,*x,*y;
    };
    
    //测试皇后k置于第x[k]列的合法性
    bool Queen::Place(int k)
    {
    	for(int j=1; j<k; j++)
    	{
    		if((abs(k-j)==abs(x[j]-x[k]))||(x[j]==x[k]))
    		{
    			return false;
    		}
    	}
    	return true;
    }
    
    //解n后问题的回溯法
    bool Queen::Backtrack(int t)
    {
    	if(t>n)
    	{
    		for(int i=1; i<=n; i++)
    		{
    			y[i] = x[i];//问题的解
    		}
    		return true;
    	}
    	else
    	{
    		for(int i=1; i<=n; i++)
    		{
    			x[t] = i;
    			if(Place(t)&&Backtrack(t+1))
    			{
    				return true;
    			}
    		}
    	}
    	return false;
    }
    
    
    //随机放置n个皇后拉斯维加斯算法
    bool Queen::QueensLV(int stopVegas)
    {
    	RandomNumber rnd;		//随机数产生器
    	int k = 1;
    	int count = 1;
    
    	//1<=stopVegas<=n
    	while((k<=stopVegas)&&(count>0))
    	{
    		count = 0;
    		for(int i=1; i<=n; i++)
    		{
    			x[k] = i;
    			if(Place(k))
    			{
    				y[count++] = i;
    			}
    		}
    
    		if(count>0)
    		{
    			x[k++] = y[rnd.Random(count)];//随机位置
    		}
    	}
    	return (count>0);		//count>0表示放置成功
    }
    
    //与回溯法相结合的解n后问题的拉斯维加斯算法
    bool nQueen(int n)
    {
    	Queen X;
    	
    	//初始化X
    	X.n = n;
    
    	int *p = new int[n+1];
    	int *q = new int[n+1];
    
    	for(int i=0; i<=n; i++)
    	{
    		p[i] = 0;
    		q[i] = 0;
    	}
    
    	X.y = p;
    	X.x = q;
    
    	int stop = 3;
    	if(n>15)
    	{
    		stop = n-15;
    	}
    
    	bool found = false;
    	while(!X.QueensLV(stop));
    
    	//算法的回溯搜索部分
    	if(X.Backtrack(stop+1))
    	{
    		for(int i=1; i<=n; i++)
    		{
    			cout<<p[i]<<" ";
    		}
    		found = true;
    		cout<<endl;
    	}
    	
    	delete []p;
    	delete []q;
    	return found;
    }
    
    int main()
    {
    	int n=8;  
        cout<<n<<"皇后问题的解为:"<<endl;  
        while(!nQueen(n));  
        return 0;  
    }
         程序运行结果如图:



    展开全文
  • 结合随机算法和回溯求解n皇后问题

    千次阅读 2010-05-30 11:10:00
    [问题描述] n皇后问题是一个古老而著名的问题,是回溯算法的典型...[算法分析]n皇后问题一般是采用回溯法求解,但当n值较大时,回溯算法效率较低,所以此次作业中将随机算法和回溯法结合起来求解n皇后问题,以提高算

    [问题描述]

        n皇后问题是一个古老而著名的问题,是回溯算法的典型例题。该问题是十九世纪著名的数学家高斯1850年提出:在8X8格的国际象棋上摆放八个皇后,使其不能互相攻击,即任意两个皇后都不能处于同一行、同一列或同一斜线上,问有多少种摆法。

    [算法分析]

    n皇后问题一般是采用回溯法求解,但当n值较大时,回溯算法效率较低,所以此次作业中将随机算法和回溯法结合起来求解n皇后问题,以提高算法的效率。引入随机算法,能保证每次找出的解是正确的,但可能在一次求解过程中找不出可行解,这一点在程序运行过程中能得到体现。

    [程序与结果]

    程序见附件,以n=8为例,运行结果如下:

    展开全文
  • 拉斯维加斯算法N皇后问题

    千次阅读 2020-06-04 13:14:58
    对所求解问题的同一实例用同一随机化算法求解两次可能得到完全不同的效果。 拉斯维加斯算法 拉斯维加斯算法不会得到不正确的解。一旦用拉斯维加斯算法找到一个解,这个解就一定是正确解。但有时用拉斯维加斯算法找不...
  • N×N皇后问题的求解过程就是一个试探回逆的过程。如图-1 (图1-1)  1、首先查找第一行的可放位置,第一行全部可以放,那么我们就先将第一个皇后放在(0,0)点。 (图1-2) 2、再...
  • 拉斯维加斯算法N皇后问题

    千次阅读 2016-12-21 22:47:06
    拉斯维加斯算法的一个显著特征是它所作的随机性决策有可能导致算法找不到所需的解。因此通常用一个bool型函数表示拉斯维加斯算法。 void Obstinate(InputType x, OutputType &y) {   // 反复调用拉斯维加斯...
  • 用遗传算法求解n皇后问题。n*n的棋盘上摆放n个皇后,两个皇后如果在同一直线或者同一对角线就会互相攻击。 找一种摆法,使得任意两个皇后之间都不会互相攻击。 问题描述: 遗传算法举例:8皇后问题 个体:长为8的...
  • n皇后的拉斯维加斯回溯算法

    千次阅读 2015-11-21 19:33:18
     拉斯维加斯算法不会得到不正确的解。一旦用拉斯维加斯算法找到一个解,这个解就一定是正确解。但有时用拉斯维加斯算法会找不到解。拉斯维加斯算法找到正确解的概率随着它所用的计算时间的增加而提高。对于所求解的...
  • 深入N皇后问题的一个高效算法的详解 author: liuzhiwei N皇后问题是一个经典的问题,在一个N*N的棋盘上放置N个皇后,每行一个并使其不能互相攻击(同一行、同一列、同一斜线上的皇后都会自动攻击)。 一、 求解N...
  • 爬山法就是完全的贪心算法,每一步都选最优位置,可能只能得到局部最优解。本实验对普通爬山法进行了简单的优化,采用了传统爬山法的变种——随机重启爬山法,当爬山步数超过一定值时,会重新打乱棋盘,重新“爬山”...
  • 概率算法(随机化算法

    千次阅读 2019-07-27 13:46:19
    概率算法也叫随机化算法。概率算法允许算法在执行过程中随机地选择下一个计算步骤。在很多情况下,算法在执行过程中面临选择时,随机性选择比最优选择省时,因此概率算法可以在很大程度上降低算法的复杂度。概率算法...
  • 随机化算法学习笔记

    2020-05-19 10:42:06
    对所求解问题的同一实例用同一随机化算法求解两次可能得到完全不同的效果(不确定的算法) 大致内容 数值化随机算法 求解数值问题的近似解,时间越长,精度越高 蒙特卡罗算法 求解准确解(不一定正确),时间越长,...
  • N皇后(1000~1000000)。 1.要求: 任意输入一个整数N, 103 £ N £ 106。 在普通个人计算机上,对输入N,3分钟内给出一个皇后不冲突的方案。 输出到磁盘。保存输出文件名为“N.txt”。N.txt用32位无符号整数的二...
  • n-皇后问题 算法代码

    2017-10-22 22:06:44
    n-皇后问题是在nn列的棋盘上放置n皇后,使得皇后彼此之间不受攻击,其规则是任意两个皇后不在同一行、同一列和相同的对角线上。 拟采用以下思路解决n-皇后问题:第i个皇后放在第i行。从第一个皇后开始,对每个...
  • 随机化算法

    千次阅读 2013-08-03 21:42:47
    0043算法笔记——【随机化算法】解非线性方程组 分类: 算法2013-06-05 11:54 308人阅读 评论(0) 收藏 举报 解非线性方程组随机化算法目标函数算法笔记数值随机化算法  问题描述  求解下面的非...
  • 人工智能课程设计——八皇后问题的求解算法比较八皇后问题的求解算法及步骤分析回溯法——通用的解法回溯法求解八皇后问题具体步骤为:爬山法——经典的解法随机重启爬山法——前进的解法模拟退火法——他山之石A* ...
  • 随机化算法1-5

    千次阅读 2014-01-09 15:04:26
    1.《随机化算法(1) — 随机数》 2.《随机化算法(2) — 数值概率算法》 3.《随机化算法(3) — 舍伍德(Sherwood)算法》 4.《随机化算法(4) — 拉斯维加斯(Las Vegas)算法》 正文: 蒙特卡罗法(Monte Carlo method)...
  • 在处理8皇后问题的时候,穷举法是最费时的,回朔比穷举好点,而当数据量比较大的时候,如1000皇后问题,穷举的化有1000的1000次方,肯定超时,用随机化算法的思路,先随机的在棋盘上放一部分皇后,再来设计算法,会...
  • 随机化算法(1) — 随机数》2.《随机化算法(2) — 数值概率算法》3.《随机化算法(3) — 舍伍德(Sherwood)算法》正文:悟性不够,这一章看代码看了快一个上午,才理解。上一章讲过《概率算法(3) — 舍伍德(Sherwood)...
  • N皇后问题

    2014-12-26 10:29:27
    N皇后问题 经典的回溯问题 8皇后问题(java算法实现),可以详细了解整一个的解题思路 解题思路: 关键是找到所满足的条件: 1.不在同一行上2.不在同一列上3.不在同一斜线上4.不在同一反斜线上 ...
  • N皇后问题就不再叙述了,Google一下就知道了(这里我们讨论找出一个或几个解,不讨论找出全部解的方法) N皇后有一个解法是回溯法,这个可以解决,但是效率不是很高。(不过这个方法可以找出所有解) 结合随机方法...
  • n皇后问题的解决 (QS2算法

    千次阅读 2006-12-27 15:47:00
    n皇后问题的解决 (QS2算法) 8皇后问题是一个广为人知的问题:将8个皇后放在8×8的棋盘上,皇后之间不能互相攻击,求各种放法。更一般的,把8换成n,其解法个数是随n成几何级增长的,因此程序运行时间也是几何级别...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 1,534
精华内容 613
关键字:

n皇后问题随机化算法