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

我所知道的十大常用算法之马踏棋盘算法（深度搜索、贪心思想优化 ）

作者：AllinToyou | 2024-05-15 15:45:54

赞

踩

骑士周游问题

前言需求

今天我们学习的是马踏棋盘算法，我们还是从一个场景里引入看看

image.png

马踏棋盘算法也被称为骑士周游问题

将马随机放在国际象棋的6×6棋盘Board0～5的某个方格中

提示：马按走棋规则(马走日字)进行移动

要求：每个方格只进入一次，走遍棋盘上全部64个方格

小游戏体验网址：4399：马踏棋盘小游戏

一、马踏棋盘问题

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

还记得图的深度优先搜索(DFS)吗？

有些模糊或者不记得小伙伴可以看往期文章：图(广度优先与深度优先)

image.png

那么按照我们的简单思路，是不是要一个位置一个位置去踩坑看看？

image.png
image.png

那么按照我们的深度优先搜索，就要一步步走下去，直至达成任务

图片.png

当我们的所选第三步的位置，无法达成完成任务

那么我们需要回溯，将原第三步更换到下一个位置里去

image.png

在以新第三步开始，进行搜索，也要一步步走下去，直至达成任务

图片.png

二、通过示例来认识算法

根据我们之前简单的思路，首先我们需要创建一个棋盘的数组

当我们做出选择下一步的时候，我们需要将当前的位置标记为已访问，并根据当前位置计算出马儿能走那些位置，并放入到一个集合中里去

图片.png

当然我们可以根据棋盘的情况来判断是否可以进行计算

图片.png

注意：:马儿不同的走法、会得到不同的结果，效率也会有影响(需优化)

规则判断是否可走

那么我怎么知道这些位置是否可走呢？我是怎么计算出来的呢？

图片.png

首先我们先分析当前位置的x、y坐标，按照规则进行计算：(马走日字)

图片.png

我们先分析一下象棋里的马走日是怎么样的吧

图片.png

马走日所说的是马从提棋位置到落棋位置是一个“日”子的对角线，在没有棋子踩住马脚时，马是可以随意走哪个方向的日字都是可以的

图片.png
图片.png

在有其他棋子在马的如图相关位置时，马就不能走该方向的日字了，我们也熟称“踩马脚了”。注意无论踩马脚的棋子是己方的棋子还是敌方的棋子，被踩方向的日字都不能走了

图片.png

如果四只马脚都被踩了，那么这只马哪里都走不了了(如图)

图片.png

在我们这个问题中，还请你看图关联看懂马儿怎么走的，即称马走日

图片.png

当我们知道规则怎么玩了，就可以从图上看出来，每个点与当前点的关系

图片.png

那么我们的马儿剩下的点与当前是什么关系呢？怎么走呢？

图片.png

骑士周游算法思路

我们创建一个类存放棋盘行、列，并记录棋盘上的是否被访问过

  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. }

我们使用Point 类来表示 (x, y) 坐标空间中的位置的点

  1. public class Point extends Point2D implements java.io.Serializable {
  2.     
  3.     public int x;
  4.  
  5.     public int y;
  6.  
  7.     private static final long serialVersionUID = -5276940640259749850L;
  8.  
  9.     public Point() {
  10.         this(0, 0);
  11.     }
  12.  
  13.     public Point(Point p) {
  14.         this(p.x, p.y);
  15.     }
  16.  
  17.     public Point(int x, int y) {
  18.         this.x = x;
  19.         this.y = y;
  20.     }
  21.  
  22.     //以双精度型返回点的 X 坐标。
  23.     public double getX() {
  24.         return x;
  25.     }
  26.  
  27.     //以双精度型返回点的 Y 坐标。
  28.     public double getY() {
  29.         return y;
  30.     }
  31.  
  32.     //返回此点的位置。
  33.     @Transient
  34.     public Point getLocation() {
  35.         return new Point(x, y);
  36.     }
  37.     //将点的位置设为指定位置
  38.     public void setLocation(Point p) {
  39.         setLocation(p.x, p.y);
  40.     }
  41.     //将此点更改为具有指定位置
  42.     public void setLocation(int x, int y) {
  43.         move(x, y);
  44.     }
  45.  
  46.     //将此点的位置设为指定的双精度坐标
  47.     public void setLocation(double x, double y) {
  48.         this.x = (int) Math.floor(x+0.5);
  49.         this.y = (int) Math.floor(y+0.5);
  50.     }
  51.  
  52.     //将此点移动到 (x,y) 坐标平面中的指定位置。
  53.     public void move(int x, int y) {
  54.         this.x = x;
  55.         this.y = y;
  56.     }
  57.  
  58.     //平移 (x,y) 位置的点，沿 x 轴平移 dx，沿 y 轴平移 dy，移动后得到点 (x+dx, y+dy)
  59.     public void translate(int dx, int dy) {
  60.         this.x += dx;
  61.         this.y += dy;
  62.     }
  63.     
  64.     //确定两个点是否相等。
  65.     public boolean equals(Object obj) {
  66.         if (obj instanceof Point) {
  67.             Point pt = (Point)obj;
  68.             return (x == pt.x) && (y == pt.y);
  69.         }
  70.         return super.equals(obj);
  71.     }
  72.     // 返回此点的字符串表示形式及其在 (x,y) 坐标空间中的位置
  73.     public String toString() {
  74.         return getClass().getName() + "[x=" + x + ",y=" + y + "]";
  75.     }
  76. }

