//---------------------------------------------------------------------------

//===============================================

//===============================================

 

 

 

七、利用哈希技術(shù)

用棋盤折疊方法計(jì)算哈希值

棋盤可看做5個(gè)int32,分別對(duì)它移位并求和,取得哈希值,移位應(yīng)適當(dāng),充分利用各子,增強(qiáng)散列

讓hash沖突變?yōu)榱愕囊c(diǎn)： 

1.利用盤面生成一個(gè)足夠亂的數(shù),你可能考慮各種各樣的雜湊算法(類似MD5的功能) 

折疊計(jì)算hash時(shí),注意各子的值盡量少被直相加(異或等),折疊計(jì)算時(shí)通過(guò)適當(dāng)移位后再相加,移位的作用是各子的數(shù)值部分盡量少重疊在一起,充分利用各子數(shù)值,產(chǎn)生足夠的散列度. 

2.利用隨機(jī)函數(shù)(rand)來(lái)產(chǎn)生,當(dāng)然隨機(jī)數(shù)應(yīng)與盤面產(chǎn)生關(guān)聯(lián)，每一盤面對(duì)應(yīng)的隨機(jī)數(shù)(一個(gè)或一組)應(yīng)是唯一的。 

3.哈希表的大小應(yīng)是表中記錄的節(jié)點(diǎn)總數(shù)的4倍以上. 

4.設(shè)哈希表為int hsb[128K+10],總節(jié)點(diǎn)數(shù)為m=30K 

某一盤面節(jié)點(diǎn)的哈希值為n,n是17位的,那么n在hash表中位置為hsb[n], 

hsb[n]里存放的是這個(gè)節(jié)點(diǎn)的另一個(gè)32位的哈希值,用于判斷哈希沖突. 

當(dāng)出現(xiàn)沖突時(shí),n在表中的位置改為n+1,這樣可充分利用哈希表，節(jié)約空間 

經(jīng)過(guò)這樣處理后,哈希沖突次數(shù)約為: 

第一次哈希突次數(shù):(1+2+...+30)/128=(n^2)/2/128=3.5k 

第二次哈希突次數(shù):(1*1+2*2+...+30*30)/(128*128)=(n^3)/3/128/128=0.55K 

接下來(lái)我們?cè)俳ǖ诙€(gè)15位哈希表hsb2[32k] 

同樣上述處理 

第三次哈希突次數(shù):(1+2+...+0.55k)/32=(n^2)/2/32k=0.005k=5次 

第四次哈希突次數(shù):(1*1+2*2+...+0.55*0.55k)/(32k*32k)=0次 

以上分析是在哈希值n的散列度理想情況下的結(jié)果,如果你的n的散列度不是很理想,沖突次數(shù)可乘上2,即: 

第一次:3.5k*2=7k 

第二次:0.55k*2=1.1 

第三次:[(1+2+...+1.1k)/32]*2=40次 

第四次:[(1*1+2*2+...+1.1*1.1k)/(32*32k)]*2=0.88次(約1次)

//===============================================

//===============================================

//===============================================

//下文是利用哈希技術(shù)優(yōu)化后的代碼

//===============================================

 

//---------------------------------------------------------------------------

//----本程序在C++Builder6.0及VC++6.0中調(diào)試通過(guò)----

//----程序名稱:"華容道之哈希算法"搜索----

//----程序設(shè)計(jì):許劍偉----

//----最后修改時(shí)間:2006.10.22----

//----速度:橫刀立馬12毫秒(P2.4G機(jī)器)

//---------------------------------------------------------------------------

#include <time.h>

#include <stdio.h>

#include <conio.h>

#include <stdlib.h>

//---------------------------------------------------------------------------

//--棋盤定義說(shuō)明及搜索過(guò)程使用的核心數(shù)據(jù)結(jié)構(gòu)--

//---------------------------------------------------------------------------

//棋盤表示使用char一維數(shù)組,例:char q[20];

//大王是5(大王只能1個(gè)),橫將是4,豎將是3,兵是2,空位用0表示

//大王與橫將前兩個(gè)須相同,余占位填充1,豎將第二個(gè)占位同樣填充1

//棋盤上只能為2個(gè)空格,不能多也不能少

//---------------------------------------------------------------------------

const COL[20]={0,1,2,3,0,1,2,3,0,1,2,3,0,1,2,3,0,1,2,3};//列號(hào)表

struct PMZB{       //盤面走步集結(jié)構(gòu)

