本文介绍: 1.马踏棋盘问题(骑士周游问题)实际上是图的深度优先搜索(DFS)的应用。2.如果使用回溯(就是深度优先搜索)来解决假如马儿踏了53个点,如图:走到了第53个,坐标(1,0),发现已经走到尽头,没办法,那就只能回退了,查看其他的路径,就在棋盘上不停的….. ,思路分析+代码实现3.先用基本方式解决然后使用贪心算法(greedyalgorithm) 进行优化解决马踏棋盘问题,体会到不同算法程序效率影响4.使用前面游戏验证算法是否正确

一、意义

1.算法是程序的灵魂,为什么有些程序可以海量数据计算时,依然保持高速计算?

2.拿老韩实际工作经历来说,在Unix开发服务器程序功能是要支持上千万人同时在线,在上线前, 做内测,一切OK,可上线后,服务器就支撑不住了,公司的CTO对代码进行优化,再次上线,坚如磐石。那一瞬间,你就能感受到程序是有灵魂的,就是算法

3.编程算法很多,比如八大排序算法(冒泡选择插入、快排、归并希尔、基数、堆排序查找算法、分治算法、动态规划算法、KMP算法、贪心算法、普里姆算法、克鲁斯卡尔算法、迪杰斯特拉算法、弗洛伊德算法

4.老韩以骑士周游问题为例,让小伙伴体验用算法去优化程序的意义,让大家直观的感受到算法的威力

二、经典算法问题 – 骑士周游问题

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

2.将马随机放在国际象棋的8x 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

注意:马儿走的策略不同,则得到的结果也不一样,效率也不一样.

多想想 很巧妙的思路

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) + "ms");
        for(int[] rows : chessBoard){
            for (int step : rows){ //step表示该位置是马儿走的第几步
                System.out.print(step + "t");
            }
            System.out.println();
        }
    }
    //编写核心算法 遍历棋盘 如果遍历成功 就把finished设置true;
    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
        //遍历
        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 &amp;&amp; !finished){
            //重置
            chessBoard[row][col] = 0;
            visited[row * X + col] = false;
        }else{
            finished = true;
        }

    }

    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 &amp;&amp; (p1.y = curPoint.y - 1) >=0){
            ps.add(new Point(p1));//避免一个点重复放
        }
        //判断是否可以走6位置
        if((p1.x = curPoint.x - 1) >= 0 &amp;&amp; (p1.y = curPoint.y - 2) >=0){
            ps.add(new Point(p1));//避免一个点重复放
        }
        //判断是否可以走7位置
        if((p1.x = curPoint.x + 1) < X &amp;&amp; (p1.y = curPoint.y - 2) >= 0){
            ps.add(new Point(p1));//避免一个点重复放
        }
        //判断是否可以走0位置
        if((p1.x = curPoint.x + 2) < X &amp;&amp; (p1.y = curPoint.y - 1) >=0){
            ps.add(new Point(p1));//避免一个点重复放
        }
        //判断是否可以走1位置
        if((p1.x = curPoint.x + 2) < X &amp;&amp; (p1.y = curPoint.y + 1) < Y){
            ps.add(new Point(p1));//避免一个点重复放
        }
        //判断是否可以走2位置
        if((p1.x = curPoint.x + 1) < X &amp;&amp; (p1.y = curPoint.y + 2) < Y){
            ps.add(new Point(p1));//避免一个点重复放
        }
        //判断是否可以走3位置
        if((p1.x = curPoint.x - 1) >= 0 &amp;&amp; (p1.y = curPoint.y + 2) < Y){
            ps.add(new Point(p1));//避免一个点重复放
        }
        //判断是否可以走4位置
        if((p1.x = curPoint.x - 2) >= 0 && (p1.y = curPoint.y + 1) < Y){
            ps.add(new Point(p1));//避免一个点重复放
        }
        return ps;
    }
}

 

代码使用贪心算法,进行优化,提高速度

分析
1.我们现在走的下一个位置,是按照我们的顺时针挑选位置,因此选择这个点的下-一个可以走的位置的个数是不确定的.

2.优化思路是:我们应该选择下一个的下一个可以走的位置较少的点,开始走,这样可以减少回溯的此时

3.代码:对我们的ps集合按照可以走的下一个位置的次数进行排序升序排序.

//写一个方法,对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();
            }
        });
    }

仅仅只是对该存放的可能点进行最小可能点排序 

原文地址:https://blog.csdn.net/qq_41891655/article/details/134693648

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任

如若转载,请注明出处:http://www.7code.cn/show_35420.html

如若内容造成侵权/违法违规/事实不符,请联系代码007邮箱suwngjj01@126.com进行投诉反馈,一经查实,立即删除

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注