馬 旭

(遼寧大學(xué)創(chuàng)新創(chuàng)業(yè)學(xué)院 遼寧 沈陽(yáng) 110036)

0 引 言

M×N方格矩陣中移子類智能游戲是高級(jí)程序設(shè)計(jì)人員必備的程序設(shè)計(jì)訓(xùn)練題目[1-4]。例如3×3方格矩陣中移動(dòng)不同數(shù)碼滑塊的“九宮八數(shù)”游戲，8×8棋盤中跳馬的“騎士游歷”游戲，4×5方格矩陣中移動(dòng)不同大小、不同形狀矩形滑塊的“華容道”游戲。

“九宮八數(shù)”游戲是一個(gè)古老的中國(guó)數(shù)學(xué)游戲。在一個(gè)3×3的方格矩陣中，放置標(biāo)志為“1”到“8”的八個(gè)數(shù)碼滑塊，留有一個(gè)空方格，每次可以移動(dòng)一個(gè)空方格相鄰的數(shù)碼滑塊到空方格中，給定原始狀態(tài)與目標(biāo)狀態(tài)(如圖1所示)，要求找出最快捷的移動(dòng)步驟。

圖1 原始狀態(tài)矩陣和目標(biāo)狀態(tài)矩陣

“九宮八數(shù)”問(wèn)題是一個(gè)典型的深度優(yōu)先搜索編程問(wèn)題[5-8]。數(shù)碼滑塊的移動(dòng)即為數(shù)碼滑塊與空方格的互換，可以把空方格看作“移動(dòng)子”，這樣不同位置的“移動(dòng)子”可有2到4種移動(dòng)方法。以圖1為原始狀態(tài)及目標(biāo)狀態(tài)，其深度優(yōu)先搜索可樹型圖解如圖2所示。

圖2 深度優(yōu)先搜索的樹型圖

基于上述編程思想，可以在方陣的存儲(chǔ)方式及移動(dòng)路徑的存儲(chǔ)方式上優(yōu)化編程，可以有效地改進(jìn)程序時(shí)間復(fù)雜度或空間復(fù)雜度，提高程序效率[9-14]。

1 方陣存儲(chǔ)法

利用整型方陣a與b存儲(chǔ)“九宮格”的原始狀態(tài)及目標(biāo)狀態(tài)(以圖1為例：int a[3][3]={8,7,6,5,4,3,2,1,0}，b[3][3]={1,2,3,4,5,6,7,8,0}；數(shù)組中0代表空方格)，存儲(chǔ)滑塊移動(dòng)過(guò)程的路徑矩陣可以利用三維數(shù)組存儲(chǔ)(int pass[40][3][3])，為優(yōu)化編程，本例采用二維數(shù)組存儲(chǔ)(int pass[40][9])(三維存儲(chǔ)路徑與二維存儲(chǔ)路徑的轉(zhuǎn)化代碼可參看實(shí)例main()函數(shù)中“設(shè)置初始路徑”循環(huán))。程序輸出的第一路徑矩陣如圖3所示。

圖3 移動(dòng)路徑矩陣pass[k][9]

實(shí)例中全局變量說(shuō)明如下：

int b[3][3]={1,2,3,4,5,6,7,8,0} : 目標(biāo)狀態(tài)矩陣。

int pass[40][9] : 移動(dòng)路徑矩陣。

int mc[40] : 移動(dòng)點(diǎn)記錄數(shù)組，記錄移子過(guò)程(記錄每次與空方格交換滑塊的數(shù)碼標(biāo)志)。

int m : 用戶輸入的移子次數(shù)要求。

int sn : 移子方法計(jì)數(shù)(完成題目要求，可有sn種移子方法)。

核心遞歸函數(shù)void move ( int x[][3], int i,int j,int n ) ，其參數(shù)x為當(dāng)前方陣狀態(tài)，i與j為空方格坐標(biāo)，n為當(dāng)前移子次數(shù)。move函數(shù)及main函數(shù)程序描述如下：

