无限大棋盘上马的遍历问题

《无限大棋盘上马的遍历问题》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、无限大棋盘上马的遍历问题无限大棋盘上马的遍历问题无限大棋盘上马的遍历问题无限大棋盘上马的遍历问题无限大棋盘上马的遍历问题无限大棋盘上马的遍历问题无限大棋盘上马的遍历问题无限大棋盘上马的遍历问题无限大棋盘上马的遍历问题无限大棋盘上马的遍历问题第5卷第3期2006年9月广东轻工职业技术学院JOURNALOFGUANGDONGINDUSTRYTECHNICALCOLLEGEvO1.5NO.3Sep.2006无限大棋盘上马的遍历问题张赞波(1.广东轻工职业技术学院计算机工程系广东广州510300;2.中山大学计算机科学系广东广州51

2、0275)摘要:我们定义无限大棋盘上马的Hamilton路径为棋盘格子的一个无限序列,在这个序列中前后相邻的格子之间可以经马步到达,而且棋盘上的每个格子在序列中出现且只出现一次.我们证明了在无限大的棋盘上存在马的一个Hamilton路径.关键词:Hamilton路径;骑士巡游问题;无限大棋盘中图分类号:0157.4文献标识码:A文章编号:1672—1950(2006)02-0015-031定义与背景介绍棋盘上马的遍历问题是一个历史悠久的问题,关于这个问题相关的文献早至18世纪初便已出现.该问题一般的形式是给定一个棋盘,要求出

3、一条马的路径,这条路径经过整个棋盘的每个格子恰好一次,还可以进一步要求马遍历完整个棋盘后恰能回到出发点,这样的一个路径称为马的回路.由于在国际象棋中马称为骑士,因此该问题也称为骑士巡游问题.我们把这个问题转化为图论的问题.把棋盘的每一个格子作为图的一个顶点,相互之间可以经马步到达的格子之间以边相连,这样得到一个图.棋盘上马的遍历问题转化为求该图的一个经过每个顶点一次的路径(回路),这样的路径(回路)称为Hamilton路径(Hamilton回路).在文献[1]中,列举了该问题的许多研究成果,主要是国际象棋8×8棋盘上取得.文

4、献[3]研究了有洞棋盘上的马的遍历问题,其定理1则说明了在何种情况下m×n的棋盘有马的Hamilton路径或回路.在m×n棋盘上除了n,m≤4的某些情况以外,均存在马的Hamilton路径.在m×n为偶数,且m≥n的棋盘上,除了n=1,2,4和n=3的某些情况以外,均存在马的Hamilton回路.文献[2]给出了一种求mxn棋盘收稿日期:2006—06—08基金项目:广东轻工职业技术学院科研启动基金资助项目(200511)作者简介:张赞波(1974一),男,博士生.上马的Hamilton回路的方法.因此可以说在mxn矩形棋盘

5、上马的Hamilton路径和回路存在性问题基本上已经解决了.目前出现的一些研究工作主要集中在非矩形棋盘上的相对应的问题,如文献[3]中的有洞棋盘,或者是计算马的Hamilton路径和回路的数量等.本文对这个问题引入新的思路,我们把m和n都取无限大,在这样的棋盘上研究马的遍历问题.从现有的文献看来,这个问题尚没有相关的研究.因为无限大棋盘上有无限多个格子,所以这种棋盘上的遍历问题与传统的遍历问题不同.首先马不可能在有限时间内遍历这个棋盘,其次棋盘上不可能有马的Hamilton回路.而无限大棋盘马的Hamilton路径,也必须重

6、新定义.我们把无限大棋盘上马的Hamilton路径定义为棋盘上格子的一个无限序列,这个序列中前后相邻的格子之间可以通过马步到达,并且棋盘上的每个格子在序列中出现且只出现一次.而求无限大棋盘上马的Hamilton路径就转化为求这样的一个序列.2问题的形式化描述我们所研究的无限大棋盘,实际上可以与平面直角坐标系上的整点集合对应.每一个棋盘格子对应一个整点.而两个整点(,y.)与(,y)之间可以通过马步到达,即点的纵,横坐标满足,I.一I=1,lyl—Y2I=2或Il一2l-2,IYl—Y2J=1.因此求马在无限大棋盘上的Hami

7、lton路径等价于求马在平面直角坐标系整点上的Hamilton路径.该l6广东轻工职业技术学院第5卷问题可以形式化的描述如下.如果在平面直角坐标系上的两个整点(,,Y.)与(,Y),它们的坐标满足,1.17l—2l=1,lYl—Y2l=2或ll—2l=2,lYl—YI=1,则称它们马步相邻.求马在平面直角坐标系整点上的Hamilton路径.即求平面直角坐标系上所有整点的一个序列,使得每个整点在这个序列中出现且只出现一次,并且相邻的两个整点之间马步相邻.这样的一个序列称为马在平面直角坐标系整点上的一个Hamilton路径.3马

8、的Hamilton路径在以下的叙述中,我们对棋盘和平面直角坐标系上的的整点方阵不加区别.首先,为了描述的方便,对任意一个8×8方阵,我们把该方阵中的格子编号如图1.707l727374”7677606l626364666750jl5253545557加41424344454647303l3