一个网站需要多少网页,网站建设得步骤,市场调研公司,2012 wordpress目录 一、Floyd算法与A * 算法
1、Floyd算法
思想
伪代码
2、 A * 算法
思想
伪代码
二、经典题目
题目一#xff1a;卡码网 97. 小明逛公园
题目链接
题解#xff1a;Floyd 算法
题目二#xff1a;卡码网 127. 骑士的攻击
题目链接 题解#xff1a;A * 算法卡码网 97. 小明逛公园
题目链接
题解Floyd 算法
题目二卡码网 127. 骑士的攻击
题目链接 题解A * 算法A-Star
三、小结 一、Floyd算法与A * 算法
1、Floyd算法
思想
Floyd算法的基本思想是逐步迭代地考虑图中的所有顶点并更新任意两点之间的最短路径长度。在每一步迭代中算法检查所有顶点对ij并通过当前考虑的顶点k看是否能够找到一条从i到j的更短路径。具有能够找到图中任意两点间的最短路径的优势适合解决多源最短路即求多个起点到多个终点的多条最短路径。
Floyd算法核心思想是动态规划。
伪代码
function floydWarshall(weights, V):let dist be a V x V arrayfor i from 0 to V-1:for j from 0 to V-1:if i j:dist[i][j] 0else if there is an edge from i to j:dist[i][j] weight of the edge from i to jelse:dist[i][j] INFINITYfor k from 0 to V-1:for i from 0 to V-1:for j from 0 to V-1:if dist[i][k] dist[k][j] dist[i][j]:dist[i][j] dist[i][k] dist[k][j]return dist2、 A * 算法
入门建议观看视频【A*寻路算法详解 #A星 #启发式搜索】
思想
A算法A-Star算法是一种在图形平面上有多个节点的路径中寻找一条从起点到终点的最短路径的算法。它的设计思想主要结合了实际代价和启发式估计以高效地搜索图形中的最优路径。
核心思想是将启发式搜索和最佳优先搜索结合起来以寻找从起始点到目标点的最短路径。
伪代码
function A*(start, goal)open_list priority_queue() // 优先队列按f值排序start.g 0start.h heuristic(start, goal)start.f start.g start.hstart.parent nullopen_list.add(start)while not open_list.is_empty()current open_list.pop() // 取出f值最小的节点if current goalreturn reconstruct_path(current)closed_list.add(current) // 将当前节点加入封闭列表for neighbor in neighbors(current)if neighbor in closed_listcontinuetentative_g current.g distance(current, neighbor)if neighbor not in open_list or tentative_g neighbor.gneighbor.parent currentneighbor.g tentative_gneighbor.h heuristic(neighbor, goal)neighbor.f neighbor.g neighbor.hif neighbor not in open_listopen_list.add(neighbor)return null // 没有找到路径function reconstruct_path(node)path []while node is not nullpath.prepend(node)node node.parentreturn path.reverse() // 反转路径以从起点到终点function heuristic(node, goal)// 返回从node到goal的启发式估计值
end functionfunction neighbors(node)// 返回node的邻居节点列表
end functionfunction distance(node1, node2)// 返回从node1到node2的实际距离
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。 输入示例 7 3
2 3 4
3 6 6
4 7 8
2
2 3
3 4 输出示例 4
-1 提示信息 从 2 到 3 的路径长度为 43 到 4 之间并没有道路。 1 N, M, Q 1000. 题解Floyd 算法
关键在于Floyd算法的实现即 使用三重循环来实现Floyd算法 外层循环变量 k 代表中间节点内两层循环变量 i 和 j 分别代表起点和终点。 在每一轮循环中检查通过中间节点 k 从 i 到 j 的路径是否比当前已知的路径更短如果是则更新 grid[i][j]。 代码实现 for (int k 1; k n; k) // k代表中间节点{for (int i 1; i n; i) // i代表起点{for (int j 1; j n; j) // j代表终点{grid[i][j] min(grid[i][j], grid[i][k] grid[k][j]); // 更新i到j的最短路径如果通过k的路径更短则更新}}}
完整代码如下
#include bits/stdc.h
using namespace std;int main()
{int n, m, p1, p2, val;cin n m;vectorvectorint grid(n 1, vectorint(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代表中间节点{for (int i 1; i n; i) // i代表起点{for (int j 1; j n; j) // j代表终点{grid[i][j] min(grid[i][j], grid[i][k] grid[k][j]); // 更新i到j的最短路径如果通过k的路径更短则更新}}}// 输出结果int Q, start, end;cin Q;while (Q--){cin start end;if (grid[start][end] 10005) // 如果最短路径长度仍然是初始值表示没有路径cout -1 endl;elsecout 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 行每行输出一个整数表示骑士从起点到目标点的最短路径长度。 输入示例 6
5 2 5 4
1 1 2 2
1 1 8 8
1 1 8 7
2 1 3 3
4 6 4 6 输出示例 2
4
6
5
1
0 提示信息 骑士移动规则如图红色是起始位置黄色是骑士可以走的地方。 题解A * 算法A-Star
关键在于A*算法实现的部分 在astar函数中使用优先队列来存储当前的Knight对象 循环直到优先队列为空即所有可能的路径都被检查过 在每次循环中从优先队列中取出F值最小的Knight对象并检查是否到达目标位置 如果未到达目标位置则遍历8个可能的方向计算下一个位置的坐标并检查是否越界或已经被访问过 如果下一个位置合法且未被访问过则更新路径消耗计算F值并将其加入优先队列 当到达目标位置时循环结束。 实现代码
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;for (int i 0; i 8; i) // 遍历骑士的8个可能移动方向{// 得到下一个位置的坐标next.x cur.x dir[i][0];next.y cur.y dir[i][1];if (next.x 1 || next.x 1000 || next.y 1 || next.y 1000) // 如果下一个位置越界则跳过continue;if (!moves[next.x][next.y]) // 如果下一个位置没有被访问过{moves[next.x][next.y] moves[cur.x][cur.y] 1; // 更新下一个位置的路径消耗// 开始计算Fnext.g cur.g 5; // 统一不开根号这样可以提高精度马走日1 * 1 2 * 2 5next.h Heuristic(next); // 计算当前节点到终点的预估消耗next.f next.g next.h; // 计算F值que.push(next); // 将下一个位置的Knight对象加入优先队列}}}
} 完整代码实现
#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_queueKnight 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)
{Knight cur, next;que.push(k);while (!que.empty()){cur que.top();que.pop();if (cur.x b1 cur.y b2)break;for (int i 0; i 8; i) // 遍历骑士的8个可能移动方向{// 得到下一个位置的坐标next.x cur.x dir[i][0];next.y cur.y dir[i][1];if (next.x 1 || next.x 1000 || next.y 1 || next.y 1000) // 如果下一个位置越界则跳过continue;if (!moves[next.x][next.y]) // 如果下一个位置没有被访问过{moves[next.x][next.y] moves[cur.x][cur.y] 1; // 更新下一个位置的路径消耗// 开始计算Fnext.g cur.g 5; // 统一不开根号这样可以提高精度马走日1 * 1 2 * 2 5next.h Heuristic(next); // 计算当前节点到终点的预估消耗next.f next.g next.h; // 计算F值que.push(next); // 将下一个位置的Knight对象加入优先队列}}}
}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;
}三、小结
这算是图论最后的内容了难度很大个人感觉只是理解了大概意思却难以代码实现后边二刷的时候会强化理解继续加油
