当前位置:   article > 正文

代码随想录算法训练营day76 | Floyd 算法精讲、A * 算法精讲

代码随想录算法训练营day76 | Floyd 算法精讲、A * 算法精讲

本次题目来自于卡码网

 ​​97. 小明逛公园 (Floyd 算法精讲)

1、确定dp数组以及下标的含义

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

2、确定递推公式

分两种情况:

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

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

第二种情况,grid[i][j][k] = 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])

3、dp数组如何初始化

把k 赋值为 0,本题 节点0 是无意义的,节点是从1 到 n

初始化代码

  1. vector<vector<vector<int>>> grid(n + 1, vector<vector<int>>(n + 1, vector<int>(n + 1, 10005))); // C++定义了一个三位数组,10005是因为边的最大距离是10^4
  2. for(int i = 0; i < m; i++){
  3. cin >> p1 >> p2 >> val;
  4. grid[p1][p2][0] = val;
  5. grid[p2][p1][0] = val; // 注意这里是双向图
  6. }

grid数组中其他元素数值应该初始化多少呢? 本题求的是最小值,所以输入数据没有涉及到的节点的情况都应该初始为一个最大数。

4、确定遍历顺序

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

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

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

所以遍历k 的for循环一定是在最外面,这样才能一层一层去遍历

5、举例推导dp数组

  1. if __name__ == '__main__':
  2. n, m = map(int, input().split())
  3. grid = [[[10005] * (n + 1) for _ in range(n + 1)] for _ in range(n + 1)] # 因为边的最大距离是10^4
  4. for i in range(m):
  5. p1, p2, val = map(int, input().split())
  6. grid[p1][p2][0] = val
  7. grid[p2][p1][0] = val # 双向图
  8. # 开始 floyd
  9. for k in range(1, n + 1):
  10. for i in range(1, n + 1):
  11. for j in range(n + 1):
  12. grid[i][j][k] = min(grid[i][j][k - 1], grid[i][k][k - 1] + grid[k][j][k - 1])
  13. # 输出结果
  14. z = int(input())
  15. for _ in range(z):
  16. start, end = map(int, input().split())
  17. if grid[start][end][n] == 10005:
  18. print(-1)
  19. else:
  20. print(grid[start][end][n])

空间优化

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

又由于本层计算中,使用了本层计算过的 grid[i][k] 和 grid[k][j] 是没问题的。那么就没必要区分,grid[i][k] 和 grid[k][j] 是 属于 k - 1 层的呢,还是 k 层的。

  1. if __name__ == '__main__':
  2. n, m = map(int, input().split())
  3. grid = [[10005] * (n + 1) for _ in range(n + 1)] # 因为边的最大距离是10^4
  4. for i in range(m):
  5. p1, p2, val = map(int, input().split())
  6. grid[p1][p2] = val
  7. grid[p2][p1] = val # 双向图
  8. # 开始 floyd
  9. for k in range(1, n + 1):
  10. for i in range(1, n + 1):
  11. for j in range(n + 1):
  12. grid[i][j] = min(grid[i][j], grid[i][k] + grid[k][j])
  13. # 输出结果
  14. z = int(input())
  15. for _ in range(z):
  16. start, end = map(int, input().split())
  17. if grid[start][end] == 10005:
  18. print(-1)
  19. else:
  20. print(grid[start][end])

126. 骑士的攻击 (A * 算法精讲)

加入了启发式函数,使用了优先队列,优先队列中自定义了比较函数(https://www.cnblogs.com/xrszff/p/14783972.html)

  1. import heapq
  2. # F = G + H
  3. # G = 从起点到该节点路径消耗
  4. # H = 该节点到终点的预估消耗
  5. class Knight:
  6. def __init__(self):
  7. self.x = 0
  8. self.y = 0
  9. self.g = 0
  10. self.h = 0
  11. self.f = 0
  12. def __lt__(self, other): # 自定义比较函数
  13. return self.f < other.f
  14. def heuristic(k): # 欧拉距离
  15. return (k.x - b1) * (k.x - b1) + (k.y - b2) * (k.y - b2) # 统一不开根号,这样可以提高精度
  16. def astar(k):
  17. heapq.heappush(que, k)
  18. while que:
  19. cur = heapq.heappop(que)
  20. if cur.x == b1 and cur.y == b2:
  21. break
  22. for i in range(8):
  23. next = Knight()
  24. next.x = cur.x + dir[i][0]
  25. next.y = cur.y + dir[i][1]
  26. if next.x < 1 or next.x > 1000 or next.y < 1 or next.y > 1000:
  27. continue
  28. if moves[next.x][next.y] == 0:
  29. moves[next.x][next.y] = moves[cur.x][cur.y] + 1
  30. # 开始计算F
  31. next.g = cur.g + 5 # 统一不开根号,这样可以提高精度,马走日,1 * 1 + 2 * 2 = 5
  32. next.h = heuristic(next)
  33. next.f = next.g + next.h
  34. heapq.heappush(que, next)
  35. if __name__ == '__main__':
  36. dir = [(-2, -1), (-2, 1), (-1, 2), (1, 2), (2, 1), (2, -1), (1, -2), (-1, -2)]
  37. que = []
  38. heapq.heapify(que)
  39. n = int(input())
  40. for _ in range(n):
  41. a1, a2, b1, b2 = map(int, input().split())
  42. moves = [[0] * 1001 for _ in range(1001)] # 每次重新开辟空间
  43. start = Knight()
  44. start.x = a1
  45. start.y = a2
  46. start.g = 0
  47. start.h = heuristic(start)
  48. start.f = start.g + start.h
  49. astar(start)
  50. while que:
  51. heapq.heappop(que) # 队列清空
  52. print(moves[b1][b2])

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/从前慢现在也慢/article/detail/821957
推荐阅读
相关标签
  

闽ICP备14008679号