寻路算法——A*算法详解并附带实现代码

刺骨的言语ヽ痛彻心扉 2023-02-17 11:12 2阅读 0赞

## 一、前言 ##

前天看了一篇博客介绍A\*算法，按照自己的理解记录一下A\*算法。

## 二、应用场景 ##

一副地图中有坐标A和B，需要找到一条路径（如果有的话）能从A到B，地图中可能有河流或墙壁不能直接穿过，我们需要怎样找到这条路径呢？

在我们以往学习到的路径寻找中，我们可以想到广度优先搜索（BFS：Breadth First Search）和深度优先搜索（DFS：Depth-First-Search） 进行路径寻找。先看一下广度优先搜索如下图（图片来源网上）。**BFS以起点A为圆心，先搜索A周围的所有点，形成一个类似圆的搜索区域，再扩大搜索半径，进一步搜索其它没搜索到的区域，直到终点B进入搜索区域内被找到**。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25pZTIzMTQ1NTA0NDE_size_16_color_FFFFFF_t_70][]

再看一下深度优先搜索，这里的深度优先搜索不是所有路径都搜索而是沿着B点方向搜索。（图片来源网上）。**DFS则是让搜索的区域离A尽量远，离B尽量近**，比如现在你在一个陌生的大学校园里，你知道校门口在你的北方，虽然你不知道你和校门口之间的路况如何，地形如何，但是你会尽可能的往北方走，总能找到校门口。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25pZTIzMTQ1NTA0NDE_size_16_color_FFFFFF_t_70 1][]

比起BFS，DFS因为尽量靠近终点的原则，其实是用终点相对与当前点的方向为导向，所以有一个大致的方向，就不用盲目地去找了，这样，就能比BFS能快地找出来最短路径，但是这种快速寻找默认起点A终点B之间没有任何障碍物，地形的权值也都差不多。如果起点终点之间有障碍物，那么DFS就会出现绕弯的情况。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25pZTIzMTQ1NTA0NDE_size_16_color_FFFFFF_t_70 2][]

图中DFS算法使电脑一路往更右下方的区域探索，可以看出，在DFS遇到障碍物时，其实没有办法找到一条最优的路径，只能保证DFS会提供其中的一条路径（如果有的话）。

大概了解了BFS和DFS，对比这两者可以看出来，**BFS保证的是从起点到达路线上的任意点花费的代价最小**（但是不考虑这个过程是否要搜索很多格子）；**DFS保证的是通过不断矫正行走方向和终点的方向的关系，使发现终点要搜索的格子更少**（但是不考虑这个过程是否绕远）。

A\*算法的设计同时融合了BFS和DFS的优势，既考虑到了从起点通过当前路线的代价（保证了不会绕路），又不断的计算当前路线方向是否更趋近终点的方向（保证了不会搜索很多图块），是一种**静态路网中最有效的直接搜索算法**。

闲谈：我们知道BFS和DFS，但将这两种思想融会贯通，创造一种新的解决问题方法（A\*算法），这在思路太棒了。膜拜学习。

## 三、A\*算法 ##

### 3.1 思想 ###

A\*算法运用的是估价思想。查找过程：

1.  在待遍历列表中（刚开始只有点A），我们在列表中查找一个估价（当前点到终点距离估价，后续会讲）最小的点（k），
2.  对点k进行一次广度优先查找，也就是它移动一次到底的下一个坐标（右，右上，上，左上，左，左下，下，右下）不包含已经遍历过的点和不能到达的点，将能查找的点添加到队列中，并将点K从队列中移除。
3.  重复1、2步骤直到到底B点，或者队列已经为空说明没有路径可以到达点B。

运用的思想：先进行一次DFS搜索再进行一次BFS搜索，循环这个过程直到找到目标点B。

过程1：运用DFS思想，尽量找离B近的点（也就是估值最小的点）。

过程2：运用BFS思想，以点K为圆心，搜索A周围的所有还未搜索的点。

### 3.2 怎样估价 ###

**3.2.1 公式：F = G + H。**

G = 从起点 A 移动到指定方格的移动代价，沿着到达该方格而生成的路径。我们约定直行移动一次代价是10，对角线的移动代价为 14。（实际对角移动距离是 2 的平方根，或者是近似的 1.414 倍的横向或纵向移动代价）。

