文章目录

  上节课老师给我们讲解了随机算法,随机算法和贪心算法一样都是比较简单的算法。随机算法在分布式计算、通信、信息检索、计算几何、密码学等许多领域都有着广泛的应用,通常可分为两类Las Vegas算法和Monte Carlo算法。简单而言,LV算法通过多次求解来获得一个一定是正确的解,而MC算法通过多次求解来提高可信度,最终获得一接近于完全正确或者可信度可以接受(如99%或者更高的可能性是正确的)的近似解。

  常见的实例有:找第k小元素的随机算法(Las Vegas算法)、Testing String Equality(Monte Carlo算法)、Pattern Matching(Monte Carlo算法)及其改进型(转为Las Vegas算法)、Random Sampling问题、主元素问题、素数测试问题、n后问题。

  其中Random Sampling问题和主元素问题过于简单,所以没有实现,如果读者感兴趣可以自行实现,很简单。

  下面进入正题,首先是找第k小元素的随机算法:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
package random;

import java.util.ArrayList;
import java.util.List;

/**
* Las Vegas算法找第K小元素的java实现
* @author jrhu05
*
*/
public class FindTheKMin {
public static void main(String[] args) {
//int[] a={34,12,6,88,3,90,13,12,22,67,99,102,33,57};
List<Integer> a=new ArrayList<Integer>();
for (int i = 0; i < 10; i++) {
a.add((int) (Math.random()*100));
}
System.out.println(a);
int index=(int) (Math.random()*9+1);
System.out.println("the "+index+" min is ");
lasVegasFind(a,index);
}

private static void lasVegasFind(List<Integer> a, int index) {
// TODO 自动生成的方法存根
if (index>a.size()||index<0) {
System.out.println("index out of boundary!");
}else {
int random=(int) (Math.random()*a.size());
int mid=a.get(random);
List<Integer> s1=new ArrayList<Integer>();
List<Integer> s2=new ArrayList<Integer>();
List<Integer> s3=new ArrayList<Integer>();
for (Integer x : a) {
if (x<mid) {
s1.add(x);
}else if (x==mid) {
s2.add(x);
} else {
s3.add(x);
}
}
if (s1.size()>=index) {
lasVegasFind(s1, index);
}else if (s1.size()+s2.size()>=index) {
System.out.println(mid);
return;
}else if (s1.size()+s2.size()<index) {
lasVegasFind(s3, index-s1.size()-s2.size());
}
}

}
}

  接着是Testing String Equality(Monte Carlo算法),问题的基本描述贴在代码里了,其中我用01二进制序列来近似替代字符序列,其实二者原理层面都是一样的,用来理解算法的基本原理没有任何问题。其中所用到的模二除法是源自CRC校验那篇文章,感兴趣的可以戳这里查看具体的算法流程。由于下一个Pattern Matching问题可以直接调用Testing String Equality中的实现类,所以所有的相关类全部用public属性,方便调用。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
package random;

import java.util.Arrays;

