代码随想录算法训练day67---图论系列11《Floyd 算法A*算法》

代码随想录算法训练

—day67

文章目录

代码随想录算法训练
前言
一、97. 小明逛公园—Floyd 算法
- 空间优化
二、127. 骑士的攻击---A * 算法
三、最短路算法总结

前言

今天是算法营的第67天，最后一天了！恭喜自己！
今日任务：
● Floyd 算法
●A*算法

一、97. 小明逛公园—Floyd 算法

卡码网题目链接
文章讲解

本题是经典的多源最短路问题。
Floyd 算法对边的权值正负没有要求，都可以处理。
Floyd算法核心思想是动态规划。
思路：
1、确定dp数组（dp table）以及下标的含义：
grid[i][j][k] = m，表示 节点i 到节点j 以[1…k] 集合中的一个节点为中间节点的最短距离为m。
2、确定递推公式：
①节点i 到节点j 的最短路径经过节点k：
i->k + k->j（因为都不经过k，所以是k-1）
grid[i][j][k] = grid[i][k][k - 1] + grid[k][j][k - 1]
②节点i 到节点j 的最短路径不经过节点k：
i->j 不经过k，grid[i][j][k] = grid[i][j][k - 1]
3、dp数组如何初始化：
把k 赋值为 0，本题节点0 是无意义的，节点是从1 到 n。
这样就可以由k=0推出k=1。
在这里插入图片描述
4、确定遍历顺序：
这就好比是一个三维坐标，i 和j 是平层，而k是垂直向上的。
遍历的顺序是从底向上一层一层去遍历。
所以遍历k 的for循环一定是在最外面，这样才能一层一层去遍历。

在这里插入图片描述

代码如下：

#include<iostream>
#include<vector>
#include<list>
using namespace std;int main() {int n, m, p1, p2, val;cin >> n >> m;//grid[i][j][k] = m，表示 节点i 到 节点j 以[1...k] 集合为中间节点的最短距离为mvector<vector<vector<int>>> grid(n + 1, vector<vector<int>>(n + 1, vector<int>(n + 1, 10005)));//初始化：k为0，存储初始的i->j的权值while (m--) {cin >> p1 >> p2 >> val;grid[p1][p2][0] = val;grid[p2][p1][0] = val;}//遍历三个变量，从ij平面向k延伸，所以k放在外面for (int k = 1; k <= n; k++) {for (int i = 1; i <= n; i++) {for (int j = 1; j <= n; j++) {//对于节点k，有经过k和不经过k两种情况，取两者最小值//经过k：i->k（不经过k，所以k-1） + k->j（不经过k，所以k-1）//不经过k:i->j（不经过k，所以k-1）grid[i][j][k] = min(grid[i][j][k - 1], grid[i][k][k - 1] + grid[k][j][k - 1]);}}}int z, start, end;cin >> z;while (z--) {cin >> start >> end;//最终结果就是考虑所有节点后，从start->end最短距离if (grid[start][end][n] == 10005) cout << -1 <<endl;else cout << grid[start][end][n] << endl;}
}

空间优化

从滚动数组的角度来看，我们定义一个 grid[n + 1][ n + 1][2]这么大的数组就可以，因为k 只是依赖于 k-1的状态。

再进一步想，如果去掉k维度，也就是本层计算gird[i][j] 用到了本层中刚计算好的 grid[i][k]行不行？

如果本层刚计算好的 grid[i][k] 比上一层（即k-1层）计算的 grid[i][k] 小，说明确实有 i 到 k 的更短路径，那么基于更小的 grid[i][k] 去计算 gird[i][j] 没有问题。

如果本层刚计算好的 grid[i][k] 比上一层（即k-1层）计算的 grid[i][k] 大，这不可能，因为这样也不会做更新 grid[i][k]的操作。

所以本层计算中，使用了本层计算过的 grid[i][k] 和 grid[k][j] 是没问题的。
所以递推公式：
grid[i][j] = min(grid[i][j], grid[i][k] + grid[k][j]);

整体代码如下：

