前言需要
明天咱们学习的是马踏棋盘算法，咱们还是从一个场景里引入看看
马踏棋盘算法也被称为骑士环游问题
将马随机放在国际象棋的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毫秒 这个速度还是很主观的，相比之前的算法更优一些