猫史档案馆

注：本人超级蒟蒻

如果有误望指正

 

之前总是在enazo.cn玩信奥你画我猜的时候出到这个题目，很好奇是什么

今天正好有时间，就去搜了搜看

简单来说（个人理解），A* = Dijkstra + 贪婪最佳优先搜索（启发式搜索）

我们可以从BFS一步步进化成A* =)

 

对于BFS，它是把所有能走的点都走。来找最短的路径。

这种算法对于平常的题还是很好用的

但如果，有一道题，要求你从起点走到终点，中间还有不同的地形，每个地形的行走消耗不同，问最少消耗

这种情况大概就不能bfs了

 

Dijkstra就上场了。Dijkstra对于bfs，多用了优先队列，同时加了一个优先值(priority)，可以使算法能优先遍历那些花费少的。如果画成图，可以看到花费高的地形的推进速度会比花费小的地形推进速度要慢。这样就能求出最小花费。

 

但不难发现，如果给Dijkstra或者bfs遍历过的格子涂上红色，你就会看见一片红的壮观景象

 

也就是说，Dijkstra浪费了许多点

 

接下来，启发式搜索就来了。值得注意的是，启发式搜索并不能求出最短路。但其走的点是明显比Dijkstra少的。

因为他会优先走往终点方向的点，可以避免不必要的浪费。

 

那如果，某一题的数据范围超大Dijkstra超时，还让你求最短路咋办？

坐在角落里很少被人看见的A*就能登场了。

（A*：苍天啊！！！我这是积了八辈子的德吗，终于能用到我了啊！）

啊没错，A*用的情况很少

洛谷上A*标签甚至只有四五题（至少比那些一题没有的好）

 

A*也是使用优先队列，和启发式还有迪某一样

其优先值为 到终点的一个距离* + 花费

*距离： 这个其实我也没太懂，但是按文中举的例子，从起点走到终点，中间有墙阻隔这个例子来说，这里的距离就是曼哈顿距离。大概就是启发函数的值吧

还需要注意，和bfs不同的是，一个点是可以被多次遍历的，如果再一次遍历到这个点的时候，其花费要小于原花费，就要重新设置当前点的花费值。

这样就可以既不浪费，又能得到最短路了！

 

A*算法大概就是这样，下面放下我那喵循环的代码

求求大佬帮我看下。

洛谷P4467，k短路

我觉得可能是我memset成2147483喵7的原因，我实在想不到启发函数

//
//  main.cpp
//  A*
//
//  Created by 就不告诉你 on 2023/8/7.
//

#include <iostream>
#include <queue>
#include <string>
#include <vector>
using namespace std;


struct Ans{
    string path;
    int length;
} anses[1001];

priority_queue<pair<int, int>> pq;

int roads_in_cities[51][51];
int from[1000001];
int costs[1000001];
bool vis[501];

vector<int> refrom;

int main(int argc, const char * argv[]) {
    int n, m, k, a, b;
    scanf("%d%d%d%d%d", &n, &m, &k, &a, &b);
    int l, r, x;
    memset(roads_in_cities, 2147483喵7, sizeof(roads_in_cities));
    for(int i=0;i<m;i++){
        scanf("%d%d%d", &l, &r, &x);
        roads_in_cities[l][r]=k; //邻接矩阵，记录长度
        roads_in_cities[r][l]=k;
    }
    pq.push(make_pair(0, a));
    int ans=0;
    pair<int, int> top;
    //A*算法
    from[a]=-1; //没有来的地方
    vis[a]=1; //走过了起点
    costs[a]=0;
    int new_cost;
    int priority;
    while(!pq.empty()){
        top = pq.top();
        pq.pop();
        if(top.second==b){ //到了终点
            ans++;
            if(ans==k){
                break;
            }
            continue;
        }
        for(int i=0;i<n;i++){ //对每个城市进行遍历
            if((!roads_in_cities[top.second][i])) continue;
            new_cost = costs[top.second]+roads_in_cities[top.second][i];
            if(vis[i]==0||new_cost<costs[i]){
                costs[i]=new_cost;
                priority = new_cost+roads_in_cities[b][i];
                pq.push(make_pair(priority, i));
                from[i]=top.second;
                vis[i]=1;
            }
        }
    }
//    cout<<1<<endl;
    int f=b;
    while(from[f]!=a){
        refrom.push_back(f);
        f=from[f];
    }
    refrom.push_back(a);
    while(refrom.size()>1){
        printf("%d-", refrom[refrom.size()-1]);
        refrom.erase(refrom.end());
    }
    printf("%d", refrom[0]);
    return 0;
}