国际象棋中马的遍历问题

home_king · 发表于 2003-12-11 18:04:42

我们数据结构课布置了一道题，供大家参阅。
设计一算法，要求如下：
国际象棋中，马按规则从任一点开始将所有格跳过一次(不重复)。

我的算法分析如下：

国际象棋马的走法：先直走或横走一格，再沿离开原来格子的方向斜走一个，合起来为一步棋；国际象棋棋盘黑白交错，格数8×8，根据马的走法，它只能从白格走向黑格，再从黑格走向白格，与此类推。
格子具有集合性，故考虑使用无向图来表示格子及其间关系；以邻接表作为该无向图中结点与相邻8个结点（4黑4白）的存储结构；以顶点表存储格子，每格为顶点表中一结点，其指针域有二，左指针链接黑格邻接表，右指针链接白格邻接表，其结点域为访问标识，访问过则为1，未访问为0；如用c实现，顶点表的头结点（下标为0的数组元素）不用，用来标识每一步的访问方向（先黑后黑或者先白后白）。
(b=black,w=white)
b1 w1 b2 w2
w3 b3 w4 b4
b5 w5 b6 w6
w7 b8 w8 b8
以b3为顶点，得顶点表与邻接表片断如下
...
b6<--b5<--b2<--b1<--[b3]-->w1-->w3-->w4-->w5
...
采用图的深度遍历算法，以方向标识的取值作为约束条件，每两个半步置值（0/1），以访问标识作为是否访问该结点或跳至下一结点的判断条件，访问所有的结点（可加一计数因子或直接在头顶点开多一域来计数）。

这样便可得到遍历的一条途径。如想得到所有可能的途径，可以在这个算法基础上加以扩展。

综合起来，使用到的算法的核心部分是传统的图深度遍历法，并无什么新鲜之处。
请大家多多指点，评价一下我的算法。

另外，有哪位兄弟能用perl实现呢？

georgek · 发表于 2003-12-11 19:08:48

還沒有看明白兄弟的意思, 但有必要分b/w 嗎?

devel · 发表于 2003-12-11 19:49:36

难阿，没下过围棋，看不懂。。。。。

georgek · 发表于 2003-12-11 19:54:19

是"国际象棋" 不是圍棋啊

看错了。我是不是常搞错阿。艾~~~~~~

georgek · 发表于 2003-12-11 20:01:39

傻了, 想成了中國象棋:p

georgek · 发表于 2003-12-11 20:06:43

"先直走或横走一格，再沿离开原来格子的方向斜走一个，合起来为一步棋" 國際象棋的馬是這樣的嗎??

home_king · 发表于 2003-12-12 10:20:34

国际象棋马的走法：
http://www.tianwai.com/belllee/chess/m.htm

我在这里补充一下算法复杂度以供各位兄弟参考：
图有n个结点，e条边。
深度遍历算法dfsL(L表示使用邻接表表示图)递归调用n次，搜索n个顶点的所有邻接点需将各边表结点扫描一遍，故时间复杂度位O(n+e)；
算法dfsL所用的辅助空间师标识数组和实现递归所用的栈，空间复杂度为O(n)。

我对perl的认识很浅，perl好像只有一种组合数据结构hash表是吧。
perl要实现针对c的算法应该要进行优化吧。比如说c中的索引就应该要通过perl中pop,push等来实现高效化。

多多指教，在此谢过各位兄弟。

home_king · 发表于 2003-12-12 14:23:09

最初由 devel 发表
对马的走法不清楚，举个例子：

ABCDE
FGHIJ
klMNO
PQRST
UVWXY

假如马在G,它可可跳到哪几格？

B or F or H or I
此乃半步，随后半步再斜走。

home · 发表于 2003-12-12 14:59:32

除了B OR F OR H OR I 还有P OR R OR N OR D
走的位置比中国象棋多。。

georgek · 发表于 2003-12-12 15:31:14

奇怪應該是dnrp 才對啊

		自动登录	找回密码
密码			注册