基于Ｊａｖａ的騎士游歷問題的預(yù)見算法

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

關(guān)鍵詞：騎士游歷；預(yù)見；Java算法

1 騎士游歷問題

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

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

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

0表示馬未到達(dá)過

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

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

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

2.1 設(shè)計(jì)思想

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

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

2.2 性能評價(jià)

回溯算法在每一格上朝一個(gè)方向盲目地進(jìn)行試探，遇到在某一格上所有方向都不能走通時(shí)，才回到前一格上來試探另一個(gè)方向。當(dāng)每一格上的所有方向都試探過，不能走通時(shí)，才做出“走不通”的結(jié)論。因此該算法在探索時(shí)帶有一定的盲目性和隨機(jī)性，運(yùn)行效率較低。

3 預(yù)見算法

3.1 設(shè)計(jì)思想

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

如果在每步選擇方向時(shí)，不是任意選擇一個(gè)方向，而是經(jīng)過一定的測試和計(jì)算，“預(yù)見”每條路的“寬窄”，再選擇一條最“窄”的路先走，成功的可能性較大。理由是先走“困難的路”，光明大道留在后面。因?yàn)槊恳桓襁t早都要走到，與其把困難留在后面，不如先走“困難的路”，這樣路就會越走越寬，成功的機(jī)會就越大。這種方法稱為預(yù)見算法。

3.2 實(shí)現(xiàn)手段

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

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

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

public class Horse

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

boolean show; //是否顯示中間結(jié)果

class Position//內(nèi)部類

{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ù)組比實(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) //設(shè)置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);//試探，選擇一個(gè)方向

if(k==0count

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

else

{count++;

corrent=goaStep(current，k);}

}

}

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

{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位置到達(dá)下一位置next1應(yīng)走的方向k

//試探next1的8個(gè)方向位置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(“當(dāng)前位置:（”+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(“選定下一個(gè)方向 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 結(jié)論

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

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

參考文獻(xiàn)

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

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

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

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