马踏棋盘算法（使用贪心算法优化的前后对比）

快来打我* 2023-07-13 15:27 58阅读 0赞

**马踏棋盘算法介绍**

1.  马踏棋盘算法也被称为骑士周游问题
2.  将马随机放在国际象棋的8×8棋盘Board\[0～7\]\[0～7\]的某个方格中，马按走棋规则(马走日字)进行移动。要求每个方格只进入一次，走遍棋盘上全部64个方格  
    ![在这里插入图片描述][20200313112259422.png]

### 马踏棋盘游戏代码实现分析 ###

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

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Z5ajEzOTI1NDc1OTU3_size_16_color_FFFFFF_t_70]  
代码示例

没有优化前的代码：

/** * 马踏棋盘算法 */
    public class HorseChessboard { 
        // 棋盘
        private int[][] chessbord;
        // 标记对应的位置是否被访问过，总的大小 = 棋盘的 X*Y, 8*8 = 64
        private boolean[] visited;
        // 记录走的部数
        private int step;
        //使用一个属性，标记是否棋盘的所有位置都被访问
        private static boolean finished; // 如果为true,表示成功
    
        public HorseChessboard(int[][] chessbord) { 
            this.chessbord = chessbord;
            visited = new boolean[chessbord.length * chessbord[0].length];
        }
    
        public void show() { 
            System.out.println("走的步数：" + step);
            for (int[] ints : chessbord) { 
                System.out.println(Arrays.toString(ints));
            }
        }
    
        /** * 完成骑士周游问题 * @param rom 骑士开始的走 第几行 * @param column 骑士开始的走 第几列 */
        public void traversalChessboard(int rom, int column, int step) { 
            // 记录该位置被访问
            visited[rom * chessbord[0].length + column] = true;
            // 把棋盘的该位置标记为已经走的步数
            chessbord[rom][column] = step;
            // 获取该位置的下一个可以走的位置集合
            List<Location> nextLocation = nextLocation(new Location(column, rom));
            //如果该集合不为null,则进行递归（深度优先）
            while (!nextLocation.isEmpty()) { 
                Location location = nextLocation.remove(0);
                // 如果该位置没被访问过，这进行递归
                if (!visited[location.y * chessbord[0].length + location.x]) { 
                    traversalChessboard(location.y, location.x, step + 1);
                }
            }
    
            // 代码走到走到这，说明已经没有位置可以走了
            if (step < visited.length && !finished ) { 
                // 如果整个棋盘还没有走完,就把该位置设置为没有走过（进行回溯，返回到上一步）
                chessbord[rom][column] = 0;
                visited[rom * chessbord[0].length + column] = false;
            } else { 
                finished = true;
            }
        }
    
        /** * 内部类，表示棋盘的位置 */
        private static class Location{ 
            // 表示列
            int x;
            // 表示行
            int y;
            public Location(int x, int y) { 
                this.x = x;
                this.y = y;
            }
        }
    
        /** * 表示当前这个位置下一步可以走的位置 * @param location 当前的位置 * @return 返回位置集合 */
        private List<Location> nextLocation(Location location) { 
            List<Location> locationList = new ArrayList<>();
            // 当前位置的行
            int y = location.y;
            // 当前位置的列
            int x =  location.x;
    
            if (x - 2 >= 0 && y - 1 >= 0) { 
                Location location1 = new Location(x - 2, y - 1);
                locationList.add(location1);
            }
            if (x - 1 >= 0 && y - 2 >= 0) { 
                Location location1 = new Location(x - 1, y - 2);
                locationList.add(location1);
            }
            if (x + 1 < chessbord[0].length && y - 2 >= 0) { 
                Location location1 = new Location(x + 1, y - 2);
                locationList.add(location1);
            }
            if (x + 2 < chessbord[0].length && y - 1 >= 0) { 
                Location location1 = new Location(x + 2, y - 1);
                locationList.add(location1);
            }
            if (x + 2 < chessbord[0].length && y + 1 < chessbord.length) { 
                Location location1 = new Location(x + 2, y + 1);
                locationList.add(location1);
            }
            if (x + 1 < chessbord[0].length && y + 2 < chessbord.length) { 
                Location location1 = new Location(x + 1, y + 2);
                locationList.add(location1);
            }
            if (x - 1 >= 0 && y + 2 < chessbord.length) { 
                Location location1 = new Location(x - 1, y + 2);
                locationList.add(location1);
            }
            if (x - 2 >= 0 && y + 1 < chessbord.length) { 
                Location location1 = new Location(x - 2, y + 1);
                locationList.add(location1);
            }
            return locationList;
        }
    }

