day60 图论章节刷题Part10(Floyd 算法、A * 算法)

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 的最短路径经过节点k:grid[i][j][k] = grid[i][k][k - 1] + grid[k][j][k - 1]
(2)节点i 到 节点j 的最短路径不经过节点k:grid[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循环,分别遍历i,j 和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 n=scan.nextInt();int m=scan.nextInt();int[][][] grid=new int[n+1][n+1][n+1];for(int i=0;i<=n;i++){for(int j=0;j<=n;j++){Arrays.fill(grid[i][j],Integer.MAX_VALUE);}}//添加边的权重,初始化for(int i=0;i<m;i++){int l=scan.nextInt();int r=scan.nextInt();int val=scan.nextInt();grid[l][r][0]=val;grid[r][l][0]=val;}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][k][k - 1] + grid[k][j][k - 1], grid[i][j][k - 1]);} else {grid[i][j][k] = grid[i][j][k - 1];}}}}int num=scan.nextInt();while(num>0){int start=scan.nextInt();int end=scan.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 Comparable<Knight> {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) {PriorityQueue<Knight> 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(); // 关闭扫描器}
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/469420.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

iOS 18.2 重磅更新:6个大动作

根据外媒报道&#xff0c;iOS 18.2迎来重磅更新&#xff0c;将带来6个大动作&#xff0c;这是一次非常实用的更新。不过要注意的是&#xff0c;其中涉及到AI的功能&#xff0c;国行iPhone 暂时还不可用&#xff0c;只能等审核通过了。 1&#xff0c;Safari下载进度 过去通过S…

【单例模式】饿汉式与懒汉式以及线程安全

1. 单例模式介绍 饿汉式单例模式&#xff1a;还没有获取实例对象&#xff0c;实例对象就已经产生了。一定是线程安全的。 懒汉式单例模式&#xff1a;需要用的时候再构造实例。 应用场景&#xff1a;比如日志模块&#xff0c;数据库模块&#xff0c;开发的解析器模块。 2.饿…

一文了解 Tableau 2024.3 如何展现已发布数据源的数据模型

通过减少数据源的重复建设&#xff0c;提高数据透明度&#xff0c;可组合数据源将为企业带来更高的数据利用效率 在 TC24 用户大会上&#xff0c;Tableau 产品团队提出了一个非常重要的功能概念——可组合的数据源。这意味着你将很快能够对 Tableau 已发布的数据源进行连接、关…

Unity 网格模型及优化

一个模型中可以包含很多网格&#xff0c;一个模型可以由多个网格组成。在Unity3D中一个网格可以由多个子网格&#xff08;Sub-Mesh)组成。 在渲染引擎的时候&#xff0c;每个子网格都要匹配一个材质球来做渲染&#xff0c;实际上一个子网格本身就是一个个普通的模型&#xff0…

第四十三章 Vue之mapMutations简化mutations操作

目录 一、引言 二、完整代码 2.1. App.vue 2.2. main.js 2.3. Son1.vue 2.4. Son2.vue 2.5. index.js 一、引言 本章节我们通过掌握辅助函数mapMutations&#xff0c;来简化前面章节中调用mutations函数的繁琐方式。mapMutations 和 mapState很像&#xff0c;它是把位于…

【论文复现】ChatGPT多模态命名实体识别

&#x1f4dd;个人主页&#x1f339;&#xff1a;Eternity._ &#x1f339;&#x1f339;期待您的关注 &#x1f339;&#x1f339; ❀ChatGPT ChatGPT辅助细化知识增强&#xff01;1. 研究背景2. 模型结构和代码3. 任务流程第一阶段&#xff1a;辅助精炼知识启发式生成第二阶段…

echarts-gl 3D柱状图配置

1. 源码 此demo可以直接在echarts的编辑器中运行 option {title: {text: 产量图,textStyle: {color: rgba(255, 255, 255, 1),fontSize: 17},left: center},tooltip: {},legend: {show: false,orient: vertical,x: left,top: 0,right: 20,textStyle: {fontSize: 12}},visualM…

c语言数据结构与算法--简单实现栈和队列的出栈与入栈

&#xff08;一&#xff09;栈的基本概念 栈(Stack)是限定仅在表尾进行插入和删除操作的线性表&#xff0c;如铁路调度。如下 图&#xff1a; &#xff08;二&#xff09;栈的的表现形式 栈有两种表示形式&#xff1a;栈的表示和实现、栈的 链式表示。 1&#xff0e;栈的表示…

人工智能(AI)和机器学习(ML)技术学习流程

目录 人工智能(AI)和机器学习(ML)技术 自然语言处理(NLP): Word2Vec: Seq2Seq(Sequence-to-Sequence): Transformer: 范式、架构和自注意力: 多头注意力: 预训练、微调、提示工程和模型压缩: 上下文学习、思维链、全量微调、量化、剪枝: 思维树、思维…

C++初阶——vector

一、什么是vector vector是表示可变大小的数组的序列容器&#xff0c;就像数组一样&#xff0c;vector也采用连续空间来存储元素。也就是说它的访问和数组一样高效&#xff0c;但是它的大小是动态可变的&#xff0c;并且它的大小会被容器自动处理。 二、vector的构造 常用的构…

移远通信亮相骁龙AI PC生态科技日,以领先的5G及Wi-Fi产品革新PC用户体验

PC作为人们学习、办公、娱乐的重要工具&#xff0c;已经深度融入我们的工作和生活。随着物联网技术的快速发展&#xff0c;以及人们对PC性能要求的逐步提高&#xff0c;AI PC成为了行业发展的重要趋势。 11月7-8日&#xff0c;骁龙AI PC生态科技日在深圳举办。作为高通骁龙的重…

AIGC专栏17——EasyAnimate V5版本详解 应用MMDIT结构,拓展模型规模到12B 支持不同控制输入的控制模型

AIGC专栏17——EasyAnimate V5版本详解 应用MMDIT结构&#xff0c;拓展模型规模到12B 支持不同控制输入的控制模型 学习前言相关地址汇总源码下载地址HF测试链接 测试效果Image to VideoText to Video EasyAnimate详解技术储备Diffusion Transformer (DiT)Stable Diffusion 3Co…

Android Studio | 最新版本配置要求高,JDK运行环境不适配,导致无法启动App

Android Studio 的最新版本配置要求比较高&#xff0c;这时候需要降低插件的版本&#xff0c;才能正常启动项目 build.gradle 文件的 dependencies 部分中&#xff0c;使用 libs 作为一些常用库的别名。这些别名在项目的 gradle.properties 文件或者某个特定的 versions.prope…

ssm093基于Java Web的毕业生就业状况管理系统设计与实现+jsp(论文+源码)_kaic

毕 业 设 计&#xff08;论 文&#xff09; 题目&#xff1a;毕业生就业状况管理系统设计与实现 摘 要 现代经济快节奏发展以及不断完善升级的信息化技术&#xff0c;让传统数据信息的管理升级为软件存储&#xff0c;归纳&#xff0c;集中处理数据信息的管理方式。本毕业生就业…

el-dialog 设置 水平垂直居中 高度不固定

小记一下&#xff1a; 希望实现不管内容高度多少 el-dialog都能水平垂直居中 效果&#xff1a; css: .form-view-dialog{display: flex;align-items: center;justify-content: center;.el-dialog{margin: 0 auto; }.el-dialog__body{max-height: 75vh; // 可选择 设置一个最…

当AI遇上时尚:未来的衣橱会由机器人来打理吗?

内容概要 在当今这个快速发展的时代&#xff0c;人工智能与时尚的结合正在逐渐改写我们对衣橱管理的认知。传统的衣橱管理常常面临着空间不足、穿搭单调及库存过多等挑战&#xff0c;许多人在挑选服饰时难以做出决策。然而&#xff0c;随着技术的进步&#xff0c;智能推荐和自…

Ubuntu 20.04安装CUDA 11.0、cuDNN 8.0.5

不知道咋弄的ubuntu20.04电脑的cuda驱动丢了&#xff0c;无奈需装PyTorch环境&#xff0c;只有CUDA11.0以上版本才支持Ubuntu20.04&#xff0c;所以安装了CUDA11.0、cuDNN8.0.5 为防止频繁在浏览器检索对应的贴子&#xff0c;今天记录一下。 一. 驱动安装 为防止驱动安装后没…

高德地图通过经纬度查找位置和轨迹回放

1、完整代码自己高德申请key,其他文章有写的 <!DOCTYPE html> <html lang"en"> <head><meta charset"UTF-8"><meta name"viewport" content"widthdevice-width, initial-scale1.0"><title><…

C++常用的特性-->day05

友元的拓展语法 声明一个类为另外一个类的友元时&#xff0c;不再需要使用class关键字&#xff0c;并且还可以使用类的别名&#xff08;使用 typedef 或者 using 定义&#xff09;。 #include <iostream> using namespace std;// 类声明 class Tom; // 定义别名 using …

使用docker形式部署jumpserver

文章目录 前言一、背景二、使用步骤1.基础环境准备2.拉取镜像3.进行部署4.备份记录启动命令 前言 记录一下使用docker形式部署jumpserver服务的 一、背景 搭建一个jumpserver的堡垒机&#xff0c;但是发现之前是二进制文件部署的&#xff0c;会在物理机上部署污染环境&#x…