旅游网站建设策划方案书,数据集网站,经典设计产品,做led灯网站有哪些呢Floyd 算法
思路#xff1a;本题是多源最短路问题#xff0c;使用Floyd算法求解。Floyd 算法对边的权值正负没有要求#xff0c;核心思想是动态规划。 我们使用动规五部曲来理解和应用Floyd算法#xff1a;
1、确定dp数组#xff08;dp table#xff09;以及下标的含义…Floyd 算法
思路本题是多源最短路问题使用Floyd算法求解。Floyd 算法对边的权值正负没有要求核心思想是动态规划。 我们使用动规五部曲来理解和应用Floyd算法
1、确定dp数组dp table以及下标的含义 我们用 grid数组来存图那就把dp数组命名为 grid。grid[i][j][k] m表示 节点i 到 节点j 以[1…k] 集合为中间节点的最短距离为m。
2、确定递推公式 分两种情况 1节点i 到 节点j 的最短路径经过节点kgrid[i][j][k] grid[i][k][k - 1] grid[k][j][k - 1] 2节点i 到 节点j 的最短路径不经过节点kgrid[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即grid[i][j][0]。同时本题求的是最小值grid数组中其他元素数值应该初始为一个最大数。
4、确定遍历顺序 从递推公式grid[i][j][k] min(grid[i][k][k - 1] grid[k][j][k - 1] grid[i][j][k - 1]) 可以看出我们需要三个for循环分别遍历ij 和k。我们把 k 0 的 i 和j 对应的数值都初始化了再去计算 k 1 时 i 和 j 对应的数值。这就好比是一个三维坐标i 和j 是平层而k 是 垂直向上 的。遍历的顺序是从底向上 一层一层去遍历。所以遍历k 的for循环一定是在最外面。
5、举例推导dp数组
代码如下
import java.util.*;
public class Main{public static void main (String[] args) {Scanner scan new Scanner(System.in);int nscan.nextInt();int mscan.nextInt();int[][][] gridnew int[n1][n1][n1];for(int i0;in;i){for(int j0;jn;j){Arrays.fill(grid[i][j],Integer.MAX_VALUE);}}//添加边的权重初始化for(int i0;im;i){int lscan.nextInt();int rscan.nextInt();int valscan.nextInt();grid[l][r][0]val;grid[r][l][0]val;}for(int k1;kn;k){for(int i1;in;i){for(int j1;jn;j){if (grid[i][k][k - 1] ! Integer.MAX_VALUE grid[k][j][k - 1] ! Integer.MAX_VALUE) {grid[i][j][k] Math.min(grid[i][k][k - 1] grid[k][j][k - 1], grid[i][j][k - 1]);} else {grid[i][j][k] grid[i][j][k - 1];}}}}int numscan.nextInt();while(num0){int startscan.nextInt();int endscan.nextInt();num--;if(grid[start][end][n]Integer.MAX_VALUE) System.out.println(-1);else System.out.println(grid[start][end][n]);}}
}注意当两个 Integer.MAX_VALUE 值相加时会导致整数溢出结果会变成一个非常小的负数如 -128。
A * 算法A star算法
Astar 是一种 广搜或者 dijkstra 的改良版。在搜索最短路的时候 如果是无权图边的权值都是1 那就用广搜代码简洁时间效率和 dijkstra 差不多如果是有权图边有不同的权值优先考虑 dijkstra。
Astar 关键在于 启发式函数也就是影响广搜或者 dijkstra 从容器队列里取元素的优先顺序。BFS 是没有目的性的 一圈一圈去搜索 而 A * 是有方向性的去搜索关键在于启发式函数。
由于从队列里取出什么元素接下来就是从哪里开始搜索。所以启发式函数主要影响队列里元素的排序对队列里节点进行排序就需要给每一个节点权值权值F 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))
本题采用欧拉距离才能最大程度体现 点与点之间的距离。使用欧拉距离计算 和 广搜搜出来的最短路的节点数是一样的。
计算出来 F 之后按照 F 的 大小选择出队列的节点。可以使用 优先级队列每次出队列就是F最小的节点。
代码如下
import java.util.PriorityQueue;
import java.util.Scanner;public class Main {// 定义一个存储移动步数的数组static int[][] moves new int[1001][1001];// 定义骑士的移动方向static int[][] dir {{-2, -1}, {-2, 1}, {-1, 2}, {1, 2}, {2, 1}, {2, -1}, {1, -2}, {-1, -2}};static int b1, b2; // 目标位置// 定义骑士的状态static class Knight implements ComparableKnight {int x, y; // 当前坐标int g, h, f; // G, H, F 值Overridepublic int compareTo(Knight k) { // 重载比较方法以便优先队列可以排序return Integer.compare(this.f, k.f);}}// 估算函数使用欧几里得距离的平方static int Heuristic(Knight k) {return (k.x - b1) * (k.x - b1) (k.y - b2) * (k.y - b2); // 省略开根号以提高精度}// A* 算法实现static void astar(Knight k) {PriorityQueueKnight que new PriorityQueue(); // 创建优先队列que.add(k); // 将起始节点加入队列while (!que.isEmpty()) {Knight cur que.poll(); // 取出队列中优先级最高的节点// 如果到达目标位置则结束搜索if (cur.x b1 cur.y b2) {break;}// 遍历所有可能的骑士移动for (int i 0; i 8; i) {Knight next new Knight(); // 创建下一个节点next.x cur.x dir[i][0]; // 更新 x 坐标next.y cur.y dir[i][1]; // 更新 y 坐标// 检查下一个位置是否在有效范围内if (next.x 1 || next.x 1000 || next.y 1 || next.y 1000) {continue;}// 检查该位置是否已经访问过if (moves[next.x][next.y] 0) {moves[next.x][next.y] moves[cur.x][cur.y] 1; // 更新步数// 计算 G, H 和 F 值next.g cur.g 5; // 统一不开根号以提高精度next.h Heuristic(next);next.f next.g next.h;que.add(next); // 将下一个节点加入队列}}}}public static void main(String[] args) {Scanner scanner new Scanner(System.in);int n scanner.nextInt(); // 读取测试用例的数量while (n-- 0) {int a1 scanner.nextInt(); // 起始 x 坐标int a2 scanner.nextInt(); // 起始 y 坐标b1 scanner.nextInt(); // 目标 x 坐标b2 scanner.nextInt(); // 目标 y 坐标// 清空步数数组for (int i 0; i moves.length; i) {for (int j 0; j moves[i].length; j) {moves[i][j] 0;}}// 初始化起始节点Knight start new Knight();start.x a1;start.y a2;start.g 0;start.h Heuristic(start);start.f start.g start.h;// 执行 A* 算法astar(start);// 输出到达目标位置的步数System.out.println(moves[b1][b2]);}scanner.close(); // 关闭扫描器}
}
