资讯专栏INFORMATION COLUMN

【程序员必会十大算法】之骑士周游问题

Baoyuan / 1049人阅读

摘要:骑士周游问题又叫马踏棋盘问题未优化前没有策略定义棋盘的行数和列数定义棋盘上的某个点是否被访问过记录是否周游结束从第一行第一列开始走,第一次走算第一步,即展示下是棋盘,

骑士周游问题又叫马踏棋盘问题

1.未优化前(没有策略)

public class Main {    //定义棋盘的行数和列数    static int X = 8;    static int Y = 8;    //定义棋盘上的某个点是否被访问过    static boolean[] isVisited;    //记录是否周游结束    static boolean isFinished = false;    public static void main(String[] args) {        isVisited = new boolean[X * Y];        int[][] chessBoard = new int[X][Y];        //从第一行第一列开始走,第一次走算第一步,即step=1        travelChessboard(chessBoard,0,0,1);        //展示下chessBoard        for (int[] row: chessBoard){            for (int step: row){                System.out.print(step + "     ");            }            System.out.println();        }    }    /**     *     * @param chessBoard 是棋盘,因为递归,所以在不断变化     * @param row 是马所在的行,也就是y值     * @param column 是马所在的列,也就是x值     * @param step 马走到的第几步     */    public static void travelChessboard(int[][] chessBoard,int row,int column,int step){        //假定这一点是可以走的,所以设置已访问,步数也得加上        chessBoard[row][column] = step;//假定可以走,所以先走过去看看,设置走过去的步数        isVisited[row * X + column] = true;//假定可以走,所以先走过去看看,设置成已访问        //得到下一步可以走的点的集合        ArrayList<Point> nextPoints = getNext(new Point(column, row));        while (!nextPoints.isEmpty()){            //首先取出一个来            Point nextPoint = nextPoints.remove(0);            //如果这个点没有被访问过            if (!isVisited[nextPoint.y * X + nextPoint.x]){                travelChessboard(chessBoard,nextPoint.y,nextPoint.x,step + 1);//这里我一开始写了step++  其实应该是step+1            }        }        //如果假定失败,其实这个点是不可以走的,那么我们就进行回溯!!!        if (step < X * Y && !isFinished){            chessBoard[row][column] = 0;            isVisited[row * X + column] = false;        }else {            isFinished = true;        }    }    /**     * 传入当前点,得到能走的下一个点的集合     * @param curPoint     * @return     */    public static ArrayList<Point> getNext(Point curPoint){        //创建结果集        ArrayList<Point> nextPoints = new ArrayList<>();        Point nextPoint = new Point();        //可以走0        if ((nextPoint.x = curPoint.x + 2) < X && (nextPoint.y = curPoint.y - 1) >= 0){            nextPoints.add(new Point(nextPoint));        }        //表示马可以走1        if ((nextPoint.x = curPoint.x + 2) < X && (nextPoint.y = curPoint.y + 1) < Y){            nextPoints.add(new Point(nextPoint));        }        //可以走2        if ((nextPoint.x = curPoint.x + 1) < X && (nextPoint.y = curPoint.y + 2) < Y){            nextPoints.add(new Point(nextPoint));        }        //可以走3        if ((nextPoint.x = curPoint.x - 1) >= 0 && (nextPoint.y = curPoint.y + 2) < Y){            nextPoints.add(new Point(nextPoint));        }        //可以走4        if ((nextPoint.x = curPoint.x - 2) >= 0 && (nextPoint.y = curPoint.y + 1) < Y){            nextPoints.add(new Point(nextPoint));        }        //可以走5        if ((nextPoint.x = curPoint.x - 2) >= 0 && (nextPoint.y = curPoint.y - 1) >= 0){            nextPoints.add(new Point(nextPoint));        }        //可以走6        if ((nextPoint.x = curPoint.x - 1) >= 0 && (nextPoint.y = curPoint.y - 2) >= 0){            nextPoints.add(new Point(nextPoint));        }        //可以走7        if ((nextPoint.x = curPoint.x + 1) < X && (nextPoint.y = curPoint.y - 2) >= 0){            nextPoints.add(new Point(nextPoint));        }        return nextPoints;    }}

结果略去,等结果时间太长了

2.贪心算法优化后

主要是添加了这个方法
添加了这个方法后,可以减少回溯的次数,极大的提高效率

public static void getNextNext(ArrayList<Point> arrayList){      //重写集合的sort方法,将其按下一步可选点数目由小到大的顺序排列,再准确一点就是非递减排序(因为有相同点)      arrayList.sort(new Comparator<Point>() {          @Override          public int compare(Point o1, Point o2) {              //得到o1的下一步可选点的数目              int count1 = getNext(o1).size();              //得到o2的下一步可选点的数目              int count2 = getNext(o2).size();              if (count1 > count2){                  return -1;              }else if (count1 == count2){                  return 0;              }else {                  return 1;              }          }      });  }

结果

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

文章版权归作者所有,未经允许请勿转载,若此文章存在违规行为,您可以联系管理员删除。

转载请注明本文地址:https://www.ucloud.cn/yun/121665.html

相关文章

  • 序员必会十大算法分治算法(汉诺塔问题

    摘要:应用分治法是一种很重要的算法。字面上的解释是分而治之,就是把一个复杂的问题分成两个或更多的相同或相似的子问题,再把子问题分成更小的子问题直到最后子问题可以简单的直接求解,原问题的解即子问题的解的合并。 ...

    codecraft 评论0 收藏0
  • 序员必会十大算法Prim算法

    摘要:问题胜利乡有个村庄现在需要修路把个村庄连通各个村庄的距离用边线表示权比如距离公里问如何修路保证各个村庄都能连通并且总的修建公路总里程最短代码重点理解中的三层循环 问...

    番茄西红柿 评论0 收藏2637
  • 序员必会十大算法二分查找算法

    摘要:递归实现不考虑相同数二分查找,不考虑有相同数的情况递归找到了考虑有相同数二分查找考虑有相同元素的情况递归要查找的值 1.递归实现 ①不考虑相同数 /** * 二分查...

    YFan 评论0 收藏0
  • 序员必会十大算法弗洛伊德算法

    摘要:学习资料迪杰斯特拉计算的是单源最短路径,而弗洛伊德计算的是多源最短路径代码不能设置为,否则两个相加会溢出导致出现负权创建顶点和边 学习资料 迪杰斯特拉计算的是单源最...

    JellyBool 评论0 收藏0
  • 序员必会十大算法贪心算法

    摘要:例题假设存在如下表的需要付费的广播台,以及广播台信号可以覆盖的地区。 例题 假设存在如下表的需要付费的广播台,以及广播台信号可以覆盖的地区。如何选择最少的广播台,让...

    macg0406 评论0 收藏0

发表评论

0条评论

Baoyuan

|高级讲师

TA的文章

阅读更多
最新活动
阅读需要支付1元查看
<