[基于Ｊａｖａ的骑士游历问题的预见算法]骑士游历问题

　　摘要：骑士游历问题是经典的NP问题。在骑士游历问题常规算法的基础上，提出一个新的算法――预见算法，用Java实现该算法，提高程序的运行效率。　　关键词：骑士游历；预见；Java算法

　　1骑士游历问题

　　在国际象棋的棋盘（8行×8列）上放置一个马，按照“马走日字”的规则，马要遍历棋盘，即到达棋盘上的每一格，并且每格只到达一次。若给定起始位置（x0,y0）,编程探索出一条路径，沿着这条路径马能遍历棋盘上的所有单元格。

　　设当前马在棋盘的某个位置（x,y）上，按照规则，下一步有8个方向可走。

　　设二维数组mat表示棋盘，每个元素表示棋盘的一格，其值定义如下：

　　0表示马未到达过

　　Mat[i,j]=-1表示棋盘边界

　　自然数表示马到达该格的步数

　　2常规的回溯算法

　　2.1设计思想

　　马从棋盘上的某一初始位置（x0,y0）开始，每次选择一个方向k，向前走一格，直到走完64格为止。每走一格，设置数组中相应格的元素值为马走的步数。

　　如果选择的方向k=0，表示可能的8种走向都试探不通，不通的原因是走向超出了棋盘范围，或当前位置已经被马访问过。此时马已无路可走，说明前几步走得不对，应该退回去重新换一种走法，这种逐步试探的设计思想称为回溯算法。

　　2.2性能评价

　　回溯算法在每一格上朝一个方向盲目地进行试探，遇到在某一格上所有方向都不能走通时，才回到前一格上来试探另一个方向。当每一格上的所有方 ……此处隐藏1400个字……

　　switch(k)

　　{case1:x-=2;y++;break;

　　case2:x--;y+=2;break;

　　case3:x++;y+=2;break;

　　case4:x+=2;y++;break;

　　case5:x+=2;y--;break;

　　case6:x++;y-=2;break;

　　case7:x--;y-=2;break;

　　case8:x-=2;y--;break;}

　　returnnewPosition(x,y);

　　}

　　publicintselect（Positionp）//选择p位置到达下一位置next1应走的方向k

　　//试探next1的8个方向位置next2的可通路数road,road的最小值为minroad

　　{inti=0,j=0,k=0,road=0,minroad=8;

　　Positionnext1=null,next2=null;

　　if(this.show)

　　{System.out.println(“当前位置:（”+p.x+”,”+p.y+”）”);

　　this.output();

　　System.out.println(”方向下一位置可通方向可通路数”)；}

　　for(i=1;i