图5：A*算法
我们并非每次都需要一个最优解。对于路径搜索来说，假设我们打游戏每设置一个目标位置就遍历全部的边，那么在需要频繁寻路的游戏中，效率就会很低。在权衡路线规划质量和执行效率的情况下，我们只需要寻求一个次优解就足够了。这时候就需要启发式搜索算法来实现了。
启发式搜索(Heuristically Search)又称为有信息搜索(Informed Search)，它是利用问题拥有的启发信息来引导搜索，达到减少搜索范围、降低问题复杂度的目的，这种利用启发信息的搜索过程称为启发式搜索。
启发式搜索算法（Heuristically Search Algorithm）利用估价函数，避免“跑偏”，贪心地朝着最有可能到达终点的方向前进。这种算法找出的路线，并不是最短路线。但是，实际的软件开发中的路线规划问题，我们往往并不需要非得找最短路线。所以，鉴于启发式搜索算法能很好地平衡路线质量和执行效率，它在实际的软件开发中的应用更加广泛。
启发式搜索算法有很多，比如 IDA 算法、蚁群算法、遗传算法、模拟退火算法等。这里我们实现A 算法来就行寻路。
估价函数与启发函数
估价函数
Dijkstra使用当前节点与起始节点的距离作为决定搜索的先后顺序，而启发式搜索通过估价函数来决定搜索顺序。估价函数（f(n)）通常是启发函数（h(n)）所得估计代价与已知代价（g(n)）的组合，即：
f(n) = h(n) + g(n)在Dijkstra算法中，h(n)等于0，g(n)等于当前顶点n到起始顶点的距离dist
启发函数
启发函数用来预测未来代价（估计代价）。这是一个从当前状态到目标状态（目标顶点）还需要多少代价的估计，而已知代价是起始顶点到当前顶点的实际长度（实际代价）。我们组合这两个变量期望我们的寻路策略不会偏离目标顶点。
启发函数通常是启发式搜索的核心。
A*
A* 算法使用欧几里得距离曼哈顿距离作为启发函数，启发函数+实际距离作为估价函数来实现。
假设我们知道每个顶点的平面直角坐标系的坐标（或者经纬度），顶点A的坐标是(x1,y1)，顶点B的坐标是(x2,y2)，则他们的欧几里得距离和曼哈顿距离的计算如下：
lAB(欧) = √((x1-x2)^2 + (y1-y2)^2)
lAB(曼) = |x1-x2| + |y1-y2|那么估价函数如下：
hi = |x1-xt| + |yi-yt|
f(i) = dist + h(i)由于我们不再需要寻找最短路径，所以一旦我们遇到目标顶点就可以结束搜索了。
实现使用到了[[图1：图的表示与存储]]中邻接矩阵的实现和[[堆1：堆与堆排序]]中堆的实现。
package cn.lishiyuan.algorithm.graph;
import cn.lishiyuan.algorithm.heap.Heap;
import cn.lishiyuan.algorithm.stack.LeeStack;
import cn.lishiyuan.algorithm.stack.LinkedStack;
import java.util.*;
/**
* 邻接矩阵
*
*/public class AdjacencyMatrix<V> implements Graph<V>,TopoSort<V> {
/**
* 顶点,可以使用 Map 存储元素与index的关系
*/
private V[] vertices;
/**
* 边
*/
private int[][] edges;
private GraphType type;
public static class Node implements Comparable<Node>{
public Object v;
public int x,y;// 坐标
public int h; // 启发函数所得估计代价
public int dist; // 实际代价
@Override
public int compareTo(Node o) {
return (h+dist) - (o.h + o.dist);
}
@Override
public boolean equals(Object obj) {
boolean eq= super.equals(obj);
if(!eq && obj instanceof Node){
eq = v.equals(((Node) obj).v);
}
return eq;
}
}
@Override
public List<V> path(V from, V to) {
if(!(to instanceof Node toNode)){
return Collections.emptyList();
}
if(!(from instanceof Node fromNode)){
return Collections.emptyList();
}
// A*算法实现
int i = indexOfVertex(from);
int j = indexOfVertex(to);
if ( i==-1 || j==-1){
return Collections.emptyList();
}
// 当前节点到起始节点估价行数所得
Map<Node,Integer> distance = new HashMap<>();
// 当前节点的上个节点
Map<Node,Node> before = new HashMap<>();
// 当前节点是否在队列中
List<Node> inHeap = new ArrayList<>();
// 小顶堆
Heap<Node> heap = new Heap<>(Heap.HeapType.MIN,vertices.length);
fromNode.dist = 0;
fromNode.h = h(fromNode,toNode);
inHeap.add(fromNode);
heap.add(fromNode);
// 为空或者已经遇到了目标顶点
while (!heap.isEmpty() && !heap.top().equals(to)) {
Node top = heap.removeTop();
int index = indexOfVertex((V) top);
// 已经取出
inHeap.remove(top);
// 处理相连节点
int[] edge = edges[index];
for (int id = 0; id < edge.length; id++) {
if (edge[id] > 0) {
Node node = ((Node) vertices[id]);
// 上次的估价
Integer dist = distance.get(node);
// 当前距离
int nowDist = edge[id] + top.dist;
// 计算估计代价
int h = h(node,toNode);
node.h = h;
// 估价函数所得代价 = h + dist
// 是否需要堆化
boolean needHeap = false;
if (dist == null){
// 第一次
node.dist = nowDist;
distance.put(node, node.dist + node.h);
before.put(node, top);
needHeap = true;
}else if ((nowDist+h) < dist){
// 已经放入过堆
node.dist = nowDist;
distance.put(node,node.dist + node.h);
before.put(node, top);
needHeap = true;
}
if (needHeap){
if (inHeap.contains(node)) {
// 更新heap
heap.update(node);
}else {
inHeap.add(node);
heap.add(node);
}
}
}
}
}
List<V> path = new ArrayList<>();
// 逆向推断出路径
if(before.containsKey(to)){
path.add(to);
V now = (V)before.get(to);
while (now!=null){
path.add(now);
now = (V)before.get(now);
}
}
return path;
}
@Override
public int distance(V from, V to) {
if(!(to instanceof Node toNode)){
return -1;
}
if(!(from instanceof Node fromNode)){
return -1;
}
// A*算法实现
int i = indexOfVertex(from);
int j = indexOfVertex(to);
if ( i==-1 || j==-1){
return -1;
}
// 当前节点到起始节点估价行数所得
Map<Node,Integer> distance = new HashMap<>();
// 当前节点的上个节点
Map<Node,Node> before = new HashMap<>();
// 当前节点是否在队列中
List<Node> inHeap = new ArrayList<>();
// 小顶堆
Heap<Node> heap = new Heap<>(Heap.HeapType.MIN,vertices.length);
fromNode.dist = 0;
fromNode.h = h(fromNode,toNode);
inHeap.add(fromNode);
heap.add(fromNode);
// 为空或者已经遇到了目标顶点
while (!heap.isEmpty() && !heap.top().equals(to)) {
Node top = heap.removeTop();
int index = indexOfVertex((V) top);
// 已经取出
inHeap.remove(top);
// 处理相连节点
int[] edge = edges[index];
for (int id = 0; id < edge.length; id++) {
if (edge[id] > 0) {
Node node = ((Node) vertices[id]);
// 上次的估价
Integer dist = distance.get(node);
// 当前距离
int nowDist = edge[id] + top.dist;
// 计算估计代价
int h = h(node,toNode);
node.h = h;
// 估价函数所得代价 = h + dist
// 是否需要堆化
boolean needHeap = false;
if (dist == null){
// 第一次
node.dist = nowDist;
distance.put(node, node.dist + node.h);
before.put(node, top);
needHeap = true;
}else if ((nowDist+h) < dist){
// 已经放入过堆
node.dist = nowDist;
distance.put(node,node.dist + node.h);
before.put(node, top);
needHeap = true;
}
if (needHeap){
if (inHeap.contains(node)) {
// 更新heap
heap.update(node);
}else {
inHeap.add(node);
heap.add(node);
}
}
}
}
}
if(distance.containsKey(to)){
return distance.get(to);
}
return -1;
}
/**
* 启发函数
* @param from
* @param to
* @return
*/
private int h(Node from,Node to){
return Math.abs(from.x - to.x) + Math.abs(from.y - to.y);
}
}
注意：类型参数V为 Node的时候才可以使用。
本质上来说A* 算法是对Dijkstra算法的一种改良。通过加入启发函数使得搜索方向得以修正，同时也兼顾到了本身路径的权重。