A*搜索

A*算法是对Dijkstra算法的优化和改造。属于一种启发式搜索算法。

常见的启发式搜索算法：IDA*算法、蚁群算法、遗传算法、模拟退火算法。

启发式搜索算法利用估价函数，避免“跑偏”，贪心的朝着最有可能到达终点的方向前进。这种算法找出的路线，并不是最短路线。但是能很好的平衡路线质量和执行效率。

算法解析

Dijkstra算法类似BFS算法，每次找到跟起点最近的顶点，往外扩展，有些盲目（离起点最近的点可能离终点最远）。
在Dijkstra算法的实现思路中，用一个优先级队列，来记录已经遍历到的顶点以及这个顶点与起点的路径长度。顶点与起点路径长度越小，就越先被从优先级队列中取出来扩展。尽管找到是从s到t的路线，但是最先被搜索的路线可能是与期望路线的反方向。

按照顶点与起点的路径长度的大小，来安排出队列顺序，与起点越近的顶点，就会越早出队列。并没有考虑到这个顶点到终点的距离，所以尽管顶点离起始顶点最近，但离终点却越来越远。

当遍历到某个顶点的时候，从起点走到这个顶点的路径长度是确定的，记作g(i)(i表示顶点编号)。
这个顶点跟终点之间的直线距离-欧几里得距离，可以近似的估计顶点跟 终点的路径长度，记作h(i)(i表示顶点编号)—启发函数。更进一步使用两点之间横纵坐标的距离之和-曼哈顿距离来简化。

原来只是单纯的通过顶点与起点之间的路径长度g(i)，来判断谁先出队列；现在加上顶点到终点的路径长度估计值，通过两者之和f(i)=g(i)+h(i)—估价函数。综合两部分，能有效避免跑偏。

代码实现

在A*算法的代码实现中，顶点Vertex类的定义，跟Dijkstra算法中的定义相比，多了x,y坐标，以及估价函数f(i)的值。图Graph类的定义跟Dijkstra算法中的定义一样。

有向有权图

public class Graph {
    private LinkedList<Edge> adj[];//邻接表
    private int v;//顶点个数

    publicGraph(int v) {
        this.v = v;
        this.adj = new LinkedList[v];//v个链表
        for(int i = 0; i < v; ++i) {
            this.adj[i] = new LinkedList<>();//每个编号的顶点都存了一个链表
        }
    }

    //添加一条边
    public void addEdge(int s, int t, int w) {
        this.add[s].add(new Edge(s,t,w));
    }

    private class Edge {
        public int sid;//边的起始顶点编号
        public int tid;//边的终止顶点编号
        public int w;//权重
        public Edge(int sid, int tid, int w) {
            this.sid = sid;
            this.tid = sid;
            this.w = w;
        }
    }

    //
    private class Vertex {
        public int id;//顶点编号ID
        public int dist;//从起始顶点到这个顶点的距离
        public int f;//f(i)=g(i)+h(i)
        public intx,y;//顶点在地图中的坐标
        public Vertex(int id, int x, int y) {
            this.id = id;
            this.x = x;
            this.y = y;
            this.f = Integer.MAX_VALUE;
            this.dist = Integer.MAX_VALUE;
        }
    }

    //Graph类的成员变量，在构造函数中初始化
    Vertex[] vertexes = new Vertex[this.v];
    //添加顶点的坐标
    public void addVertex(int id, int x, int y) {
        vertexes[id] = new Vertex(id,x,y);
    }
}

A*算法与Dijkstra算法的区别：

• 优先级队列的构建方式不同。A*算法是根据f值(f(i)=g(i)+h(i))来构建优先级队列，而Dijkstra算法是根据dist值(g(i))来构建优先级队列。
• A*算法在更新顶点dist值的时候，会同步更新f值。
• 循环结束的条件不一样。Dijkstra算法是在终点出队列的时候才结束，A*算法是一旦遍历到终点就结束。

A*算法

//从顶点s到顶点t的路径
public void astar(int s, int t) {
    //还原路径
    int[] predecessor = new int[this.v];
    //按照vertex的f值构建的小顶堆(Dijkstra按照dist)
    PriorityQueue queue = new PriorityQueue(this.v);
    //标记是否进入过队列
    boolean[] inqueue = new boolean[this.v];
    vertexes[s].dist = 0;
    vertexes[s].f = 0;
    queue.add(vertexes[s]);
    inqueue[s] = true;
    while(!queue.isEmpty()) {
        //取堆顶元素并删除
        Vertex minVertex = queue.poll();
        for(int i = 0; i < adj[minVertex.id].size(); ++i) {
            //取出一条minVertex相连的边
            Edge e = adj[minVertex.id].get(i);
            //minVertex --> nextVertex
            Vertex nextVertex = vertexes[e.tid];
            if(minVertex.dist + e.w < nextVertex.dist) {
                //更新next的dist,f
                nextVertex.dist = minVertex.dist + e.w;
                nextVertex.f = nextVertex.dist + hManhattan(nextVertex, vertexes[t]);
                predecessor[nextVertex.id] = minVertex.id;
                if(inqueue[nextVertex.id] == true) {
                    queue.update(nextVertex);
                } else {
                    queue.add(nextVertex);
                    inqueue[nextVertex.id] = true;
                }
            }
            //只要到达t就可以结束while
            if(nextVertex.id == t) {
                //清空queue，才能推出while循环
                queue.clear();
                break;
            }
        }
    }
    //输出路径
    System.out.print(s);
    print(s,t,predecessor);
}

private void print(int s, int t, int[] predecessor) {
    if(s == t) return;
    print(s, predecessor[t], predecessor);
    System.out.print("->" + t);
}

对比分析

A*算法可以更加快速的找到从起点到终点的路线，但是它并不能像Dijkstra算法那样，找到最短路线。

回溯穷举所有从s到达t的不同路径，然后对比找出最短的那个。

Dijkstra算法在回溯的基础上，利用动态规划的思想，堆回溯搜索进行了剪枝，只保留起点到某个顶点的最短路径，继续往外扩展搜索。动态规划相较于回溯搜索，只是换了一个实现思路，实际上也考察了所有从起点到终点的路线，得到的最优解。

Dijkstra算法是在终点出队列的时候才结束，A*算法是一旦遍历到终点就结束。对于Dijkstra算法来说，当终点出队列的时候，终点的dist值是优先级队列中所有顶点的最小值，即使再运行下去，终点的dist值也不会再被更新了。对于A*算法来说，一旦遍历到终点，就结束while循环，这个时候，终点的dist值未必是最小值。
A*算法利用贪心算法的思路，每次都找f值最小的顶点出队列，一旦搜索到终点就不在继续考察其他顶点和路线了。它并没有考察所有的路线，也就不可能找到最短路径。

游戏寻路问题，把地图抽象成图，把岔路口抽象成顶点，把道路抽象成边。

把地图分割成一个个的小方块。在某一个方块上的人物，只能往上下左右四个方向的方块上移动。把每个方块看做一个顶点。两个方块相邻，就在他们之间连两条有向边，并且边的权值都是1。

将问题转化成，在一个有向有权图中，找某一个顶点到另一个顶点的路径问题，将地图抽象成边权值为1的有向图之后，套用A*算法解决人物自动寻路功能。