/**
* Monte Carlo算法长字符串匹配的实现
* @author jrhu05
*
*/
public class TestingStringEquality {
/**
* 问题描述
设A处有一个长字符串x(e.g. 长度为10^6 ),
B处也有一个长字符串y,A将x发给B,由
B判断是否有x=y
*/
static int M=11483;
public static void main(String[] args) {
int[] byteA=randomByteGen();
int[] byteB=randomByteGen();
//System.out.println(Arrays.toString(byteA));
System.out.println(byteA.length);
System.out.println(byteB.length);
long mccStart=System.currentTimeMillis();
boolean isEqual=monteCarloCheck(byteA,byteA);
long mccEnd=System.currentTimeMillis();
boolean isEqual2=normalCheck(byteA,byteA);
long ncEnd=System.currentTimeMillis();
System.out.println("byteA equals to byteB?: "+isEqual);
System.out.println("the time cost of monteCarloCheck is: "+(mccEnd-mccStart)+"ms");
System.out.println("the time cost of normalCheck is: "+(ncEnd-mccEnd)+"ms");
}

/**
* 普通检测法
* @param byteA
* @param byteB
* @return
*/
public static boolean normalCheck(int[] byteA, int[] byteB) {
// TODO 自动生成的方法存根
if (byteA.length!=byteB.length) {
return false;
}else {
for (int i = 0; i < byteA.length; i++) {
if (byteA[i]!=byteB[i]) {
return false;
}
}
return true;
}
}

/**
* 指纹检测法
* @param byteA
* @param byteB
* @return
*/
public static boolean monteCarloCheck(int[] byteA, int[] byteB) {
// TODO 自动生成的方法存根
int[] mBytes=m2Binary();
if (byteA.length!=byteB.length) {
return false;
}else {
int[] fingerPrintA=mod2Div(byteA, mBytes);
int[] fingerPrintB=mod2Div(byteB, mBytes);
for (int i = 0; i < fingerPrintA.length; i++) {
if (fingerPrintA[i]!=fingerPrintB[i]) {
return false;
}
}
return true;
}
}

/**
* 将取指纹用到的M转换成二进制01数组
* @return
*/
public static int[] m2Binary(){
String mString=Integer.toBinaryString(M);
String[] mStrings=mString.split("");
int[] mBytes=new int[mStrings.length];
for (int i = 0; i < mBytes.length; i++) {
mBytes[i]=Integer.valueOf(mStrings[i]);
}
System.out.println(Arrays.toString(mBytes));
return mBytes;
}

/**
* 随机生成长度在1000000以内的01比特数组
* @return 01比特数组
*/
public static int[] randomByteGen() {
// TODO 自动生成的方法存根
int length=(int) (Math.random()*1000000);
//int length=10000000;
int[] gen=new int[length];
for (int i = 0; i < gen.length; i++) {
double flag=Math.random();
if (flag>0.5) {
gen[i]=1;
}else {
gen[i]=0;
}
}
return gen;
}

/**
* 模二除法求余数
* @param newInfo 被除数
* @param genarete 除数
* @return 余数
*/
public static int[] mod2Div(int[] newInfo, int[] genarete) {
//将生成多项式的最高位去掉,因为最高位经过xor肯定出0所以不用考虑
int[] newGen=new int[genarete.length-1];
for (int i = 0; i < newGen.length; i++) {
newGen[i]=genarete[i+1];
}
// TODO 自动生成的方法存根
int flag=newInfo[0];
//余数存储矩阵初始化
int[] temp=new int[newGen.length];
int lastIndex=temp.length-1;
for (int i = 0; i < temp.length; i++) {
temp[i]=newInfo[i+1];
}
//初始化计数器
int count=temp.length+1;
//进行窗口推进式xor运算
while (count<=newInfo.length) {
if (flag==1) {
temp=xorGroup(temp, newGen);
}
//标记位为temp的高位,如果为1则表示下一次运算结果可也上1,否则只能上0
if (count<newInfo.length) {
flag=temp[0];
//temp运算窗口移动一位,同时计数器自加
for (int i = 0; i <temp.length-1; i++) {
temp[i]=temp[i+1];
}
temp[lastIndex]=newInfo[count];
}
count++;

}
// System.out.println("模二运算计算出的余数:");
// System.out.println(Arrays.toString(temp));
return temp;
}
/**
* 对两个二进制序列进行异或运算
* @param a 待计算序列1
* @param b 待计算序列2
* @return 异或运算结果
*/
public static int[] xorGroup(int[] a,int[] b){
int[] result=new int[a.length];
for (int i = 0; i < a.length; i++) {
result[i]=xor(a[i],b[i]);
}
return result;
}
/**
* 对两个二进制位进行异或运算
* @param i 待计算二进制位1
* @param j 待计算二进制位2
* @return 异或运算结果
*/
public static int xor(int i, int j) {
// TODO 自动生成的方法存根
if (i==j) {
return 0;
}else {
return 1;
}
}
}

  在实际运行的时候,发现随机算法较之于直接比较的算法没有取得优势,反而有较大的损耗,这与理论预计不符,思考后觉得原因应该是出在我取指纹(即模二除法)部分代码不够优化,执行效率低所致,故以上代码仅供理解算法原理之用。

  附运行结果截图:

  最后是Pattern Matching,字符串匹配,我直接实现了它的改进型,转成了Las Vegas算法。其实两者没有太大区别,只是在进行指纹匹配发现为true后不直接返回,进行一一匹配,即保证100%两子串完全相同时才返回为真,这样就变成无需多次运行来提高正确概率,一次运行即可确切的给出是否有子串匹配,即算法出错的概率为0。

  具体实现如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
