骑士游历问题 空科18501班 马珩博 万旭成 黄海京.

Presentation on theme: "骑士游历问题 空科18501班 马珩博 万旭成 黄海京."— Presentation transcript:

1 骑士游历问题 空科18501班 马珩博 万旭成 黄海京

2 问题详述 回溯法 问题分析 棋盘状态树 状态树说明 程序流程图

3 问题描述 设有一个n*m的棋盘（2≤n≤50，2≤m≤50），在棋盘(x1,y1)点即第x1行第y1列有一个中国象棋马，马走的规则为：
（1）马走日字； （2）马只能向右走 任务：求出从起始点到棋盘最右边的所有路径。

4 骑士游历问题类似于八皇后问题，可用回溯法解决；
回溯法：它的求解过程实质上是一个先序遍历一棵“状态树”的过程，只是这棵树不是遍历前预先建立好的，而是隐含在遍历过程中。

5 ☆ 用一个二维表形象地表示棋盘，每个结点对应一个棋盘布局即一个二维表，在这个二维表里，骑士没有经过的点的值为0，而经过的点的值为1。 ☆ 将表示起始状态的结点作为根结点由此出发，建立棋盘状态树。 ☆ 假设起始点为（1，1），表示骑士从第一行第一列出发，因为他只能向右走，则我们把起始点所在列的下一列作为树的第二层；向右走用两种走法：1.在起点的下一列落足；2.在起点下一列没有停继续往下走即到起点的下下列也是树的第三层去寻找合适的点。

6 ☆ 在第一种走法中，对于起点（1，1），由于马走“日”字，则棋子只能放置在点（3，2）； ☆ 在第二种走法中，跳过第二列，不能在跳过第三列，因为在第四列以下就在没有与起点符合“日”字位置的点了，于是只能在第三列找合适的点，对于（1，1）点，可以找出合适点（2，3）；按照规则走下去 ，直到走出最后一列，游历成功，输出路径即输出该棋盘上值为1的点所在位置，连起来就是骑士游历路线。 ☆ 依照分析，建立状态树如下：

7 棋盘状态树 正确路径

8 说明： 1. 状态树中每一个结点除了图中表示出的二维表外，还包含n个指向孩子结点的指针域和一个整型标志变量tag，当树的i层结点的tag为1时，表示该结点在第y1＋i－1列不下棋子，tag为0时则表示在该列某行下一个棋子。 2.在m－1列时，要继续前进时，只有一种走法，就是在第m列寻找正确路径，不能在m列不下棋子，因此，m层的结点tag必须等于1。 3.如果在某列下了棋子，在下一列可以有两种选择，下棋子和不下棋子，在树中表现为分配n＋1个结点，其中一个为不下棋子即tag＝0，其它n个表示分别在下列不同的行放入棋子；如果在该列不下棋子，则下一行必须下棋子，否则会遗漏可能路径，即有n个孩子，且孩子的tag均为1。

9 程序流程图 开始 输入起始位置（x1，y1） 进入Trial子程序 y>=m 输出 在下一列某行下棋子 是否为正确位置 释放该结点指针
N 释放该结点指针

10 Thank you! 不足之处，望老师指点