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

关键词 骑士游历；预见；Java算法

一、骑士游历问题

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

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

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

            0      表示马未到达过

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

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

二、常规的回溯算法

1．设计思想

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

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

2.性能评价

回溯算法在每一格上朝一个方向盲目地进行试探。遇到在某一格上所有方向都不能走通时，才回到前一格上来试探另一个方向。当每一格上的所有方向都试探过，不能走通时，才做出“走不通”的结论。因此该算法在探索时带有一定的盲目性和随机性，它的运行效率较低。

三、预见算法

1．设计思想

回溯算法的思路是可行的，但它的运行效率较低，原因在于每步试探的随机性和盲目性。如果能够找到一种克服这种随机性和盲目性的办法，按照一定规律选择前进的方向，则将增加成功的可能性，运行时间也大为缩短。本文提出的算法在这方面有所突破。

如果在每步选择方向时，不是任意选择一个方向，而是经过一定的测试和计算，“预见”每条路的“宽窄”，再选择一条最“窄”的路先走，成功的可能性较大。理由是先走“困难的路”，光明大道留在后面。因为每一格迟早都要走到，与其把困难留在后面，不如先走“困难的路”，这样路就会越走越宽，成功的机会就越大。这种方法称为预见算法。

2．实现手段