前言需要
明天咱们学习的是马踏棋盘算法，咱们还是从一个场景里引入看看
马踏棋盘算法也被称为骑士环游问题
将马随机放在国际象棋的 6×6 棋盘 Board0～5 的某个方格中
提醒：马按走棋规定 (马走日字) 进行挪动
要求：每个方格只进入一次，走遍棋盘上全副 64 个方格
小游戏体验网址：4399：马踏棋盘小游戏
一、马踏棋盘问题
马踏棋盘问题 (骑士环游问题) 实际上是:图的深度优先搜寻 (DFS) 的利用
还记得图的深度优先搜寻（DFS）吗？
有些含糊或者不记得小伙伴能够看往期文章：图（广度优先与深度优先）
那么依照咱们的简略思路，是不是要一个地位一个地位去踩坑看看？
那么依照咱们的深度优先搜寻，就要一步步走上来，直至达成工作
当咱们的所选第三步的地位，无奈达成实现工作
那么咱们须要回溯，将原第三步更换到下一个地位里去
在以新第三步开始，进行搜寻，也要一步步走上来，直至达成工作
二、通过示例来意识算法
依据咱们之前简略的思路，首先咱们须要创立一个棋盘的数组
当咱们做出抉择下一步的时候，咱们须要 将以后的地位标记为已拜访，并依据以后地位计算出马儿能走那些地位，并放入到一个汇合中里去
当然咱们能够依据棋盘的状况来判断是否能够进行计算
留神：:马儿不同的走法、会失去不同的后果，效率也会有影响(需优化)
规定判断是否可走
那么我怎么晓得这些地位是否可走呢？我是怎么计算出来的呢？
首先咱们先剖析以后地位的 x、y 坐标，依照规定进行计算：(马走日字)
咱们先剖析一下象棋里的马走日是怎么样的吧
马走日所说的是 马从提棋地位到落棋地位是一个“日”子的对角线 ，在 没有棋子踩住马脚时 ，马是 能够随便走哪个方向的日字 都是能够的
在 有其余棋子在马的如图相干地位时，马就不能走该方向的日字 了，咱们也熟称“踩马脚了”。留神无论踩马脚的棋子是己方的棋子还是敌方的棋子，被踩方向的日字都不能走了
如果 四只马脚都被踩了，那么这只马哪里都走不了 了（如图）
在咱们这个问题中，还请你看图关联看懂马儿怎么走的，即称 马走日
当咱们晓得规定怎么玩了，就能够从图上看进去，每个点与以后点的关系
那么咱们的马儿剩下的点与以后是什么关系呢？怎么走呢？
骑士环游算法思路
咱们创立一个类寄存棋盘行、列，并记录棋盘上的是否被拜访过
public class HorseChessboard {
private static int x;// 棋盘的列数
private static int y;// 棋盘的行数
// 创立一个数组，标记棋盘的各个地位是否被拜访过
private static boolean visited[];
// 应用一个属性，标记是否棋盘的所有地位都被拜访
private static boolean finished; // 如果为 true, 示意胜利
}咱们应用 Point 类来示意 (x, y) 坐标空间中的地位的点
public class Point extends Point2D implements java.io.Serializable {
public int x;
public int y;
private static final long serialVersionUID = -5276940640259749850L;
public Point() {this(0, 0);
}
public Point(Point p) {this(p.x, p.y);
}
public Point(int x, int y) {
this.x = x;
this.y = y;
}
// 以双精度型返回点的 X 坐标。public double getX() {return x;}
// 以双精度型返回点的 Y 坐标。public double getY() {return y;}
// 返回此点的地位。@Transient
public Point getLocation() {return new Point(x, y);
}
// 将点的地位设为指定地位
public void setLocation(Point p) {setLocation(p.x, p.y);
}
// 将此点更改为具备指定地位
public void setLocation(int x, int y) {move(x, y);
}
// 将此点的地位设为指定的双精度坐标
public void setLocation(double x, double y) {this.x = (int) Math.floor(x+0.5);
this.y = (int) Math.floor(y+0.5);
}
// 将此点挪动到 (x,y) 坐标立体中的指定地位。public void move(int x, int y) {
this.x = x;
this.y = y;
}
// 平移 (x,y) 地位的点，沿 x 轴平移 dx，沿 y 轴平移 dy，挪动后失去点 (x+dx, y+dy)
public void translate(int dx, int dy) {
this.x += dx;
this.y += dy;
}
// 确定两个点是否相等。public boolean equals(Object obj) {if (obj instanceof Point) {Point pt = (Point)obj;
return (x == pt.x) && (y == pt.y);
}
return super.equals(obj);
}
// 返回此点的字符串示意模式及其在 (x,y) 坐标空间中的地位
public String toString() {return getClass().getName() + "[x=" + x + ",y=" + y + "]";
}
}
依据思路，须要依据以后地位判断马儿能走那些地位，并将后果放入 ArrayList 汇合中
public class HorseChessboard {
// 省略其余关键性代码....
/**
* 性能: 依据以后地位(Point 对象), 计算马儿还能走哪些地位(Point), 并放入到一个汇合中(ArrayList), 最多有 8 个地位
* @param curPoint
* @return
*/
public static ArrayList<Point> next(Point curPoint){ArrayList<Point> ps = new ArrayList<>();
// 创立一个点
Point p1 = new Point();
// 判断马儿是否能走 5 的地位
if((p1.x = curPoint.x - 2) >=0 && (p1.y = curPoint.y+1) >=0 ){ps.add(new Point(p1));
}
return ps;
}
} 而其余点的地位与以后地位关系，咱们之前也应用图解的形式剖析，当初代码实现
public class HorseChessboard {
// 省略其余关键性代码....
/**
* 性能: 依据以后地位(Point 对象), 计算马儿还能走哪些地位(Point), 并放入到一个汇合中(ArrayList), 最多有 8 个地位
* @param curPoint
* @return
*/
public static ArrayList<Point> next(Point curPoint){ArrayList<Point> ps = new ArrayList<>();
// 创立一个点
Point p1 = new Point();
// 示意马儿能够走 5 这个地位
if((p1.x = curPoint.x - 2) >= 0 && (p1.y = curPoint.y -1) >= 0) {ps.add(new Point(p1));
}
// 判断马儿能够走 6 这个地位
if((p1.x = curPoint.x - 1) >=0 && (p1.y=curPoint.y-2)>=0) {ps.add(new Point(p1));
}
// 判断马儿能够走 7 这个地位
if ((p1.x = curPoint.x + 1) < x && (p1.y = curPoint.y - 2) >= 0) {ps.add(new Point(p1));
}
// 判断马儿能够走 0 这个地位
if ((p1.x = curPoint.x + 2) < x && (p1.y = curPoint.y - 1) >= 0) {ps.add(new Point(p1));
}
// 判断马儿能够走 1 这个地位
if ((p1.x = curPoint.x + 2) < x && (p1.y = curPoint.y + 1) < y) {ps.add(new Point(p1));
}
// 判断马儿能够走 2 这个地位
if ((p1.x = curPoint.x + 1) < x && (p1.y = curPoint.y + 2) < y) {ps.add(new Point(p1));
}
// 判断马儿能够走 3 这个地位
if ((p1.x = curPoint.x - 1) >= 0 && (p1.y = curPoint.y + 2) < y) {ps.add(new Point(p1));
}
// 判断马儿能够走 4 这个地位
if ((p1.x = curPoint.x - 2) >= 0 && (p1.y = curPoint.y + 1) < y) {ps.add(new Point(p1));
}
return ps;
}
} 那么会不会有小伙伴有纳闷？？
为什么走五那个地位就要 >= 0 呢，走七的地位就要 <x 呢？<y 又是什么一样？
咱们先剖析走五的地位的时候，为什么要 >=0
同理，小于 x，小于 y 代表咱们只抉择在棋盘内的点，超出的则不能走
骑士环游算法实际
往期咱们应用的是二维数组代表这个点是否被拜访过
但这里是 36 步都须要走一遍，那么咱们其实能够应用一维数组进行示意
这样咱们能够是用公式：马儿所在行 * 棋盘行 + 马儿所在列 = 马儿下标 + 1
public class HorseChessboard {
// 省略其余关键性代码....
/**
* 实现骑士环游问题的算法
* @param chessboard 棋盘
* @param row 马儿以后的地位的行 从 0 开始
* @param column 马儿以后的地位的列 从 0 开始
* @param step 是第几步 , 初始地位就是第 1 步
*/
public static void traversalChessboard(int[][] chessboard, int row, int column, int step) {
// 标记以后棋盘执行的是第几步
chessboard[row][column] = step;
//row = 3 X = 6 column = 3 = 3 * 6 + 3 = 21 -1 = 20
visited[row * x + column] = true; // 标记该地位曾经拜访
// 获取以后地位能够走的下一个地位的汇合
ArrayList<Point> ps = next(new Point(column, row));
}
}当咱们获取到以后地位能够走的下一个地位的汇合，就进行遍历递归
public class HorseChessboard {
// 省略其余关键性代码....
/**
* 实现骑士环游问题的算法
* @param chessboard 棋盘
* @param row 马儿以后的地位的行 从 0 开始
* @param column 马儿以后的地位的列 从 0 开始
* @param step 是第几步 , 初始地位就是第 1 步
*/
public static void traversalChessboard(int[][] chessboard, int row, int column, int step) {
// 标记以后棋盘执行的是第几步
chessboard[row][column] = step;
//row = 3 X = 6 column = 3 = 3 * 6 + 3 = 21 -1 = 20
visited[row * x + column] = true; // 标记该地位曾经拜访
// 获取以后地位能够走的下一个地位的汇合
ArrayList<Point> ps = next(new Point(column, row));
// 遍历 ps
while(!ps.isEmpty()) {Point p = ps.remove(0);// 取出下一个能够走的地位
// 判断该点是否曾经拜访过
if(!visited[p.y * X + p.x]) {// 阐明还没有拜访过
traversalChessboard(chessboard, p.y, p.x, step + 1);
}
}
}
}咱们怎么辨别以后节点的能够走的下一个地位的汇合，是否一路就胜利了呢？
应用 step 和 应该走的步数比拟：step = X * Y
如果以后节点的能够走的下一个地位的汇合，没有一路就胜利，怎么办？
勾销该地位已拜访，并将棋盘置为 0，阐明该节点处于回溯状态
public class HorseChessboard {
// 省略其余关键性代码....
/**
* 实现骑士环游问题的算法
* @param chessboard 棋盘
* @param row 马儿以后的地位的行 从 0 开始
* @param column 马儿以后的地位的列 从 0 开始
* @param step 是第几步 , 初始地位就是第 1 步
*/
public static void traversalChessboard(int[][] chessboard, int row, int column, int step) {chessboard[row][column] = step;
//row = 4 X = 8 column = 4 = 4 * 8 + 4 = 36
visited[row * x + column] = true; // 标记该地位曾经拜访
// 获取以后地位能够走的下一个地位的汇合
ArrayList<Point> ps = next(new Point(column, row));
// 遍历 ps
while(!ps.isEmpty()) {Point p = ps.remove(0);// 取出下一个能够走的地位
// 判断该点是否曾经拜访过
if(!visited[p.y * x + p.x]) {// 阐明还没有拜访过
traversalChessboard(chessboard, p.y, p.x, step + 1);
}
}
// 判断马儿是否实现了工作，应用 step 和应该走的步数比拟，// 如果没有达到数量，则示意没有实现工作，将整个棋盘置 0
// 阐明: step < X * Y 成立的状况有两种
//1. 棋盘到目前地位, 依然没有走完
//2. 棋盘处于一个回溯过程
if(step < x * y && !finished) {chessboard[row][column] = 0;
visited[row * x + column] = false;
} else {finished = true;}
}
}接下来，让咱们应用 demo 测试一把这些思路与代码
咱们采纳上图的马儿作为起始地位，来测试看看
public class HorseChessboard {
// 省略其余关键性代码....
public static void main(String[] args) {System.out.println("骑士环游算法，开始运行~~");
// 测试骑士环游算法是否正确
x = 6;
y = 6;
int row = 4; // 马儿初始地位的行，从 1 开始编号
int column = 3; // 马儿初始地位的列，从 1 开始编号
// 创立棋盘
int[][] chessboard = new int[x][y];
visited = new boolean[x * y];// 初始值都是 false
// 测试一下耗时
long start = System.currentTimeMillis();
traversalChessboard(chessboard, row - 1, column - 1, 1);
long end = System.currentTimeMillis();
System.out.println("共耗时:" + (end - start) + "毫秒");
// 输入棋盘的最初状况
for(int[] rows : chessboard) {for(int step: rows) {System.out.print(step + "\t");
}
System.out.println();}
}
}
运行后果如下：骑士环游算法，开始运行~~
共耗时: 40 毫秒
08 03 10 29 32 05
17 28 07 04 11 30
02 09 18 31 06 33
27 16 01 20 23 12
36 19 14 25 34 21
15 26 35 22 13 24三、应用贪婪思维进行优化
利用贪婪算法的思维，对下一步的所有汇合的数目, 进行非递加排序
什么是非递加？
递增的状况是：1、2、3、4、5、6、7、8、9
递加的状况是：9、8、7、6、5、4、3、2、1
非递增的状况是：9、8、7、6、5、5、4、3、2、1
非递加的状况是：1、2、2、3、3、4、4、5、6、7
目标：使马儿走的下一步是下一步汇合中可选性起码的，缩小回溯可能性
public class HorseChessboard {
// 省略其余关键性代码....
// 依据以后这个一步的所有的下一步的抉择地位，进行非递加排序, 缩小回溯的次数
public static void sort(ArrayList<Point> ps) {ps.sort(new Comparator<Point>() {
@Override
public int compare(Point o1, Point o2) {
// TODO Auto-generated method stub
// 获取到 o1 的下一步的所有地位个数
int count1 = next(o1).size();
// 获取到 o2 的下一步的所有地位个数
int count2 = next(o2).size();
if(count1 < count2) {return -1;} else if (count1 == count2) {return 0;} else {return 1;}
}
});
}
}那么怎么应用呢，咱们在算法里进行排序优化
public class HorseChessboard {
// 省略其余关键性代码....
/**
* 实现骑士环游问题的算法
* @param chessboard 棋盘
* @param row 马儿以后的地位的行 从 0 开始
* @param column 马儿以后的地位的列 从 0 开始
* @param step 是第几步 , 初始地位就是第 1 步
*/
public static void traversalChessboard(int[][] chessboard, int row, int column, int step) {
// 标记以后棋盘执行的是第几步
chessboard[row][column] = step;
//row = 3 X = 6 column = 3 = 3 * 6 + 3 = 21 -1 = 20
visited[row * x + column] = true; // 标记该地位曾经拜访
// 获取以后地位能够走的下一个地位的汇合
ArrayList<Point> ps = next(new Point(column, row));
// 对 ps 进行排序, 排序的规定就是对 ps 的所有的 Point 对象的下一步的地位的数目，进行非递加排序
sort(ps);
// 遍历 ps
while(!ps.isEmpty()) {Point p = ps.remove(0);// 取出下一个能够走的地位
// 判断该点是否曾经拜访过
if(!visited[p.y * X + p.x]) {// 阐明还没有拜访过
traversalChessboard(chessboard, p.y, p.x, step + 1);
}
}
}
}public class HorseChessboard {
// 省略其余关键性代码....
public static void main(String[] args) {System.out.println("骑士环游算法，开始运行~~");
// 测试骑士环游算法是否正确
x = 6;
y = 6;
int row = 4; // 马儿初始地位的行，从 1 开始编号
int column = 3; // 马儿初始地位的列，从 1 开始编号
// 创立棋盘
int[][] chessboard = new int[x][y];
visited = new boolean[x * y];// 初始值都是 false
// 测试一下耗时
long start = System.currentTimeMillis();
traversalChessboard(chessboard, row - 1, column - 1, 1);
long end = System.currentTimeMillis();
System.out.println("共耗时:" + (end - start) + "毫秒");
// 输入棋盘的最初状况
for(int[] rows : chessboard) {for(int step: rows) {System.out.print(step + "t");
}
System.out.println();}
}
}
运行后果如下：骑士环游算法，开始运行~~
共耗时: 9 毫秒
08 03 10 29 32 05
17 28 07 04 11 30
02 09 18 31 06 33
27 16 01 20 23 12
36 19 14 25 34 21
15 26 35 22 13 24从 40 毫秒 到 9 毫秒 这个速度还是很主观的，相比之前的算法更优一些