测试

public class MyTest { 
        public static void main(String[] args) { 
            int[][] chessboard = new int[8][8];
    
            HorseChessboard horseChessboard = new HorseChessboard(chessboard);
            long start = System.currentTimeMillis();
            horseChessboard.traversalChessboard(0,0, 1);
            long end = System.currentTimeMillis();
            System.out.println("花费时间：" + (end - start) + "毫秒");
            horseChessboard.show();
        }
    }

测试结果

花费时间：23567毫秒
    走的步数：0
    [1, 8, 11, 16, 3, 18, 13, 64]
    [10, 27, 2, 7, 12, 15, 4, 19]
    [53, 24, 9, 28, 17, 6, 63, 14]
    [26, 39, 52, 23, 62, 29, 20, 5]
    [43, 54, 25, 38, 51, 22, 33, 30]
    [40, 57, 42, 61, 32, 35, 48, 21]
    [55, 44, 59, 50, 37, 46, 31, 34]
    [58, 41, 56, 45, 60, 49, 36, 47]

我们看运行结果一共花费了23秒，速度还是比较慢的  
我们分析下速度为什么会慢，有没有优化的方法：

1.  速度比较慢是因为每一次走下一步的时候有许多选择，最多的时候有8种走法，下一步的下一步也是有很多种走法。
2.  如果我们的下一步的下一步是选择走法最多的那一种，那么方法递归的次数就会增加很多。
3.  所以我们如果在下一步走的时候选择下一步的下一步走法比较少的那种走法，方法递归的次数就减少，从而达到优化的效果

#### 贪心算法优化 ####

从上面的分析结果可以得出，我们如果没走下一步的时候，选择下一步的下一步走法比较的那个一步，那就就会减少递归次数。代码示例

