Java 用递归和贪心算法解决和优化“骑士周游问题”

1、问题及算法描述

• 问题：在一个 8*8 的棋盘上，马按照“日”字走，给定一个起点，打印出马不重复的走完棋盘64个格子的路径。其实是图的深度优先搜索（DFS）的一个应用。
• 解答：递归 + 回溯 。对于任一步，马能走的下一步最多有8个位置，满足两个条件：
  • 依旧在棋盘内；
  • 没有被访问过；
  • 如果下一步没有可选项，这时候就需要回溯，选择新的下一步。
• 优化：
  • 暴力递归，对于8*8的棋盘，一般需要运行30秒左右才能出来结果；
  • 优化方式：贪心算法优化，对下一步的下一步可选择数目做非递减排序，然后选择走数目最少的一步，减少回溯的次数；

2、Java代码

// 骑士周游棋盘问题

package Algorithm.HorseChess;

import java.awt.*;
import java.util.ArrayList;
import java.util.Comparator;

/**
 * @author bigyang
 * @date 2020/11/09
 */
public class HorseChess {
    /**
     * 棋盘的列
     */
    private static int X;
    /**
     * 棋盘的行
     */
    private static int Y;
    /**
     * 标记棋盘各个位置是否被访问过
     */
    private static boolean[] visited;
    /**
     * 标记棋盘所有位置是否都被访问完
     */
    private static boolean finished;

    public static void main(String[] args) {
        // 棋盘的行和列都为8
        X = 8;
        Y = 8;
        // 骑士初始位置行和列都为1
        int row = 1;
        int column = 1;
        // 创建棋盘
        int[][] chessBoard = new int[X][Y];
        // 初始化棋盘所有位置都未被访问
        visited = new boolean[X * Y];

        // 测试一下耗时
        long start = System.currentTimeMillis();
        traversalChessBoard(chessBoard, row - 1, column - 1, 1);
        long end = System.currentTimeMillis();
        System.out.println("共耗时：" + (end - start) + "毫秒");

        // 输出棋盘的最后情况
        System.out.println("骑士的周游路径为：");
        for (int[] rows : chessBoard) {
            for (int step : rows) {
                System.out.print(step + "\t");
            }
            System.out.println();
        }
    }

    /**
     * 骑士周游棋盘算法
     *
     * @param chessBoard 棋盘
     * @param row        骑士当前位置的行，从0开始
     * @param column     骑士当前位置的列，从0开始
     * @param step       第几步，初始位置是第1步
     */
    public static void traversalChessBoard(int[][] chessBoard, int row, int column, int step) {
        // 标记棋盘对应的位置为行走的第几步
        chessBoard[row][column] = step;
        // 标记棋盘对应位置已被访问过
        visited[row * X + column] = true;
        // 获取下一步可走位置的集合
        ArrayList<Point> ps = next(new Point(column, row));
        // 贪心算法优化：对ps排序，排序依据为：ps的下一步可选择数目，做非递减排序
        sort(ps);

        // 遍历ps
        while (!ps.isEmpty()) {
            // 取出下一个可走的位置
            Point p = ps.remove(0);
            // 判断该点是否已经访问过
            if (!visited[p.y * X + p.x]) {
                // 递归
                traversalChessBoard(chessBoard, p.y, p.x, step + 1);
            }
        }

        // 判断马儿是否完成任务
        if (step < X * Y && !finished) {
            // 如果没有完成，将整个棋盘置为0
            chessBoard[row][column] = 0;
            visited[row * X + column] = false;
        } else {
            finished = true;
        }
    }

    /**
     * 根据当前位置（Point对象），计算骑士还能走哪些位置（Point），并放入到ArrayList集合中，最多有8个位置
     *
     * @param curPoint 当前位置
     * @return 下一步还能走的位置集合
     */
    public static ArrayList<Point> next(Point curPoint) {
        // Java的Point类，可表示坐标中的点
        ArrayList<Point> ps = new ArrayList<>();
        // 创建点对象
        Point p1 = new Point();

        // 判断骑士能不能走5这个位置
        p1.x = curPoint.x - 2;
        p1.y = curPoint.y - 1;
        if (p1.x >= 0 && p1.y >= 0) {
            ps.add(new Point(p1));
        }

        // 判断骑士能不能走6这个位置
        p1.x = curPoint.x - 1;
        p1.y = curPoint.y - 2;
        if (p1.x >= 0 && p1.y >= 0) {
            ps.add(new Point(p1));
        }

        // 判断骑士能不能走7这个位置
        p1.x = curPoint.x + 1;
        p1.y = curPoint.y - 2;
        if (p1.x < X && p1.y >= 0) {
            ps.add(new Point(p1));
        }

        // 判断骑士能不能走0这个位置
        p1.x = curPoint.x + 2;
        p1.y = curPoint.y - 1;
        if (p1.x < X && p1.y >= 0) {
            ps.add(new Point(p1));
        }

        // 判断骑士能不能走1这个位置
        p1.x = curPoint.x + 2;
        p1.y = curPoint.y + 1;
        if (p1.x < X && p1.y < Y) {
            ps.add(new Point(p1));
        }

        // 判断骑士能不能走2这个位置
        p1.x = curPoint.x + 1;
        p1.y = curPoint.y + 2;
        if (p1.x < X && p1.y < Y) {
            ps.add(new Point(p1));
        }

        // 判断骑士能不能走3这个位置
        p1.x = curPoint.x - 1;
        p1.y = curPoint.y + 2;
        if (p1.x >= 0 && p1.y < Y) {
            ps.add(new Point(p1));
        }

        // 判断骑士能不能走4这个位置
        p1.x = curPoint.x - 2;
        p1.y = curPoint.y + 1;
        if (p1.x >= 0 && p1.y < Y) {
            ps.add(new Point(p1));
        }

        return ps;
    }

    /**
     * 对当前这一步的所有的下一步的可选择位置，做非递减排序，每次都选择下一步的可走下一步最少的位置，减少回溯的次数
     * 1,2,3,4,5,.        :递增排列
     * 9,8,7,6,5,.        :递减排列
     * 1,2,3,3,4,5,8,8,.  :非递减排列
     * 9,8,7,7,6,5,5,2,1,.:非递增排列
     */
    public static void sort(ArrayList<Point> ps) {
        ps.sort(new Comparator<Point>() {
            @Override
            public int compare(Point o1, Point o2) {
                // 获取o1和o2的下一步的所有位置个数
                int count1 = next(o1).size();
                int count2 = next(o2).size();

                if (count1 < count2) {
                    return -1;
                } else if (count1 == count2) {
                    return 0;
                } else {
                    return 1;
                }
            }
        });
    }
}

3、运行结果

共耗时：19毫秒
骑士的周游路径为：
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	

进程已结束,退出代码0

 

本文地址：https://blog.csdn.net/yhxxhy978/article/details/109578587