舍伍德（Sherwood）算法学习笔记
⼀.概念引⼊
设A是⼀个确定性算法，当它的输⼊实例为x时所需的计算时间记为tA(x)。设Xn 是算法A的输⼊规模为n的实例的全体，则当问题的输⼊规模为n时，算法A所需的平均时间为。这显然不能排除存在x∈Xn使得的可能性。希望获得⼀个随机化算法B，使得对问题的输⼊规模为n的每⼀个实例均有。这就是舍伍德算法设计的基本思想。当s(n)与tA(n)相⽐可忽略时，舍伍德算法可获得很好的平均性能。
概率算法的⼀个特点是对同⼀实例多次运⽤同⼀概率算法结果可能同。舍伍德算法(O(sqrt(n))，综合了线性表和线性链表的优点)总能求的问题的⼀个正确解，当⼀个确定性算法在最坏情况和平均情况下差别较⼤时可在这个确定性算法中引⼊随机性将之改造成⼀个舍伍德算法；引⼊随机性不是为了消除最坏，⽽是为了减少最坏和特定实例的关联性。⽐如线性表a的查若是10(独⼀⽆⼆)，如果在a[0]则为O(1)，若是最后⼀个则O(n)，可见时间与输⼊实例有关，此时可引⼊随机性将之改造成⼀个舍伍德算法。
有时候⽆法直接把确定性算法改造为舍伍德算法，这时候对输⼊洗牌。
下⾯是洗牌算法源代码：
import java.util.Random;
public class Shuffle {
public static void main(String[] args) {
int a[] = new int[]{1,2,4,5,8};
/*
* Collections.shuffle(list)参数只能是list
*/
myShuffle(a);
for(int i:a) {
//犯了个低级错误，输出了a[i]，结果数组下标越界异常
System.out.print(i+" ");
}
System.out.println();
}
private static void myShuffle(int[] a) {
int len = a.length;
for(int i=0; i<len; i++) {
Random r = new Random();
//直接Int(len)提⽰静态⽅法⾥⽆法引⽤
int j = r.nextInt(len);
//Collections.swap(list,i,j)必须是list类型
if(i!=j) {//原来没加这个条件
int temp = a[i];
a[i] = a[j];
a[j] = temp;
}
}
}
}
⼆.舍伍德思想解决迅雷2010年校招--发牌
问题描述：52张扑克牌分发给4⼈，每⼈13张，要求保证随机性。已有随机整数⽣成函数rand()，但开销较⼤。请编写函数实现void deal(int a[],int b[],int c[],int d[])，扑克牌⽤序号0-51表⽰，分别存在⼤⼩为13的a，b,c,d四个数组中，要求尽可能⾼效。
import java.util.Random;
public class Poker {
/*
* 这道题确实不怎么明⽩，直接初始化后洗牌算法不得了
* 不过解答只是替换nextInt，直接线性同余了，交换次数也减少了
* 交换次数是随机产⽣的
*/
//为⽅便swap和deal函数使⽤
static int array[] = new int[52];
public static void main(String[] args) {
for(int i=0; i<array.length; i++) {
array[i] = i;
}
int a[] = new int[13];
int b[] = new int[13];
int c[] = new int[13];
int d[] = new int[13];
deal(a,b,c,d);
//这样输出⽅便
for(int i=0; i<13; i++) {
System.out.println(a[i]+" "+b[i]+" "+c[i] + " "+d[i]);
}
}
private static void deal(int[] a, int[] b, int[] c, int[] d) {
int m = 10;
int p = 31;//需要素数
int q = 10;
Random r = new Random();
int num = r.nextInt(52);//循环次数
for(int i=0; i<num; i++) {
m = m*p + q;
m = m%(51-i);
int j = 51 - m;
if(i!=j) {
swap(array,i,j);
}
}
for(int i=0; i<13; i++) {
a[i] = array[i];
b[i] = array[i+13];
c[i] = array[i+26];
d[i] = array[i+39];
}
}
private static void swap(int[] a, int i, int j) {
//交换是正确的
int temp = a[i];
a[i] = a[j];
a[j] = temp;
}
}
三.舍伍德思想快拍算法解决第k⼩问题
import java.util.Arrays;
import java.util.Random;
/*
* ⽬前还不知道不到咋办？
* 这是个愚蠢的问题，肯定得到，因为是第k个
* 只需要判断k的合法性，在selectK函数外部
*/
public class SherwoodQsort {
/**
*舍伍德思想快拍算法解决第k⼩问题(就是正所第k个)
*记得看算法导论时提出⼀个算法是维护⼀个k⼤⼩数组，扫描原有数组不断插⼊排序，最后第k个元素就是所求    *这样等于说是求出了前k⼩，并不仅仅是第k⼩，肯定效率不如下⾯。
*/
public static void main(String[] args) {
//注意：数组a的最后⼀项表⽰最⼤值
int a[] = new int[]{1,8,4,9,0,32,45,27,6,5,65535};
int b[] = new int[a.length];
java笔记总结b = pyOf(a, a.length);
//Collections.sort只对list可⽤
Arrays.sort(b);
System.out.print("待排序数组排序后为：");
for(int i:b) {
System.out.print(i+" ");
}
System.out.println();
int k = 5;
//注意：没把数组a的最后⼀项算进去
int ans = selectK(a,0,a.length-1,k);
System.out.print("第k(5)个数组元素是:"+ans+"\n");
}
private static int selectK(int[] a, int left, int right, int k) {
//注意right=a.length-1，没把数组a的最后⼀项算进去
while(true) {//更新left，right，k的值，直到到为⽌
if(left>=right) {
return a[left];
}
//随机选择划分项，注意right=a.length-1，没把数组a的最后⼀项算进去
int r = createRandom(left,right);
int i = left;
/
*
* 注意：数组a的最后⼀项65535表⽰最⼤值，是特地加上去的
* 产⽣的r最多是a.length-1(因为right=a.length-1)
* 这样下⾯的j=r+1才绝对不会越界，⼤多是这么处理的
*/
int j = right+1;//right=a.length-1，就是数组最⼤项65535
if(i!=r) {
//注意是和r交换
swap(a,a[i],a[r]);
}
//实际上是partion函数，由于需要返回p和j，就不单独写了
int p = a[left];//虽然初试i=left，但下标不可是i
while(true) {
//直到左边⼩于划分项，右边⼤于为⽌
while(a[++i]<p);
while(a[--j]>p);
//写在交换之前
if(i>=j) {
break;
}
swap(a,i,j);
}
/
/交换，完成⼀次划分
a[left] = a[j];
a[j] = p;
int t = j-left+1;
if(t==k) {
return p;//或者a[j]
}else if(t>k) {//在左边
right = j - 1;
}else {
/*
* 原来这个顺序错了，结果⼀直数组下标越界
*/
k = k - t;
left = j+1;
}
}
}
private static void swap(int[] a, int i, int j) {
//交换是正确的
int temp = a[i];
a[i] = a[j];
a[j] = temp;
}
private static int createRandom(int left, int right) {
Random r = new Random();
Int(right-left+1) + left;
}
}
四.舍伍德随机化思想搜索有序表
问题描述
⽤两个数组来表⽰所给的含有n个元素的有序集S。⽤value[0:n]存储有序集中的元素，link[0:n]存储有序集中元素在数组value中位置的指针(实际上使⽤数组模拟链表)。link[0]指向有序集中的第⼀个元素，集value[link[0]]是集合中的最⼩元素。⼀般地，如果value[i]是所给有序集S中的第k个元素，则value[link[i]]是S中第k+1个元素。S 中元素的有序性表现为，对于任意1<=i<=n有value[i]<=value[link[i]]。对于集合S中的最⼤元素value[k]有，link[k]=0且value[0]是⼀个⼤数。
举例
搜索思想
随机抽取数组元素若⼲次，从较接近搜索元素x的位置开始做顺序搜索。
import java.util.Random;
public class SearchK {
public static void main(String[] args) {
int value[] = new int[]{65535,2,3,13,1,5,21,8};
int link[] = new int[]{4,2,5,6,1,7,0,3};
//查看是否存在元素k
int k = 13;
boolean flag = searchK(value,link,k);
System.out.println("元素K(13)是否到:"+flag);
}
private static boolean searchK(int[] value, int[] link, int x) {
int max = value[1];
int m = (int)Math.sqrt(value.length-1);
Random r = new Random();
int index = 1;//这个初始化本是为了不让编译器报错(未初始化)
for(int i=0; i<m; i++) {
//随机产⽣元素位置，加1是为了不取到value[0]
int j = r.nextInt(value.length-1) + 1;
int y = value[j];
/
*
* 不明⽩max作⽤
* value[index]⼀定⼩于x，所以下⾯才可以顺序搜索
*/
if(max<y&&y<x) {
max = y;
index = j;
}
}
//顺序搜索
while(value[link[index]]<x) {
index = link[index];
}
return value[link[index]]==x;
}
}
/*
*不懂，n个元素
* if(!searchK(value,link,x))
{
value[++n] = x;
link[n] = link[index];
link[index] = n;
}
//删除集合中指定元素
template<class Type>
void OrderedList<Type>::Delete(Type k)
{
int index;
if(searchK(value,link,x))
{
int p = link[index];
if(p == n)
{
link[index] = link[p];
}
else
{
if(link[p]!=n)
{
int q = SearchLast();
link[q] = p;
link[index] = link[p];
}
value[p] = value[n];//删除元素由最⼤元素来填补
link[p] = link[n];
}
n--;
}
}
*/
五.舍伍德算法解决跳跃表问题
舍伍德型算法的设计思想还可⽤于设计⾼效的数据结构，提⾼有序链表效率的⼀个技巧是在有序链表的部分结点处增设附加指针以提⾼其搜索性能。在增设附加指针的有序链表中搜索⼀个元素时，可借助于附加指针跳过链表中若⼲结点，加快搜索速度。这种增加了向前附加指针的有序链表称为跳跃表。
有空写吧……
六.随机抽题算法
  共有n道题，要求以相同概率随机抽取m道不重复试题。可以编号为1到n，围成⼀圈，每次抽取round，并出圈，下次再选到时候忽略如此直到选好了m题；不过若是n ⽐较⼤会占⽤⽐较多的时间，先分析出圈的影响，round出圈后⼩于round的编号不变，⼤于的编号减⼀；对于已经抽到的题⽬(共k道)，存⼊数组并由⼩到⼤排好序，再次选择roundk+1，如果⼤于等于round1则roundk+1加1，⼀直进⾏⽐较到roundk，不过这样可能会死循环，可以在中间判断，如果和roundi相等则加⼀过后如果⼩于roundi+1，则则直接插⼊已选题数组，否则和roundi+2⽐较，如此进⾏。
七.总结
很多问题还是没闹明⽩，主要是资料太少，我查万⽅和维普数据库总共到不超过10篇介绍舍伍德算法的，其中⼤部分都是泛泛⽽谈。
遗留问题：搜索有序表时怎么初始化link数组？value[0]为什么搞个⽆穷⼤？初试index为什么是sqrt(n)？查了n多资料也没头绪，懂的朋友给指点下。

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。