代码随想录算法训练营第六十天 | 图 | A星算法

Day 60 总结

• 自己实现中遇到哪些困难
• 今日收获，记录一下自己的学习时间
  • 13:00 - 14:00

BFS

题目：127. 骑士的攻击

给定两个坐标，搜索最短路径

使用 BFS，广度搜索，按层搜索找到最短路径

public class Main {
    public static void main(String[] args) {
        new Main().solve();
    }

    public void solve() {
        Scanner sc = null;
        try {
             sc = new Scanner(new File("1.txt"));
        } catch (FileNotFoundException e) {
            e.printStackTrace();
        }

        int n = sc.nextInt();
        for (int i=0; i<n; i++) {
            int a1 = sc.nextInt();
            int a2 = sc.nextInt();
            int b1 = sc.nextInt();
            int b2 = sc.nextInt();
            bfs(a1,a2,b1,b2);
        }

    }

    public void bfs(int a1, int a2, int b1, int b2) {
        int[][] dir = {{-2,-1}, {-2,1}, {-1,2}, {1,2}, {2,1}, {2,-1}, {1,-2}, 
        {-1,-2},};

        Queue<int[]> queue = new LinkedList<>();
        queue.add(new int[]{a1,a2});
        int[][] moves = new int[1001][1001];// 1000 * 1000的棋盘

        while (!queue.isEmpty()) {
            int[] pos = queue.poll();
            int x = pos[0];
            int y = pos[1];
            if (x == b1 && y == b2) break;

            for (int i=0; i<8; i++) {
                int xx = x+dir[i][0];
                int yy = y+dir[i][1];
                if (xx >= 1 && xx <= 1000 && yy >= 1 && yy <= 1000 && moves[xx][yy]==0) {
                    queue.add(new int[]{xx, yy});
                    moves[xx][yy] = moves[x][y] + 1;
                }
            }
        }
        System.out.println(moves[b1][b2]);
    }
}

AStart

同样是BFS，但是有一些额外的信息

BFS 是没有目的性的 一圈一圈去搜索， 而 A * 是有方向性的去搜索

启发式函数 要影响的就是队列里元素的排序，去引导搜索方向

队列里节点进行排序，就需要给每一个节点权值

每个节点的权值为F，给出公式为：F = G + H

G：起点达到目前遍历节点的距离

H：目前遍历的节点到达终点的距离

距离计算公式

本题的图是无权网格状，在计算两点距离通常有如下三种计算方式：

1. 曼哈顿距离，计算方式： d = abs(x1-x2)+abs(y1-y2)
2. 欧氏距离（欧拉距离） ，计算方式：d = sqrt( (x1-x2)^2 + (y1-y2)^2 )
3. 切比雪夫距离，计算方式：d = max(abs(x1 - x2), abs(y1 - y2))

本题，采用欧拉距离才能最大程度体现 点与点之间的距离。

所以 使用欧拉距离计算 和 广搜搜出来的最短路的节点数是一样的。 （路径可能不同，但路径上的节点数是相同的）

A * 算法的寻路过程，动画地址：https://kamacoder.com/tools/knight.html

通过优先级队列选择节点

@FunctionalInterface
interface Heuristic {
    int apply(int a1, int a2, int b1, int b2);
}


public class Main {
    public static void main(String[] args) {
        new Main().solve();
    }

    public void solve() {
        Scanner sc = null;
        try {
             sc = new Scanner(new File("1.txt"));
        } catch (FileNotFoundException e) {
            e.printStackTrace();
        }

        int n = sc.nextInt();
        for (int i=0; i<n; i++) {
            int a1 = sc.nextInt();
            int a2 = sc.nextInt();
            int b1 = sc.nextInt();
            int b2 = sc.nextInt();
            Heuristic myHeuristic = 
                   (x1,y1,x2,y2) -> {return (x1-x2) * (x1-x2) + (y1-y2) * (y1-y2);};
            AStar(a1,a2,b1,b2, myHeuristic);
        }

    }

    public void AStar(int a1, int a2, int b1, int b2, Heuristic heuristic) {

        int[][] dir = {{-2,-1}, {-2,1}, {-1,2}, {1,2}, {2,1}, {2,-1}, {1,-2}, 
        {-1,-2},};

        PriorityQueue<int[]> queue = new PriorityQueue<int[]>(
                (a, b) -> {return Integer.compare(a[2], b[2]);});
        queue.add(new int[]{a1,a2,0});
        int[][] moves = new int[1001][1001];// 1000 * 1000的棋盘

        while (!queue.isEmpty()) {
            int[] pos = queue.poll();
            int x = pos[0];
            int y = pos[1];
            int f = pos[2];
            if (x == b1 && y == b2) break;

            for (int i=0; i<8; i++) {
                int xx = x+dir[i][0];
                int yy = y+dir[i][1];
                if (xx >= 1 && xx <= 1000 && yy >= 1 && yy <= 1000 && moves[xx][yy]==0) {
                    // 这里的g的计算为什么是这样子的啊？
                        // 起点达到目前遍历节点的距离
                    int g1 = heuristic.apply(a1, a2, xx, yy);
                    int g = f + 5;

                    int h = heuristic.apply(xx, yy, b1, b2);
                    int ff = g + h;

                    queue.add(new int[]{xx, yy, ff});
                    moves[xx][yy] = moves[x][y] + 1;
                }
            }

        }
        System.out.println(moves[b1][b2]);
    }

}