java编程游戏之骑士游历

《java编程游戏之骑士游历》由会员分享，可在线阅读，更多相关《java编程游戏之骑士游历（5页珍藏版）》请在装配图网上搜索。

1、骑士游历问题的预见算法(一)摘 要 骑士游历问题是经典的NP问题。在骑士游历问题常规算法的基础上，提出一个新的算法预见算法，用Java实现该算法，提高程序的运行效率。关键词 骑士游历；预见；Java算法一、骑士游历问题在国际象棋的棋盘（8行*8列）上放置一个马，按照“马走日字”的规则，马要遍历棋盘，即到达棋盘上的每一格，并且每格只到达一次。若给定起始位置（x0,y0）,编程探索出一条路径，沿着这条路径马能遍历棋盘上的所有单元格。设当前马在棋盘的某个位置（x,y）上，按照规则，下一步有8个方向可走。设二维数组mat表示棋盘，每个元素表示棋盘的一格，其值定义如下： 0 表示马未到达过Mati,j=

2、 -1 表示棋盘边界 自然数 表示马到达该格的步数二、常规的回溯算法1设计思想马从棋盘上的某一初始位置（x0,y0）开始，每次选择一个方向k，向前走一格，直到走完64格为止。每走一格，设置数组中相应格的元素值为马走的步数。如果选择的方向k=0，表示可能的8种走向都试探不通，不通的原因是走向超出了棋盘范围，或当前位置已经被马访问过。此时马已无路可走，说明前几步走得不对，应该退回去重新换一种走法，这种逐步试探的设计思想称为回溯算法。2.性能评价回溯算法在每一格上朝一个方向盲目地进行试探。遇到在某一格上所有方向都不能走通时，才回到前一格上来试探另一个方向。当每一格上的所有方向都试探过，不能走通时，才

3、做出“走不通”的结论。因此该算法在探索时带有一定的盲目性和随机性，它的运行效率较低。三、预见算法1设计思想回溯算法的思路是可行的，但它的运行效率较低，原因在于每步试探的随机性和盲目性。如果能够找到一种克服这种随机性和盲目性的办法，按照一定规律选择前进的方向，则将增加成功的可能性，运行时间也大为缩短。本文提出的算法在这方面有所突破。如果在每步选择方向时，不是任意选择一个方向，而是经过一定的测试和计算，“预见”每条路的“宽窄”，再选择一条最“窄”的路先走，成功的可能性较大。理由是先走“困难的路”，光明大道留在后面。因为每一格迟早都要走到，与其把困难留在后面，不如先走“困难的路”，这样路就会越走越宽

4、，成功的机会就越大。这种方法称为预见算法。2实现手段为每个方向测定一个值可通路数，它表示该位置上还有多少条通路。在每一格上对8个方向都进行试探，并分析比较，下一步应该选择可通路数值最小的方向走。 四、用Java实现算法本例声明Horse类，成员变量mat以二维数组表示棋盘，show表示是否显示中间结果，内部类Position中的成员变量x和y表示棋盘上一格的位置，x和y从1开始计数。public class Horseprivate int mat; /二维数组表示棋盘boolean show; /是否显示中间结果class Position /内部类int x,y; /表示棋盘上一格的位置P

5、osition (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 intn+2*2n+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

6、(n,1,1);public Horse() this(8,1,1);public void inition() /棋盘初始化 int i,j;for(i=0;i=1;i+) for(j=0;jmat.length;j+) /顶边两行matij=-1;for(j=0;jmat.length;j+) /底边两行matmat.length-1-ij=-1;for(j=0;jmat.length;j+) /左边两列matji=-1;for(j=o;jmat.length;j+)matjmat.length-1-i=-1; public int get(Position p) /获得p格的值 retu

7、rn matp.x+1p.y+1;public void set(Position p,int i) /设置p格的值为i matp.x+1p.y+1=i;public void play(int x,int y) /从（x,y）格开始遍历 int n=mat.length-4;Position current=new Position(x,y);int count=1;int i,j,k=1;while(count=n*n&k!=0) set(current,count);if(this.show)System.out.print(”第”+count+”步 ”);k=select(curren

8、t); /试探，选择一个方向if(k=0&count=1&p.x=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

9、: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();Sys

10、tem.out.println(”方向 下一位置 可通方向 可通路数”)；for(i=1;i8;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(roadminroad)minroad=road;k=i;if(th

11、is.show)System.out.println(“t”+road);if(this.show)System.out.println(“选定下一个方向 k=”+k+”rn”);return k;public void output() int i,j,n=mat.length;for(i=0;in;i+) for(j=0;jn;j+) if（matij&matij10）System.out.print(” ”+matij);elseSystem.out.print(“ “+matij);System.out.println();public static void main(String args) Horse h1=new Horse(8,1,1,false);h1.output();五、结论该算法在Java环境下通过了测试，证明了算法的正确性。预见算法虽然在每一格上选择下一步的方向需要花费一定的时间，但它针对性强，减少了许多盲目的试探，总的选择次数少，从而缩短了运行时间。