回溯与分支限界算法设计

1、算法设计与分析实验报告专业班级姓名学号实验名称实验四：回溯与分支限界算法设计实验目的1 1.掌握回溯法解决问题的一般步骤。2 2. .学会使用回溯法解决实际问题。3 3. .掌握分支限界法解决问题的基本思想。4 4. .学会使用分支限界法解决实际问题。实验内容1 1.骑士游历问题（米用回溯法）：在国际象棋的棋盘（8 8 行 X8X8 歹 1 1）上放置一个马，按照“马走日字”的规则，马要遍历棋盘，即到达棋盘上的每一格，并且每格只到达一次。若给定起始位置（x0,y0 x0,y0）, ,编程探索出一条路径，沿着这条路径马能遍历棋盘上的所有单元格。2 2.行列变换问题（采用分支限界法）：给定两个 m

2、nmn 方格阵列组成的图形 A A 和图形 B,B,每个方格的颜色为黑色或白色，如下图所示。行列变换问题的每一步变换可以交换任意 2 2行或 2 2 列力格的颜色，或者将某行或某列颠倒。上述每次变换算作。试设一个算法，计算最少需要多少步，才将图形 A A 变换为图形 BoBo1 1 . .骑士游历问题的解题思路或算法思想：如果在每步选择方向时，不是任意选择一个方向，而是经过一定的测试和计算，“预见”每条路的“宽窄”，再选择一条最“窄”的路先走，成功的可能性较大。理由是先走“困难的路”，光明大道留在后面。因为每一格迟早都要走到，与其把困难留在后面，不如先走“困难的路”，这样路就会越走越宽，成功的

3、机会就越大。这种方法称为预见算法。为每个方向测定一个值一一可通路数，它表示该位置上还有多少条通路。在每一格上对 8 8 个方向都进行试探，并分析比较，下一步应该选择可通路数值最小的方向走。2 2 .行列变换问题的解题思路或算法思想：先进先出队列式分支限界法输入数据，将计算出的最少变换次数和相应的变换序列输出。算法描述第 1 1 行是最少变换次数。从第 2 2 行开始，每行用 4 4 个数表示|一次及换。程序及运行结果1.1.骑士游历四题的程序：packagecom.t5;importjava.util.Scanner;publicclassQishiprivatebooleanTravel(i

4、ntfirstX,intfirstY,int口口board)/对应骑士可走的8个方向intmovex=-2,-1,1,2,2,1,-1,-2;intmovey=1,2,2,1,-1,-2,-2,-1;/下一步出路的位置intnextStepX=newintboard.length;intnextStepY=newintboard.length;/记录出路的个数intexitS=newintboard.length;intnextX=firstX;intnextY=firstY;boardnextXnextY=1;for(intm=2;m=Math.pow(board.length,2);m+)

5、初始化下一个位置可走的位置的数目for(inti=0;iboard.length;i+)exitSi=0;intcount=0;/试探8个方向for(inti=0;i8;i+)inttemI=nextX+movexi;inttemJ=nextY+moveyi;/走到边界，路断if(temI7|temJ7)continue;/记录卜口走的方向if(0=boardtemItemJ)nextStepXcount=temI;nextStepYcount=temJ;count+;)/到这里，cout表示当前点有几种走法。nextStep中存储各种走法的坐标。intmin=-1;if(count=0)re

6、turnfalse;)if(1=count)min=0;elsefor(inti=0;icount;i+)for(intj=0;j8;j+)inttemI=nextStepXi+movexj;inttemJ=nextStepYi+moveyj;if(temI7|temJ7)continue;/记录下这个位置可走的方向数if(0=boardtemItemJ)exitSi+;inttem=exitS0;min=0;/从可走的方向中，寻找最少走的出路for(inti=1;iexitSi)tem=exitSi;min=i;得到最少的出路nextX=nextStepXmin;nextY=nextStep

7、Ymin;boardnextXnextY=m;returntrue;publicstaticvoidmain(Stringargs)intfirstX,firstY;System.out.println(输入起始点(0-7):);Scannerscanner=newScanner(Systemin);firstX=scanner.nextInt();firstY=scanner.nextInt();intboard=newint88;Qishiknight=newQishi();if(knight.Travel(firstX,firstY,board)System.out.println(游历

8、完成：);elseSystem.out.println(游历失败！n);for(inti=0;iboard.length;i+)for(intj=0;jboard0.length;j+)if(boardij10)System.out.print(+boardij);elseSystem.out.print(boardij);System.out.print();System.out.println();实例:2 2.行列变换问题的程序：packagecom.t8;importjava.util.LinkedList;importjava.util.Scanner;classgraphstati

9、cintsour,dest;/sour是图形的初始整数，dest是图形的目的整数staticintans=newint116;/静态变量(即全局变量),用于存放图形变换的路径intm=4,n=4,x;introw=newint4;intcol=newint4;voidsetx(intx)this.x=x;intgetx()returnthis.x;voidrowx()/将一个整数划分成四行二进制inty;for(inti=0;im;i+)y=1;rowi=0;for(intj=0;jn;j+)if(x&1)!=0)/如果x的最低位是1rowi|=y;y=1;输入起始点15解J5完成；4