图片.png

根据思路，需要根据当前位置判断马儿能走那些位置，并将结果放入ArrayList集合中

图片.png 

  1. public class HorseChessboard {
  2.     
  3.     //省略其他关键性代码....
  4.     
  5.     /**
  6.      * 功能:根据当前位置(Point对象),计算马儿还能走哪些位置(Point),并放入到一个集合中(ArrayList),最多有8个位置
  7.      * @param curPoint
  8.      * @return
  9.      */
  10.     public static  ArrayList<Point> next(Point curPoint){
  11.         ArrayList<Point> ps = new ArrayList<>();
  12.         //创建一个点
  13.         Point p1 = new Point();
  14.         //判断马儿是否能走5的位置
  15.         if((p1.x = curPoint.x - 2) >=0 && (p1.y = curPoint.y+1) >=0 ){
  16.             ps.add(new Point(p1));
  17.         }
  18.         return  ps;
  19.     }
  20. }

而其他点的位置与当前位置关系，我们之前也使用图解的方式分析，现在代码实现

图片.png 

  1. public class HorseChessboard {
  2.     
  3.     //省略其他关键性代码....
  4.     
  5.      /**
  6.      * 功能:根据当前位置(Point对象),计算马儿还能走哪些位置(Point),并放入到一个集合中(ArrayList),最多有8个位置
  7.      * @param curPoint
  8.      * @return
  9.      */
  10.     public static  ArrayList<Point> next(Point curPoint){
  11.  
  12.         ArrayList<Point> ps = new ArrayList<>();
  13.  
  14.         //创建一个点
  15.         Point p1 = new Point();
  16.  
  17.         //表示马儿可以走5这个位置
  18.         if((p1.x = curPoint.x - 2) >= 0 && (p1.y = curPoint.y -1) >= 0) {
  19.             ps.add(new Point(p1));
  20.         }
  21.         //判断马儿可以走6这个位置
  22.         if((p1.x = curPoint.x - 1) >=0 && (p1.y=curPoint.y-2)>=0) {
  23.             ps.add(new Point(p1));
  24.         }
  25.         //判断马儿可以走7这个位置
  26.         if ((p1.x = curPoint.x + 1) < x && (p1.y = curPoint.y - 2) >= 0) {
  27.             ps.add(new Point(p1));
  28.         }
  29.         //判断马儿可以走0这个位置
  30.         if ((p1.x = curPoint.x + 2) < x && (p1.y = curPoint.y - 1) >= 0) {
  31.             ps.add(new Point(p1));
  32.         }
  33.         //判断马儿可以走1这个位置
  34.         if ((p1.x = curPoint.x + 2) < x && (p1.y = curPoint.y + 1) < y) {
  35.             ps.add(new Point(p1));
  36.         }
  37.         //判断马儿可以走2这个位置
  38.         if ((p1.x = curPoint.x + 1) < x && (p1.y = curPoint.y + 2) < y) {
  39.             ps.add(new Point(p1));
  40.         }
  41.         //判断马儿可以走3这个位置
  42.         if ((p1.x = curPoint.x - 1) >= 0 && (p1.y = curPoint.y + 2) < y) {
  43.             ps.add(new Point(p1));
  44.         }
  45.         //判断马儿可以走4这个位置
  46.         if ((p1.x = curPoint.x - 2) >= 0 && (p1.y = curPoint.y + 1) < y) {
  47.             ps.add(new Point(p1));
  48.         }
  49.         return  ps;
  50.     }
  51. }

