大学网站建设,优化设计官方电子版,电商美工培训哪个学校好,seo优化培训公司Floyd 算法本题是经典的多源最短路问题.Floyd 算法对边的权值正负没有要求#xff0c;都可以处理。Floyd算法核心思想是动态规划。例如我们再求节点1 到 节点9 的最短距离#xff0c;用二维数组来表示即#xff1a;grid[1][9]#xff0c;如果最短距离是10 #xff0c;那就…Floyd 算法本题是经典的多源最短路问题.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的最短距离 可以由更小的区间组成。那么这样我们是不是就找到了子问题推导求出整体最优方案的递归关系呢。这里我们用 grid数组来存图那就把dp数组命名为 grid。grid[i][j][k] m表示 节点i 到 节点j 以[1...k] 集合中的一个节点为中间节点的最短距离为m。 这里的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])grid[i][j][k] m表示 节点i 到 节点j 以[1...k] 集合为中间节点的最短距离为m。刚开始初始化k 是不确定的。例如题目中只是输入边节点2 - 节点6权值为3那么grid[2][6][k] 3k需要填什么呢把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 的最小距离了。遍历的顺序是从底向上 一层一层去遍历。所以遍历k 的for循环一定是在最外面这样才能一层一层去遍历。kama97. 小明逛公园
题目描述小明喜欢去公园散步公园内布置了许多的景点相互之间通过小路连接小明希望在观看景点的同时能够节省体力走最短的路径。 给定一个公园景点图图中有 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.1 w 10000.#include bits/stdc.h
using namespace std;
int main()
{int n,m,p1,p2,val;cinnm;vectorvectorvectorint grid(n1,vectorvectorint(n1,vectorint(n1,10001)));while(m--){cinp1p2val;grid[p1][p2][0] val;//可以想象为一个三维的空间我们只初始化空间的底层后续遍历的时候从底层一层一层往上遍历。grid[p2][p1][0] val;//双向图}for(int k 1;kn;k)//注意这里先遍历k{for(int i 1;in;i){for(int j 1;jn;j){grid[i][j][k] min(grid[i][j][k-1],grid[i][k][k-1]grid[k][j][k-1]);}}}int q,start,end;cinq;while(q--){cinstartend;if(grid[start][end][n]10001)cout-1endl;else coutgrid[start][end][n]endl;}
}
A * 算法Astar 是一种 广搜的改良版。 有的是 Astar是 dijkstra 的改良版。其实只是场景不同而已 我们在搜索最短路的时候 如果是无权图边的权值都是1 那就用广搜代码简洁时间效率和 dijkstra 差不多 具体要取决于图的稠密如果是有权图边有不同的权值优先考虑 dijkstra。而 Astar 关键在于 启发式函数 也就是 影响 广搜或者 dijkstra 从 容器队列里取元素的优先顺序。大家可以发现 BFS 是没有目的性的 一圈一圈去搜索 而 A * 是有方向性的去搜索。 启发式函数 要影响的就是队列里元素的排序对队列里节点进行排序就需要给每一个节点权值如何计算权值呢每个节点的权值为F给出公式为F G HG起点达到目前遍历节点的距离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 * 算法的结果不同。本题采用欧拉距离才能最大程度体现 点与点之间的距离。相对了 普通BFSA * 算法只从 队列里取出 距离终点最近的节点。那么问题来了A * 在一次路径搜索中大量不需要访问的节点都在队列里会造成空间的过度消耗。IDA * 算法 对这一空间增长问题进行了优化关于 IDA * 算法本篇不再做讲解感兴趣的录友可以自行找资料学习。另外还有一种场景 是 A * 解决不了的。如果题目中给出 多个可能的目标然后在这多个目标中 选择最近的目标这种 A * 就不擅长了 A * 只擅长给出明确的目标 然后找到最短路径。如果是多个目标找最近目标特别是潜在目标数量很多的时候可以考虑 Dijkstra BFS 或者 Floyd。127. 骑士的攻击
题目描述在象棋中马和象的移动规则分别是“马走日”和“象走田”。现给定骑士的起始坐标和目标坐标要求根据骑士的移动规则计算从起点到达目标点所需的最短步数。棋盘大小 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提示信息骑士移动规则如图红色是起始位置黄色是骑士可以走的地方。#include bits/stdc.h
using namespace std;
int dir[8][2] {-2,-1,-2,1,-1,2,1,2,2,1,2,-1,1,-2,-1,-2};
int moves[1001][1001];
int b1, b2;
struct Knight
{int x,y;int f,g,h; //f g h; g为从起点到当前遍历节点的消耗h为当前遍历节点到终点的“预计“消耗bool operator (const Knight k) const{return k.f f;//后续的priority_queue会根据这个来找出f最小的。}
};
priority_queueKnight que;
int calDistance(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;for(int i 0;i8;i){next.x cur.x dir[i][0];next.y cur.y dir[i][1];if(next.x1||next.x1000||next.y1||next.y1000)continue;if(!moves[next.x][next.y]){moves[next.x][next.y] moves[cur.x][cur.y] 1;next.g cur.g 5;//马走日2*21*1.next.h calDistance(next);next.f next.g next.h;que.push(next);}}}
}
int main()
{int n,a1,a2;cinn;while(n--){cina1a2b1b2;memset(moves,0,sizeof(moves));Knight start;start.x a1;start.y a2;start.g 0;start.h calDistance(start);start.f start.g start.h;astar(start);while(!que.empty())que.pop();coutmoves[b1][b2]endl;}return 0;
}
