回溯与分支限界算法设计.doc

《回溯与分支限界算法设计.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

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

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

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

4、er;publicclassQishi{privatebooleanTravel(intfirstX,intfirstY,int[][]board){//对应骑士可走的8个方向int[]movex={-2,-1,1,2,2,1,-1,-2};int[]movey={1,2,2,1,-1,-2,-2,-1};//下一步出路的位置int[]nextStepX=newint[board.length];int[]nextStepY=newint[board.length];//记录出路的个数int[]exitS=n

5、ewint[board.length];intnextX=firstX;intnextY=firstY;board[nextX][nextY]=1;for(intm=2;m<=Math.pow(board.length,2);m++){//初始化下一个位置可走的位置的数目for(inti=0;i

6、vey[i];//走到边界，路断if(temI<0

7、

8、temI>7

9、

10、temJ<0

11、

12、temJ>7){continue;}//记录下可走的方向if(0==board[temI][temJ]){nextStepX[count]=temI;nextStepY[count]=temJ;count++;}}//到这里，cout表示当前点有几种走法。nextStep中存储各种走法的坐标。intmin=-1;if(count==0){returnfalse;}if(1==count){min=0;}else{for(in

13、ti=0;i

14、

15、temI>7

16、

17、temJ<0

18、

19、temJ>7){continue;}//记录下这个位置可走的方向数if(0==board[temI][temJ]){exitS[i]++;}}}inttem=exitS[0];min=0;//从可走的方向中，寻找最少走的出路for(inti=1;i

20、++){if(tem>exitS[i]){tem=exitS[i];min=i;}}}//得到最少的出路nextX=nextStepX[min];nextY=nextStepY[min];board[nextX][nextY]=m;}returntrue;}publicstaticvoidmain(String[]args){intfirstX,firstY;System.out.println("