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

代码随想录算法训练

—day67

前言

今天是算法营的第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] 集合为中间节点的最短距离为m
    vector<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] = 0
            if (!moves[next.x][next.y]) {
                moves[next.x][next.y] = moves[cur.x][cur.y] + 1; //当前坐标+1步
                //计算F
                next.g = cur.g + 5; //马走日， 1*1 + 2*2 = 5
                next.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;
}

三、最短路算法总结

文章讲解

四大最短路算法：

• dijkstra朴素版
• dijkstra堆优化版
• Bellman_ford
• Bellman_ford 队列优化算法（又名SPFA）
• bellman_ford 算法判断负权回路
• bellman_ford之单源有限最短路
• Floyd 算法
• 启发式搜索：A * 算法

单源且边为正数：Dijkstra。
单源边可为负数： Bellman-Ford。
有负权回路：优先 Bellman-Ford。
有限节点最短路：优先Bellman-Ford。
多源点求最短路：Floyd。
游戏开发、地图导航、数据包路由： A * 算法。