骑士周游算法

算法优化意义

1.算法是程序的灵魂，为什么有些程序可以在海量数据计算时，依然保持高速计算？
2.在Unix下开发服务器程序，功能是要支持上干万人同时在线，在上线前，做内测，一切OK,可上线后，服务器就支撑不住了，公司的CTO对代码进行优化，再次上线，坚如磐石。那瞬间，你就能感受到程序是有灵魂的，就是算法。
3.编程中算法很多，比如八大排序算法
（冒泡、选择、插入、快排、归并、希尔、基数、堆排序)、查找算法、分治算法、动态规划算法、KMP算法、贪心算法、普里姆算法、克鲁斯卡尔算法、迪杰斯特拉算法、弗洛伊德算法
4.以骑士周游问题为例，让小伙伴体验用算法去优化程序的意义，让大家直观的感受到算法的威力

马踏棋盘算法介绍和游戏演示

1.马踏棋盘算法也被称为骑士周游问题
2.将马随机放在国际象棋的8×8棋盘Board[0_7][07]的某个方格中，马按走棋规则（马走日字）进行移动。要求每
个方格只进入一次，走遍棋盘上全部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

注意：马儿走的策略不同，则得到的结果也不一样，效率也不一样.

代码实现

java">package com.hspedu;import java.awt.*;
import java.util.ArrayList;/*** @program: chapter28* @since: jdk1.8* @description:* @author: Administrator* @create: 2024-12-22 12:33**/
public class HorseChessBoard {// 定义属性private static int X = 6; // 表示列colprivate static int Y = 6; // 表示行rowprivate 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 startTime = System.currentTimeMillis();traversalChessBoard(chessBoard, row - 1, col - 1, 1);long endTime = System.currentTimeMillis();System.out.println("遍历耗时：" + (endTime - startTime) + "ms");// 遍历棋盘for (int[] rows : chessBoard) {for (int step : rows) {System.out.print(step + "\t");}System.out.println();}}/*** 遍历棋盘，记录马儿走的每一步。* 编写最核心算法，遍历棋盘，如果遍历成功，就把 finished 设置为true 并且，将马儿走的每一步，记录到chessBoard** @param chessBoard 二维数组，表示棋盘，用于记录马儿走的每一步* @param row        当前位置的行索引* @param col        当前位置的列索引* @param step       当前步数*/public static void traversalChessBoard(int[][] chessBoard, int row, int col, int step) {// 先把step记录到chessBoardchessBoard[row][col] = step;// 把这个位置设置为已经访问visited[row * X + col] = true;// 获取当前这个位置可以走的下一个位置有哪些ArrayList<Point> ps = next(new Point(col, row));while (!ps.isEmpty()) {// 取出一个位置（点）Point p = ps.remove(0);// 判断该位置是否走过，如果没有走过就递归遍历/*p.y * X + p.x：这是一个计算索引的表达式，用于将二维空间中的点p转换为一维数组visited的索引。这里假设二维空间的宽度为X，即每行有X个元素。通过将p的y坐标乘以X（即每行的元素数量），再加上p的x坐标，就可以得到该点在一维数组visited中的位置。*//*在实际应用中，这个条件判断语句通常用于图的遍历算法（如深度优先搜索DFS或广度优先搜索BFS）中，以确保每个点只被访问一次，避免无限循环或重复处理。如果点p尚未被访问，则可以在条件判断语句内的代码块中执行访问该点的操作（如标记为已访问、处理该点的数据等）。*/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;}}/*** 获取当前位置可以走的下一步的所有位置** @param curPoint 当前位置* @return 包含下一步所有可能位置的ArrayList<Point>*/public static ArrayList<Point> next(Point curPoint) {ArrayList<Point> ps = new ArrayList<>();// 创建一个Point对象(点/位置)，准备放入到psPoint 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位置,<X是防止越界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;}
}

问题：如果马儿在第二行第二列的时候耗时特别长

流程图

使用贪心算法优化耗时

分析

1.我们现在走的下一个位置，是按照我们的顺时针
来挑选位置，因此选择的这个点的下一个可以走的
位置的个数是不确定的.
2.优化思路是：我们应该选择下一个的下一个可以
走的位置较少的点，开始走，这样可以减少回溯的次数
3.代码：对我们的ps集合按照可以走的下一个位置
的次数进行排序，升序排序

java">![马踏棋盘算法-贪心算法优化](算法.assets/马踏棋盘算法-贪心算法优化.png)package com.hspedu;import java.awt.*;
import java.util.ArrayList;
import java.util.Comparator;/*** @program: chapter28* @since: jdk1.8* @description:* @author: Administrator* @create: 2024-12-22 12:33**/
public class HorseChessBoard {// 定义属性private static int X = 6; // 表示列colprivate static int Y = 6; // 表示行rowprivate 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 startTime = System.currentTimeMillis();traversalChessBoard(chessBoard, row - 1, col - 1, 1);long endTime = System.currentTimeMillis();System.out.println("遍历耗时：" + (endTime - startTime) + "ms");// 遍历棋盘for (int[] rows : chessBoard) {for (int step : rows) {System.out.print(step + "\t");}System.out.println();}}/*** 对点的集合进行排序。** @param ps 点的集合，类型为ArrayList<Point>*/public static void sort(ArrayList<Point> ps) {ps.sort(new Comparator<Point>() {@Overridepublic int compare(Point o1, Point o2) {return next(o1).size() - next(o2).size();}});}/*** 遍历棋盘，记录马儿走的每一步。* 编写最核心算法，遍历棋盘，如果遍历成功，就把 finished 设置为true 并且，将马儿走的每一步，记录到chessBoard** @param chessBoard 二维数组，表示棋盘，用于记录马儿走的每一步* @param row        当前位置的行索引* @param col        当前位置的列索引* @param step       当前步数*/public static void traversalChessBoard(int[][] chessBoard, int row, int col, int step) {// 先把step记录到chessBoardchessBoard[row][col] = step;// 把这个位置设置为已经访问visited[row * X + col] = true;// 获取当前这个位置可以走的下一个位置有哪些ArrayList<Point> ps = next(new Point(col, row));sort(ps);// 排序while (!ps.isEmpty()) {// 取出一个位置（点）Point p = ps.remove(0);// 判断该位置是否走过，如果没有走过就递归遍历/*p.y * X + p.x：这是一个计算索引的表达式，用于将二维空间中的点p转换为一维数组visited的索引。这里假设二维空间的宽度为X，即每行有X个元素。通过将p的y坐标乘以X（即每行的元素数量），再加上p的x坐标，就可以得到该点在一维数组visited中的位置。*//*在实际应用中，这个条件判断语句通常用于图的遍历算法（如深度优先搜索DFS或广度优先搜索BFS）中，以确保每个点只被访问一次，避免无限循环或重复处理。如果点p尚未被访问，则可以在条件判断语句内的代码块中执行访问该点的操作（如标记为已访问、处理该点的数据等）。*/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;}}/*** 获取当前位置可以走的下一步的所有位置** @param curPoint 当前位置* @return 包含下一步所有可能位置的ArrayList<Point>*/public static ArrayList<Point> next(Point curPoint) {ArrayList<Point> ps = new ArrayList<>();// 创建一个Point对象(点/位置)，准备放入到psPoint 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位置,<X是防止越界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;}
}

输出

流程图