【代码随想录练习营第42期 Day61打卡 - 图论Part11 - Floyd 算法与A * 算法

目次

一、Floyd算法与A * 算法
1、Floyd算法
头脑
伪代码
2、 A * 算法
头脑
伪代码
二、经典标题
标题一：卡码网 97. 小明逛公园
标题链接
题解：Floyd 算法
标题二：卡码网 127. 骑士的攻击
标题链接
 题解：A * 算法（A-Star）
三、小结

---

一、Floyd算法与A * 算法

1、Floyd算法

头脑

Floyd算法的根本头脑是渐渐迭代地思量图中的全部顶点，并更新恣意两点之间的最短路径长度。在每一步迭代中，算法查抄全部顶点对（i，j），并通过当前思量的顶点k，看是否可以大概找到一条从i到j的更短路径。具有可以大概找到图中恣意两点间的最短路径的上风，恰当办理多源最短路，即求多个出发点到多个止境的多条最短路径。
Floyd算法焦点头脑是动态规划。
伪代码

1. function floydWarshall(weights, V):
2.     let dist be a V x V array
3.     for i from 0 to V-1:
4.         for j from 0 to V-1:
5.             if i == j:
6.                 dist[i][j] = 0
7.             else if there is an edge from i to j:
8.                 dist[i][j] = weight of the edge from i to j
9.             else:
10.                 dist[i][j] = INFINITY
12.     for k from 0 to V-1:
13.         for i from 0 to V-1:
14.             for j from 0 to V-1:
15.                 if dist[i][k] + dist[k][j] < dist[i][j]:
16.                     dist[i][j] = dist[i][k] + dist[k][j]
18.     return dist

复制代码

2、 A * 算法

入门发起观看视频：【A*寻路算法详解 #A星 #开导式搜刮】
头脑

A算法（A-Star算法）是一种在图形平面上，有多个节点的路径中，探求一条从出发点到止境的最短路径的算法。它的计划头脑告急团结了现实代价和开导式估计，以高效地搜刮图形中的最优路径。
焦点头脑是将开导式搜刮和最佳优先搜刮团结起来，以探求从起始点到目标点的最短路径。
伪代码

1. function A*(start, goal)
2.     open_list = priority_queue() // 优先队列，按f值排序
3.     start.g = 0
4.     start.h = heuristic(start, goal)
5.     start.f = start.g + start.h
6.     start.parent = null
7.     open_list.add(start)
9.     while not open_list.is_empty()
10.         current = open_list.pop() // 取出f值最小的节点
11.         if current == goal
12.             return reconstruct_path(current)
14.         closed_list.add(current) // 将当前节点加入封闭列表
16.         for neighbor in neighbors(current)
17.             if neighbor in closed_list
18.                 continue
19.             tentative_g = current.g + distance(current, neighbor)
20.             if neighbor not in open_list or tentative_g < neighbor.g
21.                 neighbor.parent = current
22.                 neighbor.g = tentative_g
23.                 neighbor.h = heuristic(neighbor, goal)
24.                 neighbor.f = neighbor.g + neighbor.h
25.                 if neighbor not in open_list
26.                     open_list.add(neighbor)
28.     return null // 没有找到路径
30. function reconstruct_path(node)
31.     path = []
32.     while node is not null
33.         path.prepend(node)
34.         node = node.parent
35.     return path.reverse() // 反转路径以从起点到终点
37. function heuristic(node, goal)
38.     // 返回从node到goal的启发式估计值
39. end function
41. function neighbors(node)
42.     // 返回node的邻居节点列表
43. end function
45. function distance(node1, node2)
46.     // 返回从node1到node2的实际距离
47. end function

复制代码

二、经典标题

标题一：卡码网 97. 小明逛公园

标题链接

97. 小明逛公园 (kamacoder.com)
   标题形貌
  小明喜好去公园散步，公园内摆设了许多的景点，相互之间通过小路毗连，小明渴望在观看景点的同时，可以大概节流体力，走最短的路径。 
  
  给定一个公园景点图，图中有 N 个景点（编号为 1 到 N），以及 M 条双向门路毗连着这些景点。每条门路上行走的间隔都是已知的。
  
  小明有 Q 个观景筹划，每个筹划都有一个出发点 start 和一个止境 end，体现他想从景点 start 前去景点 end。由于小明渴望节流体力，他想知道每个观景筹划中从出发点到止境的最短路径长度。 请你资助小明盘算出每个观景筹划的最短路径长度。
  输入形貌
  第一行包罗两个整数 N, M, 分别体现景点的数量和门路的数量。 
  接下来的 M 行，每行包罗三个整数 u, v, w，体现景点 u 和景点 v 之间有一条长度为 w 的双向门路。 
  接下里的一行包罗一个整数 Q，体现观景筹划的数量。 
  接下来的 Q 行，每行包罗两个整数 start, end，体现一个观景筹划的出发点和止境。
  输出形貌
  对于每个观景筹划，输出一行体现从出发点到止境的最短路径长度。假如两个景点之间不存在路径，则输出 -1。
  输入示例

