devbox
盐析白兔
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

【算法】马踏棋盘（骑士周游）问题回溯算法实现以及使用贪心算法优化

作者：盐析白兔 | 2024-08-19 09:53:24

赞

踩

【算法】马踏棋盘（骑士周游）问题回溯算法实现以及使用贪心算法优化

目录

1.游戏规则

2.算法分析

3.解决步骤和思路

4.马踏棋盘算法的代码实现

4.1计算马儿还能走哪些位置

4.2马踏棋盘的核心代码

4.3马踏棋盘算法完整代码

4.4使用贪心算法进行优化

4.4.1思路

4.4.2代码实现 

1.游戏规则

将马儿随机放在国际象棋的 8*8 棋盘的某个方格中，马儿按照“马走日”进行移动，要求每个方格只进入一次，走遍棋盘上全部 64 个方格。

2.算法分析

  1. 马踏棋盘（骑士周游）问题实际上是图的深度优先搜索（DFS）的应用
  2. 如果使用回溯（就是深度优先搜索）来解决，假如马儿踏了 53 个点，如图：走到了第 53 个，坐标 (1,0)，发现已经走到尽头，没办法，那就只能回退了。为了查看其他的路径，就在棋盘上不停的回溯
  3. 使用贪心算法进行优化

3.解决步骤和思路

  1. 创建棋盘 chessBoard，是一个二维数组
  2. 将当前位置设置为已经访问，然后根据当前位置，计算马儿还能走哪些位置，并放入到一个集合（ArrayList）中，最多有 8 个位置，每走一步，就让 step + 1
  3. 遍历 ArrayList 中存放的所有位置，看看哪个可以走通，如果走通就继续，走不通就回溯
  4. 判断马儿是否完成了任务，使用 step 和应该走的步数比较，如果没有达到数量，则表示没有完成任务，将整个棋盘置 0

注意：马儿不同的走法会得到不同的结果，效率也会有影响

4.马踏棋盘算法的代码实现

4.1计算马儿还能走哪些位置

  1. public static ArrayList<Point> next(Point curPoint) {
  2.         //创建一个 ArrayList
  3.         ArrayList<Point> ps = new ArrayList<>();
  4.         //创建一个 Point
  5.         Point p1 = new Point();
  6.         //左偏上
  7.         if ((p1.x = curPoint.x - 2) >= 0 && (p1.y = curPoint.y - 1) >= 0) {
  8.             ps.add(new Point(p1));
  9.         }
  10.         //上偏左
  11.         if ((p1.x = curPoint.x - 1) >= 0 && (p1.y = curPoint.y - 2) >= 0) {
  12.             ps.add(new Point(p1));
  13.         }
  14.         //上偏右
  15.         if ((p1.x = curPoint.x + 1) < X && (p1.y = curPoint.y - 2) >= 0) {
  16.             ps.add(new Point(p1));
  17.         }
  18.         //右偏上
  19.         if ((p1.x = curPoint.x + 2) < X && (p1.y = curPoint.y - 1) >= 0) {
  20.             ps.add(new Point(p1));
  21.         }
  22.         //右偏下
  23.         if ((p1.x = curPoint.x + 2) < X && (p1.y = curPoint.y + 1) < Y) {
  24.             ps.add(new Point(p1));
  25.         }
  26.         //下偏右
  27.         if ((p1.x = curPoint.x + 1) < X && (p1.y = curPoint.y + 2) < Y) {
  28.             ps.add(new Point(p1));
  29.         }
  30.         //下偏左
  31.         if ((p1.x = curPoint.x - 1) >= 0 && (p1.y = curPoint.y + 2) < Y) {
  32.             ps.add(new Point(p1));
  33.         }
  34.         //左偏下
  35.         if ((p1.x = curPoint.x - 2) >= 0 && (p1.y = curPoint.y + 1) < Y) {
  36.             ps.add(new Point(p1));
  37.         }
  38.         return ps;
  39.     }

