ACM国际大学生程序设计竞赛系列讲座-通用搜索算法及实现

ACM国际大学生程序设计竞赛系列讲座--------------通用搜索算法及实现目录1.组合问题的通用搜索算法1.1状态空间树的搜索1.2状态空间的原地搜索和展开搜索1.3基于遍历器的搜索2.优化问题的通用搜索算法2.1加权状态空间树的搜索2.2加权状态空间的原地搜索和展开搜索状态空间树的搜索publicinterfaceNode{intsubnodenum();booleantarget();Nodedown(inti);voidoutput(booleancn);}publicinterfaceMonoextendsNode{Nodeup();}publicclassBacktracking{Monoprob;intnum,bound,dep,level;publicBacktracking(Monop,intb,intd){prob=p;bound=b;dep=d;}publicvoiddepthfirst(){intn=prob.subnodenum();if(prob.target()){prob.output(true);++num;}for(inti=0;numbound&∈++i)if(prob.down(i)!=null){depthfirst();prob.up();}}}N皇后问题publicclassQueens1implementsMono{intn,level;int[]board;PrintWriterout;boolean[]column,d1,d2;publicQueens1(intk,PrintWritero){n=k;board=newint[n];out=o;column=newboolean[n];d1=newboolean[2*n-1];d2=newboolean[2*n-1];}publicNodedown(inti){Queens1ans=null;if(leveln&&!column[i]&&!d1[level+i]&&!d2[level-i+n-1]){column[i]=d1[level+i]=d2[level-i+n-1]=true;board[level++]=i;ans=this;}returnans;}publicNodeup(){inti=board[--level];column[i]=d1[level+i]=d2[level-i+n-1]=false;returnthis;}publicintsubnodenum(){returnleveln?n:0;}publicbooleantarget(){returnlevel==n;}}N皇后问题publicclassQueensimplementsMono{intn,level;int[]board;PrintWriterout;publicQueens(intk,PrintWritero){n=k;board=newint[n];out=o;}publicNodedown(inti){Queensans=null;booleannorm=leveln;for(intk=level-1;norm&&k=0;--k)norm=i!=board[k]&&i+level-k!=board[k]&&i-level+k!=board[k];if(norm){board[level++]=i;ans=this;}returnans;}publicNodeup(){--level;returnthis;}publicintsubnodenum(){returnleveln?n:0;}publicbooleantarget(){returnlevel==n;}}点着色问题例(点着色问题)用n种颜色给无向图的顶点着色，要求相邻顶点颜色不同。求符合条件的一个着色方法。publicclassColorClassimplementsMono{intm,n,level;List[]graph;int[]perm=newint[m];publicbooleantarget(){returnlevel==m;}publicintsubnodenum(){returnlevelm?n:0;}publicNodedown(inti){Iteratornodes=graph[level].iterator();booleanans=true;while(ans&&nodes.hasNext()){intk=((Integer)nodes.next()).intValue();ans=k=level||perm[k]!=i;}if(ans){perm[level++]=i;returnthis;}elsereturnnull;}publicNodeup(){--level;returnthis;}}排列树的搜索publicinterfacePerNode{intdepth();PerNodedown(inti);voidoutput(booleancn);}publicinterfacePerMonoextendsPerNode{PerNodeup();}排列树的搜索publicclassPerBacktracking{PerMonoprob;int[]perm;intdep,num,bound,level;publicPerBacktracking(PerMonop,intb){prob=p;bound=b;dep=p.depth();perm=newint[dep];for(inti=0;idep;++i)perm[i]=i;}publicvoiddepthfirst(){if(level==dep){prob.output(true);++num;}elsefor(inti=level;numbound&&idep;++i)if(prob.down(perm[i])!=null){intt=perm[level];perm[level]=perm[i];perm[i]=t;++level;depthfirst();prob.up();--level;t=perm[level];perm[level]=perm[i];perm[i]=t;}}}N皇后问题publicclassPerQueen1implementsPerMono{intn,level;int[]board;PrintWriterout;boolean[]d1,d2;publicPerQueen1(intk,PrintWritero){n=k;board=newint[n];out=o;d1=newboolean[2*n-1];d2=newboolean[2*n-1];}publicintdepth(){returnn;}publicPerNodedown(inti){PerQueen1ans=null;if(!d1[level+i]&&!d2[level-i+n-1]){d1[level+i]=d2[level-i+n-1]=true;board[level++]=i;ans=this;}returnans;}publicPerNodeup(){inti=board[--level];d1[level+i]=d2[level-i+n-1]=false;returnthis;}}跳马问题publicclassKnight2implementsMono{int[][]move;intm,n;int[][]board,parent;PrintWriterout;intx,y,level=1;publicKnight2(intmm,intnn,int[][]mov,PrintWritero){m=mm;n=nn;out=o;move=mov;parent=newint[m][m];board=newint[m][m];board[0][0]=1;}publicbooleantarget(){returnlevel==m*m;}publicintsubnodenum(){returnlevelm*m?n:0;}publicNodedown(inti){Knight2ans=null;intx1=x+move[i][0],y1=y+move[i][1];if(x1=0&&x1m&&y1=0&&y1m&&board[x1][y1]==0){x=x1;y=y1;board[x][y]=++level;parent[x][y]=i;ans=this;}returnans;}publicNodeup(){inti=parent[x][y];board[x][y]=0;x-=move[i][0];y-=move[i][1];--level;returnthis;}publicvoidoutput(){for(inti=0;im;++i){for(intj=0;jm;++j){if(board[i][j]10)out.print(0);out.print(board[i][j]+,);}out.println();}out.println();}}0-1矩阵问题例（0-1矩阵问题）求一个0-1矩阵，使每行的和和每列的和都等于给定的数值。publicclassBitmClass1implementsMono{intm,n;int[]row,column;int[][]data;int[]rowcount,colcount;intx,y;publicbooleantarget(){returnx==m;}publicintsubnodenum(){return2;}publicNodedown(inti){booleanans=i==0?rowcount[x]+n-1-y=row[x]&&colcount[y]+m-1-x=column[y]:rowcount[x]row[x]&&colcount[y]column[y];if(ans){if(i==0)data[x][y]=0;else{data[x][y]=1;++rowcount[x];++colcount[y];}++y;if(y==n){y=0;++x;}returnthis;}returnnull;}publicNodeup(){--y;if(y0){y=n-1;--x;returnthis;}if(data[x][y]==1){--rowcount[x];--colcount[y];}}}非递归的状态空间树的搜索publicclassMonoSearch{Monoprob;Linkhead;int[]path,wids;intnum,wid,dep,level;staticclassLink{publicintcur,bound;publicLinknext;publicLink(intc,intb,Linkn){cur=c;bound=b;next=n;}}publicvoidfind(intk){while(head!=null&&k0){booleanq=true;inti=head.cur,b=head.bound;while(ib&&(q=prob.down(i++)==null));if(q){if((head=head.next)!=null)prob.up();}else{head.cur=i;head=newLink(0,prob.subnodenum(),head);if(prob.target()){prob.output(true);++num;--k;}}}}}状态空间的有关定义定义（状态空间）一