九宫八数问题的四种深度优先编程方法
2018-05-22马旭
马 旭
(辽宁大学创新创业学院 辽宁 沈阳 110036)
0 引 言
M×N方格矩阵中移子类智能游戏是高级程序设计人员必备的程序设计训练题目[1-4]。例如3×3方格矩阵中移动不同数码滑块的“九宫八数”游戏，8×8棋盘中跳马的“骑士游历”游戏，4×5方格矩阵中移动不同大小、不同形状矩形滑块的“华容道”游戏。
“九宫八数”游戏是一个古老的中国数学游戏。在一个3×3的方格矩阵中，放置标志为“1”到“8”的八个数码滑块，留有一个空方格，每次可以移动一个空方格相邻的数码滑块到空方格中，给定原始状态与目标状态(如图1所示)，要求找出最快捷的移动步骤。
图1 原始状态矩阵和目标状态矩阵
“九宫八数”问题是一个典型的深度优先搜索编程问题[5-8]。数码滑块的移动即为数码滑块与空方格的互换，可以把空方格看作“移动子”，这样不同位置的“移动子”可有2到4种移动方法。以图1为原始状态及目标状态，其深度优先搜索可树型图解如图2所示。
图2 深度优先搜索的树型图
基于上述编程思想，可以在方阵的存储方式及移动路径的存储方式上优化编程，可以有效地改进程序时间复杂度或空间复杂度，提高程序效率[9-14]。
1 方阵存储法
利用整型方阵a与b存储“九宫格”的原始状态及目标状态(以图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}；数组中0代表空方格)，存储滑块移动过程的路径矩阵可以利用三维数组存储(int pass[40][3][3])，为优化编程，本例采用二维数组存储(int pass[40][9])(三维存储路径与二维存储路径的转化代码可参看实例main()函数中“设置初始路径”循环)。程序输出的第一路径矩阵如图3所示。
图3 移动路径矩阵pass[k][9]
实例中全局变量说明如下：
int b[3][3]={1,2,3,4,5,6,7,8,0} : 目标状态矩阵。
int pass[40][9] : 移动路径矩阵。
int mc[40] : 移动点记录数组，记录移子过程(记录每次与空方格交换滑块的数码标志)。
int m : 用户输入的移子次数要求。
int sn : 移子方法计数(完成题目要求，可有sn种移子方法)。
核心递归函数void move ( int x[][3], int i,int j,int n ) ，其参数x为当前方阵状态，i与j为空方格坐标，n为当前移子次数。move函数及main函数程序描述如下：
void move ( int x[][3], int i, int j, int n )
{ int y[3][3];
/* 备份当前数组(当前矩阵状态) */
mcopy(y,x);
/* 判断移动矩阵x是否为目标矩阵，若为目标矩阵则输出路径。*/
if ( moveover(x) ) putpass();
/* 按用户最多移子次数要求，递归调用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} ; /* 设置初始路径 pass[0][] */ for ( k=0; k<9; k++ ) { i=k/3 ; j=k%3 ; pass[0][k]=a[i][j] ; } printf( ″enter m:″ ) ; scanf( ″%d″ , &m) ; move(a,2,2,0) ; /* 本例初始空方格坐标为(2,2) */ printf(″Total number of the problem solving methods is :%d
″,sn); getch(); } 程序中调用的各相关函数程序略，功能描述如下： (1) void putpass() ：输出满足用户要求的实现路径。 (2) void mcopy( int x1[][3], int x2[][3])：复制方阵x2到x1。 (3) int moveok( int x[][3], int i0, int j0, int i1, int j1, int n)：判定空方格x[i0][j0]是否可以移到x[i1][j1]，即判定移子后的新矩阵状态是否已在路径矩阵pass[40][9]中存在，若不存在，在路径矩阵中插入新路径，返回1，否则不插入新路径，返回0。 (4) int moveover(int x[][3])：判断矩阵x[3][3]是否为目标矩阵，返回1或0。 使用方阵存储状态信息，存储直观清晰，程序标准易读。程序运行实例如下： 【输入】 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 九宫八数(图1)问题的10种移子方法 利用字符串a与b存储“九宫格”的原始状态及目标状态(char a[]=″876543210″，b[]=″123456780″；)，存储滑块移动过程的路径矩阵可以利用二维字符数组存储(char pass[40][10])。核心递归函数void move( char x[], int p,int n) ，其参数x为当前方阵状态，p为空点位置(p>=0 && p<=8)，n为当前移子次数。 程序全局变量说明、move函数及main函数程序描述如下： char b[]=″123456780″ : 目标状态矩阵。 char pass[40][10] : 路径矩阵。 char mc[40] : 移动点记录数组，记录移子过程。(记录每次与空方格交换滑块的数码标志) int m，sn : 功能同“矩阵存储法”中同名变量。 void move( char x[], int p,int n) { int i,j; char y[10]; /* 备份当前数组(当前矩阵状态) */ strcpy(y,x); /* 判断移动字串x是否为目标字串，若为目标字串则输出路径。*/ if ( strcmp(b,x)==0 ) putpass(); /* i,j为当前空点位子坐标 */ i=p/3, j=p%3; /* 按用户最多移子次数要求，递归调用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(″enter m:″); scanf(″%d″,&m); move(a,8,0); /* 本例初始空方格为a[8] */ printf(″Total number of the problem solving methods is :%d
″,sn); getch(); } 程序中调用的各相关函数程序略，功能同“方阵存储法”中同名函数。程序输出的全部路径同上例，见图4。 “方阵存储法”与“字串存储法”程序中调用各函数的时间复杂度分析如表1所示。表中move()函数递归调用最低次数为输出第一次移动路径时的递归调用次数，move()函数递归调用最高次数为输出最后一次移动路径后的递归调用总次数。在“字串存储法”中没有使用自编函数mcopy()和moveover()，而是利用了系统函数strcpy()和strcmp()。 表1 “方阵存储法”与“字串存储法”程序中调用各函数的时间复杂度及递归调用次数 分析表1可知，“方阵存储法”所调用函数总体程序时间复杂度ΣT(n)=O(n)+4O(n2)=O(n2)，为平方级时间复杂度。“字串存储法”所调用函数总体程序时间复杂度ΣT(n)=2O(n)=O(n)，为线性级时间复杂度。即使在“字串存储法”中附加调用了系统已优化的2个字串函数，“字串存储法”程序时间复杂度也明显优于“方阵存储法”。无论是move()函数的最低调用次数还是最高调用次数，“字串存储法”都比“方阵存储法”优化近40%。 “方阵存储法”与“字串存储法”程序全局变量及各函数局部变量使用如表2所示。 表2 “方阵存储法”与“字串存储法”程序变量使用 分析表2可知，在全局变量及各函数局部变量的使用上，“方阵存储法”的空间使用要明显高于“字串存储法”。“九宫八数”问题终归是递归编程问题，递归调用函数的空间使用，将随递归调用次数的增加而线性增加。 综上所述，无论在时间复杂度，还是在空间复杂度，“字串存储法”都比“方阵存储法”更优化。“字串存储法”还可以充分调用C语言系统提供并已优化的字符串处理函数，更进一步提高程序时空效率。实例运行如表3所示，在整体的运行时间上，“字串存储法”比“方阵存储法”缩短近35%。 表3 四种编程方法运行时间比较 s 为“九宫格”的9个位置按行优先排序做标记为0到8，利用方阵存储“九宫格”原始及目标状态，可以预先建立一个9×9标识矩阵sign[9][9]。其中置1点的横坐标i代表空白点移动前的初始位置，纵坐标j代表该空白点可以移动到的目标位置，例如sign[0][1]=1代表位置0处的空白点可以移动到位置1处。按照上述规则，建立“九宫格”的路径标识矩阵如图5所示。 图5 路径标识矩阵 递归函数void move(int x[][3], int p, int n)，参数p为空方格坐标的序号(p=3×i+j)。建立路径标志矩阵后，每次移动坐标序号为p的空方格时，就可以直接在标志矩阵的指定行中确定可移动点的坐标序号k ( if (sign[p][k]==1 && moveok(x,p,k,n) )。move函数及main函数程序描述如下： 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( ″enter m:″ ); scanf( ″%d″,&m ); creatsm(); /* 建立路径标识矩阵 */ p=2*3+2; /* 本例初始空方格坐标为(2,2)，序号为p。*/ move(a,p,0); getch(); } 利用路径标识矩阵辅助递归，虽然在程序开始要预先调用标识矩阵生成函数，但可以减少递归函数中的条件判断，减少递归代码，从而能够优化程序运行时间。实例运行结果同“方阵存储法”图4所示，实例运行时间如表3所示。 路径标识矩阵是三角矩阵，针对不同的移子要求，路径标识矩阵的遍历可以采用多种优化方法。尤其是单元格移动方向较多(例如骑士游历程序，每一个单元格最多有8个移动方向)，且递归调用频繁的程序，利用路径标识矩阵辅助递归编程，可以显著减少程序的运行时间。针对移动滑块形状不同的实例(例如“华容道”游戏)，可以为不同滑块建立不同的路径标识矩阵来辅助递归编程。 以上3种move函数编程方法中，都有形参数组(int x[][3]或char x[10])和备份数组(int y[][3]或char y[10])做局部变量，用于保存状态信息。保留状态信息的递归方法便于理解，每次调用后恢复调用前状态即可向下执行。由于递归处理是内存压栈式存储，所有递归函数中的局部变量都将作为状态信息被压栈存储，当递归深度较深，局部变量空间较大，就会出现内存空间不足，程序运行速度降低，以至程序中断执行。以上述“字串存储法”为例，move()函数的局部变量有形参数组char x[10]，备份数组char y[10]。move()函数最低递归调用次数为8 292 445，最高递归调用次数为12 926 284，可知内存压栈空间较大。“矩阵存储法”内存压栈就需要更大空间。 为了最大程度地减少递归函数中的局部变量，节省递归压栈空间，本例将删除递归函数中的形参数组及备份数组。采用全局变量int a[][3]存储九宫格状态，恢复时使用路径矩阵中的最新矩阵即可。 move函数及main函数程序描述如下： 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] ); /* 恢复移动前矩阵状态 */ } } } void main() { int p; mcopy( pass[0],a ); /* 此时全局变量a为矩阵初始状态 */ printf( ″enter m:″ ); scanf( ″%d″,&m ); creatsm(); p=2*3+2; move(p,0); getch(); } 实例证明，由于保留路径信息的递归方法节省大量内存使用空间，运行速度可显著提高,运行结果同上述各方法，运行时间如表3所示。 上述四种算法实例，应用WIN-TC 1.91编程，在Intel(R)Core(TM) i5-4460s CPU配置上运行时间如表3所示。 M×N方格矩阵中移子类智能游戏还有多种形式，编程思想也有多种[15-16]，上述4种常规编程方法也有多种优化方式。本文各函数都采用基本编程方法，主要是提高程序可读性，方便编程爱好者阅读。 参 考 文 献 [1] 马旭,王大勇.趣味智能模拟程序设计实例[J].计算机与数字工程,2016,44(5):979-982. [2] 王乐芹,李月,徐炳伟,等.九宫方阵的数学解法[J].数学学习与研究,2015(13):86-86. [3] 惠燕,潘煜.骑士游历问题算法的研究[J].电子设计工程,2011,19(11):112-114. [4] 李彦辉,李爱军.一种改进的广度优先求解华容道问题的方法[J].计算机系统应用,2010,19(11):222-225. [5] 石竑松,秦志光.对数空间可构造的无向图遍历序列[J].计算机工程与应用,2010,46(8):11-15. [6] 欧阳圣,胡望宇.几种经典搜索算法研究与应用[J].计算机系统应用,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] 单学广,杨庆红,焦莉.递归问题的非递归实现方法的应用研究[J].计算机与现代化,2011(1):25-28. [10] 杨春花,姚进,赵培英,等.一个递归算法非递归化的算法框架[J].计算机应用与软件,2010,27(9):81-84. [11] 雍龙泉.一种全局和声搜索算法求解绝对值方程[J].计算机应用研究,2013,30(11):3276-3279. [12] 高遵海,高颖,程果.图的赋权路径矩阵与所有点对最短路径问题[J].计算机工程与应用,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] 马旭,易俗.二分搜索法求解悬链线问题[J].计算机应用与软件,2017,34(9):50-56. [16] 马旭.超高精度计算程序设计实例[J].计算机工程与应用,2017,53(14):51-55.
2 字串存储法
3 “方阵存储法”与“字串存储法”程序复杂度分析
4 建立路径标识矩阵
5 保留路径信息的递归方法
6 结 语