4.2马踏棋盘的核心代码

  1.     /**
  2.      * 完成马踏棋盘问题的算法
  3.      * @param chessboard 棋盘
  4.      * @param row        马儿当前位置的行 从0开始
  5.      * @param column     马儿当前位置的列 从0开始
  6.      * @param step       是第几步，初始位置就是第1步
  7.      */
  8.     public static void traversalChessboard(int[][] chessboard, int row, int column, int step) {
  9.         chessboard[row][column] = step;
  10.         visited[row * X + column] = true;  //标记该位置已经访问
  11.         //获取当前位置可以走的下一个位置的集合
  12.         ArrayList<Point> ps = next(new Point(column, row));
  13.         //遍历 ps
  14.         while (!ps.isEmpty()) {
  15.             Point p = ps.remove(0);//取出下一个可以走的位置
  16.             //判断该点是否已经访问过
  17.             if (!visited[p.y * X + p.x]) {//说明还没有访问过
  18.                 traversalChessboard(chessboard, p.y, p.x, step + 1);
  19.             }
  20.         }
  21.         /*
  22.         判断马儿是否完成任务，使用step和应该走的步数比较
  23.         如果没有达到数量，则表示没有完成任务，将整个棋盘置0
  24.         说明：step < X * Y 成立的条件有两种
  25.         1.棋盘到目前为止，仍然没有走完
  26.         2.棋盘处于一个回溯过程
  27.          */
  28.         if (step < X * Y && !finished) {
  29.             chessboard[row][column] = 0;
  30.             visited[row * X + column] = false;
  31.         } else {
  32.             finished = true;
  33.         }
  34.     }

4.3马踏棋盘算法完整代码

  1. public class HorseChessboard {
  2.     private static int X;  //棋盘的列数
  3.     private static int Y;  //棋盘的行数
  4.     //创建一个数组，标记棋盘的各个位置是否被访问过
  5.     private static boolean visited[];
  6.     //使用一个属性，标记是否棋盘的所有位置都被访问
  7.     private static boolean finished;  //如果为 true，表示成功
  8.  
  9.     public static void main(String[] args) {
  10.         System.out.println("马踏棋盘算法开始运行");
  11.         //测试马踏棋盘算法是否正确
  12.         X = 8;
  13.         Y = 8;
  14.         int row = 1;  //马儿初始位置的行，从1开始编号
  15.         int column = 1;  //马儿初始位置的列，从1开始编号
  16.         //创建棋盘
  17.         int[][] chessboard = new int[X][Y];
  18.         visited = new boolean[X * Y];  //初始值都是false
  19.         //测试一下耗时
  20.         long start = System.currentTimeMillis();
  21.         traversalChessboard(chessboard, row - 1, column - 1, 1);
  22.         long end = System.currentTimeMillis();
  23.         System.out.println("共耗时" + (end - start) + "毫秒");
  24.  
  25.         //输出棋盘的最后结果
  26.         for (int[] rows : chessboard) {
  27.             for (int step : rows) {
  28.                 System.out.print(step + "\t");
  29.             }
  30.             System.out.println();
  31.         }
  32.  
  33.     }
  34.  
  35.     /**
  36.      * 完成马踏棋盘问题的算法
  37.      * @param chessboard 棋盘
  38.      * @param row        马儿当前位置的行 从0开始
  39.      * @param column     马儿当前位置的列 从0开始
  40.      * @param step       是第几步，初始位置就是第1步
  41.      */
  42.     public static void traversalChessboard(int[][] chessboard, int row, int column, int step) {
  43.         chessboard[row][column] = step;
  44.         visited[row * X + column] = true;  //标记该位置已经访问
  45.         //获取当前位置可以走的下一个位置的集合
  46.         ArrayList<Point> ps = next(new Point(column, row));
  47.         //遍历 ps
  48.         while (!ps.isEmpty()) {
  49.             Point p = ps.remove(0);//取出下一个可以走的位置
  50.             //判断该点是否已经访问过
  51.             if (!visited[p.y * X + p.x]) {//说明还没有访问过
  52.                 traversalChessboard(chessboard, p.y, p.x, step + 1);
  53.             }
  54.         }
  55.         /*
  56.         判断马儿是否完成任务，使用step和应该走的步数比较
  57.         如果没有达到数量，则表示没有完成任务，将整个棋盘置0
  58.         说明：step < X * Y 成立的条件有两种
  59.         1.棋盘到目前为止，仍然没有走完
  60.         2.棋盘处于一个回溯过程
  61.          */
  62.         if (step < X * Y && !finished) {
  63.             chessboard[row][column] = 0;
  64.             visited[row * X + column] = false;
  65.         } else {
  66.             finished = true;
  67.         }
  68.     }
  69.  
  70.     public static ArrayList<Point> next(Point curPoint) {
  71.         //创建一个 ArrayList
  72.         ArrayList<Point> ps = new ArrayList<>();
  73.         //创建一个 Point
  74.         Point p1 = new Point();
  75.         //左偏上
  76.         if ((p1.x = curPoint.x - 2) >= 0 && (p1.y = curPoint.y - 1) >= 0) {
  77.             ps.add(new Point(p1));
  78.         }
  79.         //上偏左
  80.         if ((p1.x = curPoint.x - 1) >= 0 && (p1.y = curPoint.y - 2) >= 0) {
  81.             ps.add(new Point(p1));
  82.         }
  83.         //上偏右
  84.         if ((p1.x = curPoint.x + 1) < X && (p1.y = curPoint.y - 2) >= 0) {
  85.             ps.add(new Point(p1));
  86.         }
  87.         //右偏上
  88.         if ((p1.x = curPoint.x + 2) < X && (p1.y = curPoint.y - 1) >= 0) {
  89.             ps.add(new Point(p1));
  90.         }
  91.         //右偏下
  92.         if ((p1.x = curPoint.x + 2) < X && (p1.y = curPoint.y + 1) < Y) {
  93.             ps.add(new Point(p1));
  94.         }
  95.         //下偏右
  96.         if ((p1.x = curPoint.x + 1) < X && (p1.y = curPoint.y + 2) < Y) {
  97.             ps.add(new Point(p1));
  98.         }
  99.         //下偏左
  100.         if ((p1.x = curPoint.x - 1) >= 0 && (p1.y = curPoint.y + 2) < Y) {
  101.             ps.add(new Point(p1));
  102.         }
  103.         //左偏下
  104.         if ((p1.x = curPoint.x - 2) >= 0 && (p1.y = curPoint.y + 1) < Y) {
  105.             ps.add(new Point(p1));
  106.         }
  107.         return ps;
  108.     }
  109. }

