骑士周游问题

1.算法优化意义904

1.算法是程序的灵魂。为什么有些程序在计算海量数据时仍能保持高速计算？

2.在Unix下开发服务器程序的功能是支持数千万人同时在线。在上线之前，做内部测试。一切都可以，但在上线后，服务器无法支持它。公司的CTO优化了代码，再次上线，就像岩石一样坚固。那个

一瞬间，你就能感觉到程序有灵魂，也就是算法。

3.编程中有很多算法，如八种排序算法(冒泡、选择、插入、快速排序、回井、希尔、基数、堆排序)、搜索算法、分治算法、动态规划算法、KMP算法、贪婪算法、普里姆算法、克鲁斯卡尔算法、迪杰斯特拉算法、弗洛伊德算法

4.以骑士周游为例，让朋友体验用算法优化程序的意义，让大家直观感受算法的力量

1.马踏棋盘算法也被称为骑士周游

2.将马随机放在国际象棋的8x8棋盘Board[0~7][0~7]的某个方格中，马按照走棋规则(马走日字)移动。每个方格只需进入一次，棋盘上有64个方格

3.游戏演示：

https://u.ali213.net/games/horsesun/index.html?gamecode=403

4.将使用图纸的遍历算法(DFS)+贪婪算法优化

1.马踏棋盘问题(骑士周游问题)实际上是图片深度优先搜索(DFS)的应用。

2.如果用可追溯性(即深度优先搜索)来解决，如果马踩了53分，如图:走到第53分，坐标(1、0)，发现已经走到了尽头，没办法，只能回去看看其他路径，不停地在棋盘上回去。...,思维分析+代码实现

3.先用基本方法解决，再用贪婪算法(greedyalgorithm)优化。解决马踏棋盘问题，认识到不同算法对程序效率的影响

4.使用前面的游戏来验证算法是否正确

解决骑士周游问题的步骤和思路分析

1.创建棋盘chesboard是一个二维数组

2.将当前位置设置为已访问位置，然后根据当前位置计算马还能走哪些位置，并将其放入集合中(ArrayList),最多8个，每走一步，使用step+1

3.遍历ArrayList中存储的所有位置，看看可以走的位置。如果可以通过，就继续。如果不能通过，可以追溯

4.判断马是否完成了任务，使用step与步骤进行比较。如果没有达到数量，则表示没有完成任务，并将整个棋盘设置为0

package com.stulzl.horse_chessboard;import java.awt.*;import java.util.ArrayList;///马踏棋盘 906public 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 = 5;        int col = 5;        long start = System.currentTimeMillis();        traversalChessBoard(chessBoard,row-1,col-1,1);        long end = System.currentTimeMillis();        System.out.println(”遍历时间=”+(end-start));        ////输出当前棋盘情况        //增强for，解释，以二维数组为几个一维数组，即每行为一维数组，然后遍历一维数组        for(int[] rows : chessBoard){            for (int step : rows){                System.out.print(step+"\t");            }            System.out.println();        }        ///普通for/////        for (int i = 0; i < chessBoard.length; i++) {//            for (int j=0;j//                System.out.print(chessBoard[i][j]+"\t");//            }//            System.out.println();//        }    }    //编写核心算法，遍历棋盘，如果成功遍历，将finished设置为true，并且   907    ///将马走的每一步step记录在chessboard二维数组中    public static void traversalChessBoard(int[][] chessBoard,int row,int col,int step){        ///先将step记录在chesboard中        chessBoard[row][col] = step;        ///将这个位置设置为已经访问的位置，即通过，可以通过，但通过，不用再走了        visited[row*X+col] = true;        ///获得当前位置的下一个位置是什么？        ArrayList ps = next(new Point(col, row));//注意col是垂直坐标，即Y，row是横坐标，即X        //遍历        while(!ps.isEmpty(){//如果集合不是空的，则进入循环，然后取出集合中的点            //解释:取出ps集合中的第一个位置(点)(因为remove(0) 0代表当前集合的第一个元素的索引)            // ，我们在这里取出的点是使用remove删除(解释为什么边取边删除，因为我们的ps集合会边取边删除。            // 它会越来越小，这意味着删除原始的第一个元素 也就是说，索引0对应的元素，后面的第二个元素成为第一个元素，            // 就像聚在一起向前走一样，这样，我们就可以取出集合中的所有元素，因为我们不知道集合中            // 到底有多少元素，(因为下一步是否合法不确定)就不能用具体的0、1、2..等等来获取相关数据，            // 边取边删就可以了，因为删完就结束了)，            // 因为进入循环的条件是判断集合是否空，当我们删除当前点的下一个位置的集合边时            // ，这一点的集合不需要进入循环判断            Point p = ps.remove(0);//从集合中取出一个点，边取边删的返回值就是这个被删点的数据            ///判断这个位置是否通过。如果没有通过，我们就让这个点递归到遍历。            //解释p.y对应row横坐标，p.x对应col纵坐标            if(!visited[p.y*X+p.x]){//如果不等于true，也就是false，false就是没有走过                //没有通过这一点，就把这一点作为当前的一点(因为我们的这一点是从集合中取出的，即“下一个合法点”，                // 进入递归，以此点为当前点) 进入递归                traversalChessBoard(chessBoard,p.y,p.x,step+1);            }        }        ///推出while循环后，看看它是否成功，如果不成功，重置相应的值，然后进行回溯        //解释!finished和true，因为我们的finished的初始值是false，finished说游戏结束了，我们将        //!finished和true，因为我们的finished的初始值是false，finished说游戏结束了，我们将        //！finished和true表示游戏还没有结束        if(step<X*Y && !finished){//表示游戏没有结束，可以进入循环            //重置            //既然走不通，就回到这一点(注意这一点不一定值起点，也可能是递归中的一个分支点)            chessBoard[row][col] = 0;            visited[row*X+col] = false;///把false放在那个时候        }else{            finished = true;///成功结束游戏        }    }    //写一个方法，可获得当前位置，可返回下一步所有合法点位置(Point表示x，y)   906    public static ArrayList next(Point curPoint){//curPoint目前的位置        //创建ArrayList，用于盛放当前坐标curPoint，下一步符合法律法规的点(最多8点)        ArrayList ps = new ArrayList<>();        如果此点坐标符合规则，///创建Point对象(点/位置)放入ps集合        Point p1 = new Point();///这个p1是curpoint下一步的合法点        ///判断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        }        ///判断能否走一个位置        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;    }}

