当前位置: 首页 > 图灵资讯 > 技术篇> 骑士周游问题及优化

骑士周游问题及优化

来源:图灵教育
时间:2023-06-27 15:02:35

文章和代码已归档为[Github仓库:<https://github.com/timerring/java-tutorial> 】或者公众号【AIShareLab】回复 java 也可获取。

骑士周游问题算法优化意义
  1. 算法是程序的灵魂。为什么有些程序在计算海量数据时仍能保持高速计算?
  2. 编程中有许多算法,如八种排序算法(气泡、选择、插入、快速排序、合并、希尔、基数、堆排序)、查找算法、分治算法、动态规划算法、KMP算法、贪婪算法、普里姆算法、克鲁斯卡尔算法、迪杰斯特拉算法、弗洛伊德算法。
经典算法面试题-骑士周游问题马踏棋盘算法介绍
  1. 马踏棋盘算法也被称为骑士周游
  2. 在国际象棋中随机放置马8×8棋盘Board[0 ~7][0~7]在某个方格中,马按照走棋规则(马走日字)移动。每个方格只需进入一次,所有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。

注:马走的策略不同,结果也不同,效率也不同。

使用贪婪算法优化代码,提高速度:

分析

  1. 我们现在的下一个位置是根据我们的顺时针选择位置,所以下一个位置的数量是不确定的.
  2. 优化思路是:我们应该选择下一个位置较少的点,开始行走,以减少可追溯性。
  3. 代码:根据下一个位置的次数对我们的ps集合进行排序,并对其进行升序排序。

package com.hspedu;import javax.swing.*;import java.awt.*;import java.util.ArrayList;import java.util.Comparator;public 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 = 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 (int[] rows : chessBoard) {            for (int step : rows) {//step 表示 这个位置是马应该走的第一步                System.out.print(step + "\t");            }            System.out.println();        }    }    //写一个方法,对ps的每个位置,可以走下一个位置的次数进行排序, 从小到大排序可能的下一个位置    public static void sort(ArrayList<Point> ps) {        ps.sort(new Comparator<Point>() {            @Override            public int compare(Point o1, Point o2) {                return next(o1).size() - next(o2).size();            }        });    }    ///编写核心算法,遍历棋盘,如果遍历成功,就把 finished 设置为true ,    //而且,记录马走的每一步step chessBoard    public static void traversalChessBoard(int[][] chessBoard, int row, int col, int step) {        ///先把step 记录到 chessBoard        chessBoard[row][col] = step;        //把这个位置,设置为已访问        visited[row * X + col] = true;        ///获得当前位置的下一个位置是什么?        ArrayList<Point> ps = next(new Point(col, row)); // 注意这里的处理: col - X , row - Y        sort(ps);// 排名:我们应该选择下一个位置较少的点,开始行走,以减少可追溯性        //遍历        while (!ps.isEmpty()) {            //取出现在的这个 ps 第一个位置(点)            Point p = ps.remove(0);            ///判断这个位置是否通过。如果我们没有通过,我们将把它递归遍历            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;        }    }    //编写方法,所有可以获得当前位置和下一步的位置(Point表示 x,y)    public static ArrayList<Point> next(Point curPoint) {        ///创建ArrayList        ArrayList<Point> ps = new ArrayList<>();        //创建Point对象(点/位置), 准备放入到 ps        Point 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个位置        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;    }}