4.4使用贪心算法进行优化

4.4.1思路

  1. 获取当前位置的可以走的下一个位置的集合
  2. 对 ps 中所有的 Point 的下一步的所有集合的数目进行非递减排序

4.4.2代码实现 

  1. public class HorseChessboard {
  2.     private static int X;  //棋盘的列数
  3.     private static int Y;  //棋盘的行数
  4.     //创建一个数组，标记棋盘的各个位置是否被访问过
  5.     private static boolean visited[];
  6.     //使用一个属性，标记是否棋盘的所有位置都被访问
  7.     private static boolean finished;  //如果为 true，表示成功
  8.  
  9.     public static void main(String[] args) {
  10.         System.out.println("马踏棋盘算法开始运行");
  11.         //测试马踏棋盘算法是否正确
  12.         X = 8;
  13.         Y = 8;
  14.         int row = 1;  //马儿初始位置的行，从1开始编号
  15.         int column = 1;  //马儿初始位置的列，从1开始编号
  16.         //创建棋盘
  17.         int[][] chessboard = new int[X][Y];
  18.         visited = new boolean[X * Y];  //初始值都是false
  19.         //测试一下耗时
  20.         long start = System.currentTimeMillis();
  21.         traversalChessboard(chessboard, row - 1, column - 1, 1);
  22.         long end = System.currentTimeMillis();
  23.         System.out.println("共耗时" + (end - start) + "毫秒");
  24.  
  25.         //输出棋盘的最后结果
  26.         for (int[] rows : chessboard) {
  27.             for (int step : rows) {
  28.                 System.out.print(step + "\t");
  29.             }
  30.             System.out.println();
  31.         }
  32.  
  33.     }
  34.  
  35.     /**
  36.      * 完成马踏棋盘问题的算法
  37.      * @param chessboard 棋盘
  38.      * @param row        马儿当前位置的行 从0开始
  39.      * @param column     马儿当前位置的列 从0开始
  40.      * @param step       是第几步，初始位置就是第1步
  41.      */
  42.     public static void traversalChessboard(int[][] chessboard, int row, int column, int step) {
  43.         chessboard[row][column] = step;
  44.         visited[row * X + column] = true;  //标记该位置已经访问
  45.         //获取当前位置可以走的下一个位置的集合
  46.         ArrayList<Point> ps = next(new Point(column, row));
  47.         //对 ps 进行排序
  48.         sort(ps);
  49.         //遍历 ps
  50.         while (!ps.isEmpty()) {
  51.             Point p = ps.remove(0);//取出下一个可以走的位置
  52.             //判断该点是否已经访问过
  53.             if (!visited[p.y * X + p.x]) {//说明还没有访问过
  54.                 traversalChessboard(chessboard, p.y, p.x, step + 1);
  55.             }
  56.         }
  57.         /*
  58.         判断马儿是否完成任务，使用step和应该走的步数比较
  59.         如果没有达到数量，则表示没有完成任务，将整个棋盘置0
  60.         说明：step < X * Y 成立的条件有两种
  61.         1.棋盘到目前为止，仍然没有走完
  62.         2.棋盘处于一个回溯过程
  63.          */
  64.         if (step < X * Y && !finished) {
  65.             chessboard[row][column] = 0;
  66.             visited[row * X + column] = false;
  67.         } else {
  68.             finished = true;
  69.         }
  70.     }
  71.  
  72.     public static ArrayList<Point> next(Point curPoint) {
  73.         //创建一个 ArrayList
  74.         ArrayList<Point> ps = new ArrayList<>();
  75.         //创建一个 Point
  76.         Point p1 = new Point();
  77.         //左偏上
  78.         if ((p1.x = curPoint.x - 2) >= 0 && (p1.y = curPoint.y - 1) >= 0) {
  79.             ps.add(new Point(p1));
  80.         }
  81.         //上偏左
  82.         if ((p1.x = curPoint.x - 1) >= 0 && (p1.y = curPoint.y - 2) >= 0) {
  83.             ps.add(new Point(p1));
  84.         }
  85.         //上偏右
  86.         if ((p1.x = curPoint.x + 1) < X && (p1.y = curPoint.y - 2) >= 0) {
  87.             ps.add(new Point(p1));
  88.         }
  89.         //右偏上
  90.         if ((p1.x = curPoint.x + 2) < X && (p1.y = curPoint.y - 1) >= 0) {
  91.             ps.add(new Point(p1));
  92.         }
  93.         //右偏下
  94.         if ((p1.x = curPoint.x + 2) < X && (p1.y = curPoint.y + 1) < Y) {
  95.             ps.add(new Point(p1));
  96.         }
  97.         //下偏右
  98.         if ((p1.x = curPoint.x + 1) < X && (p1.y = curPoint.y + 2) < Y) {
  99.             ps.add(new Point(p1));
  100.         }
  101.         //下偏左
  102.         if ((p1.x = curPoint.x - 1) >= 0 && (p1.y = curPoint.y + 2) < Y) {
  103.             ps.add(new Point(p1));
  104.         }
  105.         //左偏下
  106.         if ((p1.x = curPoint.x - 2) >= 0 && (p1.y = curPoint.y + 1) < Y) {
  107.             ps.add(new Point(p1));
  108.         }
  109.         return ps;
  110.     }
  111.  
  112.     //根据当前这一步的所有下一步的数目进行非递减排序，减少回溯的可能
  113.     public static void sort(ArrayList<Point> ps) {
  114.         ps.sort(new Comparator<Point>() {
  115.             @Override
  116.             public int compare(Point o1, Point o2) {
  117.                 //获取到 o1 的下一步的所有位置的个数
  118.                 int count1 = next(o1).size();
  119.                 //获取到 o2 的下一步的所有位置的个数
  120.                 int count2 = next(o2).size();
  121.                 if (count1 < count2) {
  122.                     return -1;
  123.                 }else if (count1 == count2) {
  124.                     return 0;
  125.                 } else {
  126.                     return 1;
  127.                 }
  128.             }
  129.         });
  130.     }
  131. }
声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/盐析白兔/article/detail/1001766
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号