LeetCodeCampsDay62图论part11

Floyd算法与A*算法

97.小明逛公园

题目描述

小明喜欢去公园散步，公园内布置了许多的景点，相互之间通过小路连接，小明希望在观看景点的同时，能够节省体力，走最短的路径。

给定一个公园景点图，图中有 N 个景点（编号为 1 到 N），以及 M 条双向道路连接着这些景点。每条道路上行走的距离都是已知的。

小明有 Q 个观景计划，每个计划都有一个起点 start 和一个终点 end，表示他想从景点 start 前往景点 end。由于小明希望节省体力，他想知道每个观景计划中从起点到终点的最短路径长度。请你帮助小明计算出每个观景计划的最短路径长度。

输入描述

第一行包含两个整数 N, M, 分别表示景点的数量和道路的数量。

接下来的 M 行，每行包含三个整数 u, v, w，表示景点 u 和景点 v 之间有一条长度为 w 的双向道路。

接下里的一行包含一个整数 Q，表示观景计划的数量。

接下来的 Q 行，每行包含两个整数 start, end，表示一个观景计划的起点和终点。

输出描述

对于每个观景计划，输出一行表示从起点到终点的最短路径长度。如果两个景点之间不存在路径，则输出 -1。

输入示例

输出示例

1
2

4
-1

提示信息

从 2 到 3 的路径长度为 4，3 到 4 之间并没有道路。

1 <= N, M, Q <= 1000.

1 <= w <= 10000.

Floyd思路

在这之前我们讲解过，dijkstra朴素版、dijkstra堆优化、Bellman算法、Bellman队列优化（SPFA）都是单源最短路，即只能有一个起点。

而本题是多源最短路，即求多个起点到多个终点的多条最短路径。

Floyd 算法对边的权值正负没有要求，都可以处理。

Floyd的核心思想是动态规划

例如我们再求节点1 到节点9 的最短距离，用二维数组来表示即：grid[1][9]，如果最短距离是10 ，那就是 grid[1][9] = 10。

那节点1 到节点9 的最短距离是不是可以由节点1 到节点5的最短距离 + 节点5到节点9的最短距离组成呢？

即 grid[1][9] = grid[1][5] + grid[5][9]

节点1 到节点5的最短距离是不是可以有节点1 到节点3的最短距离 + 节点3 到节点5 的最短距离组成呢？

即 grid[1][5] = grid[1][3] + grid[3][5]

以此类推，节点1 到节点3的最短距离可以由更小的区间组成。

节点1 到节点9 的最短距离可以由节点1 到节点5的最短距离 + 节点5到节点9的最短距离组成，也可以有节点1 到节点7的最短距离 + 节点7 到节点9的最短距离的距离组成。

选择其中最小的一个即可

之前在讲解动态规划的时候，给出过动规五部曲：

确定dp数组（dp table）以及下标的含义
确定递推公式
dp数组如何初始化
确定遍历顺序
举例推导dp数组

dp数组下标与含义

grid[i][j][k] = m，表示 节点i 到节点j 以[1…k] 集合中的一个节点为中间节点的最短距离为m。

节点i 到节点j 的最短距离为m，这句话可以理解，但以[1…k]集合为中间节点就理解不了。

节点i 到节点j 的最短路径中一定是经过很多节点，那么这个集合用[1…k] 来表示。

反过来想，节点i 到节点j 中间一定经过很多节点，那么你能用什么方式来表述中间这么多节点呢？

所以这里的k不能单独指某个节点，k 一定要表示一个集合，即[1…k] ，表示节点1 到节点k 一共k个节点的集合。

后续可以优化成二维数组，到时可能更方便理解

递推公式

我们分两种情况：

节点i 到节点j 的最短路径经过节点k
节点i 到节点j 的最短路径不经过节点k

对于第一种情况，grid[i][j][k] = grid[i][k][k - 1] + grid[k][j][k - 1]

节点i 到节点k 的最短距离是不经过节点k，中间节点集合为[1…k-1]，所以表示为grid[i][k][k - 1]

节点k 到节点j 的最短距离也是不经过节点k，中间节点集合为[1…k-1]，所以表示为 grid[k][j][k - 1]

第二种情况，grid[i][j][k] = grid[i][j][k - 1]

如果节点i 到节点j的最短距离不经过节点k，那么中间节点集合[1…k-1]，表示为 grid[i][j][k - 1]

因为我们是求最短路，对于这两种情况自然是取最小值。