1. 7 3
2. 2 3 4
3. 3 6 6
4. 4 7 8
5. 2
6. 2 3
7. 3 4

复制代码

输出示例

1. 4
2. -1

复制代码

提示信息
  从 2 到 3 的路径长度为 4，3 到 4 之间并没有门路。
  1 <= N, M, Q <= 1000.
  题解：Floyd 算法

关键在于Floyd算法的实现，即：
   使用三重循环来实现Floyd算法：
  外层循环变量 k 代表中心节点，内两层循环变量 i 和 j 分别代表出发点和止境。
  在每一轮循环中，查抄通过中心节点 k 从 i 到 j 的路径是否比当前已知的路径更短，假如是，则更新 grid[j]。
  代码实现：

1. for (int k = 1; k <= n; k++) // k代表中间节点
2.     {
3.         for (int i = 1; i <= n; i++) // i代表起点
4.         {
5.             for (int j = 1; j <= n; j++) // j代表终点
6.             {
7.                 grid[i][j] = min(grid[i][j], grid[i][k] + grid[k][j]); // 更新i到j的最短路径，如果通过k的路径更短，则更新
8.             }
9.         }
10.     }

复制代码

完备代码如下：

1. #include <bits/stdc++.h>using namespace std;int main(){    int n, m, p1, p2, val;    cin >> n >> m;    vector<vector<int>> grid(n + 1, vector<int>(n + 1, 10005)); // 创建一个二维向量grid来存储图的毗连矩阵，由于边的最大间隔为10**4    // 读取m条边的信息，并更新毗连矩阵    for (int i = 0; i < m; i++)    {        cin >> p1 >> p2 >> val;        grid[p1][p2] = val;        grid[p2][p1] = val; // 留意这里是双向图：必要思量两个方向    }    // 开始 floyd 算法    for (int k = 1; k <= n; k++) // k代表中间节点
2.     {
3.         for (int i = 1; i <= n; i++) // i代表起点
4.         {
5.             for (int j = 1; j <= n; j++) // j代表终点
6.             {
7.                 grid[i][j] = min(grid[i][j], grid[i][k] + grid[k][j]); // 更新i到j的最短路径，如果通过k的路径更短，则更新
8.             }
9.         }
10.     }    // 输出结果    int Q, start, end;    cin >> Q;    while (Q--)    {        cin >> start >> end;        if (grid[start][end] == 10005) // 假如最短路径长度仍然是初始值，体现没有路径            cout << -1 << endl;        else            cout << grid[start][end] << endl;    }    return 0;}

复制代码

标题二：卡码网 127. 骑士的攻击

标题链接

127. 骑士的攻击 (kamacoder.com)
   标题形貌
  在象棋中，马和象的移动规则分别是“马走日”和“象走田”。现给定骑士的起始坐标和目标坐标，要求根据骑士的移动规则，盘算从出发点到达目标点所需的最短步数。
  
  棋盘巨细 1000 x 1000（棋盘的 x 和 y 坐标均在 [1, 1000] 区间内，包罗边界）
  输入形貌
  第一行包罗一个整数 n，体现测试用例的数量，1 <= n <= 100。
  接下来的 n 行，每行包罗四个整数 a1, a2, b1, b2，分别体现骑士的起始位置 (a1, a2) 和目标位置 (b1, b2)。
  输出形貌
  输出共 n 行，每行输出一个整数，体现骑士从出发点到目标点的最短路径长度。
  输入示例

1. 6
2. 5 2 5 4
3. 1 1 2 2
4. 1 1 8 8
5. 1 1 8 7
6. 2 1 3 3
7. 4 6 4 6

复制代码

输出示例

1. 2
2. 4
3. 6
4. 5
5. 1
6. 0

复制代码

提示信息
  骑士移动规则如图，赤色是起始位置，黄色是骑士可以走的地方。
  
  
  
  

   题解：A * 算法（A-Star）

关键在于A*算法实现的部门：
   在astar函数中，使用优先队列来存储当前的Knight对象；
  循环直到优先队列为空，即全部大概的路径都被查抄过；
  在每次循环中，从优先队列中取出F值最小的Knight对象，并查抄是否到达目标位置；
  假如未到达目标位置，则遍历8个大概的方向，盘算下一个位置的坐标，并查抄是否越界或已经被访问过；
  假如下一个位置合法且未被访问过，则更新路径斲丧，盘算F值，并将其到场优先队列；
  当到达目标位置时，循环竣事。
  实当代码：

