文档介绍：《数据结构(C++版)》
叶核亚
《数据结构(C++版)》
第1章绪论
第2章线性表
第3章排序
第4章串
第5章栈与队列
第6章数组和广义表
第7章树和二叉树
第8章查找
第9章图
第10章综合应用设计
第10章综合应用设计
用“预见算法”解骑士游历问题
综合应用实习
数据结构(C++版)》叶核亚
用“预见算法”解骑士游历问题
题意
在国际象棋的棋盘(8行×8列)上放置一个马,按照“马走日字”的规则,马要遍历棋盘,即到达棋盘上的每一格,并且每格只到达一次。若给定起始位置(x0, y0),编程探索出一条路径,沿着这条路径马能遍历棋盘上的所有单元格,这就是“骑士游历”问题。
图10-1 马下一步可走的8个方向
数据结构(C++版)》叶核亚
设二维数组mat表示棋盘,每个元素表示棋盘的一格,其值定义为:
图10-2 从(1, 1)开始的一次成功的遍历
数据结构(C++版)》叶核亚
“回溯算法”
(1)设计思想
(2)辅助结构——栈
(3)性能评价
图10-3 “回溯算法”流程图
数据结构(C++版)》叶核亚
4.“预见算法”
(1)设计思想
如果在每步选择方向时,不是任意选择一个方向,而是经过一定的测试和计算,“预见”每条路的“宽窄”,再选择一条最“窄”的路先走,成功的可能性较大。
数据结构(C++版)》叶核亚
(2)实现手段
表10-1 (5, 4)位置的可通路数情况
方向
下一位置
可通路数
1
(3,5)
7
2
(4,6)
7
3
(6,6)
7
4
(7,5)
5
5
(7,3)
5
6
(6,2)
5
7
(4,2)
5
8
(3,3)
7
数据结构(C++版)》叶核亚
例10-1 用“预见算法”解骑士游历问题
数据结构(C++版)》叶核亚
算法描述
图10-4 play()方法实现游历的算法流程
数据结构(C++版)》叶核亚