  char s[10],d[10];//原位置,目標(biāo)位置,最多只會(huì)有10步

  int n;           //總步數(shù)

};

typedef char QP[20];

//---------------------------------------------------------------------------

//--以下定義幾函數(shù)--

//---------------------------------------------------------------------------

//以下define用于棋盤復(fù)制,不要用環(huán)循,實(shí)地址直接引用要快8倍

#define qpcpy(q,p) {int *a=(int*)q,*b=(int*)p;a[0]=b[0],a[1]=b[1],a[2]=b[2],a[3]=b[3],a[4]=b[4];}/*復(fù)制棋盤*/

void qkmem(void *ps,int n){ //內(nèi)存塊置0,同memset(mem,0,memsize);

  register int *p=(int*)ps,*p2=p+n/4;

  while(p<p2) *p++=0;

  char *p3=(char *)p,*p4=(char *)ps+n;

  while(p3<p4) *p3++=0;

}

//---------------------------------------------------------------------------

//--以下是搜索算法之一(解決哈希表問(wèn)題)--

//---------------------------------------------------------------------------

#define hsize 128*1024//使用128k(17位)哈希表,如果改用更大的表,相應(yīng)的哈希計(jì)算位數(shù)也要改

//以下這兩個(gè)哈希計(jì)算是對(duì)棋盤折疊計(jì)算,注意異或與加法相似,不會(huì)提高散列度,適當(dāng)?shù)囊莆粍t會(huì)提高散列度

#define hs17(h1,h) h=(h1&0x0001FFFF)^(h1>>17) //17位哈希值計(jì)算(折疊式計(jì)算)

#define hs15(h1,h) h=(h1&0x00007FFF)^(h1>>19) //15位哈希值計(jì)算(折疊式計(jì)算)

#define phs(h1,h,b){if(!b[h]){b[h]=h1;return 1;} if(b[h]==h1)return 0;h++;} //哈希值測(cè)試,返回1是新節(jié)點(diǎn)

class PmHx{ //盤面哈希計(jì)算

 public:

 unsigned int *hsb,*hsb2; //哈希表

 int cht; //哈希沖突次數(shù)

 PmHx(){//初始化編碼表

   int i;

   hsb=new unsigned int[hsize+hsize/4+64];hsb2=hsb+hsize+32; //第二哈希表大小為第一哈希表的1/4

   reset();

 }

 ~PmHx(){ delete[] hsb; }

 void reset(){ cht=0; qkmem(hsb,(hsize+hsize/4+64)*sizeof(unsigned int));}

 int check(char *q){ //盤面編碼

   //生成散列參數(shù)n1,n2,m0

   //以下參數(shù)生成算法不保證參數(shù)與棋盤的唯一對(duì)應(yīng)關(guān)系,因此理論上存在哈希表沖突判斷錯(cuò)誤的可能

   //只不過(guò)產(chǎn)生錯(cuò)誤的可能性幾乎可能完全忽略

   unsigned int i,n1,n2,m0,h,h1,*p=(unsigned int*)q;

   n1=(p[1]<<3)+(p[2]<<5)+p[0]; //每次折疊時(shí)都應(yīng)充分發(fā)揮各子作用,增強(qiáng)散列

   n2=(p[3]<<1)+(p[4]<<4);

   m0=(n2<<6)^(n1<<3); //增強(qiáng)散列參數(shù)

   int a=1;

   //第一哈希處理

   h1=n1+n2+m0; hs17(h1,h);//h1為散列和,h為第一哈希索引

   for(i=0;i<2;i++) phs(h1,h,hsb); //多次查表,最多32次

   //第二哈希處理

   h1=n1-n2+m0; hs15(h1,h);//h1為散列差,h為第二哈希值

   for(i=0;i<10;i++) phs(h1,h,hsb2); //首次查表

   cht++; //哈希沖突計(jì)數(shù)(通過(guò)5次哈希,一般情況下沖突次數(shù)為0)

   return 1;

 }

 void check2(char *q){ //按左右對(duì)稱規(guī)則考查棋盤,并記錄到哈希表

   char i,q2[20];

   for(i=0;i<20;i+=4) q2[i]=q[i+3],q2[i+1]=q[i+2],q2[i+2]=q[i+1],q2[i+3]=q[i];

   check(q2);

   //check2()執(zhí)行次數(shù)較少,是實(shí)節(jié)點(diǎn)的次數(shù),約為check()執(zhí)行次數(shù)的1/3,所以不必過(guò)份求其速度

 }

}; //建立哈希表索引器