10、1 14434625 1627244 5S49IFIF381 241713 424S5847 2632856 6S54393950 37182353 1257485921294G49 625136 49321911 527 6021 3d5308 61193 3J J6 312033voidcolx()/将一个整数划分成四列二进制inty;for(intj=0；jn；j+)colj=0;y=1；for(inti=0;im;i+)for(intj=0;j=1;y=1;voidrowy()/将四行二进制转换成一个整数intz=1,x=0,y;for(inti=0;im;i+)y=rowi;for(

11、intj=0;jn;j+)if(y&1)!=0)/如果y的最低位是1x|=z;z=1;this.x=x;voidcoly()/将四列二进制转换成一个整数intz=1,x=0,y;for(inti=0;im;i+)for(intj=0;jn;j+)if(colj&1)!=0)/如果y的最低位是1x|=z;z=1;this.x=x;voidSwaprow(inti,intj)/将二进数进行行互换into;o=rowi;rowi=rowj;rowj=o;)voidSwapcol(inti,intj)/将二进数进行列互换into;o=coli;coli=colj;colj=o;)voi

12、dreveR(intk)/将二进数进行行颠倒inty=0,z=1(4-1);for(intj=0;j=1;rowk=1;)rowk=y;)voidreveC(intk)/将二进数进行列颠倒inty=0,z=1(4-1);for(intj=0;j=1;colk=1;)colk=y;)introwswap(intx,inti,intj)/将二进制数的第i行与第j行互换this.x=x;rowx();Swaprow(i,j);rowy();returnthis.x;)intcolswap(intx,inti,intj)/将二进制数的第i列与第j列互换this.x=x;colx();Swapcol(i

13、,j);coly();returnthis.x;)intrevrow(intx,intk)/将二进制数的第K行颠倒this.x=x;rowx();reveR(k);rowy();returnthis.x;)intrevcol(intx,intk)/将二进制数的第K列颠倒this.x=x;colx();reveC(k);coly();returnthis.x;)publicclassTuxingpublicstaticvoidmain(String口args)finalintMaxsize=116;graphgN;用丁进行行变换、列变换、行颠倒、列颠倒intE,N;变换前的初始值，变换前的结果值

14、gN=newgraph();inthash=newint116;inti,j,h=0;charc;graphG1=newgraph();初始化，输入初始值和目标值，即1010010000101010和1010000001100101Scannerscanner=newScanner(Systemjn);Stringss=scanner.nextLine();charchArrs=ss.toCharArray();for(graph.sour=i=0;i16;i+)c=chArrsi;graph.sour|=(int)(c-0)i;)Stringsd=scanner.nextLine();cha

15、rchArrd=sd.toCharArray();for(graph.dest=i=0;i16;i+)c=chArrdi;graph.dest|=(int)(c-0)i;)LinkedListqueue=newLinkedList();/初始化先进先出队列for(intk=0;kMaxsize;k+)hashk=-1;G1.x=graph.sour;hashG1.x=0;queue.add(G1.x);while(!queue.isEmpty()以先进先出队列式头现分支限界法E=(int)queue.removeFirst();for(i=0;i4-1;i+)/行变换for(j=i+1;j4;

16、j+)gN.x=gN.rowswap(E,i,j);N=gN.x;if(hashN=-1)hashN=hashE+1;graph.ansN=E;queue.add(N);)for(i=0;i4-1;i+)/列变换for(j=i+1;j4;j+)gN.x=gN.colswap(E,i,j);N=gN.x;if(hashN=-1)hashN=hashE+1;graph.ansN=E;queue.add(N);)for(i=0;i4;i+)/行颠倒gN.x=gN.revrow(E,i);N=gN.x;if(hashN=-1)hashN=hashE+1;graph.ansN=E;queueadd(N)

17、;)for(i=0;i4;i+)/列颠倒gN.x=gN.revcol(E,i);N=gN.x;if(hashN=-1)hashN=hashE+1;graph.ansN=E;queue.add(N);if(hashgraph.dest!=-1)/如果目的值被遍历到，则退出循System.out.println(OK);break;System.out.println(hashgraph.dest);output(graph.dest);输出变换的路径publicstaticvoidoutb(intx)/将一个整数以四行二进制的形式显示for(inti=0;i4;i+)for(intj=0;j4;j+)if(x&1)!=0)System.out.print(1);elseSystem.out.print(0);x/=2;System.out.println();publicstaticvoidoutput(intN)if(N=graph.sour)System.out.println();outb(N);return;output(graph.ansN);/graph.ansN存放着从初始值到目