1.我们现在的下一个位置是根据我们的顺时针选择位置，所以下一个位置的数量是不确定的.

2.优化思路是:我们应该选择下一个可以少走的地方，开始走，这样可以减少回溯

3.代码：根据下一个位置的次数对我们的ps集合进行排序，并对其进行升序排序

package com.stulzl.horse_chessboard_pro;import java.awt.*;import java.util.ArrayList;import java.util.Comparator;///马踏棋盘 贪心算法版 908public class HorseChessBoardPro {    //定义属性    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，解释，以二维数组为几个一维数组，即每行为一维数组，然后遍历一维数组        for(int[] rows : chessBoard){            for (int step : rows){                System.out.print(step+"\t");            }            System.out.println();        }        ///普通for/////        for (int i = 0; i < chessBoard.length; i++) {//            for (int j=0;j//                System.out.print(chessBoard[i][j]+"\t");//            }//            System.out.println();//        }    }    //写一个方法，对ps的每个位置，可以走下一个位置的次数进行排序， 从小到大排序可能的下一个位置  908    public static void sort(ArrayList ps) {        ps.sort(new Comparator() 别纠结{///这块            @Override            public int compare(Point o1, Point o2) {                return next(o1).size()-next(o2).size();            }        });    }    //编写核心算法，遍历棋盘，如果成功遍历，将finished设置为true，并且   907    ///将马走的每一步step记录在chessboard二维数组中    public static void traversalChessBoard(int[][] chessBoard,int row,int col,int step){        ///先将step记录在chesboard中        chessBoard[row][col] = step;        ///将这个位置设置为已经访问的位置，即通过，可以通过，但通过，不用再走了        visited[row*X+col] = true;        ///获得当前位置的下一个位置是什么？        ArrayList ps = next(new Point(col, row));//注意col是垂直坐标，即Y，row是横坐标，即X        sort(ps);//排序后  908        //遍历        while(!ps.isEmpty(){//如果集合不是空的，则进入循环，然后取出集合中的点            //解释:取出ps集合中的第一个位置(点)(因为remove(0) 0代表当前集合的第一个元素的索引)            // ，我们在这里取出的点是使用remove删除(解释为什么边取边删除，因为我们的ps集合会边取边删除。            // 它会越来越小，这意味着删除原始的第一个元素 也就是说，索引0对应的元素，后面的第二个元素成为第一个元素，            // 就像聚在一起向前走一样，这样，我们就可以取出集合中的所有元素，因为我们不知道集合中            // 到底有多少元素，(因为下一步是否合法不确定)就不能用具体的0、1、2..等等来获取相关数据，            // 边取边删就可以了，因为删完就结束了)，            // 因为进入循环的条件是判断集合是否空，当我们删除当前点的下一个位置的集合边时            // ，这一点的集合不需要进入循环判断            Point p = ps.remove(0);//从集合中取出一个点，边取边删的返回值就是这个被删点的数据            ///判断这个位置是否通过。如果没有通过，我们就让这个点递归到遍历。            //解释p.y对应row横坐标，p.x对应col纵坐标            if(!visited[p.y*X+p.x]){//如果不等于true，也就是false，false就是没有走过                //没有通过这一点，就把这一点作为当前的一点(因为我们的这一点是从集合中取出的，即“下一个合法点”，                // 进入递归，以此点为当前点) 进入递归                traversalChessBoard(chessBoard,p.y,p.x,step+1);            }        }        ///推出while循环后，看看它是否成功，如果不成功，重置相应的值，然后进行回溯        //解释!finished和true，因为我们的finished的初始值是false，finished说游戏结束了，我们将        //!finished和true，因为我们的finished的初始值是false，finished说游戏结束了，我们将        //！finished和true表示游戏还没有结束        if(step<X*Y && !finished){//表示游戏没有结束，可以进入循环            //重置            //既然走不通，就回到这一点(注意这一点不一定值起点，也可能是递归中的一个分支点)            chessBoard[row][col] = 0;            visited[row*X+col] = false;///把false放在那个时候        }else{            finished = true;///成功结束游戏        }    }    //写一个方法，可获得当前位置，可返回下一步所有合法点位置(Point表示x，y)   906    public static ArrayList next(Point curPoint){//curPoint目前的位置        //创建ArrayList，用于盛放当前坐标curPoint，下一步符合法律法规的点(最多8点)        ArrayList ps = new ArrayList<>();        如果此点坐标符合规则，///创建Point对象(点/位置)放入ps集合        Point p1 = new Point();///这个p1是curpoint下一步的合法点        ///判断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        }        ///判断能否走一个位置        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;    }}