package random;
/**
* LasVegas算法实现字符串匹配
* @author jrhu05
*
*/
public class PatternMatching {
/**
* 问题描述
 给定两个字符串:X=x 1 ,…,x n ,Y=y 1 ,…,y m ,
看Y是否为X的子串?(即Y是否为X中的一段)
*
*/
public static void main(String[] args) {
//包含Y的字符串
// int[] X={1,0,1,0,1,0,0,1,1,1,1,0,0,1,1,1,1,0,0,1,0,1,1,0,1,0,1,1,1,1,0,
// 0,1,0,1,1,0,1,0,1,1,1,1,0,0,1,0,1,1,0,1,0,1,1,1,1,0,0,1,0,1,1,
// 0,1,0,1,1,1,1,0,0,1,0,1,1,0,1,0,1,1,1,1,0,0,1,0,1,1,0,1,0,1,1,
// 1,1,0,0,1,0,1,1,0,1,0,1,1,1,1,0,0,1,0,1,1,0,1,0,1,1,1,1,0,0,1,
// 0,1,1,0,1,0,1,1,1,1,0,0,1,0,1,1,0,1,0,1,1,1,1,0,0,1,0,1,1,0,1,
// 0,1,1,1,1,0,0,1,0,1,1,0,1,0,1,1,1,1,0,0,1,0,1,1,0,1,0,1,1,1,1,
// 0,0,1,0,1,1,0,1,0,1,0,1,1,0,1,0,0,1,1,1,0,0,1,1};
//不包含Y的字符串 供测试使用
int[] X={1,0,1,0,1,0,0,1,1,1,1,0,0,1,1,1,1,0,0,1,0,1,1,0,1,0,1,1,1,1,0,
0,1,0,1,1,0,1,0,1,1,1,1,0,0,1,0,1,1,0,1,0,1,1,1,1,0,0,1,0,1,1,
0,1,0,1,1,1,1,0,0,1,0,1,1,0,1,0,1,1,0,1,1,0,1,0,1,1,1,1,0,0,1,0,1,1,0,1,0,1,1,
1,1,0,0,1,0,1,1,0,1,0,1,1,1,1,0,0,1,0,1,1,0,1,0,1,1,1,1,0,0,1,
0,1,1,0,1,0,1,1,1,1,0,0,1,0,1,0,1,1,0,1,0,1,1,1,0,1,0,1,1,1,1,0,0,1,0,1,1,0,1,
0,1,1,1,1,0,0,1,0,1,1,0,1,0,1,1,1,1,0,0,1,0,1,1,0,1,0,1,1,1,1,
0,0,1,0,1,1,0,1,0,1,0,1,1,0,1,0,0,1,1,1,0,0,1,1};
int[] Y={1,1,1,1,0,0,1,0,1,1,0,1,0,1,1,1,1,0,0,1,0,1,1,0,1,0,1,1,1,1,
0,0,1,0,1,1,0,1,0,1,1,1,1,0,0,1,0,1,1,0,1,0,1,1,1,1,0,0,1,0,1,
1,0,1,0,1,1,1,1,0,0,1,0,1,1,0,1,0,1,1,1,1,0,0,1,0,1,1,0,1,0,1,
1,1,1,0,0,1,0,1,1,0,1,0,1,1,1,1,0,0,1,0,1,1,0,1,0,1,1,1,1,0,0,
1,0,1,1,0,1,0,1,1,1,1,0,0,1,0,1,1,0,1,0,1,1,1,1,0,0,1,0,1,1,0,
1,0,1,1,1,1,0,0,1,0,1,1,0,1,0,1,1,1,1,0,0,1,0,1,1,0,1,0,};
boolean isContain=lasVegPatMatch(X,Y);
System.out.println(isContain);
}
private static boolean lasVegPatMatch(int[] x, int[] y) {
// TODO 自动生成的方法存根
for (int i = 0; i < x.length-y.length; i++) {
int[] subX=new int[y.length];
for (int j = 0; j < subX.length; j++) {
subX[j]=x[i+j];
}
boolean isEqual=TestingStringEquality.monteCarloCheck(subX, y);
if (isEqual) {
boolean isAbsEqual=TestingStringEquality.normalCheck(subX, y);
if (isAbsEqual) {
System.out.println("sub is from: "+i);
return true;
}else {
return true;
}
}
}
return false;
}

}

  明天的课要讲素数测试问题和N皇后问题,bravo!好高大上的样子。

  补完素数测试和N后问题。

  素数测试问题:

  PPT里给出的迭代方式求解的方法实在看不懂,所以我又照着概念自己写了个非递归的,2333。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
package random;

import java.util.Random;