#include<iostream>
#include<vector>
#include<list>
using namespace std;int main() {int n, m, p1, p2, val;cin >> n >> m;//grid[i][j][k] = m，表示 节点i 到 节点j 以[1...k] 集合为中间节点的最短距离为m//空间优化，计算grid[i][j]的时候用到grid[i][k]如果是本层的结果也没关系vector<vector<int>> grid(n + 1, vector<int>(n + 1, 10005));//初始化：k为0，存储初始的i->j的权值while (m--) {cin >> p1 >> p2 >> val;grid[p1][p2] = val;grid[p2][p1] = val;}//遍历三个变量，从ij平面向k延伸，所以k放在外面for (int k = 1; k <= n; k++) {for (int i = 1; i <= n; i++) {for (int j = 1; j <= n; j++) {//对于节点k，有经过k和不经过k两种情况，取两者最小值//经过k：i->k（k维度去掉） + k->j（k维度去掉）//不经过k:i->j（k维度去掉）grid[i][j] = min(grid[i][j], grid[i][k] + grid[k][j]);}}}int z, start, end;cin >> z;while (z--) {cin >> start >> end;//最终结果就是考虑所有节点后，从start->end最短距离if (grid[start][end] == 10005) cout << -1 <<endl;else cout << grid[start][end] << endl;}
}

二、127. 骑士的攻击—A * 算法

卡码网题目链接
文章讲解

如果直接用广搜的话，做了很多无用的遍历，会超时：
在这里插入图片描述
而Astar 是一种广搜的改良版。
Astar算法是通过一个启发式函数，来找到下一步应该往哪个方向走更好。

使用A * 的话，其搜索过程是这样的：
在这里插入图片描述
对队列里节点进行排序，就需要给每一个节点权值，

每个节点的权值为F，给出公式为：F = G + H

G：起点达到目前遍历节点的距离

H：目前遍历的节点到达终点的距离

在计算两点距离通常有如下三种计算方式：

1.曼哈顿距离，计算方式： d = abs(x1-x2)+abs(y1-y2)
2.欧氏距离（欧拉距离），计算方式：d = sqrt( (x1-x2)^2 + (y1-y2)^2 )
3.切比雪夫距离，计算方式：d = max(abs(x1 - x2), abs(y1 - y2))

x1, x2 为起点坐标，y1, y2 为终点坐标，abs 为求绝对值，sqrt 为求开根号，

选择哪一种距离计算方式也会导致 A * 算法的结果不同。
A * 算法并不是一个明确的最短路算法，A * 算法搜的路径如何，完全取决于启发式函数怎么写。

本题中，采用欧拉距离才能最大程度体现点与点之间的距离。

计算出F后，使用优先级队列按F的值从小到大排序。

代码如下：

#include<iostream>
#include<queue>
#include<string.h>
using namespace std;int moves[1001][1001]; //记录走到每个坐标的最少步数
int dir[8][2] = {-2,-1,-2,1,-1,2,1,2,2,1,2,-1,1,-2,-1,-2}; //马的八个方向位移
int b1, b2; //目标坐标
// F = G + H
// G = 从起点到该节点路径消耗
// H = 该节点到终点的预估消耗struct Knight {int x, y;int f, g, h;//重载运算符<,按f从小到大排序//例如a < b，如果b.f < a.f的话，返回true，表示a的优先级低//priority_queue是大顶堆，通过k.f < f 反转了比较方向，变成小顶堆bool operator < (const Knight& k) const {// 这里的第二个 const 表示 函数是常量成员函数：// 这个函数内部不能修改当前对象的成员（如 x, y, g, h, f）return k.f < f;}
};priority_queue<Knight> que;int Heuristic(const Knight& k) { //欧拉距离return (k.x - b1) * (k.x - b1) + (k.y - b2) *(k.y - b2); //统一不开根号，保持整数运算，避免浮点数的问题
}void astar(const Knight& k) {Knight cur, next;que.push(k);while (!que.empty()) {//取出排序后的位置来预测下一步cur = que.top(); que.pop();//到达终点退出if (cur.x == b1 && cur.y == b2) break;//遍历8个方向for (int i = 0; i < 8; i++) {next.x = cur.x + dir[i][0];next.y = cur.y + dir[i][1];//判断next坐标是否越界if (next.x < 1 || next.x > 1000 || next.y < 1 || next.y > 1000) continue;//没有访问过的坐标 moves[next.x][next.y] = 0if (!moves[next.x][next.y]) {moves[next.x][next.y] = moves[cur.x][cur.y] + 1; //当前坐标+1步//计算Fnext.g = cur.g + 5; //马走日， 1*1 + 2*2 = 5next.h = Heuristic(next);next.f = next.g + next.h;//放入队列中排序que.push(next);}}}
}int main() {int n, a1, a2;cin >> n;while (n--) {cin >> a1 >> a2 >> b1 >> b2;memset(moves, 0, sizeof(moves));//初始化起点的Knight，计算好起点的g,h,f再调用astar去计算最短距离Knight start;start.x = a1;start.y = a2;start.g = 0;start.h = Heuristic(start);start.f = start.g + start.h;astar(start);while(!que.empty()) que.pop();cout << moves[b1][b2] << endl;}return 0;
}