//---------------------------------------------------------------------------

//以下設(shè)計(jì)走法生成器

//---------------------------------------------------------------------------

#define zin0(des) z->s[z->n]=i,z->d[z->n++]=des //保存步法宏

#define zin1(des) z->s[z->n]=i-1,z->d[z->n++]=des-1 //保存步法宏(左移1列)

#define zin4(des) z->s[z->n]=i-4,z->d[z->n++]=des-4 //保存步法宏(上移1行)

#define zinb(des,fx) i=des+(fx); if(q[i]==2) {if(h){zin0(k1);zin0(k2);}else zin0(des);}

void zbFX(char *q,PMZB *z){ //分析當(dāng)前可能的步法,并將所有可能的步法保存在z中

  int i,k1=-1,k2,h=0;z->n=0;  //k1空格1位置,k2空格2位置,h為兩空格的聯(lián)合類型,計(jì)步復(fù)位

  for(i=0;i<20;i++){ if(!q[i]){if(k1==-1) k1=i; else { k2=i; break; }} } //查空格的位置

  int col1=COL[k1],col2=COL[k2];

  if(k1+4==k2) h=1;         //空格豎聯(lián)合

  if(k1+1==k2&&col1<3) h=2; //空格橫聯(lián)合

  if(col1>0){zinb(k1,-1);

    if(q[i]==3) {if(h==1) zin0(k1);}

    if(q[i]==5) {if(h==1) zin1(k1);}

    if(q[i]==4) {if(h==2) zin1(k2); zin1(k1);}

  }

  if(col1<3){zinb(k1,1);

    if(q[i]==3) {if(h==1) zin0(k1);}

    if(q[i]==5) {if(h==1) zin0(k1);}

    if(q[i]==4) {zin0(k1);} //如果橫聯(lián)合,k1不是第一空,所以不用判斷h

  }

  if(k1>3){zinb(k1,-4);

    if(q[i]==4&&q[i+1]==4&&(col1!=1||q[i-1]!=4)){ if(h==2) zin0(k1); }

    if(q[i]==1){

      if(q[i-4]==3) {if(h==1) zin4(k2); zin4(k1);}

      if(q[i-4]==5&&q[i-3]==5){if(h==2) zin4(k1);}

    }

  }

  if(k1<16){zinb(k1,4);

    if(q[i]==3) zin0(k1);

    if(q[i]==4&&q[i+1]==4&&(col1!=1||q[i-1]!=4)){ if(h==2) zin0(k1); }

    if(q[i]==5&&q[i+1]==5){ if(h==2) zin0(k1); }

  }

  if(col2>0){zinb(k2,-1); if(q[i]==4) zin1(k2); }

  if(k2>3)  {zinb(k2,-4); if(q[i]==1&&q[i-4]==3)zin4(k2);}

  if(col2<3){zinb(k2,1);  if(q[i]==4) {if(h==2) zin0(k1); zin0(k2);}}

  if(k2<16) {zinb(k2,4);  if(q[i]==3) {if(h==1) zin0(k1); zin0(k2);}}

}

//---------------------------------------------------------------------------

//--以下是搜索過(guò)程（廣度優(yōu)先）--

//---------------------------------------------------------------------------

class ZBD{ //走步隊(duì)(搜索器)

 public:

 QP *z;       //棋盤隊(duì)列

 int dn,dm,cur;//隊(duì)(隊(duì)尾),隊(duì)頭及隊(duì)頭內(nèi)走步集游標(biāo)

 PMZB zbj;    //隊(duì)頭走步集

 int *hs;     //回溯用的指針,指向父親(對(duì)應(yīng)的父親)

 char*hss;    //對(duì)應(yīng)的源步

 int max;     //最大隊(duì)長(zhǎng)

 int *res,ren;//結(jié)果

 int js,js2;  //搜索情況計(jì)數(shù)

 PmHx Hx;     //希希處理類

 ZBD(int k){ z=new QP[k]; hs=new int[k*2+500]; res=hs+k; hss=new char[k]; max=k; reset(); }

 ~ZBD(){ delete[] z; delete[] hs; delete[] hss; }

 void reset() { dn=0; dm=0,cur=-1; ren=0; js=js2=0; hss[dn]=-1;}

