摘要：騎士游歷問題是經典的NP問題。在騎士游歷問題常規(guī)算法的基礎上，提出一個新的算法——預見算法，用Java實現(xiàn)該算法，提高程序的運行效率。

關鍵詞：騎士游歷；預見；Java算法

1 騎士游歷問題

在國際象棋的棋盤（8行×8列）上放置一個馬，按照“馬走日字”的規(guī)則，馬要遍歷棋盤，即到達棋盤上的每一格，并且每格只到達一次。若給定起始位置（x0，y0），編程探索出一條路徑，沿著這條路徑馬能遍歷棋盤上的所有單元格。

設當前馬在棋盤的某個位置（x，y）上，按照規(guī)則，下一步有8個方向可走。

設二維數(shù)組mat表示棋盤，每個元素表示棋盤的一格，其值定義如下：

0表示馬未到達過

Mat[i，j]= -1表示棋盤邊界

自然數(shù) 表示馬到達該格的步數(shù)

2 常規(guī)的回溯算法

2.1 設計思想

馬從棋盤上的某一初始位置（x0，y0）開始，每次選擇一個方向k，向前走一格，直到走完64格為止。每走一格，設置數(shù)組中相應格的元素值為馬走的步數(shù)。

如果選擇的方向k=0，表示可能的8種走向都試探不通，不通的原因是走向超出了棋盤范圍，或當前位置已經被馬訪問過。此時馬已無路可走，說明前幾步走得不對，應該退回去重新?lián)Q一種走法，這種逐步試探的設計思想稱為回溯算法。

2.2 性能評價

回溯算法在每一格上朝一個方向盲目地進行試探，遇到在某一格上所有方向都不能走通時，才回到前一格上來試探另一個方向。當每一格上的所有方向都試探過，不能走通時，才做出“走不通”的結論。因此該算法在探索時帶有一定的盲目性和隨機性，運行效率較低。

3 預見算法

3.1 設計思想

回溯算法的思路是可行的，但它的運行效率較低，原因在于每步試探的隨機性和盲目性。如果能夠找到一種克服這種隨機性和盲目性的辦法，按照一定規(guī)律選擇前進的方向，則將增加成功的可能性，運行時間也大為縮短。本文提出的算法在這方面有所突破。

如果在每步選擇方向時，不是任意選擇一個方向，而是經過一定的測試和計算，“預見”每條路的“寬窄”，再選擇一條最“窄”的路先走，成功的可能性較大。理由是先走“困難的路”，光明大道留在后面。因為每一格遲早都要走到，與其把困難留在后面，不如先走“困難的路”，這樣路就會越走越寬，成功的機會就越大。這種方法稱為預見算法。

3.2 實現(xiàn)手段

為每個方向測定一個值——可通路數(shù)，它表示該位置上還有多少條通路。在每一格上對8個方向都進行試探，并分析比較，下一步應該選擇可通路數(shù)值最小的方向走。

4 用Java實現(xiàn)算法

本例聲明Horse類，成員變量mat以二維數(shù)組表示棋盤，show表示是否顯示中間結果，內部類Position中的成員變量x和y表示棋盤上一格的位置，x和y從1開始計數(shù)。

public class Horse

{private int mat[][]; //二維數(shù)組表示棋盤

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)//數(shù)組比實際棋盤多兩行兩列

{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，1);}

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

mat[i][j]=-1;

for(j=0;j

mat[mat.length-1-i][j]=-1;

for(j=0;j

mat[j][i]=-1;

for(j=o;j

mat[j][mat.length-1-i]=-1;}

}

public int get(Position p) //獲得p格的值

{return mat[p.x+1][p.y+1];}

public void set(Position p，int i) //設置p格的值為i

{mat[p.x+1][p.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*nk!=0)

{set(current，count);

if(this.show)

System.out.print(”第”+count+”步 ”);

k=select(current);//試探，選擇一個方向

if(k==0count

System.out.println(”第”+count+”步無路可通！”)；

else

{count++;

corrent=goaStep(current，k);}

}

}

public boolean isValid(Position p)//判斷p是否在棋盤內且未被訪問過

{int n=mat.length-4;

if(p!=1p.x>=1p.x<=np.y>=1p.y<=nget(p)==0)

return true;}

else

return 1;}

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的可通路數(shù)road，road的最小值為minroad

{int i=0，j=0，k=0，road=0，minroad=8;

Position next1=1，next2=1;

if(this.show)

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

this.output();

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

for(i=1;i<8;i++)

{road=0;

next1=goaStep(p，i);

if(isValid(next1))

{if(this.show)

system.out.print(“ “+i+”\(“+next1.x+”，”+next1.y+”)\”);

for(j=1;j<=8;j++)

{next2=goaStep(next1，j);

if(isValid(next2))

{road++;

if(this.show)

System.out.print(j+”，”);}

}

if(road

{minroad=road;

k=i;}

if(this.show)

System.out.println(“\”+road);}

}

if(this.show)

System.out.println(“選定下一個方向 k=”+k+”\\r\”);

return k;}

public void output()

{int i，j，n=mat.length;

for(i=0;i

{for(j=0;j

{if（mat[i][j]mat[i][j]<10）

System.out.print(””+mat[i][j]);

else

System.out.print(“ “+mat[i][j]);}

System.out.println();}

System.out.println();}

public static void main(String args[])

{ Horse h1=new Horse(8，1，1，1);

h1.output();}

}

5 結論

該算法在Java環(huán)境下通過了測試，證明了算法的正確性。

預見算法雖然在每一格上選擇下一步的方向需要花費一定的時間，但它針對性強，減少了許多盲目的試探，總的選擇次數(shù)少，從而縮短了運行時間。

參考文獻

[1]張居敏，石禮娟，龍翔. Java程序設計經典教程(融合上機操作實例) [M].北京: 電子工業(yè)出版社，2008.

[2]Bruce Eckel.Java編程思想(第4版) [M].北京:機械工業(yè)出版社，2007.

[3]葉核亞 . 數(shù)據結構（Java版）[M].北京:電子工業(yè)出版社，2004.

[4] 黃曉東 . JAVA課程設計案例精編[M].北京:中國水利水電出版社，2004.