算法设计与分析课程设计论文-骑士问题、图着色问题、离散帝国竞争算法
需积分: 50 138 浏览量
2018-05-07
22:10:43
上传
评论 6
收藏 1.08MB PDF 举报
试题一
有骑士问题如下： 在 8*8 方格棋盘上，从左上角方格（0，0）出发，为马寻找一条走遍棋
盘每一个并且子经过一次的一条路经。
（1）分别利用递归法和回溯法，实现骑士问题；若存在多条，请都找出。
（2）结合骑士问题，用自己的语言，说说递归算法和回溯算法的异同点。
X
y
1
2
3
4
5
6 7
8
（1）解：
递归法：
1 问题分析
骑士的跳马规则为：横 1 步，竖 2 步；或者横 2 步，竖 1 步。
递归法的核心思想是分治思想。即通过逐渐减小问题的规模，最终求解结果。对于本问
题，在 8*8 大小的棋盘上，从一个起始点出发，要不重复的变量完棋盘上的每一个方格，则
总共要走的步骤为 8*8=64 步。可以将其看成问题的规模，每走一步，剩余的步数减一，即
问题的规模减一。
骑士在遍历方格的时候，对于每一个遍历过的方格要设置标志位，用来表示该方格是否
已经遍历过。对此初始化时，我们将棋盘的每个方格的标志位设置为 0，表示还没访问过。
在遍历过中，每访问一个，则标志位+1，即表示第几次访问到的。
骑士遍历时，可行走的方向为 8。根据骑士的跳马规则，我们对当前位置（如上图马所
在位置）的 8 个方向进行编码如下：
在 1 位置时：
(
𝑥,𝑦
)
→
(
𝑥−1,𝑦+2
)
在 2 位置时：
(
𝑥,𝑦
)
→
(
𝑥−2,𝑦+1
)
在 3 位置时：
(
𝑥,𝑦
)
→
(
𝑥−2,𝑦−1
)
在 4 位置时：
(
𝑥,𝑦
)
→
(
𝑥−1,𝑦−2
)
剩余27页未读，继续阅读
评论0
最新资源