最短路径之A*算法 最短路径算法中的最短是指

在求最短路径问题是，如果去除负权边的情况，可以使用Dijkstra算法来替代贝尔曼-福特算法，复杂度更优。接下来介绍的A*算法，也是一种相对更优的算法。看下图：

使用Dijkstra算法来计算AB的最短路径，基本上要把所有的点、边都遍历，才能得到最短路径——绿线。但是站在人类的角度来看，蓝线是不需要考虑的，因为有个成语叫“南辕北辙”，我们非常清楚地知道，按照蓝线走，哪怕走一步，都离目标B远了。所以在搜索路径的时候，完全可以抛弃蓝线。等于是在众多分支中，“剪”去一条——这就是“剪枝”。

那么按照什么标准“剪”，就很重要了，这里引出下一个概念——估价函数。

正如之前所说，我们之所以“剪”去蓝线，就是因为我们“估计”走蓝线会离目的地的“距离”更大。所以我们可以通过估价函数，先“估”出起点到终点的距离，在搜索路径的时候，如果某条路线距离目的地的距离越来越大，则可以“剪”去。

当然，估值对算法的影响很大。估大了，比如100万公里，去趟月球再绕回来都有富余；估小了，比如1米，那连门都出不了了。

在A*算法中，常用的距离估价函数就是之前写的三个，不再赘述。下面着重讲A*算法。

如上图，设尽可上下左右移动，距离估价函数使用曼哈顿距离，边权重统一为10，起点8，终点18，10，16，22为障碍物。

我们要对节点进行松弛操作，也就是将节点的权重降至最小。A*算法相比较贝尔曼-福特算法、Dijkstra算法重要的不同之一就是对权重值的计算，函数如下：

权重值f=起点到节点的移动代价g+节点到终点的预估距离h。

A*算法设置两个集合：open——待处理节点、close——已处理节点。

算法描述：

0、初始化open集合，将起点放入open中，权重为0。
1、遍历open集合
 1.1、如果open为空则说明搜索完成，跳出。
 1.2、不为空，取出权重最小的节点。
  1.2.1、节点是终点，跳出。
  1.2.2、节点非终点。
   1.2.2.1、从open挪入close。
   1.2.2.2、遍历节点的临近节点。
    1.2.2.2.1、临近节点在close中，跳出。
    1.2.2.2.2、临近节点不在open中：
                      计算起点到临近节点的曼哈顿距离g；计算临近节点到终点的曼哈顿距离h；总距离f=g+h；放入open集合中；修改节点的g、h值；记录父节点。
    1.2.2.2.3、临近节点在open中：
                      获取临近节点原g——tmpG；起点经父节点到临近节点的新距离g=(父g+10)；
                      如果tmpG<=g，跳出。
                      如果tmpG>g：临近节点新总距离f=g+原h；放入open集合中；修改临近节点的g值；记录父节点。//这一步就是松弛操作，三个距离f、g、h，使用g作比较，是因为节点到终点的距离H是固定的，G越小，说明起点到节点的距离越小，总距离F就越小。

代码如下：

public void getShortestPath(int start, int end) {
        // 初始化节点的父节点Map
        Map<Integer, Integer> parentMap = Maps.newHashMap();
        // 初始化节点路径
        Table<Integer, Integer, Integer> ppw = this.buildPPW();
        // 初始化节点Map
        Map<Integer, Node> nodeMap = this.buildNodeMap();
        nodeMap.get(start).setG(0);
        nodeMap.get(start).setH(Distance.manhattan(nodeMap.get(start), nodeMap.get(end)).intValue());
        // 初始化open集合，将起点放入，权重F为0
        Map<Integer, Integer> openMap = Maps.newHashMap();
        openMap.put(start, 0);
        Map<Integer, Integer> closeMap = Maps.newHashMap();

        while (!openMap.isEmpty()) {
            // 获取权重值最小的节点
            Map.Entry<Integer, Integer> min = this.getMinPoint(openMap);
            // 最小权重节点是终点，跳出
            if (min.getKey().equals(end)) {
                break;
            }
            // 将最小权重节点从open集合移除，加入close集合
            closeMap.put(min.getKey(), min.getValue());
            openMap.remove(min.getKey());

            // 开始遍历min的临近节点。完全可以采用Map<节点，临近节点List>的数据结构
            for (Map.Entry<Integer, Node> entry : nodeMap.entrySet()) {
                // 节点不相邻
                if (Objects.isNull(ppw.get(min.getKey(), entry.getKey()))) {
                    continue;
                }
                // 临近节点在close集合中
                if (closeMap.containsKey(entry.getKey())) {
                    continue;
                }
                // 临近节点不在open集合中
                if (!openMap.containsKey(entry.getKey())) {
                    // 起点到临近节点的距离
                    int g = Distance.manhattan(nodeMap.get(min.getKey()), nodeMap.get(entry.getKey())).intValue();
                    // 临近节点到终点的距离
                    int h = Distance.manhattan(nodeMap.get(entry.getKey()), nodeMap.get(end)).intValue();
                    // 起点经临近节点到终点的总距离
                    int f = g + h;
                    // 放入open集合
                    openMap.put(entry.getKey(), f);
                    // 更改Node的距离值
                    nodeMap.get(entry.getKey()).setG(g);
                    nodeMap.get(entry.getKey()).setH(h);
                    // 记录父节点
                    parentMap.put(entry.getKey(), min.getKey());
                } else {
                    // 临近节点在open集合中
                    // 获取临近节点的原权重G
                    int tmpG = nodeMap.get(entry.getKey()).getG();
                    // 起点经父节点到临近节点的距离。使用G来作比较，是因为节点到终点的距离H是固定的，G越小，说明起点到节点的距离越小，总距离F就越小
                    int g = nodeMap.get(min.getKey()).getG() + 10;
                    // 新值较小
                    if (tmpG > g) {
                        // 临近节点到终点的距离
                        int h = nodeMap.get(entry.getKey()).getH();
                        // 起点经临近节点到终点的总距离
                        int f = g + h;
                        // 放入open集合
                        openMap.put(entry.getKey(), f);
                        // 更改Node的距离值
                        nodeMap.get(entry.getKey()).setG(g);
                        // 记录父节点
                        parentMap.put(entry.getKey(), min.getKey());
                    }
                }
            }
        }
    }

在代码中，Node就4个属性：坐标x、y；距离h、g——初始值都是Integer.MAX_VALUE。不再赘述。

额外要说的是节点路径集合Table<Integer, Integer, Integer> ppw，这个是我沿用以前的代码，并不优化，大家完全可以构建一个Map<节点,临近节点List>替换。