A*算法理解

Luci990722 / 2024-03-12 / 原文

A*算法本质还是BFS宽度优先算法，只不过加入了评估函数h，用以衡量每个加入点的优先级。

实现方式是采用优先队列，权重值设置为：f(x） + h(x)，其中f(x)代表当前实际消耗，h(x)表示预测到达终点消耗。

评估函数h（x）作为一种预测，要求小于等于实际到达终点的距离。

力扣1631 最小体力消耗路径

class Solution {
public:
    int dir[5] = {-1, 0, 1, 0, -1};
    char op[4] = {'u', 'r', 'd', 'l'};
    struct Node{
        int u;
        int maxV;
        bool operator <(const Node& x) const{
            return maxV > x.maxV;
        }
    };

    int minimumEffortPath(vector<vector<int>>& heights) {
        int n = heights.size(), m = heights[0].size();
        priority_queue<Node> pq;
        pq.push({0, 0});
        unordered_map<int, int> dist;
        unordered_map<int, pair<char, int>> path;
        dist[0] = 0;
        while(pq.size()){
            auto [u, maxV] = pq.top();
            pq.pop();
            if(u == m * n - 1){
                break;
            }
            for(int k = 0; k < 4; ++k){
                int x = u / m, y = u % m;
                int nx = x + dir[k], ny = y + dir[k + 1];
                if(nx < 0 || nx >= n || ny < 0 || ny >= m){
                    continue;
                }
                int tmpMax = max(maxV, abs(heights[x][y] - heights[nx][ny]));
                int v = nx * m + ny;
                if(!dist.count(v) || dist[v] > tmpMax){
                    dist[v] = tmpMax;
                    pq.emplace(v, tmpMax);
                    path[v] = {op[k], u};
                }  
            }
        }
        vector<char> pathAns;
        int st = m * n - 1, ed = 0;
        while(st != ed){
            pathAns.emplace_back(path[st].first);
            st = path[st].second;
        }
        reverse(pathAns.begin(), pathAns.end());
        for(auto c : pathAns){
            cout << c << " ";
        }
        return dist[m * n - 1];
    }
};

八数码

#include<iostream>
#include<algorithm>
#include<cstring>
#include<unordered_map>
#include<queue>

#define x first
#define y second

using namespace std;

typedef pair<int,string> PIS;

int f(string m)//估计函数
{
    int dt=0;
    for(int i=0;i<9;i++)//这里1~8对应的下标为0~7
    if(m[i]!='x')
    {
        int t=m[i]-'1';//对应下标
        dt=dt+abs(i/3-t/3)+abs(i%3-t%3);//曼哈顿距离
    }
    return dt;//返回总曼哈顿距离
}

string bfs(string start)
{
    string end="12345678x";//终点

    unordered_map<string,int> d;//存储距离
    priority_queue<PIS, vector<PIS>, greater<PIS>> heap;//小根堆,将元素的估计终点距离从小到大排序
    unordered_map<string,pair<string,char>> last;//存储一个元素由哪种状态,经过哪种操作得来,跟前面几题一样

    heap.push({f(start),start});//加入起点
    d[start]=0;//起点到起点的距离为0
    //要将操作数组与坐标变化数组一一对应
    char oper[]="udlr";
    int dx[4]={-1,1,0,0},dy[4]={0,0,-1,1};

    while(heap.size())
    {
        auto t=heap.top();//队头
        heap.pop();//弹出
        string state=t.y;//记录

        if(t.y==end) break;//终点出列的话就退出

        int x,y;//查找x的横纵坐标
        for(int i=0;i<9;i++)
        if(state[i]=='x')
        {
            x=i/3,y=i%3;
            break;
        }

        string init=state;
        for(int i=0;i<4;i++)
        {
            int a=x+dx[i],b=y+dy[i];
            if(a<0||a>=3||b<0||b>=3) continue;//越界就跳过
            swap(state[a*3+b],state[x*3+y]);//交换下标位置
            if(!d.count(state)||d[state]>d[init]+1)//如果没有被记录或者小于记录值
            {
                d[state]=d[init]+1;//更新距离
                heap.push({f(state)+d[state],state});//加入堆中
                last[state]={init,oper[i]};//标记由哪种状态转移而来,并且记录执行的操作
            }
            state=init;//因为要扩展到四个方向,所以要还原
        }
    }

    string ans;
    //跟前面几题原来相同
    while(end!=start)
    {
        ans+=last[end].y;
        end=last[end].x;
    }
    reverse(ans.begin(),ans.end());//将其反转
    return ans;
}

int main()
{
    string start,x,c;
    while(cin>>c)//这样输入可以忽视空格
    {
        start+=c;
        if(c!="x") x+=c;
    }

    int res=0;//统计逆序对的数量
    for(int i=0;i<8;i++)
     for(int j=i+1;j<8;j++)
      if(x[i]>x[j]) 
       res++;

    if(res%2) printf("unsolvable\n");//如果逆序对为奇数,就不可能抵达终点
    else cout<<bfs(start)<<endl;//输出答案

    return 0;
}