1. void astar(const Knight &k)
2. {
3.     Knight cur, next;
4.     que.push(k);
5.     while (!que.empty())
6.     {
7.         cur = que.top();
8.         que.pop();
9.         if (cur.x == b1 && cur.y == b2)
10.             break;
11.         for (int i = 0; i < 8; i++) // 遍历骑士的8个可能移动方向
12.         {
13.             // 得到下一个位置的坐标
14.             next.x = cur.x + dir[i][0];
15.             next.y = cur.y + dir[i][1];
16.             if (next.x < 1 || next.x > 1000 || next.y < 1 || next.y > 1000) // 如果下一个位置越界，则跳过
17.                 continue;
18.             if (!moves[next.x][next.y]) // 如果下一个位置没有被访问过
19.             {
20.                 moves[next.x][next.y] = moves[cur.x][cur.y] + 1; // 更新下一个位置的路径消耗
21.                 // 开始计算F
22.                 next.g = cur.g + 5;       // 统一不开根号，这样可以提高精度，马走日，1 * 1 + 2 * 2 = 5
23.                 next.h = Heuristic(next); // 计算当前节点到终点的预估消耗
24.                 next.f = next.g + next.h; // 计算F值
25.                 que.push(next);           // 将下一个位置的Knight对象加入优先队列
26.             }
27.         }
28.     }
29. }

复制代码

 完备代码实现：

1. #include <bits/stdc++.h>using namespace std;int moves[1001][1001];                                              // 界说一个二维数组moves，用于存储骑士从出发点到当前位置的移动步数int dir[8][2] = {-2, -1, -2, 1, -1, 2, 1, 2, 2, 1, 2, -1, 1, -2, -1, -2}; // 界说一个方向数组dir，用于存储骑士大概的移动方向int b1, b2;struct Knight // 界说一个结构体Knight，用于存储骑士的当前位置和路径斲丧等信息{    int x, y;    int g, h, f;    bool operator<(const Knight &k) const // 重载运算符，用于优先队列的排序    {        return k.f < f; // 从小到大排序    }};priority_queue<Knight> que; // 界说一个优先队列que，用于存储Knight对象，并按照f值排序int Heuristic(const Knight &k) // 欧拉间隔{    return (k.x - b1) * (k.x - b1) + (k.y - b2) * (k.y - b2); // 同一不开根号，如允许以进步精度}// 实行A*算法：参数k是当前的Knight对象void astar(const Knight &k)
2. {
3.     Knight cur, next;
4.     que.push(k);
5.     while (!que.empty())
6.     {
7.         cur = que.top();
8.         que.pop();
9.         if (cur.x == b1 && cur.y == b2)
10.             break;
11.         for (int i = 0; i < 8; i++) // 遍历骑士的8个可能移动方向
12.         {
13.             // 得到下一个位置的坐标
14.             next.x = cur.x + dir[i][0];
15.             next.y = cur.y + dir[i][1];
16.             if (next.x < 1 || next.x > 1000 || next.y < 1 || next.y > 1000) // 如果下一个位置越界，则跳过
17.                 continue;
18.             if (!moves[next.x][next.y]) // 如果下一个位置没有被访问过
19.             {
20.                 moves[next.x][next.y] = moves[cur.x][cur.y] + 1; // 更新下一个位置的路径消耗
21.                 // 开始计算F
22.                 next.g = cur.g + 5;       // 统一不开根号，这样可以提高精度，马走日，1 * 1 + 2 * 2 = 5
23.                 next.h = Heuristic(next); // 计算当前节点到终点的预估消耗
24.                 next.f = next.g + next.h; // 计算F值
25.                 que.push(next);           // 将下一个位置的Knight对象加入优先队列
26.             }
27.         }
28.     }
29. }int main(){    int n, a1, a2;    cin >> n;    while (n--)    {        cin >> a1 >> a2 >> b1 >> b2;        memset(moves, 0, sizeof(moves)); // 每次循环都初始化moves数组为0，确保每个骑士题目都有独立的路径记载        // 界说出发点Knight对象start        // F = G + H        // G = 从出发点到该节点路径斲丧        // H = 该节点到止境的预估斲丧        Knight start;        start.x = a1;        start.y = a2;        start.g = 0;        start.h = Heuristic(start);        start.f = start.g + start.h;        // 实行A*算法，以出发点Knight对象start为出发点        astar(start);        // 实行A*算法后，清空优先队列que，以便下一次循环使用        while (!que.empty())            que.pop();        cout << moves[b1][b2] << endl; // 输出本次从出发点到目标点的路径斲丧，即moves[b1][b2]    }    return 0;}

复制代码

三、小结

这算是图论末了的内容了，难度很大，个人感觉只是明白了大概意思，却难以代码实现，后边二刷的时间会强化明白，继承加油！