/**
* Monte Carlo算法+二次探测实现素数测试
* @author jrhu05
*
*/
public class PrimeCheck {
static boolean composite;
public static void main(String[] args) {
//int n=61237;
//int n=17;
int n=561;//561是一个典型的Carmichael数,故用之来测试
System.out.println(n+" is prime?:"+prim(n));
}

private static boolean prim(int n) {
// TODO 自动生成的方法存根
int a,result;
composite=false;
a=(int) (Math.random()*(n-3)+2);//随机取底数a,随机性体现的地方
//result=power(a,n-1,n);
result=powerNoRec(a,n-1,n);
if (composite||(result!=1)) {
return false;
}else return true;

// if (result!=1) {
// //如果没有二次探测,那么对于这个问题false是百分之百正确的
// //即回答是合数
// return false;
// }else {
// //而true是有可能错误的
// return true;
// }
}

private static int powerNoRec(int a, int i, int n) {
// TODO 自动生成的方法存根
//我自己实现的非递归方法
int result=(int) (Math.pow(a, i)%n);
if (n<2) {
composite=false;
}else {
for (int j = 2; j < n-1; j++) {
if ((j*j)%n==1) {
composite=true;
}
}
}
return result;
}

private static int power(int a, int p, int n) {
// TODO 自动生成的方法存根
//ppt中用递归来进行实现的方法
//计算a^p mod n,并实施对n的二次探测
int x,result;
if (p==0) {
result=1;
}else {
x=power(a, p/2, n);//递归计算
result=(x*x)%n;//二次探测
if ((result==1)&&(x!=1)&&(x!=(n-1))) {
//即表示则方程x^2 ≡ 1(mod p)
//的解不为x=1,p-1
//即二次探测失败
composite=true;
}

if ((p%2)==1) {//p是奇数
result=(result*a)%n;
}
}
return result;
}
}

  N后问题:相当有名的问题,我用随机算法没有求解出结果,最高只能求到7,后面的死活凑不出最后一位来,也难怪8^8=16 777 216其中只有96中情况符合要求,概率小的可怜,百万分之几的概率。

  不过思路是没问题的,下面的回溯法应该有确定性的解法,到时候在看吧。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
package random;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Map.Entry;
import java.util.Set;

/**
* 用随机算法解决N后问题
* 以八皇后问题为例
* @author jrhu05
*
*/
public class NQueens {
private static int[][] map=new int[8][8];
public static void main(String[] args) {
//地图初始化,0表示空,1表示皇后在这个位置上
for (int i = 0; i < map.length; i++) {
for (int j = 0; j < map[i].length; j++) {
map[i][j]=0;
}
}
//这部分是求解正确答案的循环,有兴趣的可以取消注释跑一下玩//玩,反正我跑了几分钟也没出结果,2333
// int count=0;
// while (count<8) {
// count=0;
// eightQueen();
// for (int i = 0; i < map.length; i++) {
// for (int j = 0; j < map[i].length; j++) {
// if (map[i][j]==1) {
// count++;
// }
// }
// }
// System.out.println(count);
// }
eightQueen();
for (int i = 0; i < map.length; i++) {
for (int j = 0; j < map[i].length; j++) {
System.out.print(map[i][j]+" ");
}
System.out.println();
}

}


private static void eightQueen() {
// TODO 自动生成的方法存根
for (int i = 0; i < map.length; i++) {
for (int j = 0; j < map[i].length; j++) {
map[i][j]=0;
}
}
for (int i = 0; i < map.length; i++) {
boolean stopFlag=false;
int count=0;
while (!stopFlag) {
int localtion=(int) (Math.random()*7);//随机产生皇后位置
if (count>=100000) {
//超时,未找到完整解时返回
return;
}
if (i==0) {
map[i][localtion]=1;//第一行直接摆,无需检测冲突
stopFlag=true;
}else {
if (!checkCollision(i,localtion)) {
map[i][localtion]=1;//如果没有检测到冲突
stopFlag=true;
}
}
count++;
}
}
}
/**
* 冲突检测,检测要摆的皇后为位置和上面已经摆好的所有皇后的位置是否有冲突
* @param i 准备摆的皇后的行
* @param localtion 准备摆的皇后的列
* @return 是否有冲突
*/
private static boolean checkCollision(int i, int localtion) {
// TODO 自动生成的方法存根
boolean collison=false;
List<Integer[]> resultList=new ArrayList<Integer[]>();
for (int j = 0; j < map.length; j++) {
for (int j2 = 0; j2 < map[j].length; j2++) {
if (map[j][j2]==1) {
resultList.add(new Integer[]{j,j2});
}
}
}

for (Integer[] integers : resultList) {
int locRow=integers[0];//已摆好的queen的行
int locCol= integers[1];//已摆好的queen的列
int unLocRow=i;//未摆好的queen的行
int unLocCol=localtion;//未摆好的queen的列
if (unLocCol==locCol ||
(locRow-unLocRow)==(locCol-unLocCol)||(locRow-unLocRow)==-(locCol-unLocCol)) {
collison=true;
}
}


return collison;
}
}

结果示意图:

文章目录