H = 从指定的方格移动到终点 B 的估算成本。计算从当前方格横向或纵向移动到达目标所经过的方格数，忽略对角移动，然后把总数乘以 10 。

**3.2.2 计算**

我们设当前点为K

H 值很容易计算，H = （两个点横坐标距离 + 两个点纵坐标距离） X 10

G 值计算，计算K到A的最小估价我们只需要计算K点的周围八个点（**可以被访问且已经被访问点**）的g值+到K点的移动代价，其中最小估价即为K点的g值，这个点我们称为K点的父节点。k点正在访问，那么它周围至少有一个点已经被访问了。

**3.2.2 约定**

在一个方格中我们将FGH标记在它的左上，左下和右下三个位置，以便我们观察每次估价的结果。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25pZTIzMTQ1NTA0NDE_size_16_color_FFFFFF_t_70 3][]

箭头指向的是它父节点的坐标，后续找路线需要用到。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25pZTIzMTQ1NTA0NDE_size_16_color_FFFFFF_t_70 4][]

### 3.3 实例演示一 无障碍物 （对应编码实现中测试用例9） ###

**说明**：坐标访问和父节点查找约定顺序：右，右上，上，左上，左，左下，下，右下，沿X轴增加的方向为右，沿Y轴增加的方向为上，父节点可能会有多个，这里选择代价最小最后搜索的为父节点。

坐标A(2，2)，目标坐标B(6，3)，已经对坐标A进行了估值。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25pZTIzMTQ1NTA0NDE_size_16_color_FFFFFF_t_70 5][]

1. 对点（2，2）八个方向的坐标进行估值，它们的父节点都是（2，2），最小估值坐标紫色（3，3），标记紫色只是为了方便下一次寻找。估值顺序我们约定（右，右上，上，左上，左，左下，下，右下），此后我们都按照这个顺序进行。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25pZTIzMTQ1NTA0NDE_size_16_color_FFFFFF_t_70 6][]

2. 对点（3，3）八个方向的坐标进行估值（已经估值的不用再计算），我们称已经估值的点为已经被访问，最小估值坐标紫色（4，3）。父节点搜索顺序约定（右，右上，上，左上，左，左下，下，右下），g值**最小最后**访问的点为父节点。**如下图。这个图我们需要理解箭头是怎样确定的**。例如点（4，3）它的父节点既可以是点（3，3）也可以是点（3，2），访问顺序是先访问点（3，3）后访问点（3，2）所以我们把点（3，2）作为点（4，3）的父节点。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25pZTIzMTQ1NTA0NDE_size_16_color_FFFFFF_t_70 7][]

3. 对点（4，3）继续寻找，最小估值坐标紫色（5，3）

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25pZTIzMTQ1NTA0NDE_size_16_color_FFFFFF_t_70 8][]

4. 对点（5，3）继续寻找，搜索到了终点，停止搜索

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25pZTIzMTQ1NTA0NDE_size_16_color_FFFFFF_t_70 9][]

5. 通过终点依次查找它们的父节点直到起点，然后将坐标点逆序，就是我们要的路线了。

路线：（2，2）、（3，2）、（4，2）、（5，2）、（6，3）

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25pZTIzMTQ1NTA0NDE_size_16_color_FFFFFF_t_70 10][]

### 3.4 实例演示二 有障碍物 （对应编码实现中测试用例10） ###

有无障碍物处理是一样的。

坐标A(2，2)，目标坐标B(6，3)，已经对坐标A进行了估值。其中坐标（4，1）、（4，2）、（4，3）无障碍物不能访问

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25pZTIzMTQ1NTA0NDE_size_16_color_FFFFFF_t_70 11][]

1. 对点（2，2）八个方向的坐标进行估值，它们的父节点都是（2，2），最小估值坐标紫色（3，3）

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25pZTIzMTQ1NTA0NDE_size_16_color_FFFFFF_t_70 12][]

2. 对点（3，3）继续寻找，最小估值坐标紫色（2，3）

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25pZTIzMTQ1NTA0NDE_size_16_color_FFFFFF_t_70 13][]

3. 对点（3，2）继续寻找，最小估值坐标紫色（4，4）

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25pZTIzMTQ1NTA0NDE_size_16_color_FFFFFF_t_70 14][]

