参考文献：https://www.gamedev.net/reference/articles/article2003.asp
这篇东西写的贼好。

介绍

A*算法主要用于寻路，比如游戏中的自动寻路系统。比其他算法优越的地方就在于他缩小了搜索空间。像迪杰斯特拉弗洛伊德算法这些都只是考虑了到原点的距离，他没有考虑到终点的代价，而且求出了很多不太必要的信息。如果我们仅仅只是求两点的距离，就没有必要用迪杰斯特拉和弗洛伊德了，因为他们把原点到所有点的距离都求了出来。
还有一些其他的算法比如广度和深度搜索，这些算法的都是遍历可能的空间，而深度优先不适用于最短路径的搜索，因为深度优先求出来的路径和代码编写的搜索方向有关系，也就是说深度优先搜索的路径有随机性。所以深度优先如果要做最短路径就只能遍历所有的路径了。广度优先搜索适用于最短路径，但是搜索空间还是很大的，比如如下的场景：

@是起点和终点，#是墙，如果是广度优先，需要把以起点到终点为半径的圆都搜索一遍。

算法细节

和迪杰斯特拉类似，迪杰斯特拉是寻找离原点最近的点，那么我们只需要加上终点代价即可，于是我们定义代价函数F = G + H，G是原点的距离，用勾股定理可以知道斜方向的距离是14，正方向的距离是10，乘10方便计算。H是到达原点的距离，用哈密顿距离即可。
事实上这样的估计只是一种粗略估计，求出来的就算不是最短路径那也和最短路径差不多了。如果存在场景使得哈密顿距离误差很大的话那么求出来的就未必是最短路径了。
需要注意的是，对于终点的计算，方块都是固定的，但是对于G的计算有些特别，讲道理每一方块到原点距离都是一样的，但是如果一直用这样用勾股定理计算，麻烦不说，并且在搜索过程中就没办法调整路径了。
比如，我们要计算路径，自然要保存父节点

代码实现

class node {
private:
    int x, y;
    node *parent;
    double G;
    double H;
    double F;

节点node信息，getset方法不贴了。

    int nRow;
    int nColumn;
    pair<int, int> beginning;
    pair<int, int> ending;
    vector<pair<int, int>> walls;
    vector<string> maps;
    vector<bool> visited_open;
    vector<bool> visited_end;
    //F G node
    vector<node *> openList;
    vector<node *> endList;

map中存储数据结构。visited_open和visited_end是为了防止搜索重复遍历open和end列表。

    void generateMap() {
        vector<string> results;
        results.resize(nRow);
        visited_open.resize(nRow * nColumn);
        visited_end.resize(nRow * nColumn);
        for (int i = 0; i < nRow; i++) {
            for (int j = 0; j < nColumn; j++) {
                results[i][j] = '.';
            }
        }
        for (int i = 0; i < walls.size(); i++) {
            results[walls[i].first][walls[i].second] = '#';
        }
        results[beginning.first][beginning.second] = '@';
        results[ending.first][ending.second] = '@';
        maps = results;
    }

生成地图。
主算法：

        node *begin = new node(beginning.first, beginning.second, nullptr);
        begin->setF(0);
        begin->setG(0);
        begin->setH(0);
        //起始点丢进openlist里面,更新最小点
        openList.push_back(begin);
        visited_open[begin->getX() * nColumn + begin->getY()] = true;

可以把起点丢进open列表，begin->getX() * nColumn + begin->getY()是这个点的编号，把矩阵拉长变成一维编号留下的值。

        while (!openList.empty()) {
            int index = getLowestF();
            node *current = openList[index];

            //cout << current->getX() << " " << current->getY() << endl;

            openList.erase(openList.begin() + index);

            endList.push_back(current);
            visited_end[current->getX() * nColumn + current->getY()] = true;
            if (current->getX() == ending.first && current->getY() == ending.second) {
                return;
            }

            addPoint(current);
        }
    }

首先遍历获取最小的F值，从open取出并加入end中，别忘了维护visited，其次把扩展的候选点加入open。

代码效果

初始地图。

箭头即是最短路径。
我们来看看搜索空间：

算法优化

很明显，这个算法优化的空间还是比较大的，之前在openList就考虑过能不能用优先队列，因为在迪杰斯特拉算法中有优先队列是有很大的效率提升，但是问题就在于，在候选点存在openList列表的时候，我们需要进行更新父节点，这个时候要搜索openList了，C++的优先队列没有提供遍历功能，总不能全部倒出来再塞回去吧。所以如果使用优先队列，就需要考虑如何在优先队列中获取特点元素并完成动态更新的过程，因为你找到这个节点如果更新了之后，优先队列需要再动态的排序一次的。而具有让priorityqueue能动态排序的我目前就知道pair。不知道其他的语言优先队列能不能遍历，C++可以自己实现一个二叉堆即可。
其次，代价还是对于算法影响是非常大的，当H是0的时候，就完全退化成了迪杰斯特拉算法，因为他之和原点距离有关了。当H比实际代价要小上许多时，我们的搜索复杂度就会增加，因为这个时候主要取决于G，于是就会在原点周围不断扩展，搜索的点会非常多。
我们上面的例子中代价都是乘10，H的代价也是乘10的，一个格子就是10，我们现在缩减十倍，对于G来说，上下左右+10，斜方向加14，而对于H来说一格只加1，我们看看搜索空间的变化。

可以看到基本就退化成了广度优先。
当H原大于实际代价的时候，这就有一点随机性了，得看你障碍物的位置和你代码编写遍历方向的顺序有关系了。因为这个时候主要取决于H的变化。这就有点像BFS了。
所以按照这个方向优化，我们可以考虑让H代价更准确一点，修改代价函数F = G + W * H。W可以影响H的权重，这里的W可能要根据不同场景进行设置，可以设置所有节点都一样，也可以设置没个节点都不同。或许可以随着搜索的增加不断的增大H，使得搜索空间成一个哑铃的形状。当然这只是个想法，是不是还得实验一下。

代码：https://github.com/GreenArrow2017/PracticeAlgorithm/tree/master/Astar