深圳网站推广优,C2C电商网站,微信小程序开发编辑器,手机电脑同步网站开发Floyd 算法精讲 Floyd 算法代码很简单#xff0c;但真正理解起原理 还是需要花点功夫#xff0c;大家在看代码的时候#xff0c;会发现 Floyd 的代码很简单#xff0c;甚至看一眼就背下来了#xff0c;但我为了讲清楚原理#xff0c;本篇还是花了大篇幅来讲解。 代码随想… Floyd 算法精讲 Floyd 算法代码很简单但真正理解起原理 还是需要花点功夫大家在看代码的时候会发现 Floyd 的代码很简单甚至看一眼就背下来了但我为了讲清楚原理本篇还是花了大篇幅来讲解。 代码随想录 方法1三维dp数组 import java.util.*;public class Main{public static void main (String[] args) {Scanner sc new Scanner(System.in);int n sc.nextInt();int m sc.nextInt();int[][][] grid new int[n1][n1][n1];//grid[i][j][k] m 表示节点i 到 j 以[1...k] 集合为中间节点的最短距离为mfor(int i 1; i n; i){for(int j 1; j n; j){Arrays.fill(grid[i][j], Integer.MAX_VALUE);} grid[i][i][0] 0;}for(int i 0; i m; i){int u sc.nextInt();int v sc.nextInt();int w sc.nextInt();grid[u][v][0] w;grid[v][u][0] w;}for(int k 1; k n; k){for(int i 1; i n; i){for(int j 1; j n; 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][j][k-1], grid[i][k][k-1]grid[k][j][k-1]);}else{grid[i][j][k] grid[i][j][k-1];// grid[i][j][k]并不会继承grid[i][j][k-1]而是保留为初始值;}}}}int q sc.nextInt();for(int i 0; i q; i){int start sc.nextInt();int end sc.nextInt();if(grid[start][end][n] Integer.MAX_VALUE){System.out.println(-1);}else{System.out.println(grid[start][end][n]); }}}} 方法2二维dp数组 import java.util.*;public class Main{public static void main (String[] args) {Scanner sc new Scanner(System.in);int n sc.nextInt();int m sc.nextInt();int[][] grid new int[n1][n1];//grid[i][j][k] m 表示节点i 到 j 以[1...k] 集合为中间节点的最短距离为mfor(int i 1; i n; i){Arrays.fill(grid[i], 10001);grid[i][i] 0;}for(int i 0; i m; i){int u sc.nextInt();int v sc.nextInt();int w sc.nextInt();grid[u][v] w;grid[v][u] w;}for(int k 1; k n; k){for(int i 1; i n; i){for(int j 1; j n; j){grid[i][j] Math.min(grid[i][j], grid[i][k]grid[k][j]);}}}int q sc.nextInt();for(int i 0; i q; i){int start sc.nextInt();int end sc.nextInt();if(grid[start][end] 10001){System.out.println(-1);}else{System.out.println(grid[start][end]); }}}} 总结 1.确定dp数组dp table以及下标的含义 //grid[i][j][k] m 表示节点i 到 j 以[1...k] 集合为中间节点的最短距离为m2 2.确定递推公式 第一种情况不经过中间节点K那么 grid[i][j][k] grid[i][j][k-1] 第二种情况经过中间节点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] Math.min(grid[i][j][k-1], grid[i][k][k-1]grid[k][j][k-1]); 3.dp数组如何初始化需要初始化K0的情况K0就是两个节点直接相连没有中间节点所以直接赋值边的权值就可以了(双向或者无向需要两个方向初始化有向图只要一个方向初始化)。然后其他对角元素应该初始化为0其他元素初始化为边的权值的最大值10001或者最大整形都可以10001更加方便后续不需要考虑溢出的情况。 4.确定遍历顺序 grid[i][j][k] Math.min(grid[i][j][k-1], grid[i][k][k-1]grid[k][j][k-1]); 初始化的时候把 k 0 的 i 和j 对应的数值都初始化了这样才能去计算 k 1 的时候 i 和 j 对应的数值。这就好比是一个三维坐标i 和j 是平层而k是垂直向上的。遍历的顺序是从底向上 一层一层去遍历。所以遍历k 的for循环一定是在最外面这样才能一层一层去遍历。k 依赖于 k - 1 i 和j 的到并不依赖与 i - 1 或者 j - 1 。所以一定是把k 的for循环放在最外面才能用上 初始化和上一轮计算的结果了。i和j的遍历顺序就无所谓了。 5.二维的dp数组就把k这一维度去掉。每次进入新的k其实都保留着上一轮k的数值靠着最外层的for循环来实现对k的滚动。 6.Floyd 算法的时间复杂度相对较高Floyd 算法适合多源最短路即 求多个起点到多个终点的多条最短路径。适合 稠密图且源点较多的情况。时间复杂度 O(n^3)如果 源点少其实可以 多次dijsktra 求源点到终点。Floyd 算法对边的权值正负没有要求都可以处理。 A * 算法精讲 A star算法 一般 笔试或者 面试的时候不会考察A* 都是会结合具体业务场景问 A*算法例如地图导航游戏开发 等等。其实基础版的A* 并不难所以大家不要畏惧理解本篇内容甚至独立写出代码大家可以做到加油 A * 算法精讲 A star算法 | 代码随想录 import java.util.*;public class Main {static int[][] moves new int[1001][1001]; // 记录每个位置的移动次数static int[][] dir { // 马的8个方向{-2, -1}, {-2, 1}, {-1, 2}, {1, 2}, {2, 1}, {2, -1}, {1, -2}, {-1, -2}};static int b1, b2; // 目标位置的x, y坐标static class Knight implements ComparableKnight {int x, y, g, h, f;Knight(int x, int y, int g, int h) {this.x x;this.y y;this.g g; // G 从起点到该节点的路径消耗this.h h; // H 从该节点到终点的预估消耗this.f g h; // F G H}Overridepublic int compareTo(Knight k) {return Integer.compare(this.f, k.f); // 按照f值从小到大排序}}// 欧拉距离的启发函数不开根号以提高精度static int heuristic(Knight k) {return (k.x - b1) * (k.x - b1) (k.y - b2) * (k.y - b2);}static void astar(Knight start) {PriorityQueueKnight queue new PriorityQueue();queue.add(start);while (!queue.isEmpty()) {Knight cur queue.poll(); // 取出f值最小的节点// 如果到达目标位置直接退出if (cur.x b1 cur.y b2) {break;}for (int[] d : dir) {int nx cur.x d[0];int ny cur.y d[1];// 检查边界if (nx 1 || nx 1000 || ny 1 || ny 1000) {continue;}// 如果这个位置没有访问过if (moves[nx][ny] 0) {moves[nx][ny] moves[cur.x][cur.y] 1; // 更新移动次数int g cur.g 5; // 马走日消耗固定为5int h heuristic(new Knight(nx, ny, 0, 0));Knight next new Knight(nx, ny, g, h);queue.add(next); // 加入优先队列}}}}public static void main(String[] args) {Scanner sc new Scanner(System.in);int n sc.nextInt(); // 测试案例数量while (n-- 0) {int a1 sc.nextInt(), a2 sc.nextInt(); // 起点坐标b1 sc.nextInt();b2 sc.nextInt(); // 终点坐标for (int[] row : moves) {Arrays.fill(row, 0); // 初始化moves数组}Knight start new Knight(a1, a2, 0, heuristic(new Knight(a1, a2, 0, 0)));astar(start);System.out.println(moves[b1][b2]); // 输出结果}sc.close();}
} PriorityQueueKnight queue new PriorityQueue();这个PriorityQueue 自动根据 compareTo 方法维护堆的性质或任何自定义比较器的实现。 Overridepublic int compareTo(Person other) {return Integer.compare(this.age, other.age); // 按年龄升序排序}//反向比较
Override
public int compareTo(Knight k) {return Integer.compare(k.f, this.f); // 交换位置k 在前面
}1.为什么按照 F 值排序 F G H 表示从起点经过当前节点到终点的总代价估计值。按照 F 值排序能够保证优先探索 当前预估代价最小的路径从而以最快的速度找到最优解。 示例解释 假设 当前节点 A 的 G2, H5, 所以 F257。另一个节点 B 的 G4, H2, 所以 F426。 如果只按照 H 值排序会优先选择 AH 5 但 A 的总代价 F7并不是最优路径。 按照 F 值排序会优先选择 BF 6更接近最终的最优路径。 核心思路就是从队列里面优先弹出F值更小的元素那么使用优先级队列就可以做到。Java 的优先级队列 (PriorityQueue) 默认是小顶堆。这意味着在队列中优先级最低的元素数值最小的元素会排在队首即最先被弹出。 2.moves 数组的作用是 记录某个棋盘位置是否已经访问过以及该位置从起点到当前的 步数。 3.Astar 是一种 广搜的改良版。 或者是 dijkstra 的改良版。如果是无权图边的权值都是1 那就用广搜。如果是有权图边有不同的权值优先考虑 dijkstra。Astar 关键在于 启发式函数 也就是 影响 广搜或者 dijkstra 从 容器队列里取元素的优先顺序。 最短路算法总结篇 最各个最短路算法有个全面的了解 最短路算法总结篇 | 代码随想录 图论总结 图论总结篇 | 代码随想录