即： grid[i][j][k] = min(grid[i][k][k - 1] + grid[k][j][k - 1]， grid[i][j][k - 1])

dp初始化

grid[i][j][k] = m，表示节点i 到节点j 以[1…k] 集合为中间节点的最短距离为m。

刚开始初始化k 是不确定的。

例如题目中只是输入边（节点2 -> 节点6，权值为3），那么grid[2][6][k] = 3，k需要填什么呢？

把k 填成1，那如何上来就知道节点2 经过节点1 到达节点6的最短距离是多少呢。

所以 只能把k 赋值为 0，本题节点0 是无意义的，节点是从1 到 n。

这样我们在下一轮计算的时候，就可以根据 grid[i][j][0] 来计算 grid[i][j][1]，此时的 grid[i][j][1] 就是节点i 经过节点1 到达节点j 的最小距离了

grid数组是一个三维数组，那么我们初始化的数据在 i 与 j 构成的平层，如图：

红色的底部一层是我们初始化好的数据，注意：从三维角度去看初始化的数据很重要，下面我们在聊遍历顺序的时候还会再讲。

所以初始化代码：

vector<vector<vector<int>>> grid(n + 1, vector<vector<int>>(n + 1, vector<int>(n + 1, 10005)));  // C++定义了一个三位数组，10005是因为边的最大距离是10^4

for(int i = 0; i < m; i++){
    cin >> p1 >> p2 >> val;
    grid[p1][p2][0] = val;
    grid[p2][p1][0] = val; // 注意这里是双向图
}

grid数组中其他元素数值应该初始化多少呢？

本题求的是最小值，所以输入数据没有涉及到的节点的情况都应该初始为一个最大数。

这样才不会影响，每次计算去最小值的时候初始值对计算结果的影响。

所以grid数组的定义可以是：

1 2	// C++写法，定义了一个三位数组，10005是因为边的最大距离是10^4 vector<vector<vector<int>>> grid(n + 1, vector<vector<int>>(n + 1, vector<int>(n + 1, 10005)));

遍历顺序

从递推公式：grid[i][j][k] = min(grid[i][k][k - 1] + grid[k][j][k - 1]， grid[i][j][k - 1]) 可以看出，我们需要三个for循环，分别遍历i，j 和k

而 k 依赖于 k - 1， i 和j 的到并不依赖与 i - 1 或者 j - 1 等等。

那么这三个for的嵌套顺序应该是什么样的呢？

我们来看初始化，我们是把 k =0 的 i 和j 对应的数值都初始化了，这样才能去计算 k = 1 的时候 i 和 j 对应的数值。

这就好比是一个三维坐标，i 和j 是平层，而k 是垂直向上的。

遍历的顺序是从底向上一层一层去遍历。

所以遍历k 的for循环一定是在最外面，这样才能一层一层去遍历。如图：

至于遍历 i 和 j 的话，for 循环的先后顺序无所谓。

代码如下：

for (int k = 1; k <= n; k++) {
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            grid[i][j][k] = min(grid[i][j][k-1], grid[i][k][k-1] + grid[k][j][k-1]);
        }
    }
}

基于三维数组的Floyd

时间复杂度： O(n^3)
空间复杂度：O(n^2)

def main():
    n, m = map(int, input().split())

    graph = [[[10005] * (n + 1) for _ in range(n + 1)] for _ in range(n + 1)] 

    for _ in range(m):
        u, v, w = map(int, input().split())
        graph[u][v][0] = w
        graph[v][u][0] = w
    
    for k in range(1, n + 1):
        for i in range(1, n + 1):
            for j in range(1, n + 1):
                graph[i][j][k] = min(graph[i][j][k - 1], graph[i][k][k - 1] + graph[k][j][k - 1])

    q = int(input())

    for _ in range(q):
        s, t = map(int, input().split())
        print(graph[s][t][n] if graph[s][t][n] != 10005 else -1)
    

if __name__ == "__main__":
    main()

空间优化

这里我们可以做一下空间上的优化，从滚动数组的角度来看，我们定义一个 grid[n + 1][ n + 1][2] 这么大的数组就可以，因为k 只是依赖于 k-1的状态，并不需要记录k-2，k-3，k-4 等等这些状态。

那么我们只需要记录 grid[i][j][1] 和 grid[i][j][0] 就好，之后就是 grid[i][j][1] 和 grid[i][j][0] 交替滚动。

再进一步想，如果本层计算（本层计算即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][k] 和 grid[k][j] 是属于 k - 1 层的呢，还是 k 层的。

