文章和代码曾经归档至【Github仓库：https://github.com/timerring/java-tutorial 】或者公众号【AIShareLab】回复 java 也可获取。

骑士环游问题

算法优化意义

  1. 算法是程序的灵魂，为什么有些程序能够在海量数据计算时，仍然保
    持高速计算?
  2. 编程中算法很多，比方八大排序算法(冒泡、抉择、插入、快排、归并.
    希尔、基数、堆排序)、查找算法、分治算法、动静布局算法、KMP算法、贪婪算法、普里姆算法、克鲁斯卡尔算法、迪杰斯特拉算法、弗洛伊德算法。

经典算法面试题-骑士环游问题

马踏棋盘算法介绍

  1. 马踏棋盘算法也被称为骑士环游问题
  2. 将马随机放在国际象棋的8×8棋盘Board[0 ~7][0~7]的某个方格中，马按走棋规定(马走日字)进行挪动。要求每个方格只进入一次，走遍棋盘上全副64个方格。
  3. 游戏演示:
    https://u.ali213.net/games/horsesun/index.html?game_code=403
  4. 会应用到图的遍历算法(DFS)+贪婪算法优化

  1. 马踏棋盘问题(骑士环游问题)实际上是图的深度优先搜寻(DFS)的利用。
  2. 如果应用回溯(就是深度优先搜寻)来解决,如果马儿踏了53个点，如图:走到了第53个,坐标(1,0)，发现曾经走到止境, 没方法，那就只能回退了，查看其余的门路，就在棋盘上不停的回溯.....，思路剖析+代码实现。
  3. 先用根本形式来解决，而后应用贪婪算法(greedyalgorithm)进行优化。解决马踏棋盘问题,领会到不同的算法对程序效率的影响。
  4. 应用后面的游戏来验证算法是否正确。

骑士环游问题的解决步骤和思路剖析

  1. 创立棋盘chessBoard,是二维数组
  2. 将以后地位设置为曾经拜访,而后依据以后地位，计算马儿还能走哪些地位，并放入到一个汇合中(ArrayList), 最多有8个，每走一步，应用step + 1。
  3. 遍历ArrayList中寄存的所有地位，看看那个能够走，如果能够走通，就持续，走不通，就回溯。
  4. 判断马儿是否实现了工作，应用step和应该走的步数比拟，如果没有达到数量，则示意没有实现工作，将整个棋盘设置为0。

留神:马儿走的策略不同，则失去的后果也不一样，效率也不一样。

对代码应用贪婪算法，进行优化，进步速度：

剖析

  1. 咱们当初走的下一个地位，是依照咱们的顺时针来筛选地位，因而抉择的这个点的下一个能够走的地位的个数是不确定的.
  2. 优化思路是:咱们应该抉择下一个的下一个能够走的地位较少的点，开始走，这样能够缩小回溯。
  3. 代码:对咱们的ps汇合依照能够走的下一个地位的次数进行排序，升序排序。
package com.hspedu;import javax.swing.*;import java.awt.*;import java.util.ArrayList;import java.util.Comparator;public class HorseChessBoard {    //定义属性    private static int X = 6; // 示意col    private static int Y = 6; // 示意row    private static int[][] chessBoard = new int[Y][X]; //棋盘    private static boolean[] visited = new boolean[X * Y];//记录某个地位是否走过    private static boolean finished = false; //记录马儿是否遍历完棋盘.    public static void main(String[] args) {        int row = 2;        int col = 2;        //测试一把        long start = System.currentTimeMillis();        traversalChessBoard(chessBoard, row - 1, col - 1, 1);        long end = System.currentTimeMillis();        System.out.println("遍历耗时=" + (end - start));        //输入以后这个棋盘的状况        for (int[] rows : chessBoard) {            for (int step : rows) {//step 示意 该地位是马儿应该走的第几步                System.out.print(step + "\t");            }            System.out.println();        }    }    //写一个办法，对ps的各个地位，能够走的下一个地位的次数进行排序, 把可能走的下一个地位从小到大排序    public static void sort(ArrayList<Point> ps) {        ps.sort(new Comparator<Point>() {            @Override            public int compare(Point o1, Point o2) {                return next(o1).size() - next(o2).size();            }        });    }    //编写最外围的算法，遍历棋盘，如果遍历胜利，就把 finished 设置为true ,    //并且，将马儿走的每一步step，记录到 chessBoard    public static void traversalChessBoard(int[][] chessBoard, int row, int col, int step) {        //先把step 记录到 chessBoard        chessBoard[row][col] = step;        //把这个地位，设置为曾经拜访        visited[row * X + col] = true;        //获取以后这个地位能够走的下一个地位有哪些        ArrayList<Point> ps = next(new Point(col, row)); // 留神这里的解决： col - X , row - Y        sort(ps);// 排序：咱们应该抉择下一个的下一个能够走的地位较少的点，开始走，这样能够缩小回溯        //遍历        while (!ps.isEmpty()) {            //取出以后这个 ps 第一个地位(点)            Point p = ps.remove(0);            //判断该地位是否走过，如果没有走过，咱们就递归遍历            if (!visited[p.y * X + p.x]) {                //递归遍历                traversalChessBoard(chessBoard, p.y, p.x, step + 1);            }        }        //当退出while，看看是否遍历胜利, 如果没有胜利，就重置相应的值，而后进行回溯        if (step < X * Y && !finished) {            //重置            chessBoard[row][col] = 0;            visited[row * X + col] = false;        } else {            finished = true;        }    }    //编写办法，能够获取以后地位，能够走的下一步的所有地位(Point示意 x,y)    public static ArrayList<Point> next(Point curPoint) {        //创立一个ArrayList        ArrayList<Point> ps = new ArrayList<>();        //创立一个Point对象(点/地位), 筹备放入到 ps        Point p1 = new Point();        //判断在 curPoint 是否能够走如下地位，如果能够走，就将该点(Point) 放入到ps        //判断是否能够走5地位        if ((p1.x = curPoint.x - 2) >= 0 && (p1.y = curPoint.y - 1) >= 0) {            ps.add(new Point(p1)); //这里肯定要new Point        }        //判断是否能够走6地位        if ((p1.x = curPoint.x - 1) >= 0 && (p1.y = curPoint.y - 2) >= 0) {            ps.add(new Point(p1)); //这里肯定要new Point        }        //判断是否能够走7地位        if ((p1.x = curPoint.x + 1) < X && (p1.y = curPoint.y - 2) >= 0) {            ps.add(new Point(p1)); //这里肯定要new Point        }        //判断是否能够走0地位        if ((p1.x = curPoint.x + 2) < X && (p1.y = curPoint.y - 1) >= 0) {            ps.add(new Point(p1)); //这里肯定要new Point        }        //判断是否能够走1地位        if ((p1.x = curPoint.x + 2) < X && (p1.y = curPoint.y + 1) < Y) {            ps.add(new Point(p1)); //这里肯定要new Point        }        //判断是否能够走2地位        if ((p1.x = curPoint.x + 1) < X && (p1.y = curPoint.y + 2) < Y) {            ps.add(new Point(p1)); //这里肯定要new Point        }        //判断是否能够走3地位        if ((p1.x = curPoint.x - 1) >= 0 && (p1.y = curPoint.y + 2) < Y) {            ps.add(new Point(p1)); //这里肯定要new Point        }        //判断是否能够走4地位        if ((p1.x = curPoint.x - 2) >= 0 && (p1.y = curPoint.y + 1) < Y) {            ps.add(new Point(p1)); //这里肯定要new Point        }        return ps;    }}