 void zb(char *q,char s,char d){ //走一步函數(shù)

   char c=q[s];q[s]=0;

   switch(c){

    case 3: q[s+4]=0; q[d+4]=1; break; //豎,余位填充1

    case 4: q[s+1]=0; q[d+1]=c; break; //橫

    case 5: q[s+1]=q[s+4]=q[s+5]=0; q[d+1]=c,q[d+4]=q[d+5]=1; break;

   }q[d]=c;

 }

 int zbcd(char *q){ //走步出隊(duì)

   if(cur==-1) zbFX(z[dm],&zbj);

   cur++; if(cur>=zbj.n) {dm++,cur=-1; return 1;} //步集游標(biāo)控制

   if(hss[dm]==zbj.s[cur]) return 1;//和上次移動(dòng)同一個(gè)棋子時(shí)不搜索,可提速20%左右

   qpcpy(q,z[dm]); zb(q,zbj.s[cur],zbj.d[cur]); //走步后產(chǎn)生新節(jié)點(diǎn),結(jié)果放在q中(出隊(duì))

   return 0;

 }

 void zbrd(char *q){ //走步入隊(duì)

   if(dn>=max) { printf("隊(duì)溢出.\r\n"); return; }

   qpcpy(z[dn],q); //出隊(duì)

   if(cur>=0) hss[dn]=zbj.d[cur]; //記錄下移動(dòng)的目標(biāo)位置(用于剪枝)

   hs[dn++]=dm; //記錄回溯點(diǎn)

 }

 char* getre(int n){ return z[res[n]];} //取第n步盤面

 int bfs(char *qp,int dep,int all=0){ //廣度優(yōu)先搜索,參數(shù)為棋盤及搜索最大深度,all為窮舉節(jié)點(diǎn)總數(shù)

  if(dep>500||dep<=0) dep=200;

  reset(); Hx.reset(); //哈希表及隊(duì)復(fù)位

  char q[20]; qpcpy(q,qp);

  int i,k;

  for(zbrd(q),i=1;i<=dep;i++){ //一層一層的搜索

    k=dn; if(dm==k) return -1;

    if(all)printf("第%d層共%d節(jié)點(diǎn)\r\n",i-1,k-dm);

    while(dm<k){ //廣度優(yōu)先

      if(zbcd(q)) continue;     //返回1說(shuō)明是步集出隊(duì),不是步出隊(duì)

      js++; //遍歷總次數(shù)計(jì)數(shù)

      if(q[13]==5&&q[14]==5&&!all) { //大王出來(lái)了

        for(ren=i,k=ren-2,res[ren-1]=dm;k>=0;k--) res[k]=hs[res[k+1]]; //回溯

        return 1;

      }

      if(i<dep&&Hx.check(q)){ //到了最后一層可以不再入隊(duì)了

        js2++;       //js2遍歷的實(shí)結(jié)點(diǎn)個(gè)數(shù),js2不包括起始點(diǎn),出隊(duì)時(shí)阻止了回頭步,始節(jié)點(diǎn)不可能再遍歷

        Hx.check2(q);//對(duì)稱節(jié)點(diǎn)做哈希處理

        zbrd(q);

      }

    }

  }

  return 0;

 }

}S(40*1024); //建立搜索引擎

//---------------------------------------------------------------------------

//----輸入輸出部分----

//---------------------------------------------------------------------------

void prt(char *q){ //打印棋盤

  int i,j,k;

  char y[20],x[20],xy[20],p[20],c1,c2;

  for(i=0;i<20;i++){

    y[i]='|',x[i]='-',xy[i]='+';

    if(q[i]) p[i]=q[i]+48; else p[i]=' ';

    if(q[i]==1) p[i]=p[i-4];

  }

  for(i=0;i<20;i++){

    if(q[i]==0) {if(COL[i]<3&&q[i+1]==0) y[i]=' '; if(i<16&&q[i+4]==0) x[i]=' ';}

    if(q[i]==3) { x[i]='.'; }

    if(q[i]==4) { y[i]='.'; i++; }

    if(q[i]==5) { y[i]=' '; y[i+4]=' '; x[i]=' '; x[i+1]=' '; xy[i]='.'; i++; }

  }

  printf("+-+-+-+-+\r\n");

  for(i=0;i<5;i++){

    k=i*4;

    printf("|");

    for(j=0;j<4;j++){ printf("%c%c",p[k+j],y[k+j]); }

    printf("\r\n|");

    for(j=0;j<4;j++){ printf("%c%c",x[k+j],xy[k+j]); }