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;
}