那么会不会有小伙伴有疑惑？？

为什么走五那个位置就要>=0呢，走七的位置就要<x呢？<y又是什么一样？

我们先分析走五的位置的时候，为什么要>=0

图片.png

同理，小于x，小于y代表我们只选择在棋盘内的点，超出的则不能走

骑士周游算法实践

往期我们使用的是二维数组代表这个点是否被访问过

但这里是36步都需要走一遍，那么我们其实可以使用一维数组进行表示

图片.png

这样我们可以是用公式：马儿所在行 * 棋盘行 +马儿所在列 = 马儿下标 + 1 

  1. public class HorseChessboard {
  2.     
  3.     //省略其他关键性代码....
  4.     
  5.     
  6.     /**
  7.      * 完成骑士周游问题的算法
  8.      * @param chessboard 棋盘
  9.      * @param row 马儿当前的位置的行 从0开始
  10.      * @param column 马儿当前的位置的列  从0开始
  11.      * @param step 是第几步 ,初始位置就是第1步
  12.      */
  13.     public static void traversalChessboard(int[][] chessboard, int row, int column, int step) {
  14.  
  15.         //标记当前棋盘执行的是第几步
  16.         chessboard[row][column] = step;
  17.  
  18.         //row = 3 X = 6 column = 3 = 3 * 6 + 3 = 21 -1 = 20
  19.         visited[row * x + column] = true; //标记该位置已经访问
  20.  
  21.         //获取当前位置可以走的下一个位置的集合
  22.         ArrayList<Point> ps = next(new Point(column, row));
  23.     }
  24. }

当我们获取到当前位置可以走的下一个位置的集合，就进行遍历递归

  1. public class HorseChessboard {
  2.     
  3.     //省略其他关键性代码....
  4.     
  5.     
  6.     /**
  7.      * 完成骑士周游问题的算法
  8.      * @param chessboard 棋盘
  9.      * @param row 马儿当前的位置的行 从0开始
  10.      * @param column 马儿当前的位置的列  从0开始
  11.      * @param step 是第几步 ,初始位置就是第1步
  12.      */
  13.     public static void traversalChessboard(int[][] chessboard, int row, int column, int step) {
  14.  
  15.         //标记当前棋盘执行的是第几步
  16.         chessboard[row][column] = step;
  17.  
  18.         //row = 3 X = 6 column = 3 = 3 * 6 + 3 = 21 -1 = 20
  19.         visited[row * x + column] = true; //标记该位置已经访问
  20.  
  21.         //获取当前位置可以走的下一个位置的集合
  22.         ArrayList<Point> ps = next(new Point(column, row));
  23.         
  24.         //遍历 ps
  25.         while(!ps.isEmpty()) {
  26.             Point p = ps.remove(0);//取出下一个可以走的位置
  27.             //判断该点是否已经访问过
  28.             if(!visited[p.y * X + p.x]) {//说明还没有访问过
  29.                 traversalChessboard(chessboard, p.y, p.x, step + 1);
  30.             }
  31.         }
  32.     }
  33. }

我们怎么区分当前节点的可以走的下一个位置的集合，是否一路就成功了呢？

使用step 和 应该走的步数比较：step = X * Y

假如当前节点的可以走的下一个位置的集合，没有一路就成功，怎么办？

取消该位置已访问，并将棋盘置为0，说明该节点处于回溯状态

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

接下来，让我们使用demo 测试一把这些思路与代码

图片.png

我们采用上图的马儿作为起始位置，来测试看看

  1. public class HorseChessboard {
  2.     
  3.     //省略其他关键性代码....
  4.     
  5.     
  6.     public static void main(String[] args) {
  7.  
  8.         System.out.println("骑士周游算法，开始运行~~");
  9.         //测试骑士周游算法是否正确
  10.         x = 6;
  11.         y = 6;
  12.         int row = 4; //马儿初始位置的行，从1开始编号
  13.         int column = 3; //马儿初始位置的列，从1开始编号
  14.  
  15.         //创建棋盘
  16.         int[][] chessboard = new int[x][y];
  17.         visited = new boolean[x * y];//初始值都是false
  18.  
  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.         for(int[] rows : chessboard) {
  26.             for(int step: rows) {
  27.                 System.out.print(step + "\t");
  28.             }
  29.             System.out.println();
  30.         }
  31.     }
  32. }
  33.  
  34. 运行结果如下：
  35. 骑士周游算法，开始运行~~
  36. 共耗时: 40 毫秒
  37. 08    03    10    29    32    05    
  38. 17    28    07    04    11    30    
  39. 02    09    18    31    06    33    
  40. 27    16    01    20    23    12    
  41. 36    19    14    25    34    21    
  42. 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