4. 对点（4，4）继续寻找，最小估值坐标紫色（5，3）

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25pZTIzMTQ1NTA0NDE_size_16_color_FFFFFF_t_70 15][]

5. 对点（5，3）继续寻找，搜索到了终点，停止搜索

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25pZTIzMTQ1NTA0NDE_size_16_color_FFFFFF_t_70 16][]

6. 通过终点依次查找它们的父节点直到起点，然后将坐标点逆序，就是我们要的路线了。

路线：（2，2）、（3，3）、（4，4）、（5，3）、（6，3）

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25pZTIzMTQ1NTA0NDE_size_16_color_FFFFFF_t_70 17][]

##  ##

## 四、编码实现 ##

//==========================================================================
    /**
    * @file    : Astar.h
    * @author  : niebingyu
    * @title   : A*算法
    * @purpose : A*算法实现
    *
    * 博客：https://blog.csdn.net/nie2314550441/article/details/106733189
    */
    //==========================================================================
    #pragma once
    #include <assert.h>
    #include <vector>
    #include <list>
    #include <iostream>
    #include <queue>
    using namespace std;
    
    #define NAMESPACE_ASTAR namespace NAME_ASTAR {
    #define NAMESPACE_ASTAREND }
    NAMESPACE_ASTAR
    
    #define GET_ARRAY_LEN(array) (sizeof(array)/sizeof(array[0]))
    struct Point
    {
        int x;		// 宽
        int y;		// 高
        Point(int tx = 0, int ty = 0) : x(tx), y(ty) {}
    
        // 两个坐标距离：横坐标距离 + 纵坐标距离
        int operator - (const Point& p)
        {
            return abs(x - p.x) + abs(y - p.y);
        }
    
        bool operator == (const Point& p)
        {
            return x == p.x && y == p.y;
        }
    };
    
    struct PointV : public Point
    {
        int value;	// 0 :无障碍; 1:有障碍
        PointV(int nx = 0, int ny = 0, int v = 0) : Point(nx, ny), value(v) {}
    };
    
    struct PointAStart : public Point
    {
        int f, g, h;
        bool visited;	// 是否被访问过，0：未被访问，1已经被访问
        Point parentNode;
    
        PointAStart(int tf = 0, int tg = 0, int th = 0, int tx = 0, int ny = 0) : Point(tx, ny), f(tf), g(tg), h(th), visited(false), parentNode() {};
        bool operator < (const PointAStart& t) { return f < t.f; }
        void SetFGH(int tf, int tg, int th) { f = tf; g = tg, h = th; }
    };
    
    // 重写仿函数, 优先队列元素大小比较
    struct comp //重写仿函数
    {
        bool operator() (PointAStart* a, PointAStart* b)
        {
            return a->f > b->f; //小顶堆
        }
    };
    
    // A* 算法
    class AStar
    {
    public:
        // arr 是一个二维数组 
        // s 起点; e 终点
        vector<Point> operator()(const vector<vector<int>>& arr, Point s, Point e)
        {
            if (arr.empty() || s == e)
                return {};
    
            int lenY = (int)arr.size() - 1;		    // 高
            int lenX = (int)arr[0].size() - 1;		// 宽
    
            if (s.x > lenX || s.y > lenY || e.x > lenX || e.y > lenY)
                return {};
    
            if (arr[s.y][s.x] != 0 || arr[e.y][e.x] != 0)
                return {};
    
            for (int i = 0; i < lenY; ++i)
                assert(lenX == (int)arr[i].size() - 1);
    
            vector<vector<PointAStart>> pArr(lenY + 1, vector<PointAStart>(lenX + 1));	// 父结点
            priority_queue<PointAStart*, vector<PointAStart*>, comp> openList; // by 2020/07/30 改用优先队列
    
            int g = 0, h = (s - e) * 10, f = g + h;
            PointAStart pt(f, g, h, s.x, s.y);
            pt.visited = true;
            pArr[s.y][s.x] = pt;
            openList.push(&pArr[s.y][s.x]);
    
            bool seek = true;
            const int dirs[8][3] = { {0,1,10},{1,1,14},{1,0,10},{1,-1,14},{0,-1,10},{-1,-1,14},{-1,0,10},{-1,1,14} };//8个移动方向（右，右上，上，左上，左，左下，下，右下）
            while (seek && !openList.empty())
            {
                PointAStart& p = *openList.top();
                openList.pop();
                p.visited = true;
    
                for (int i = 0; i < GET_ARRAY_LEN(dirs) && seek; ++i)
                {
                    Point t(p.x + dirs[i][1], p.y + dirs[i][0]);
                    // t 需要未被访问
                    if (t.x < 0 || t.x > lenX || t.y < 0 || t.y > lenY || arr[t.y][t.x] == 1 || pArr[t.y][t.x].visited)
                        continue;
    
                    // 找父节点
                    g = p.g + dirs[i][2];
                    h = (t - e) * 10;
                    f = g + h;
                    int minf = f;
                    PointAStart newPoint(f, g, h, t.x, t.y);
                    newPoint.visited = 1;
                    newPoint.parentNode.x = p.x;
                    newPoint.parentNode.y = p.y;
                    for (int j = 0; j < GET_ARRAY_LEN(dirs); ++j)
                    {
                        Point pp(t.x + dirs[j][1], t.y + dirs[j][0]);  //父节点Parent Point
                        // 父节点pp, 在需要已经被访问
                        if (pp.x < 0 || pp.x > lenX || pp.y < 0 || pp.y > lenY || arr[pp.y][pp.x] == 1 || !pArr[pp.y][pp.x].visited)
                            continue;
    
                        g = pArr[pp.y][pp.x].g + dirs[j][2];
                        f = g + h;
                        if (f <= minf)
                        {
                            minf = f;
                            f = g + h;
    
                            newPoint.SetFGH(f, g, h);
                            newPoint.parentNode = pp;
                        }
    
                    }
    
                    pArr[t.y][t.x] = newPoint;
                    openList.push(&pArr[t.y][t.x]);
    
                    if (t == e)
                        seek = false;
                }
            }
    
            if (!pArr[e.y][e.x].visited)
            {
                cout << "无法到达" << endl;
                return {};
            }
            else
            {
                vector<Point> path;
                path.push_back(e);
                Point p = pArr[e.y][e.x].parentNode;
                while (true)
                {
                    if (!pArr[p.y][p.x].visited)
                    {
                        cout << "无法到达" << endl;
                        return {};
                    }
    
                    path.push_back(p);
                    if (p == s)
                        break;
    
                    p = pArr[p.y][p.x].parentNode;
                }
    
                reverse(path.begin(), path.end());
                SetVisitedCount(pArr);	// 辅助测试，记录访问的结点数
    
                return path;
            }
        }
    
        // 辅助测试，用于获取访问的结点数
        void SetVisitedCount(const vector<vector<PointAStart>>& pArr)
        {
            visitCount = 0;
            for (int i = 0; i < pArr.size(); ++i)
            {
                for (int j = 0; j < pArr[i].size(); ++j)
                {
                    if (pArr[i][j].visited)
                        ++visitCount;
                }
            }
        }
    
        int visitCount;
    };
    
    //
    // 测试 用例 START
    void test(const char* testName, const vector<vector<int>>& arr, Point s, Point e)
    {
        AStar as;
        vector<Point> result = as(arr, s, e);
    
        cout << testName << "[" << as.visitCount << ", " << result.size() << "]";
        for (int i = 0; i < result.size(); ++i)
        {
            cout << ", (" << result[i].x << "," << result[i].y << ")";
        }
        cout << endl;
    }
    
    // 测试用例
    void Test1()
    {
        vector<vector<int>> arr =
        {
            {0,0},
        };
    
        Point s(0, 0);
        Point e(1, 0);
        test("Test1()", arr, s, e);
    }
    
    void Test2()
    {
        vector<vector<int>> arr =
        {
            {0},
            {0}
        };
    
        Point s(0, 0);
        Point e(0, 1);
    
        test("Test2()", arr, s, e);
    }
    
    void Test3()
    {
        vector<vector<int>> arr =
        {
            {0,0,},
            {0,0,},
        };
    
        Point s(0, 0);
        Point e(1, 1);
    
        test("Test3()", arr, s, e);
    }
    
    void Test4()
    {
        vector<vector<int>> arr =
        {
            {0,0,0,},
            {0,0,0,},
        };
    
        Point s(0, 0);
        Point e(2, 1);
    
        test("Test4()", arr, s, e);
    }
    
    void Test5()
    {
        vector<vector<int>> arr =
        {
            {0,1,0,},
            {0,1,0,},
            {0,0,0,},
        };
    
        Point s(0, 0);
        Point e(2, 0);
    
        test("Test5()", arr, s, e);
    }
    
    void Test6()
    {
        vector<vector<int>> arr =
        {
            {0,0,0,0,0,0,0,0},
            {0,0,0,0,1,0,0,0},
            {0,0,0,0,1,0,0,0},
            {0,0,0,0,1,0,0,0},
            {0,0,0,0,0,0,0,0},
            {0,0,0,0,0,0,0,0},
        };
    
        Point s(2, 2);
        Point e(6, 2);
    
        test("Test6()", arr, s, e);
    }
    
    void Test7()
    {
        vector<vector<int>> arr =
        {
            {0,0,0,0,0,0,0,0},
            {0,0,0,0,1,0,0,0},
            {0,0,0,0,1,0,0,0},
            {0,0,0,0,1,0,0,0},
            {0,0,0,0,1,0,0,0},
            {0,0,0,0,1,0,0,0},
        };
    
        Point s(2, 2);
        Point e(6, 2);
    
        test("Test7()", arr, s, e);
    }
    
    void Test8()
    {
        vector<vector<int>> arr =
        {
            {0,0,0,0,0,0,0,0,0},
            {0,0,0,0,1,1,1,1,0},
            {0,0,0,0,1,0,0,1,0},
            {0,0,0,0,1,0,0,1,0},
            {0,0,0,0,1,0,1,1,0},
            {0,0,0,0,1,0,0,0,0},
        };
    
        Point s(2, 2);
        Point e(6, 2);
    
        test("Test8()", arr, s, e);
    }
    
    void Test9()
    {
        vector<vector<int>> arr =
        {
            {0,0,0,0,0,0,0,0,0,0},
            {0,0,0,0,0,0,0,0,0,0},
            {0,0,0,0,0,0,0,0,0,0},
            {0,0,0,0,0,0,0,0,0,0},
            {0,0,0,0,0,0,0,0,0,0},
            {0,0,0,0,0,0,0,0,0,0},
        };
    
        Point s(2, 2);
        Point e(6, 3);
    
        test("Test9()", arr, s, e);
    }
    
    void Test10()
    {
        vector<vector<int>> arr =
        {
            {0,0,0,0,0,0,0,0,0,0},
            {0,0,0,0,1,0,0,0,0,0},
            {0,0,0,0,1,0,0,0,0,0},
            {0,0,0,0,1,0,0,0,0,0},
            {0,0,0,0,0,0,0,0,0,0},
            {0,0,0,0,0,0,0,0,0,0},
        };
    
        Point s(2, 2);
        Point e(6, 3);
    
        test("Test10()", arr, s, e);
    }
    
    void Test11()
    {
        vector<vector<int>> arr =
        {
            {0,0,0,0,1,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
            {0,1,0,0,1,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
            {0,1,0,0,1,0,0,0,1,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0},
            {0,1,0,0,1,0,0,0,1,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0},
            {0,1,0,0,1,0,0,0,1,0,0,0,0,1,0,0,1,1,1,0,0,0,0,0,0,0,0},
            {0,1,0,0,1,0,0,0,1,0,0,0,0,1,0,0,1,0,1,0,0,0,0,0,0,0,0},
            {0,1,0,0,1,0,0,0,1,0,0,0,0,1,0,0,1,0,1,0,0,0,0,0,0,0,0},
            {0,1,0,0,1,0,0,0,1,0,0,0,0,1,0,1,1,0,1,0,0,0,0,0,0,0,0},
            {0,1,1,1,1,0,0,0,1,0,0,0,0,1,0,1,0,0,1,0,0,0,0,0,0,0,0},
            {0,0,0,0,0,0,0,0,1,0,0,0,0,1,0,1,0,0,1,0,0,0,0,0,0,0,0},
            {0,0,0,0,0,0,0,0,1,0,0,0,0,1,0,1,0,0,1,0,0,0,0,0,0,0,0},
            {0,0,0,0,0,0,0,0,1,0,0,0,0,1,1,1,0,0,1,0,0,0,0,0,0,0,0},
            {0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0},
            {0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0},
        };
    
        Point s(2, 7);
        Point e(17, 5);
    
        test("Test11()", arr, s, e);
    }
    NAMESPACE_ASTAREND
    // 测试 用例 END
    //
    
    void AStar_Test()
    {
    #if 1
        NAME_ASTAR::Test1();
        NAME_ASTAR::Test2();
        NAME_ASTAR::Test3();
        NAME_ASTAR::Test4();
        NAME_ASTAR::Test5();
        NAME_ASTAR::Test6();
        NAME_ASTAR::Test7();
        NAME_ASTAR::Test8();
        NAME_ASTAR::Test9();
        NAME_ASTAR::Test10();
        NAME_ASTAR::Test11();
    #endif
        //NAME_ASTAR::Test9();
    }

**执行结果：**

![20200730100013286.png][]

## 五、拓展 ##

### 5.1 如果现在需求有变，不能沿对角线移动，也就是只能上下左右移动，需要怎样实现呢？ ###

修改第82行代码 const int dirs\[8\]\[3\] = \{ \{0,1,10\},\{1,1,14\},\{1,0,10\},\{1,-1,14\},\{0,-1,10\},\{-1,-1,14\},\{-1,0,10\},\{-1,1,14\} \};//8个移动方向（右，右上，上，左上，左，左下，下，右下）

改为 const int dirs\[4\]\[3\] = \{ \{0,1,10\},\{1,0,10\},\{0,-1,10\},\{-1,0,10\} \};//8个移动方向（右，上，左，下）

### 5.2 需求再变动一下，只能沿着上下左右移动，但向右可以一次移动1格或者2格，需要怎样实现呢？ ###

同理修改第82行代码 const int dirs\[8\]\[3\] = \{ \{0,1,10\},\{1,1,14\},\{1,0,10\},\{1,-1,14\},\{0,-1,10\},\{-1,-1,14\},\{-1,0,10\},\{-1,1,14\} \};//8个移动方向（右，右上，上，左上，左，左下，下，右下）

改为 const int dirs\[5\]\[3\] = \{ \{0,1,10\}, \{0,2,20\},\{1,0,10\},\{0,-1,10\},\{-1,0,10\} \};//8个移动方向（右1格，右2格，上，左，下）

### 六、闲谈 ###

前面我们介绍的都是起点去找终点，观察一下下面这种情况，黄色是起点，红色是终点。起点找终点会搜索大量无用的坐标点，而如果是终点去寻找起点搜索需要坐标点会少很多。那我们可不可以**起点和终点一起去寻找**对方呢？

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25pZTIzMTQ1NTA0NDE_size_16_color_FFFFFF_t_70 18][]

参考：[https://blog.csdn.net/nie2314550441/article/details/106673966][https_blog.csdn.net_nie2314550441_article_details_106673966]

[https://zhuanlan.zhihu.com/p/23199073][https_zhuanlan.zhihu.com_p_23199073]

**2020/6/14 补充说明**

## 六、延伸扩展 ##

已经知道A\*算法过程，再逆序思索一下这个算法。起点A，终点B，假设存在一条最优的路线能从A到B。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25pZTIzMTQ1NTA0NDE_size_16_color_FFFFFF_t_70 19][]

我们继续观察这个图，如果存在最优路线。到达B的上一个坐标点一定是B点周围的一个坐标称之为父节点。也就是我们只需要找到这个点父节点。这种思路不就是动态规划中的自顶向下。自顶向下效率不佳，我们将其转换成自底向上求解就可以了。我们在求解动态规划问题往往都是计算最终结果，如果需要求解这个过程是怎样的呢？

A\*算法就是这个问题的自底向上求解的过程。A\*算法给我们提供了一个很好的思路，我们只需要记录当前结果产生的父节点，通过父节点倒推这个过程。例如[《算法导论——钢条切割》][Link 1]需要求解的是最大价值，那最多价值切割的方法是怎样呢？可以通过上面说的方法求解。

可以理解A\*算法 是结合了 深度优先、广度优先、以及动态规划的思想。个人理解。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25pZTIzMTQ1NTA0NDE_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200613154420270.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25pZTIzMTQ1NTA0NDE=,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25pZTIzMTQ1NTA0NDE_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200613154527320.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25pZTIzMTQ1NTA0NDE=,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25pZTIzMTQ1NTA0NDE_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20200613154600288.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25pZTIzMTQ1NTA0NDE=,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25pZTIzMTQ1NTA0NDE_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/20200613155345232.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25pZTIzMTQ1NTA0NDE=,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25pZTIzMTQ1NTA0NDE_size_16_color_FFFFFF_t_70 4]: https://img-blog.csdnimg.cn/20200613155403177.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25pZTIzMTQ1NTA0NDE=,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25pZTIzMTQ1NTA0NDE_size_16_color_FFFFFF_t_70 5]: https://img-blog.csdnimg.cn/20200613155450297.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25pZTIzMTQ1NTA0NDE=,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25pZTIzMTQ1NTA0NDE_size_16_color_FFFFFF_t_70 6]: https://img-blog.csdnimg.cn/20200613155539115.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25pZTIzMTQ1NTA0NDE=,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25pZTIzMTQ1NTA0NDE_size_16_color_FFFFFF_t_70 7]: https://img-blog.csdnimg.cn/20200614093807605.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25pZTIzMTQ1NTA0NDE=,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25pZTIzMTQ1NTA0NDE_size_16_color_FFFFFF_t_70 8]: https://img-blog.csdnimg.cn/20200614093534277.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25pZTIzMTQ1NTA0NDE=,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25pZTIzMTQ1NTA0NDE_size_16_color_FFFFFF_t_70 9]: https://img-blog.csdnimg.cn/20200614093619526.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25pZTIzMTQ1NTA0NDE=,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25pZTIzMTQ1NTA0NDE_size_16_color_FFFFFF_t_70 10]: https://img-blog.csdnimg.cn/2020061409370776.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25pZTIzMTQ1NTA0NDE=,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25pZTIzMTQ1NTA0NDE_size_16_color_FFFFFF_t_70 11]: https://img-blog.csdnimg.cn/20200613155909875.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25pZTIzMTQ1NTA0NDE=,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25pZTIzMTQ1NTA0NDE_size_16_color_FFFFFF_t_70 12]: https://img-blog.csdnimg.cn/20200613155955192.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25pZTIzMTQ1NTA0NDE=,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25pZTIzMTQ1NTA0NDE_size_16_color_FFFFFF_t_70 13]: https://img-blog.csdnimg.cn/20200614090536830.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25pZTIzMTQ1NTA0NDE=,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25pZTIzMTQ1NTA0NDE_size_16_color_FFFFFF_t_70 14]: https://img-blog.csdnimg.cn/2020061409070473.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25pZTIzMTQ1NTA0NDE=,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25pZTIzMTQ1NTA0NDE_size_16_color_FFFFFF_t_70 15]: https://img-blog.csdnimg.cn/20200614091408725.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25pZTIzMTQ1NTA0NDE=,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25pZTIzMTQ1NTA0NDE_size_16_color_FFFFFF_t_70 16]: https://img-blog.csdnimg.cn/20200614091311640.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25pZTIzMTQ1NTA0NDE=,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25pZTIzMTQ1NTA0NDE_size_16_color_FFFFFF_t_70 17]: https://img-blog.csdnimg.cn/20200614091601210.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25pZTIzMTQ1NTA0NDE=,size_16,color_FFFFFF,t_70
[20200730100013286.png]: https://img-blog.csdnimg.cn/20200730100013286.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25pZTIzMTQ1NTA0NDE_size_16_color_FFFFFF_t_70 18]: https://img-blog.csdnimg.cn/20200613160923797.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25pZTIzMTQ1NTA0NDE=,size_16,color_FFFFFF,t_70
[https_blog.csdn.net_nie2314550441_article_details_106673966]: https://blog.csdn.net/nie2314550441/article/details/106673966
[https_zhuanlan.zhihu.com_p_23199073]: https://zhuanlan.zhihu.com/p/23199073
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25pZTIzMTQ1NTA0NDE_size_16_color_FFFFFF_t_70 19]: https://img-blog.csdnimg.cn/20200614112626491.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25pZTIzMTQ1NTA0NDE=,size_16,color_FFFFFF,t_70
[Link 1]: https://blog.csdn.net/nie2314550441/article/details/106270866