所以递归公式可以为：

1	grid[i][j] = min(grid[i][j], grid[i][k] + grid[k][j]);

基于二维数组的Floyd

时间复杂度： O(n^3)
空间复杂度：O(n^2)

def main():
    n, m = map(int, input().split())

    graph = [[10005 for _ in range(n + 1)] for _ in range(n + 1)] 

    for _ in range(m):
        u, v, w = map(int, input().split())
        graph[u][v] = w
        graph[v][u] = w
    

    for k in range(1, n + 1):
        for i in range(1, n + 1):
            for j in range(1, n + 1):
                graph[i][j] = min(graph[i][j], graph[i][k] + graph[k][j])


    q = int(input())

    for _ in range(q):
        s, t = map(int, input().split())
        print(graph[s][t] if graph[s][t] != 10005 else -1)
    

if __name__ == "__main__":
    main()

把k不放在最外层遍历是否可以？

难道遍历k 放在最里层就不行吗？

k 放在最里层，代码是这样：

for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= n; j++) {
        for (int k = 1; k <= n; k++) {
            grid[i][j][k] = min(grid[i][j][k-1], grid[i][k][k-1] + grid[k][j][k-1]);
        }
    }
}

此时就遍历了 j 与 k 形成一个平面，i 则是纵面，那遍历就是这样的：

而我们初始化的数据是 k 为0， i 和 j 形成的平面做初始化，如果以 k 和 j 形成的平面去一层一层遍历，就造成了递推公式用不上上一轮计算的结果，从而导致结果不对（初始化的部分是 i 与j 形成的平面，在初始部分有讲过）。

我再给大家举一个测试用例

就是图：

求节点1 到节点 2 的最短距离，运行结果是 10 ，但正确的结果很明显是3。

为什么呢？

因为 k 放在最里面，先就把节点1 和节点 2 的最短距离就确定了，后面再也不会计算节点 1 和节点 2的距离，同时也不会基于初始化或者之前计算过的结果来计算，即：不会考虑节点1 到节点3，节点3 到节点 4，节点4到节点2 的距离。

造成这一原因，是在三维立体坐标中，我们初始化的是 i 和 i 在k 为0 所构成的平面，但遍历的时候是以 j 和 k构成的平面以 i 为垂直方向去层次遍历。

而遍历k 的for循环如果放在中间呢，同样是 j 与k 行程一个平面，i 是纵面，遍历的也是这样：

同样不能完全用上初始化和上一层计算的结果。

根据这个情况再举一个例子：

图：

求节点1 到节点3 的最短距离，如果k循环放中间，程序的运行结果是 -1，也就是不能到达节点3。

在计算 grid[i][j][k] 的时候，需要基于 grid[i][k][k-1] 和 grid[k][j][k-1]的数值。

也就是计算 grid[1][3][2] （表示节点1 到节点3，经过节点2）的时候，需要基于 grid[1][2][1] 和 grid[2][3][1]的数值，而我们初始化，只初始化了 k为0 的那一层。

造成这一原因依然是在三维立体坐标中，我们初始化的是 i 和 j 在k 为0 所构成的平面，但遍历的时候是以 j 和 k构成的平面以 i 为垂直方向去层次遍历。

很多录友对于 floyd算法的遍历顺序搞不懂，其实是没有从三维的角度去思考，同时我把三维立体图给大家画出来，遍历顺序标出来，大家就很容易想明白，为什么 k 放在最外层才能用上初始化和上一轮计算的结果了。

127.骑士的攻击

题目描述

在象棋中，马和象的移动规则分别是“马走日”和“象走田”。现给定骑士的起始坐标和目标坐标，要求根据骑士的移动规则，计算从起点到达目标点所需的最短步数。

棋盘大小 1000 x 1000（棋盘的 x 和 y 坐标均在 [1, 1000] 区间内，包含边界）

输入描述

第一行包含一个整数 n，表示测试用例的数量，1 <= n <= 100。

接下来的 n 行，每行包含四个整数 a1, a2, b1, b2，分别表示骑士的起始位置 (a1, a2) 和目标位置 (b1, b2)。

输出描述

输出共 n 行，每行输出一个整数，表示骑士从起点到目标点的最短路径长度。

输入示例

输出示例

提示信息

骑士移动规则如图，红色是起始位置，黄色是骑士可以走的地方。

Astrar思路

Astar 是一种广搜的改良版。有的是 Astar是 dijkstra 的改良版。

