上面三幅图是采用三种启发式函数计算得到的A*搜索路径

先给出结论：A* 算法 并不是一个明确的最短路算法，A*算法搜的路径如何，完全取决于启发式函数的写法

卡玛网：126骑士的攻击

A*算法是广搜或者迪杰斯特拉算法的改良版。

A*关键在于 启发式函数，也就是影响 广搜 或者 迪杰斯特拉从队列中取元素的优先顺序。

卡码网提供的网站可以清晰看出A*算法与传统BFS算法搜索效果：

https://kamacoder.com/tools/knight.html

启发式函数是根据队列中节点的权值来评判排序，权值计算公式为 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))

x1, x2 为起点坐标，y1, y2 为终点坐标 ，abs 为求绝对值，sqrt 为求开根号，

选择哪一种距离计算方式 也会导致 A * 算法的结果不同。

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

计算出来 F 之后，按照 F 的 大小，来选去出队列的节点。通过引入优先级队列实现的小顶堆，实现排序。

完整代码：

import java.util.*;

public class Main{
    public static int[][] dir = { {1, 2}, {2, 1},
                                {2, -1}, {1, -2},
                                {-2, -1}, {-1, -2},
                                {-2, 1}, {-1, 2}};
    public static int endX;//骑士需要到达的终点横坐标
    public static int endY;//骑士需要到达的终点纵坐标    
    //创建优先级队列实现小顶堆
    public static PriorityQueue<Knight> pq = new PriorityQueue<>(
                new Comparator<Knight>(){
                    @Override
                    public int compare(Knight k1 , Knight k2){
                        return k1.f - k2.f;
                    }
            });
    //构建地图并初始化,默认值都为0，
    //地图grid上点坐标值表示骑士从起点出发到达该节点的最短距离
    public static int[][] grid = new int[1001][1001];

    public static void main (String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        //遍历n名骑士
        for(int i = 0; i < n; i++){
            //骑士入场
            //对该骑士进行初始化
            Knight knight = new Knight();
            knight.x = scanner.nextInt();
            knight.y = scanner.nextInt();
            endX = scanner.nextInt();
            endY = scanner.nextInt();
            knight.g = 0;//初始化骑士当前节点距离起始节点的距离
            knight.h = distance(knight);//初始化骑士当前节点距离终点的距离
            knight.f = knight.g + knight.h;
            pq.add(knight);
            //开始A*算法
            aStar(knight);
            //输出结果
            System.out.println(grid[endX][endY]);
            //上一个骑士已经结束，开始下一位骑士
            //清空队列和地图
            pq.clear();
            for(int[] gd : grid){
                Arrays.fill(gd, 0);
            }
        }
    }

    //A*算法修改的广搜
    public static void aStar(Knight knight){
        while(!pq.isEmpty()){
            Knight curKnight = pq.poll();
            if(curKnight.x == endX && curKnight.y == endY){
                return;
            }
            for(int i = 0; i < 8; i++){
                int nextX = curKnight.x + dir[i][0];
                int nextY = curKnight.y + dir[i][1];
                if(nextX < 1 || nextX >= grid.length || nextY < 1 || nextY >= grid[0].length){
                    continue;
                }
                //如果该链接的点没被访问过
                if(grid[nextX][nextY] == 0){
                    grid[nextX][nextY] = grid[curKnight.x][curKnight.y] + 1;
                    Knight nextKnight = new Knight();
                    nextKnight.x = nextX;
                    nextKnight.y = nextY;
                    //节点所走的8个方向，距离去除根号都是5。
                    //比如说节点(1, 1)距离节点(2, 3)的距离就是5
                    nextKnight.g = curKnight.g + 5;//骑士当前节点距离起始节点的距离
                    nextKnight.h = distance(nextKnight);//骑士当前节点距离终点的距离
                    nextKnight.f = nextKnight.g + nextKnight.h;
                    pq.add(nextKnight);
                }
                
            }
        }
    }

    //启发式函数（欧氏距离）
    private static int distance(Knight knight){
        return (knight.x - endX) * (knight.x - endX) + (knight.y - endY) * (knight.y - endY);
    }  
}

//用于记录骑士的起点以及当前所处的节点坐标上
class Knight{
    //骑士所处的节点坐标
    public int x;
    public int y;
    //g = 起点到该节点的距离
    //h = 该节点到终点的距离
    //f = g + h
    public int f, g, h;
}