java编程游戏之骑士游历

java编程游戏之骑士游历 骑士游历问题的预见算法(一) 摘 要 骑士游历问题是经典的NP问题。在骑士游历问题常规算法的基础上， 提出一个新的算法—预见算法，用Java实现该算法，提高程序的运行 效率。 关键词 骑士游历;预见;Java算法 一、骑士游历问题 在国际象棋的棋盘(8行*8列)上放置一个马，按照“马走日字”的规则，马要遍历棋盘，即到达棋盘上的每一格，并且每格只到达一次。若给定起始位置(xy),编程探索出一条路径，沿着这条路径马能遍历棋盘上的所有单元格。 0,0 设当前马在棋盘的某个位置(x,y)上，按照规则，下一步有8个方向可走。 设二维数组mat示棋盘，每个元素表示棋盘的一格，其值定义如下: 0 表示马未到达过 Mat[i,j]= -1 表示棋盘边界 自然数 表示马到达该格的步数 二、常规的回溯算法 1(思想 马从棋盘上的某一初始位置(xy)开始，每次选择一个方向k，向前走一0,0 格，直到走完64格为止。每走一格，设置数组中相应格的元素值为马走的步数。 如果选择的方向k=0，表示可能的8种走向都试探不通，不通的原因是走向超出了棋盘范围，或当前位置已经被马访问过。此时马已无路可走，说明前几步走得不对，应该退回去重新换一种走法，这种逐步试探的设计思想称为回溯算法。 2.性能评价 回溯算法在每一格上朝一个方向盲目地进行试探。遇到在某一格上所有方向都不能走通时，才回到前一格上来试探另一个方向。当每一格上的所有方向都试探过，不能走通时，才做出“走不通”的结论。因此该算法在探索时带有一定的盲目性和随机性，它的运行效率较低。 三、预见算法 1(设计思想 回溯算法的思路是可行的，但它的运行效率较低，原因在于每步试探的随机性和盲目性。如果能够找到一种克服这种随机性和盲目性的办法，按照一定规律选择前进的方向，则将增加成功的可能性，运行时间也大为缩短。本文提出的算法在这方面有所突破。 如果在每步选择方向时，不是任意选择一个方向，而是经过一定的测试和计算，“预见”每条路的“宽窄”，再选择一条最“窄”的路先走，成功的可能性较大。理由是先走“困难的路”，光明大道留在后面。因为每一格迟早都 要走到，与其把困难留在后面，不如先走“困难的路”，这样路就会越走越宽， 成功的机会就越大。这种方法称为预见算法。 2(实现手段 为每个方向测定一个值—可通路数，它表示该位置上还有多少条通路。在每一格上对8个 方向都进行试探，并分析比较，下一步应该选择可通路数值最小的方向走。 四、用Java实现算法 本例声明Horse类，成员变量mat以二维数组表示棋盘，show表示是否显 示中间结果，内部类Position中的成员变量x和y表示棋盘上一格的位置，x 和y从1开始计数。 public class Horse {private int mat[][]; //二维数组表示棋盘 boolean show; //是否显示中间结果 class Position //内部类 {int x,y; //表示棋盘上一格的位置 Position (int x,int y) {this.x=x; this.y=y;} Position () {this(1,1);} Position (Position p) {this.x=p.x; this.y=p.y; }} public Horse(int n,int x,int y,boolean show) //数组比实际棋盘多 两行两列 { mat=new int[n+2*2][n+2*2]: this.show=show; inition(); //棋盘初始化 play(x,y);} public Horse(int n,int x,int y) { this(n,x,y,false);} public Horse(int n) { this(n,1,1);} public Horse() { this(8,1,1);} public void inition() //棋盘初始化 { int i,j; for(i=0;i<=1;i++) { for(j=0;j=1&&p.x<=n&&p.y>=1&&p.y<=n&&get(p)==0) return true;} else return false;} public Position goaStep(Position p,int k) //返回p位置按k方向 的下一位置 {int x=p.x; int y=p.y; switch(k) { case 1:x-=2;y++;break; case 2:x--;y+=2;break; case 3:x++;y+=2;break; case 4:x+=2;y++;break; case 5:x+=2;y--;break; case 6:x++;y-=2;break; case 7:x--;y-=2;break; case 8:x-=2;y--;break;} return new Position(x,y);} public int select(Position p)//选择p位置到达下一位置next1应走 的方向k //试探next1的8个方向位置next2的可通路数road,road的最小值为 minroad { int i=0,j=0,k=0,road=0,minroad=8; Position next1=null,next2=null; if(this.show) { System.out.println(“当前位置:(”+p.x+”,”+p.y+”)”); this.output(); System.out.println(”方向 下一位置 可通方向 可通路数”);} for(i=1;i<8;i++) { road=0; next1=goaStep(p,i); if(isValid(next1)) { if(this.show) system.out.print(“ “+i+”\t(“+next1.x+”,”+next1.y+”)\t”); for(j=1;j<=8;j++) { next2=goaStep(next1,j); if(isValid(next2)) {road++; if(this.show) System.out.print(j+”,”);)} if(road证明

住所证明下载场所使用证明下载诊断证明下载住所证明下载爱问住所证明下载爱问