void move ( int x[][3], int i, int j, int n )

{ int y[3][3];

/* 備份當(dāng)前數(shù)組(當(dāng)前矩陣狀態(tài)) */

mcopy(y,x);

/* 判斷移動(dòng)矩陣x是否為目標(biāo)矩陣，若為目標(biāo)矩陣則輸出路徑。*/

if ( moveover(x) ) putpass();

/* 按用戶最多移子次數(shù)要求，遞歸調(diào)用move()，生成輸出路徑。*/

if(n

{ n++;

if ( i!=0 && moveok ( x, i, j, i-1, j, n) )

{ mc[n]=x[i][j]; move( x, i-1, j, n); }

mcopy(x,y);

if ( i!=2 && moveok ( x, i, j, i+1, j, n) )

{ mc[n]=x[i][j]; move( x, i+1, j, n); }

mcopy(x,y);

if (j!=0 && moveok ( x, i, j, i, j-1, n) )

{ mc[n]=x[i][j]; move( x, i, j-1, n); }

mcopy(x,y);

if (j!=2 && moveok ( x, i, j, i, j+1, n) )

{ mc[n]=x[i][j]; move( x, i, j+1, n); }

mcopy(x,y);

} }

void main()

{ int i, j, k ;

int a[3][3] = {8,7,6,5,4,3,2,1,0} ;

/* 設(shè)置初始路徑 pass[0][] */

for ( k=0; k<9; k++ )

{ i=k/3 ; j=k%3 ; pass[0][k]=a[i][j] ; }

printf( ″e(cuò)nter m:″ ) ; scanf( ″%d″ , &m) ;

move(a,2,2,0) ;

/* 本例初始空方格坐標(biāo)為(2,2) */

printf(″Total number of the problem solving methods is :%d ″,sn); getch();

}

程序中調(diào)用的各相關(guān)函數(shù)程序略，功能描述如下：

(1) void putpass() ：輸出滿足用戶要求的實(shí)現(xiàn)路徑。

(2) void mcopy( int x1[][3], int x2[][3])：復(fù)制方陣x2到x1。

(3) int moveok( int x[][3], int i0, int j0, int i1, int j1, int n)：判定空方格x[i0][j0]是否可以移到x[i1][j1]，即判定移子后的新矩陣狀態(tài)是否已在路徑矩陣pass[40][9]中存在，若不存在，在路徑矩陣中插入新路徑，返回1，否則不插入新路徑，返回0。

(4) int moveover(int x[][3])：判斷矩陣x[3][3]是否為目標(biāo)矩陣，返回1或0。

使用方陣存儲(chǔ)狀態(tài)信息，存儲(chǔ)直觀清晰，程序標(biāo)準(zhǔn)易讀。程序運(yùn)行實(shí)例如下：

【輸入】

Enter m: 30

【輸出】

Pass No 1:

3，4，7，8，5，2，1，7，8，5，

2，1，7，8，5，6，4，3，8，5，

6，4，3，4，6，2，1，4，5，8，

Pass No 2-10：略(見圖4)。

圖4 九宮八數(shù)(圖1)問(wèn)題的10種移子方法

2 字串存儲(chǔ)法

利用字符串a(chǎn)與b存儲(chǔ)“九宮格”的原始狀態(tài)及目標(biāo)狀態(tài)(char a[]=″876543210″，b[]=″123456780″；)，存儲(chǔ)滑塊移動(dòng)過(guò)程的路徑矩陣可以利用二維字符數(shù)組存儲(chǔ)(char pass[40][10])。核心遞歸函數(shù)void move( char x[], int p,int n) ，其參數(shù)x為當(dāng)前方陣狀態(tài)，p為空點(diǎn)位置(p>=0 && p<=8)，n為當(dāng)前移子次數(shù)。

程序全局變量說(shuō)明、move函數(shù)及main函數(shù)程序描述如下：

char b[]=″123456780″ : 目標(biāo)狀態(tài)矩陣。

char pass[40][10] : 路徑矩陣。

char mc[40] : 移動(dòng)點(diǎn)記錄數(shù)組，記錄移子過(guò)程。(記錄每次與空方格交換滑塊的數(shù)碼標(biāo)志)

int m，sn : 功能同“矩陣存儲(chǔ)法”中同名變量。

void move( char x[], int p,int n)

{ int i,j;

char y[10];

/* 備份當(dāng)前數(shù)組(當(dāng)前矩陣狀態(tài)) */

strcpy(y,x);

/* 判斷移動(dòng)字串x是否為目標(biāo)字串，若為目標(biāo)字串則輸出路徑。*/

if ( strcmp(b,x)==0 ) putpass();

/* i,j為當(dāng)前空點(diǎn)位子坐標(biāo) */

i=p/3, j=p%3;

/* 按用戶最多移子次數(shù)要求，遞歸調(diào)用move()，生成輸出路徑。*/

if(n

{ n++;

if ( i!=0 && moveok( x, p, p-3,n) )

{ mc[n]=x[p]; move(x,p-3,n); }

strcpy(x,y);

if ( i!=2 && moveok( x, p, p+3,n) )

{ mc[n]=x[p]; move(x,p+3,n); }

strcpy(x,y);

if ( j!=0 && moveok( x, p, p-1,n) )

{ mc[n]=x[p]; move(x,p-1,n); }

strcpy(x,y);

if ( j!=2 && moveok( x, p, p+1,n) )

{ mc[n]=x[p]; move(x,p+1,n); }

strcpy(x,y);

}}

void main()

{ char a[]=″876543210″;

strcpy( pass[0], a );

printf(″e(cuò)nter m:″); scanf(″%d″,&m);

move(a,8,0);

/* 本例初始空方格為a[8] */

printf(″Total number of the problem solving methods is :%d ″,sn); getch();

}

程序中調(diào)用的各相關(guān)函數(shù)程序略，功能同“方陣存儲(chǔ)法”中同名函數(shù)。程序輸出的全部路徑同上例，見圖4。

3 “方陣存儲(chǔ)法”與“字串存儲(chǔ)法”程序復(fù)雜度分析

“方陣存儲(chǔ)法”與“字串存儲(chǔ)法”程序中調(diào)用各函數(shù)的時(shí)間復(fù)雜度分析如表1所示。表中move()函數(shù)遞歸調(diào)用最低次數(shù)為輸出第一次移動(dòng)路徑時(shí)的遞歸調(diào)用次數(shù)，move()函數(shù)遞歸調(diào)用最高次數(shù)為輸出最后一次移動(dòng)路徑后的遞歸調(diào)用總次數(shù)。在“字串存儲(chǔ)法”中沒(méi)有使用自編函數(shù)mcopy()和moveover()，而是利用了系統(tǒng)函數(shù)strcpy()和strcmp()。

表1 “方陣存儲(chǔ)法”與“字串存儲(chǔ)法”程序中調(diào)用各函數(shù)的時(shí)間復(fù)雜度及遞歸調(diào)用次數(shù)

分析表1可知，“方陣存儲(chǔ)法”所調(diào)用函數(shù)總體程序時(shí)間復(fù)雜度ΣT(n)=O(n)+4O(n2)=O(n2)，為平方級(jí)時(shí)間復(fù)雜度?！白执鎯?chǔ)法”所調(diào)用函數(shù)總體程序時(shí)間復(fù)雜度ΣT(n)=2O(n)=O(n)，為線性級(jí)時(shí)間復(fù)雜度。即使在“字串存儲(chǔ)法”中附加調(diào)用了系統(tǒng)已優(yōu)化的2個(gè)字串函數(shù)，“字串存儲(chǔ)法”程序時(shí)間復(fù)雜度也明顯優(yōu)于“方陣存儲(chǔ)法”。無(wú)論是move()函數(shù)的最低調(diào)用次數(shù)還是最高調(diào)用次數(shù)，“字串存儲(chǔ)法”都比“方陣存儲(chǔ)法”優(yōu)化近40%。

“方陣存儲(chǔ)法”與“字串存儲(chǔ)法”程序全局變量及各函數(shù)局部變量使用如表2所示。

表2 “方陣存儲(chǔ)法”與“字串存儲(chǔ)法”程序變量使用

分析表2可知，在全局變量及各函數(shù)局部變量的使用上，“方陣存儲(chǔ)法”的空間使用要明顯高于“字串存儲(chǔ)法”。“九宮八數(shù)”問(wèn)題終歸是遞歸編程問(wèn)題，遞歸調(diào)用函數(shù)的空間使用，將隨遞歸調(diào)用次數(shù)的增加而線性增加。

綜上所述，無(wú)論在時(shí)間復(fù)雜度，還是在空間復(fù)雜度，“字串存儲(chǔ)法”都比“方陣存儲(chǔ)法”更優(yōu)化?！白执鎯?chǔ)法”還可以充分調(diào)用C語(yǔ)言系統(tǒng)提供并已優(yōu)化的字符串處理函數(shù)，更進(jìn)一步提高程序時(shí)空效率。實(shí)例運(yùn)行如表3所示，在整體的運(yùn)行時(shí)間上，“字串存儲(chǔ)法”比“方陣存儲(chǔ)法”縮短近35%。

