拉斯维加斯算法之n后问题
拉斯维加斯算法之n后问题
1、拉斯维加斯(Las Vegas)算法
舍伍德算法优点在于计算时间复杂度对所有实例相对均匀，但与其相应的确定性算法相比，其平均时间复杂度没有改进。拉斯维加斯算法则不然，它能显著改进算法的有效性，甚至对某些迄今为止找不到有效算法的问题，也能得到满意的算法。
拉斯维加斯算法不会得到不正确的解。一旦用拉斯维加斯算法找到一个解，这个解就一定是正确解。但有时用拉斯维加斯算法找不到解。与蒙特卡罗算法类似，拉斯维加斯算法找到正确解的概率随着它所用的计算时间的增加而提高。对于所求解问题的任一实例，用同一拉斯维加斯算法反复对该实例求解足够多次，可使求解失败的概率任意小。拉斯维加斯算法的一个显著特征是它所作的随机性决策有可能导致算法找不到所需的解。
void obstinate(Object x, Object y) {// 反复调用拉斯维加斯算法LV(x,y)，直到找到问题的一个解y bool success= false; while (!success) success=lv(x,y); }View Code
设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个皇后均已相容地放置好，或已没有下一个皇后的可放置位置时为止。
具体实现代码如下：
//随机化算法 拉斯维加斯算法 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; }View Code
#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); }View Code
代码实现结果：
上述算法一旦发现无法再放置下一个皇后，就全部重新开始，下面是将随机放置策略与回溯法结合例子。
//随机化算法 拉斯维加斯算法 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; }View Code
#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); }View Code
运行结果：
参考文献：王晓东《算法设计与分析》第二版
https://blog.csdn.net/liufeng_king/article/details/9245585
拉斯维加斯算法之n后问题相关教程
-
拉斯维加斯随机化算法求解整数因子分解
问题描述 设n1是一个整数。关于整数n的因子分解问题是找出n的如下形式的 唯一分解式 ：。其中，p1p2…pk是k个素数，m1,m2,…,mk是k个正整数。如果n是一个合数，则n必有一个非平凡因子x，1xn，使得x可以整除n。 给定一个合数n， 求n的一个非平凡因子的问题称
-
java面试之归并排序的应用
文章背景： 在复习算法及数据结构时，找到了面试笔试题目，下面我们来看看题目： （学习视频分享：java教学视频） 在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数P。并将P对1
-
【快速因数分解】Pollards Rho 算法
Pollard-Rho 是一个很神奇的算法，用于在 $O(n^{\frac{1}4}) $的期望时间复杂度内计算合数 n 的某个非平凡因子（除了1和它本身以外能整除它的数）。事书上给出的复杂度是 \(O(\sqrt{p})\) ， p 是 n 的某个最小因子，满足 p 与 n/p 互质。虽然是随机的，但 P
-
常用的无损压缩算法有哪些
常用的无损压缩算法有：1、LZ77算法，该算法是很多其他无损压缩算法的基础；2、LZR算法，是旨在提升LZ77的一个算法；3、LZSS算法，该算法目标是成为LZ77的一个线性时间替换算法；4、DEFLATE算法；5、LZMA算法等等。 数据压缩是保留相同或绝大部分数据前提下
-
数据结构与算法：利用数组实现完全二叉树（C++）
数据结构与算法：利用数组实现完全二叉树（C++） 任务：使用C++语言，通过数组的形式来实现一颗平衡二叉树，包括树的创建，添加结点，查找结点，删除结点等功能。 main.cpp 代码如下： #include CompleteBinaryTree.hint main(){ CompleteBinaryTreechar tree
-
周练（8）53. 最大子序和
周练（8）53. 最大子序和 贪心算法 class Solution: def maxSubArray(self, nums: List[int]) - int: # 贪心算法 nlen = len(nums) if not nums: return float(-inf) cur_sum = max_sum = nums[0] for i in range(1, nlen): cur_sum = max(nums[i], cur_sum +
-
循环冗余校验码CRC算法实现和求出碰撞值
循环冗余校验码CRC算法实现和求出碰撞值 答： 八位的碰撞一共有八个 10001101 1010 10011110 1010 10101011 1010 10111000 1010 11000001 1010 11010010 1010 11100111 1010 11110100 1010 代码 a=['1', '0', '0', '1', '1'] #除数b=['1', '0', '1', '0', '1'
-
STL算法的简介
STL算法的简介 一、STL算法介绍 STL算法部分主要是由三个头文件承担： algorithm、numeric、functional algorithm：意思是算法，只要想使用STL库中的算法函数就得包含该头文件。 numeric：包含了一系列用于计算数值序列的算法，其具有一定的灵活性，也能够适