A*算法详解

一、什么是A*算法

A*算法是一种启发式搜索算法，它在寻找从起点到终点的最短路径时极具有效性和实用性。它采用估价函数来计算从某个点到目标点的距离，进而选取优先级最高的点进行搜索。相较于其他算法，A*算法拥有更高的搜索效率和准确性。

关于估价函数，需要注意的是，它并不一定要与实际的距离一致，而是根据当前状态下获取的信息进行推导，得出最为可能的结果。A*采用的是启发函数，有较强的启发作用，这是它优于其他算法的优点之一。

二、A*算法的原理

任何搜索算法都需要寻找一种方式来衡量每个节点的价值，然后以某种规则决定查找的先后顺序。A*算法通过综合考虑两个因素来计算每个节点的价值：从起点到当前节点的真实代价（g(x)）和从当前节点到终点的估计代价（h(x)）。

因此，对于一个节点x，它的总代价就是 f(x) = g(x) + h(x)。在这个算法中，我们希望找到代价最小的点来作为下一个搜索节点。

三、A*算法的实现步骤

1. 构建地图

首先，需要确定起点、终点以及地图的其他状态。地图的构建可以采用矩阵等方式表达。

例如，我们可以使用二维数组来表示地图，1表示可通行，0表示障碍物。

  int[][] map = {
        {1, 1, 1, 1, 0},
        {1, 0, 1, 1, 0},
        {1, 1, 1, 1, 0},
        {0, 0, 0, 1, 0},
        {0, 0, 0, 1, 1}
    };

2. 定义节点和构建搜索树

我们用结构体来定义一个节点，它包括横坐标x、纵坐标y、f(g+h)，g和h。我们采用优先队列来存储搜索过程中的所有节点，节点从队首到队尾按照f值的大小递增排序。

deque<pair> q; //定义队列

int vis[111][111] = {};　//记录某个点是否被搜索过

struct node{
int x, y, f, g, h;
};

3. 搜索

使用A*算法实现搜索的主要流程：

(1)将起点节点入队，并将f、g、h值初始化为0。

(2)重复以下操作，直到队列为空或找到了终点节点：

(3)从队列中选取f值最小的节点，并将其出队。

(4)遍历该节点周围的节点，如果找到了终点，返回结果。

(5)如果当前节点未被访问过，更新其f、g、h值，并将其入队。

流程展示：

//起点入队

    q.push_back([start_x,start_y,0,0,0]);

    while(!q.empty()) {

        node a = q.front();

        q.pop_front();

        vis[a.x][a.y] = 1;

        if(a.x == end_x && a.y == end_y) return a.g;

        for(int i=0;i<4;i++){

            int x = a.x + dx[i], y = a.y + dy[i];  //dx dy 是四个方向

            if(x>=1 && x=1 && y<=M && !vis[x][y] && map[x][y]) {

                node b;
                b.x = x; b.y = y;
                b.g = a.g + 1;
                b.h = abs(x-end_x)+abs(y-end_y);
                b.f = b.g + b.h;
                q.push_back(b);

            }
        }
        sort(q.begin(),q.end(),cmp);

    }

    return -1;//没有路径

其中f值的大小可以通过改变启发函数h(x)的取值来实现A*算法的不同策略，例如如果h(x)始终为0，则等同于广度优先搜索。

4. 代码示例

下面是A*算法的完整代码，其中有详细的注释信息。请注意对于实际问题，需要根据具体场景修改代码。

const int dx[4] = {0,-1,0,1}, dy[4] = {1,0,-1,0}; //四个方向
int N = 5, M = 5;　　//地图大小
int vis[111][111] = {};　//记录某个点是否被搜索过
int map[111][111] = {};　　//存储地图信息

struct node{
    int x, y, f, g, h;
};

bool cmp(const node &a, const node &b){
    return a.f > b.f;
}

int A_star(int start_x, int start_y, int end_x, int end_y){
    deque q;  //定义队列 
    //起点入队
    q.push_back((node){start_x,start_y,0,0,0});
    while(!q.empty()) {
        node a = q.front();
        q.pop_front();
        vis[a.x][a.y] = 1;　//标记该点已被搜索过
        if(a.x == end_x && a.y == end_y) return a.g; //找到了终点
        for(int i=0;i=1 && x=1 && y<=M && !vis[x][y] && map[x][y]) { //如果未访问且可通过
                node b;
                b.x = x; b.y = y;
                b.g = a.g + 1;
                b.h = abs(x-end_x)+abs(y-end_y); //曼哈顿距离
                b.f = b.g + b.h;
                q.push_back(b);
            }
        }
        sort(q.begin(),q.end(),cmp); //节点按照f值排序，保证每次搜索最优的点
    }
    return -1; //没有路径
}

int main(){
    //地图的初始化
    int map_array[5][5] = {
        {1, 1, 1, 1, 0},
        {1, 0, 1, 1, 0},
        {1, 1, 1, 1, 0},
        {0, 0, 0, 1, 0},
        {0, 0, 0, 1, 1}
    };
    for(int i=0;i<N;++i){
        for(int j=0;j<M;++j){
            map[i+1][j+1] = map_array[i][j];
        }
    }
    //寻找最短路径
    int step = A_star(1,1,5,5);
    cout<<step<<"\n";
    return 0;
}

原创文章，作者：UBYGL，如若转载，请注明出处：https://www.506064.com/n/360715.html