表3 四種編程方法運(yùn)行時(shí)間比較 s

4 建立路徑標(biāo)識(shí)矩陣

為“九宮格”的9個(gè)位置按行優(yōu)先排序做標(biāo)記為0到8，利用方陣存儲(chǔ)“九宮格”原始及目標(biāo)狀態(tài)，可以預(yù)先建立一個(gè)9×9標(biāo)識(shí)矩陣sign[9][9]。其中置1點(diǎn)的橫坐標(biāo)i代表空白點(diǎn)移動(dòng)前的初始位置，縱坐標(biāo)j代表該空白點(diǎn)可以移動(dòng)到的目標(biāo)位置，例如sign[0][1]=1代表位置0處的空白點(diǎn)可以移動(dòng)到位置1處。按照上述規(guī)則，建立“九宮格”的路徑標(biāo)識(shí)矩陣如圖5所示。

圖5 路徑標(biāo)識(shí)矩陣

遞歸函數(shù)void move(int x[][3], int p, int n)，參數(shù)p為空方格坐標(biāo)的序號(hào)(p=3×i+j)。建立路徑標(biāo)志矩陣后，每次移動(dòng)坐標(biāo)序號(hào)為p的空方格時(shí)，就可以直接在標(biāo)志矩陣的指定行中確定可移動(dòng)點(diǎn)的坐標(biāo)序號(hào)k ( if (sign[p][k]==1 && moveok(x,p,k,n) )。move函數(shù)及main函數(shù)程序描述如下：

void move( int x[][3], int p, int n )

{ int y[3][3], k ;

mcopy (y,x);

if ( moveover(x) ) putpass();

if (n

{ n++;

for ( k=0;k<3*3;k++ )

{ if ( sign[p][k]==1 && moveok(x,p,k,n) )

{ int i, j ;

i=p/3, j=p%3; mc[n]=x[i][j]；

move(x,k,n);

}

mcopy(x,y);

} } }

void main()

{ int p;

int a[3][3]={8,7,6,5,4,3,2,1,0};

mcopy( pass[0],a );

printf( ″e(cuò)nter m:″ ); scanf( ″%d″,&m );

creatsm(); /* 建立路徑標(biāo)識(shí)矩陣 */

p=2*3+2;

/* 本例初始空方格坐標(biāo)為(2,2)，序號(hào)為p。*/

move(a,p,0); getch();

}

利用路徑標(biāo)識(shí)矩陣輔助遞歸，雖然在程序開始要預(yù)先調(diào)用標(biāo)識(shí)矩陣生成函數(shù)，但可以減少遞歸函數(shù)中的條件判斷，減少遞歸代碼，從而能夠優(yōu)化程序運(yùn)行時(shí)間。實(shí)例運(yùn)行結(jié)果同“方陣存儲(chǔ)法”圖4所示，實(shí)例運(yùn)行時(shí)間如表3所示。

路徑標(biāo)識(shí)矩陣是三角矩陣，針對(duì)不同的移子要求，路徑標(biāo)識(shí)矩陣的遍歷可以采用多種優(yōu)化方法。尤其是單元格移動(dòng)方向較多(例如騎士游歷程序，每一個(gè)單元格最多有8個(gè)移動(dòng)方向)，且遞歸調(diào)用頻繁的程序，利用路徑標(biāo)識(shí)矩陣輔助遞歸編程，可以顯著減少程序的運(yùn)行時(shí)間。針對(duì)移動(dòng)滑塊形狀不同的實(shí)例(例如“華容道”游戲)，可以為不同滑塊建立不同的路徑標(biāo)識(shí)矩陣來(lái)輔助遞歸編程。

5 保留路徑信息的遞歸方法

以上3種move函數(shù)編程方法中，都有形參數(shù)組(int x[][3]或char x[10])和備份數(shù)組(int y[][3]或char y[10])做局部變量，用于保存狀態(tài)信息。保留狀態(tài)信息的遞歸方法便于理解，每次調(diào)用后恢復(fù)調(diào)用前狀態(tài)即可向下執(zhí)行。由于遞歸處理是內(nèi)存壓棧式存儲(chǔ)，所有遞歸函數(shù)中的局部變量都將作為狀態(tài)信息被壓棧存儲(chǔ)，當(dāng)遞歸深度較深，局部變量空間較大，就會(huì)出現(xiàn)內(nèi)存空間不足，程序運(yùn)行速度降低，以至程序中斷執(zhí)行。以上述“字串存儲(chǔ)法”為例，move()函數(shù)的局部變量有形參數(shù)組char x[10]，備份數(shù)組char y[10]。move()函數(shù)最低遞歸調(diào)用次數(shù)為8 292 445，最高遞歸調(diào)用次數(shù)為12 926 284，可知內(nèi)存壓棧空間較大。“矩陣存儲(chǔ)法”內(nèi)存壓棧就需要更大空間。

為了最大程度地減少遞歸函數(shù)中的局部變量，節(jié)省遞歸壓?？臻g，本例將刪除遞歸函數(shù)中的形參數(shù)組及備份數(shù)組。采用全局變量int a[][3]存儲(chǔ)九宮格狀態(tài)，恢復(fù)時(shí)使用路徑矩陣中的最新矩陣即可。

move函數(shù)及main函數(shù)程序描述如下：

int a[][3]={8,7,6,5,4,3,2,1,0} ,

b[][3]={1,2,3,4,5,6,7,8,0};

void move(int p,int n)

{ int k;

if ( moveover() ) putpass();

if ( n

{ n++;

for ( k=0; k<3*3; k++ )

{ if ( sign[p][k]==1 && moveok(p,k,n) )

{ int i,j;

i=p/3,j=p%3; mc[n]=a[i][j]; move(k,n);

}

mcopy( a,pass[n-1] );

/* 恢復(fù)移動(dòng)前矩陣狀態(tài) */

} } }

void main()

{ int p;

mcopy( pass[0],a );

/* 此時(shí)全局變量a為矩陣初始狀態(tài) */

printf( ″e(cuò)nter m:″ ); scanf( ″%d″,&m );

creatsm(); p=2*3+2;

move(p,0); getch();

}

實(shí)例證明，由于保留路徑信息的遞歸方法節(jié)省大量?jī)?nèi)存使用空間，運(yùn)行速度可顯著提高,運(yùn)行結(jié)果同上述各方法，運(yùn)行時(shí)間如表3所示。

上述四種算法實(shí)例，應(yīng)用WIN-TC 1.91編程，在Intel(R)Core(TM) i5-4460s CPU配置上運(yùn)行時(shí)間如表3所示。

6 結(jié) 語(yǔ)

M×N方格矩陣中移子類智能游戲還有多種形式，編程思想也有多種[15-16]，上述4種常規(guī)編程方法也有多種優(yōu)化方式。本文各函數(shù)都采用基本編程方法，主要是提高程序可讀性，方便編程愛好者閱讀。

參 考 文 獻(xiàn)

[1] 馬旭,王大勇.趣味智能模擬程序設(shè)計(jì)實(shí)例[J].計(jì)算機(jī)與數(shù)字工程,2016,44(5):979-982.

[2] 王樂(lè)芹,李月,徐炳偉,等.九宮方陣的數(shù)學(xué)解法[J].數(shù)學(xué)學(xué)習(xí)與研究,2015(13):86-86.

[3] 惠燕,潘煜.騎士游歷問(wèn)題算法的研究[J].電子設(shè)計(jì)工程,2011,19(11):112-114.

[4] 李彥輝,李愛軍.一種改進(jìn)的廣度優(yōu)先求解華容道問(wèn)題的方法[J].計(jì)算機(jī)系統(tǒng)應(yīng)用,2010,19(11):222-225.

[5] 石竑松,秦志光.對(duì)數(shù)空間可構(gòu)造的無(wú)向圖遍歷序列[J].計(jì)算機(jī)工程與應(yīng)用,2010,46(8):11-15.

[6] 歐陽(yáng)圣,胡望宇.幾種經(jīng)典搜索算法研究與應(yīng)用[J].計(jì)算機(jī)系統(tǒng)應(yīng)用,2011,20(5):243-247.

[7] Kreher D L,Stinson D R.Combinatorial algorithms:generation,enumeration,and search[M].London:CRC Press,1999:151-186.

[8] Jungnickel D.Graphs Networks and Algorithms[M].Translated from German by Tilla Schade Springer,1999:3-51.

[9] 單學(xué)廣,楊慶紅,焦莉.遞歸問(wèn)題的非遞歸實(shí)現(xiàn)方法的應(yīng)用研究[J].計(jì)算機(jī)與現(xiàn)代化,2011(1):25-28.

[10] 楊春花,姚進(jìn),趙培英,等.一個(gè)遞歸算法非遞歸化的算法框架[J].計(jì)算機(jī)應(yīng)用與軟件,2010,27(9):81-84.

[11] 雍龍泉.一種全局和聲搜索算法求解絕對(duì)值方程[J].計(jì)算機(jī)應(yīng)用研究,2013,30(11):3276-3279.

[12] 高遵海,高穎,程果.圖的賦權(quán)路徑矩陣與所有點(diǎn)對(duì)最短路徑問(wèn)題[J].計(jì)算機(jī)工程與應(yīng)用,2017,53(9):47-50.

[13] Rohn J.An algorithm for computing all solutions of an absolute value equation[J].Optimization Letters,2012,6(5):851-856.

[14] Zou Dexuan,Gao Liqun,Li Steven,et al.Solving 0-1 knapsack problem by a novel global harmony search algorithm[J].Applied Soft Computing,2011,11(2):1556-1564.

[15] 馬旭,易俗.二分搜索法求解懸鏈線問(wèn)題[J].計(jì)算機(jī)應(yīng)用與軟件,2017,34(9):50-56.

[16] 馬旭.超高精度計(jì)算程序設(shè)計(jì)實(shí)例[J].計(jì)算機(jī)工程與應(yīng)用,2017,53(14):51-55.