/** * 马踏棋盘算法 */
    public class HorseChessboard { 
        // 棋盘
        private int[][] chessbord;
        // 标记对应的位置是否被访问过，总的大小 = 棋盘的 X*Y, 8*8 = 64
        private boolean[] visited;
        // 记录走的部数
        private int step;
        //使用一个属性，标记是否棋盘的所有位置都被访问
        private static boolean finished; // 如果为true,表示成功
    
        public HorseChessboard(int[][] chessbord) { 
            this.chessbord = chessbord;
            visited = new boolean[chessbord.length * chessbord[0].length];
        }
    
        public void show() { 
            System.out.println("走的步数：" + step);
            for (int[] ints : chessbord) { 
                System.out.println(Arrays.toString(ints));
            }
        }
    
        //根据当前这个一步的所有的下一步的选择位置，进行非递减排序, 减少回溯的次数
        private void sort(List<Location> locations) { 
            locations.sort(new Comparator<Location>() { 
                @Override
                public int compare(Location o1, Location o2) { 
                    //获取到o1的下一步的所有位置个数
                    int count1 = nextLocation(o1).size();
                    //获取到o2的下一步的所有位置个数
                    int count2 = nextLocation(o2).size();
                    if(count1 < count2) { 
                        return -1;
                    } else if (count1 == count2) { 
                        return 0;
                    } else { 
                        return 1;
                    }
                }
            });
        }
    
        /** * 完成骑士周游问题 * @param rom 骑士开始的走 第几行 * @param column 骑士开始的走 第几列 */
        public void traversalChessboard(int rom, int column, int step) { 
            // 记录该位置被访问
            visited[rom * chessbord[0].length + column] = true;
            // 把棋盘的该位置标记为已经走的步数
            chessbord[rom][column] = step;
            // 获取该位置的下一个可以走的位置集合
            List<Location> nextLocation = nextLocation(new Location(column, rom));
            // 贪心算法优化，排序，按照下一次走法比较小的递增
            sort(nextLocation);
            //如果该集合不为null,则进行递归（深度优先）
            while (!nextLocation.isEmpty()) { 
                Location location = nextLocation.remove(0);
                // 如果该位置没被访问过，这进行递归
                if (!visited[location.y * chessbord[0].length + location.x]) { 
                    traversalChessboard(location.y, location.x, step + 1);
                }
            }
    
            // 代码走到走到这，说明已经没有位置可以走了
            if (step < visited.length && !finished ) { 
                // 如果整个棋盘还没有走完,就把该位置设置为没有走过（进行回溯，返回到上一步）
                chessbord[rom][column] = 0;
                visited[rom * chessbord[0].length + column] = false;
            } else { 
                finished = true;
            }
        }
    
        /** * 内部类，表示棋盘的位置 */
        private static class Location{ 
            // 表示列
            int x;
            // 表示行
            int y;
            public Location(int x, int y) { 
                this.x = x;
                this.y = y;
            }
        }
    
        /** * 表示当前这个位置下一步可以走的位置 * @param location 当前的位置 * @return 返回位置集合 */
        private List<Location> nextLocation(Location location) { 
            List<Location> locationList = new ArrayList<>();
            // 当前位置的行
            int y = location.y;
            // 当前位置的列
            int x =  location.x;
    
            if (x - 2 >= 0 && y - 1 >= 0) { 
                Location location1 = new Location(x - 2, y - 1);
                locationList.add(location1);
            }
            if (x - 1 >= 0 && y - 2 >= 0) { 
                Location location1 = new Location(x - 1, y - 2);
                locationList.add(location1);
            }
            if (x + 1 < chessbord[0].length && y - 2 >= 0) { 
                Location location1 = new Location(x + 1, y - 2);
                locationList.add(location1);
            }
            if (x + 2 < chessbord[0].length && y - 1 >= 0) { 
                Location location1 = new Location(x + 2, y - 1);
                locationList.add(location1);
            }
            if (x + 2 < chessbord[0].length && y + 1 < chessbord.length) { 
                Location location1 = new Location(x + 2, y + 1);
                locationList.add(location1);
            }
            if (x + 1 < chessbord[0].length && y + 2 < chessbord.length) { 
                Location location1 = new Location(x + 1, y + 2);
                locationList.add(location1);
            }
            if (x - 1 >= 0 && y + 2 < chessbord.length) { 
                Location location1 = new Location(x - 1, y + 2);
                locationList.add(location1);
            }
            if (x - 2 >= 0 && y + 1 < chessbord.length) { 
                Location location1 = new Location(x - 2, y + 1);
                locationList.add(location1);
            }
            return locationList;
        }
    }

运行结果：\`

花费时间：33毫秒
    走的步数：0
    [1, 16, 37, 32, 3, 18, 47, 22]
    [38, 31, 2, 17, 48, 21, 4, 19]
    [15, 36, 49, 54, 33, 64, 23, 46]
    [30, 39, 60, 35, 50, 53, 20, 5]
    [61, 14, 55, 52, 63, 34, 45, 24]
    [40, 29, 62, 59, 56, 51, 6, 9]
    [13, 58, 27, 42, 11, 8, 25, 44]
    [28, 41, 12, 57, 26, 43, 10, 7]

从结果可以看出经过贪心算法优化，花费的时间才33毫秒，而没有优化前花了了23秒，可以看出经过算法优化的魅力，大大提高了程序的效率。

贪心算法优化的核心是每次对下一次可以的步数进行从小到大排序  
核心方法如下:

//根据当前这个一步的所有的下一步的选择位置，进行非递减排序, 减少回溯的次数
        private void sort(List<Location> locations) { 
            locations.sort(new Comparator<Location>() { 
                @Override
                public int compare(Location o1, Location o2) { 
                    //获取到o1的下一步的所有位置个数
                    int count1 = nextLocation(o1).size();
                    //获取到o2的下一步的所有位置个数
                    int count2 = nextLocation(o2).size();
                    if(count1 < count2) { 
                        return -1;
                    } else if (count1 == count2) { 
                        return 0;
                    } else { 
                        return 1;
                    }
                }
            });
        }

[20200313112259422.png]: /images/20230529/157f900fd8bd4f9ea915205b7c7c6066.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Z5ajEzOTI1NDc1OTU3_size_16_color_FFFFFF_t_70]: /images/20230529/5db0c5a9eba448f78a55e14ffd7c3cb4.png