算法变革：BFS->Dijkstra->A*
BFS
1162. 地图分析
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| void BFS(){
int x, y, z;
int nx, ny, nz;
while(!que.empty()){
z = que.front();
que.pop();
vis[z] = true;
x = z/n;
y = z%n;
for(int i=0;i<4;i++){
nx = x+dir[i][0];
ny = y+dir[i][1];
nz = nx*n+ny;
if(nx>=0&&nx<n&&ny>=0&&ny<n&&!mp[nx][ny]&&!vis[nz]&&dis[nz]>dis[z]+1){
dis[nz] = dis[z] + 1;
que.push(nz);
}
}
ans = dis[z];
}
}
|
BFS只能用来解决无权图的最短路问题。
Dijkstra
743. 网络延迟时间
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| void Dijkstra(){
int mx = 0;
dis[0] = 0x3f3f3f3f;
for(int i=1;i<=m;i++){
mx = 0;
for(int j=1;j<=m;j++){
if(!vis[j]&&dis[j]<dis[mx]){
mx = j;
}
}
if(mx==0) break;
vis[mx] = true;
for(int j=1;j<=m;j++){
if(!vis[j]&&dis[j]>dis[mx]+mp[mx][j]){
dis[j] = dis[mx] + mp[mx][j];
}
}
ans = max(ans, dis[mx]);
}
}
|
Dijkstra可以解决带权图的最短路问题，但是普通版Dijkstra的时间复杂度是O(N^2)的，可以使用堆优化来降低复杂度。
堆优化Dijkstra
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
| struct node{
int num;
int dis;
bool operator <(const node &a) const{
return a.dis<dis;
}
};
void Dijkstra(){
priority_queue<node> que;
for(int j=1;j<=m;j++){
if(dis[j]==0){
que.push(node{j,0});
}
}
while(!que.empty()){
node tmp = que.top();
int u = tmp.num;
que.pop();
if(vis[u]) continue;
vis[u] = true;
for(int j=1;j<=m;j++){
if(!vis[j]&&dis[j]>dis[u]+mp[u][j]){
dis[j] = dis[u] + mp[u][j];
que.push(node{j,dis[j]});
}
}
ans = max(ans, dis[u]);
}
}
|
堆优化就是把每次寻找优先级最高的节点的操作用一个小顶堆代替，复杂度为O(nlogn)。
BestFirst(最佳优先搜索)
BestFirst就是把未搜索节点的优先级定义为该节点与目标节点之间的估计距离，如果这个估计距离刚好是真实距离，则BestFirst可以很快搜索到目标节点，但是大多数情况下估计距离时不准确的。这个估计距离是非常启发式的，比如曼哈顿距离等。如果估计距离设定的不准确，那么很可能得到的最短路是错误的。
A*
A*结合了Dijkstra和BestFirst，关键的区别也是对未搜索节点的优先级定义。A*将优先级定义为：f(n) = g(n) + h(n)。其中g(n)是该节点到其实节点的距离，h(n)是一个启发式函数表示该节点到目标节点之间的估计距离。
在极端情况下，如果h(n)=0则A*退化为Dijkstra，如果g(n)=0则A*退化为BestFirst。
如果h(n)小于该节点到目标节点的实际距离，则A*一定能找到最短路，但是h(n)越小，搜索的节点就越多，导致算法就越慢；
如果h(n)刚好等于该节点到目标节点的实际距离，则A*会以很快的速度找到最短路，但是在现实中很难找到这样的h(n);
如果h(n)大于该节点到目标节点的实际距离，则A*不一定能找到最短路，不过此时算法的速度会很快。