其实只是场景不同而已我们在搜索最短路的时候，如果是无权图（边的权值都是1）那就用广搜，代码简洁，时间效率和 dijkstra 差不多（具体要取决于图的稠密）

如果是有权图（边有不同的权值），优先考虑 dijkstra。

而 Astar 关键在于启发式函数，也就是影响广搜或者 dijkstra 从容器（队列）里取元素的优先顺序。

以下，我用BFS版本的A * 来进行讲解。

在BFS中，我们想搜索，从起点到终点的最短路径，要一层一层去遍历。

如果使用A * 的话，其搜索过程是这样的，如图，图中着色的都是我们要遍历的点。

（上面两图中最短路长度都是8，只是走的方式不同而已）

大家可以发现 BFS 是没有目的性的一圈一圈去搜索，而 A * 是有方向性的去搜索。

看出 A * 可以节省很多没有必要的遍历步骤。

为了让大家可以明显看到区别，我将 BFS 和 A * 制作成可视化动图，大家可以自己看看动图，效果更好。

地址：https://kamacoder.com/tools/knight.html

那么 A * 为什么可以有方向性的去搜索，它的如何知道方向呢？

其关键在于启发式函数。

那么启发式函数落实到代码处，如果指引搜索的方向？

在本篇开篇中给出了BFS代码，指引搜索的方向的关键代码在这里：

1 2	int m=q.front();q.pop(); int n=q.front();q.pop();

从队列里取出什么元素，接下来就是从哪里开始搜索。

所以启发式函数要影响的就是队列里元素的排序！

这是影响BFS搜索方向的关键。

对队列里节点进行排序，就需要给每一个节点权值，如何计算权值呢？

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

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

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

起点达到目前遍历节点的距离 + 目前遍历的节点到达终点的距离就是起点到达终点的距离。

本题的图是无权网格状，在计算两点距离通常有如下三种计算方式：

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

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

选择哪一种距离计算方式也会导致 A * 算法的结果不同。

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

所以使用欧拉距离计算和广搜搜出来的最短路的节点数是一样的。（路径可能不同，但路径上的节点数是相同的）

我在制作动画演示的过程中，分别给出了曼哈顿、欧拉以及契比雪夫三种计算方式下，A * 算法的寻路过程，大家可以自己看看看其区别。

动画地址：https://kamacoder.com/tools/knight.html

计算出来 F 之后，按照 F 的大小，来选去出队列的节点。

可以使用优先级队列帮我们排好序，每次出队列，就是F最小的节点。

实现代码如下：（启发式函数采用欧拉距离计算方式）

代码

A * 算法的时间复杂度其实是不好去量化的，因为他取决于启发式函数怎么写。

最坏情况下，A * 退化成广搜，算法的时间复杂度是 O(n * 2)，n 为节点数量。

最佳情况，是从起点直接到终点，时间复杂度为 O(dlogd)，d 为起点到终点的深度。

因为在搜索的过程中也需要堆排序，所以是 O(dlogd)。

实际上 A * 的时间复杂度是介于最优和最坏情况之间，可以非常粗略的认为 A * 算法的时间复杂度是 O(nlogn) ，n 为节点数量。

A * 算法的空间复杂度 O(b ^ d) ,d 为起点到终点的深度，b 是图中节点间的连接数量，本题因为是无权网格图，所以节点间连接数量为 4。

import heapq

moves = [(1, 2), (2, 1), (-1, 2), (2, -1,), (1, -2), (-2, 1), (-1, -2), (-2, -1)]

# 计算两点之间的距离
def distance(a, b):
    return ((a[0] - b[0]) ** 2 + (a[1] - b[1]) ** 2) ** 0.5

# 
def bfs(start, end):
    q = [(distance(start, end), start)]

    step = {start: 0}

    while q:
        d, cur = heapq.heappop(q)
        if cur == end:
            return step[cur]
        for i, j in moves:
            nextx = cur[0] + i
            nexty = cur[1] + j
            if 1 <= nextx <= 1000 and 1 <= nexty <= 1000:
                # 
                step_new = step[cur] + 1
                new = (nextx, nexty)
                if step_new < step.get(new, float('inf')):
                    step[new] = step_new
                    # 将走new这个节点添加到堆，并进行排序
                    heapq.heappush(q, (distance(new, end) + step_new, new))
    
    return False

def main():
    n = int(input())

    for _ in range(n):
        a1, a2, b1, b2 = map(int, input().split())
        print(bfs((a1, a2), (b1, b2)))

if __name__ == "__main__":
    main()