目的：使马儿走的下一步是下一步集合中可选性最少的，减少回溯可能性

  1. public class HorseChessboard {
  2.     
  3.     //省略其他关键性代码....
  4.     
  5.     //根据当前这个一步的所有的下一步的选择位置，进行非递减排序, 减少回溯的次数
  6.     public static void sort(ArrayList<Point> ps) {
  7.         ps.sort(new Comparator<Point>() {
  8.  
  9.             @Override
  10.             public int compare(Point o1, Point o2) {
  11.                 // TODO Auto-generated method stub
  12.                 //获取到o1的下一步的所有位置个数
  13.                 int count1 = next(o1).size();
  14.                 //获取到o2的下一步的所有位置个数
  15.                 int count2 = next(o2).size();
  16.                 if(count1 < count2) {
  17.                     return -1;
  18.                 } else if (count1 == count2) {
  19.                     return 0;
  20.                 } else {
  21.                     return 1;
  22.                 }
  23.             }
  24.             
  25.         });
  26.     }
  27. }

那么怎么使用呢，我们在算法里进行排序优化

  1. public class HorseChessboard {
  2.     
  3.     //省略其他关键性代码....
  4.     
  5.     
  6.     /**
  7.      * 完成骑士周游问题的算法
  8.      * @param chessboard 棋盘
  9.      * @param row 马儿当前的位置的行 从0开始
  10.      * @param column 马儿当前的位置的列  从0开始
  11.      * @param step 是第几步 ,初始位置就是第1步
  12.      */
  13.     public static void traversalChessboard(int[][] chessboard, int row, int column, int step) {
  14.  
  15.         //标记当前棋盘执行的是第几步
  16.         chessboard[row][column] = step;
  17.  
  18.         //row = 3 X = 6 column = 3 = 3 * 6 + 3 = 21 -1 = 20
  19.         visited[row * x + column] = true; //标记该位置已经访问
  20.  
  21.         //获取当前位置可以走的下一个位置的集合
  22.         ArrayList<Point> ps = next(new Point(column, row));
  23.         
  24.         //对ps进行排序,排序的规则就是对ps的所有的Point对象的下一步的位置的数目，进行非递减排序
  25.         sort(ps);
  26.  
  27.         //遍历 ps
  28.         while(!ps.isEmpty()) {
  29.             Point p = ps.remove(0);//取出下一个可以走的位置
  30.             //判断该点是否已经访问过
  31.             if(!visited[p.y * X + p.x]) {//说明还没有访问过
  32.                 traversalChessboard(chessboard, p.y, p.x, step + 1);
  33.             }
  34.         }
  35.     }
  36. }
  1. public class HorseChessboard {
  2.     
  3.     //省略其他关键性代码....
  4.     
  5.     
  6.     public static void main(String[] args) {
  7.  
  8.         System.out.println("骑士周游算法，开始运行~~");
  9.         //测试骑士周游算法是否正确
  10.         x = 6;
  11.         y = 6;
  12.         int row = 4; //马儿初始位置的行，从1开始编号
  13.         int column = 3; //马儿初始位置的列，从1开始编号
  14.  
  15.         //创建棋盘
  16.         int[][] chessboard = new int[x][y];
  17.         visited = new boolean[x * y];//初始值都是false
  18.  
  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.         for(int[] rows : chessboard) {
  26.             for(int step: rows) {
  27.                 System.out.print(step + "t");
  28.             }
  29.             System.out.println();
  30.         }
  31.     }
  32. }
  33.  
  34. 运行结果如下：
  35. 骑士周游算法，开始运行~~
  36. 共耗时: 9 毫秒
  37. 08    03    10    29    32    05    
  38. 17    28    07    04    11    30    
  39. 02    09    18    31    06    33    
  40. 27    16    01    20    23    12    
  41. 36    19    14    25    34    21    
  42. 15    26    35    22    13    24

从40毫秒 到9毫秒 这个速度还是很客观的，相比之前的算法更优一些

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/AllinToyou/article/detail/573639
推荐阅读
相关标签

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

  

闽ICP备14008679号