当前位置: 首页 > news >正文

python 实现 A* 算法

A*算法是一种广泛使用的路径搜索算法,结合了启发式搜索和Dijkstra算法的优点。它通过评估每个节点的代价函数 ( f(n) = g(n) + h(n) ) 来选择最优路径,其中:

  • ( g(n) ) 是从起点到当前节点的实际代价。
  • ( h(n) ) 是从当前节点到目标节点的启发式估计代价(如曼哈顿距离或欧几里得距离)。

以下是一个Python实现的A*算法示例:


Python实现A*算法

import heapq
from math import sqrtclass Node:def __init__(self, position, parent=None):self.position = position  # 节点的坐标 (x, y)self.parent = parent     # 父节点self.g = 0               # 从起点到当前节点的实际代价self.h = 0               # 启发式估计代价self.f = 0               # 总代价 f = g + hdef __eq__(self, other):return self.position == other.positiondef __lt__(self, other):return self.f < other.fdef heuristic(a, b):"""启发式函数:计算曼哈顿距离"""return abs(a[0] - b[0]) + abs(a[1] - b[1])def a_star(grid, start, end):"""A*算法实现"""open_list = []  # 优先队列,存储待探索的节点closed_list = set()  # 存储已探索的节点start_node = Node(start)end_node = Node(end)heapq.heappush(open_list, start_node)while open_list:current_node = heapq.heappop(open_list)closed_list.add(current_node.position)# 如果找到目标节点,返回路径if current_node == end_node:path = []while current_node:path.append(current_node.position)current_node = current_node.parentreturn path[::-1]  # 反转路径,从起点到终点# 遍历当前节点的邻居for neighbor in [(0, -1), (0, 1), (-1, 0), (1, 0)]:  # 上下左右四个方向neighbor_position = (current_node.position[0] + neighbor[0], current_node.position[1] + neighbor[1])# 检查邻居是否在地图范围内且不是障碍物if (neighbor_position[0] < 0 or neighbor_position[0] >= len(grid) orneighbor_position[1] < 0 or neighbor_position[1] >= len(grid[0]) orgrid[neighbor_position[0]][neighbor_position[1]] == 1):continue# 创建邻居节点neighbor_node = Node(neighbor_position, current_node)# 如果邻居节点已经探索过,跳过if neighbor_node.position in closed_list:continue# 计算 g, h, f 值neighbor_node.g = current_node.g + 1neighbor_node.h = heuristic(neighbor_node.position, end_node.position)neighbor_node.f = neighbor_node.g + neighbor_node.h# 如果邻居节点已经在 open_list 中且新代价更高,跳过if any(neighbor_node == open_node and neighbor_node.g > open_node.g for open_node in open_list):continue# 将邻居节点加入 open_listheapq.heappush(open_list, neighbor_node)return None  # 如果没有找到路径,返回 None# 示例地图 (0 表示可通行,1 表示障碍物)
grid = [[0, 0, 0, 0, 1, 0],[0, 1, 1, 0, 1, 0],[0, 0, 0, 0, 1, 0],[0, 1, 0, 1, 1, 0],[0, 0, 0, 0, 0, 0]
]# 起点和终点
start = (0, 0)
end = (4, 5)# 运行A*算法
path = a_star(grid, start, end)
if path:print("找到路径:", path)
else:print("未找到路径")

代码说明:

  1. Node:表示搜索中的每个节点,包含位置、父节点、代价等信息。
  2. heuristic 函数:计算启发式估计代价(这里使用曼哈顿距离)。
  3. a_star 函数:实现A*算法的核心逻辑,使用优先队列(堆)来管理待探索的节点。
  4. 地图表示grid 是一个二维列表,0 表示可通行的路径,1 表示障碍物。
  5. 路径返回:如果找到路径,返回从起点到终点的坐标列表;否则返回 None

示例输出:

对于上面的地图,输出可能是:

找到路径: [(0, 0), (0, 1), (0, 2), (1, 2), (2, 2), (2, 3), (3, 3), (4, 3), (4, 4), (4, 5)]

扩展:

  • 启发式函数:可以替换为欧几里得距离或其他更适合的启发式函数。
  • 地图生成:可以从文件中读取地图,或动态生成随机地图。
  • 可视化:可以使用 matplotlibpygame 可视化路径搜索过程。

相关文章:

python 实现 A* 算法

A*算法是一种广泛使用的路径搜索算法&#xff0c;结合了启发式搜索和Dijkstra算法的优点。它通过评估每个节点的代价函数 ( f(n) g(n) h(n) ) 来选择最优路径&#xff0c;其中&#xff1a; ( g(n) ) 是从起点到当前节点的实际代价。( h(n) ) 是从当前节点到目标节点的启发式…...

MyBatis 如何创建 SqlSession 对象的?

MyBatis 创建 SqlSession 对象的过程主要由 SqlSessionFactory 接口及其实现类来完成。以下是详细步骤&#xff1a; 1. SqlSessionFactory 接口: SqlSessionFactory 是 MyBatis 的核心接口之一&#xff0c;它负责创建 SqlSession 对象。 你可以将 SqlSessionFactory 视为 Sql…...

微服务》》四个问题

客户端如何访问 API 网关 如 Core中 Ocelot技术 服务如何治理 服务注册与发现 如 Core中 的 consul技术 服务挂了怎么办 可以利用 重试机制、限流、熔断、降级等 服务之间通信问题 》》同步 1. Http 对外 跨防火墙 【 序列化、反序列化 2 &#xff08; 因为http是应用层…...

CockroachDB MCP -cursor适用

CockroachDB MCP 服务器 GitHub仓库置顶 这是一个用于 Cursor 的 CockroachDB MCP 服务器&#xff0c;基于 Model Context Protocol (MCP) 规范实现&#xff0c;可以让你在 Cursor 中直接与 CockroachDB 数据库交互。 功能 连接到 CockroachDB 数据库获取数据库中的所有表获…...

GOC学习

for(int i1;i<5;i){//这里的所有语句都会被执行 5 次 } int main(){pen.a(200,16,1,0).a(200,-16,1,0);pen.rt(16).fd(200).bk(200);pen.lt(32).fd(200).bk(200);///pen.rt(-32).fd(200).bk(200);for(int i1;i<5;i){pen.a(200,16,1,0).a(200,-16,1,0);pen.rt(16).fd(200)…...

【机器学习】基于t-SNE的MNIST数据集可视化探索

一、前言 在机器学习和数据科学领域&#xff0c;高维数据的可视化是一个极具挑战但又至关重要的问题。高维数据难以直观地理解和分析&#xff0c;而有效的可视化方法能够帮助我们发现数据中的潜在结构、模式和关系。本文以经典的MNIST手写数字数据集为例&#xff0c;探讨如何利…...

Vscode工具开发Vue+ts项目时vue文件ts语法报错-红波浪线等

Vscode工具开发Vuets项目时vue文件ts语法报错-红波浪线等 解决方案 问题如题描述&#xff0c;主要原因是开发工具使用的代码检查与项目的中的ts不一致导导致&#xff0c;解决办法&#xff0c;修改 vscode 中&#xff0c; 快捷键&#xff1a;command shift p, 输入&#xff…...

Python在数据处理中的应用:从入门到精通

活动发起人小虚竹 想对你说&#xff1a; 这是一个以写作博客为目的的创作活动&#xff0c;旨在鼓励大学生博主们挖掘自己的创作潜能&#xff0c;展现自己的写作才华。如果你是一位热爱写作的、想要展现自己创作才华的小伙伴&#xff0c;那么&#xff0c;快来参加吧&#xff01…...

vue3实现跨页面缓存

避免频繁向后端发送请求,vue3中,可以用缓存机制,为了实现跨页面缓存,可以把缓存放到localsotrage里面 关键代码: const globalCache JSON.parse(localStorage.getItem(globalCache)) || {}; 然后加一个forceRefresh关键字, const fetchData async (forceRefresh false) …...

YOLO优化之多信息融合MIF

设计背景 在目标检测领域,随着深度学习技术的不断进步,研究者们一直在寻求提高模型性能和效率的方法。其中, 多模态数据融合 作为一种有效的策略,近年来受到了广泛关注。多模态融合旨在将来自不同传感器或模态的数据进行整合,以提供更全面、丰富的信息供模型学习和推断。…...

人工智能与人的智能,改变一生的思维模型【8】逆向思维

逆向偏差思维模型&#xff1a;顶尖高手如何「反常识」破局 &#xff08;斯坦福决策科学中心认证的逆向思考框架&#xff09; 一、直击本质&#xff1a;什么是逆向偏差思维&#xff1f; 定义&#xff1a; 逆向偏差思维是一种主动对抗本能认知倾向的决策模式&#xff0c;通过系…...

Python 科学计算与机器学习入门:NumPy + Scikit-Learn 实战指南

Langchain系列文章目录 01-玩转LangChain&#xff1a;从模型调用到Prompt模板与输出解析的完整指南 02-玩转 LangChain Memory 模块&#xff1a;四种记忆类型详解及应用场景全覆盖 03-全面掌握 LangChain&#xff1a;从核心链条构建到动态任务分配的实战指南 04-玩转 LangChai…...

深入理解 Qt 系统托盘图标:创建自定义的系统托盘图标类

文章目录 深入理解 Qt 系统托盘图标&#xff1a;创建自定义的系统托盘图标类1. 什么是 QSystemTrayIcon&#xff1f;2. 自定义系统托盘图标类&#xff1a;SysTraylcon3. 代码解析1. **类的定义**2. **构造函数&#xff1a;SysTraylcon::SysTraylcon(QWidget *parent)**3. **ini…...

DeepSeek-R1 面试 -—— GRPO

DeepSeek训练中应用的GRPO算法&#xff0c;它源自于强化学习领域的PPO算法。GRPO与PPO算法之间存在哪些差异&#xff1f;这两种算法各自的优劣何在&#xff1f;为何DeepSeek选择采用GRPO算法而非PPO算法&#xff1f;本文将对这些问题提供解答。 一、PPO算法 PPO&#xff08;Pr…...

AI作曲DiffRhythm原理及本地部署

1.原理简介 最近AI在音乐生成方面的进展引起了极大的关注&#xff0c;但现有的方法面临着严重的限制。一些当前的生成模型只能合成人声或伴奏轨道。虽然一些模型可以生成组合的人声和伴奏&#xff0c;但它们通常依赖于精心设计的多阶段级联架构和复杂的数据管道&#xff0c;阻…...

农业电商|基于SprinBoot+vue的农业电商服务系统(源码+数据库+文档)

农业电商服务系统 目录 基于SprinBootvue的农业电商服务系统 一、前言 二、系统设计 三、系统功能设计 5.1系统功能实现 5.2后台模块实现 5.2.1管理员模块实现 5.2.2商家模块实现 四、数据库设计 五、核心代码 六、论文参考 七、最新计算机毕设选题推荐 八、源码…...

深度学习有哪些算法?

深度学习包含多种算法和模型&#xff0c;广泛应用于图像处理、自然语言处理、语音识别等领域。以下是主要分类及代表性算法&#xff1a; 一、基础神经网络 多层感知机&#xff08;MLP&#xff09; 最简单的深度学习模型&#xff0c;由多个全连接层组成&#xff0c;用于分类和回…...

鸿蒙开发-一多开发之媒体查询功能

在HarmonyOS中&#xff0c;使用ArkTS语法实现响应式布局的媒体查询是一个强大的功能&#xff0c;它允许开发者根据不同的设备特征&#xff08;如屏幕尺寸、屏幕方向等&#xff09;动态地调整UI布局和样式。以下是一个使用媒体查询实现响应式布局的实例&#xff1a; 1. 导入必要…...

历年华中科技大学计算机考研复试上机真题

历年华中科技大学计算机考研复试上机真题 2022华中科技大学计算机考研复试上机真题 2021华中科技大学计算机考研复试上机真题 2019华中科技大学计算机考研复试上机真题 在线评测&#xff1a;https://pgcode.cn 八进制 题目描述 输入一个整数&#xff0c;将其转换成八进制数…...

卷积神经网络(CNN)的主要架构

卷积神经网络&#xff08;CNN, Convolutional Neural Networks&#xff09;是深度学习中最重要的模型之一&#xff0c;广泛应用于计算机视觉、目标检测、语义分割等任务。自 LeNet 诞生以来&#xff0c;CNN 结构经历了多个重要发展阶段&#xff0c;出现了许多经典架构&#xff…...

IDEA:项目结构不见了,项目文件消失解决

IDEA&#xff1a;看不见目录结构了。 1、确认项目是否仍存在&#xff1a;检查项目文件夹是否仍然存在于磁盘上。如果项目文件夹被删除或移动了&#xff0c;您需要将其还原或重新导入到IDEA中。 2、重新导入项目&#xff1a;如果项目文件存在&#xff0c;在 IDEA 中找到项目文…...

基于ssm的宠物医院信息管理系统(全套)

一、系统架构 前端&#xff1a;html | layui | vue | element-ui 后端&#xff1a;spring | springmvc | mybatis 环境&#xff1a;jdk1.8 | mysql | maven | tomcat | idea | nodejs 二、代码及数据库 三、功能介绍 01. web端-首页1 02. web端-首页…...

How to install a package in offline scenario in Ubuntu 24.04

概述 做过信创项目的兄弟们在工作上每天可能面对很多需要解决的问题&#xff0c;不过&#xff0c;有一类问题可能是大家经常遇的&#xff0c;比方说&#xff0c;有时候我们不得不硬着头皮在离线生产环境中安装某些软件包&#xff0c;相信很多兄弟被这种细碎的小事搞得焦头烂额…...

将pdf或者word转换成base64格式

废话不多说直接上代码&#xff1a; function fileToBase64(file) {return new Promise((resolve, reject) > {const reader new FileReader();reader.readAsDataURL(file);reader.onload function (event) {const base64Data event.target.result.split(,)[1];resolve(b…...

使用Nodejs基于DeepSeek加chromadb实现RAG检索增强生成 本地知识库

定义 检索增强生成&#xff08;RAG&#xff09;的基本定义 检索增强生成&#xff08;Retrieval-Augmented Generation&#xff0c;简称RAG&#xff09;是一种结合了信息检索技术与语言生成模型的人工智能技术。RAG通过从外部知识库中检索相关信息&#xff0c;并将其作为提示&…...

乐观锁VS分布式锁实现抢单服务

司机开始接单&#xff0c;乘客填写出发地——目的地&#xff0c;开始下单 service-order模块 Operation(summary"司机抢单") GetMapping("/robNewOrder/{driverId}/{orderId}") public Result<Boolean> robNewOrder(PathVariable Long driverId,P…...

通过特征值和特征向量实现的图像压缩和特征提取

前文&#xff0c;我们在学习人工智能的线性代数基础的时候&#xff0c;就了解到&#xff0c;矩阵在人工智能中被广泛使用&#xff0c;接下来我们就从大家非常常见的图像开始&#xff0c;深度理解矩阵在人工智能中的应用。有关线性代数基础的文章可以看的我CSDN:人工智能中的线性…...

ranger集成starrock报错

org.apache.ranger.plugin.client.HadoopException: initConnection: Unable to connect to StarRocks instance, please provide valid value of field : {jdbc.driverClassName}.. com.mysql.cj.jdbc.Driver. 可能的原因 JDBC 驱动缺失&#xff1a;运行环境中没有安装 MySQL …...

第J2周:ResNet50V2算法实现01(Tensorflow硬编码版)

&#x1f368; 本文为&#x1f517;365天深度学习训练营 中的学习记录博客&#x1f356; 原作者&#xff1a;K同学啊 目标 使用tensorflow实现ResNetV50V2的网络结构。本次根据第一层的细节手动硬编码&#xff0c;没有任何的优化&#xff0c;只为了更好的理解细节。 目录结构&…...

论文分享 | HE-Nav: 一种适用于复杂环境中空地机器人的高性能高效导航系统

阿木实验室始终致力于通过开源项目和智能无人机产品&#xff0c;为全球无人机开发者提供强有力的技术支持&#xff0c;并推出了开源项目校园赞助活动&#xff0c;助力高校学子在学术研究与技术创新中取得更大突破。近日&#xff0c;香港大学王俊铭同学&#xff0c;基于阿木实验…...

【mysql】centOS7安装mysql详细操作步骤!—通过tar包方式

【mysql】centOS7安装mysql详细操作步骤&#xff01; linux系统安装mysql版本 需要 root 权限&#xff0c;使用 root 用户进行命令操作。使用tar文件包&#xff0c;安装&#xff0c;gz包也可以但是还需要配置用户&#xff0c;tar包虽然大&#xff0c;但是全啊&#xff01; 1. …...

java学习笔记1

程序编译步骤 java程序执行步骤 相关代码及解释&#xff1a; /* 对第一个java程序进行总结 1. java程序编写-编译-运行的过程 编写&#xff1a;我们将编写的java代码保存在以".java"结尾的源文件中 编译&#xff1a;使用javac.exe命令编译我们的java源文件。格式&am…...

强大的数据库DevOps工具:NineData 社区版

本文作者司马辽太杰&#xff0c; gzh&#xff1a;程序猿读历史 在业务快速变化与数据安全日益重要的今天&#xff0c;生产数据库变更管理、版本控制、数据使用是数据库领域的核心挑战之一。传统的解决方式往往采用邮件或即时通讯工具发起审批流程&#xff0c;再通过堡垒机直连数…...

「Unity3D」UGUI运行时设置元素的锚点Anchor,维持元素Rect的显示不变,即待在原处

在编辑器中&#xff0c;通过设置Raw edit mode&#xff0c;可以切换两种&#xff0c;元素锚点的改变模式&#xff1a; 一种是锚点单独改变&#xff0c;即&#xff1a;不开启原始模式&#xff0c;保持原样&#xff0c;改变anchoredPosition与sizeDelta。一种是锚点联动显示&…...

深入解析大语言模型的 Function Call 实现—— 以 Qwen2.5为例

引言 在现代大语言模型&#xff08;LLM&#xff09;中&#xff0c;Function Call&#xff08;函数调用&#xff09;能力极大地提升了模型的实用性&#xff0c;使其能够调用外部 API、执行复杂计算或获取实时数据。例如&#xff0c;在 OpenAI API 和 Qwen2.5-7B-Instruct 这样的…...

鸿蒙路由 HMrouter 配置及使用一

1、学习链接 HMRouter地址 https://gitee.com/hadss/hmrouter/blob/dev/HMRouterLibrary/README.md 2、工程配置 下载安装 ohpm install hadss/hmrouter 添加编译插件配置 在工程目录下的build-profile.json5中&#xff0c;配置useNormalizedOHMUrl属性为true (我这项目创…...

驾驭 DeepSeek 科技之翼,翱翔现代学习新天际

在当今这个信息爆炸的时代&#xff0c;学习的方式和途径正在经历着前所未有的变革。人工智能技术的飞速发展&#xff0c;为我们的学习带来了全新的机遇和挑战。DeepSeek 作为一款强大的大语言模型&#xff0c;凭借其卓越的性能和丰富的功能&#xff0c;为现代学习注入了新的活力…...

[Windows] 轻量级景好鼠标录制器 v2.1 单文件版,支持轨迹+鼠标键盘录制复刻

[Windows] 轻量级景好鼠标录制器 链接&#xff1a;https://pan.xunlei.com/s/VOLHz0rPyqdhV4bgyTYuW6W7A1?pwd98uj# 软件特性&#xff1a; 高效播放控制&#xff1a;动作间隔优化至100 ms&#xff0c;进度条可视化&#xff0c;支持随机循环/多次播放。 深度自定义&#xff1…...

C#生产型企业ERP系统管理软件PCB行业ERP进销存MRP管理系统BOM管理

背景 本软件为为苏州某生产型电子科技企业开发的ERP管理软件。 功能说明 希哲管理系统v1.0是一款在流览器上使用的企业管理软件&#xff0c;使用上与客户端版的优势是&#xff1a; 1.安装更新部署方便&#xff0c;只需服务器部署了软件&#xff0c;其它客户端的用户无需安装&am…...

【Linux内核系列】:文件系统

&#x1f525; 本文专栏&#xff1a;Linux &#x1f338;作者主页&#xff1a;努力努力再努力wz ★★★ 本文前置知识&#xff1a; 文件系统初识 那么在我们此前关于文件的学习中&#xff0c;我们学习的都是进程与打开的文件之间的关系&#xff0c;以及打开的文件如何进行管理…...

工程化与框架系列(35)--前端微服务架构实践

前端微服务架构实践 &#x1f3d7;️ 引言 随着前端应用规模的不断扩大&#xff0c;微服务架构在前端领域的应用越来越广泛。本文将深入探讨前端微服务架构的实现方案、最佳实践和相关工具。 微服务架构概述 前端微服务架构主要包括以下方面&#xff1a; 应用拆分&#xf…...

多条件下的免杀webshell

前言 在做webshell免杀的时候&#xff0c;很多情况下都是对system,eval等命令执行函数进行匹配&#xff0c;如果说把变量当做一个函数来使用的话&#xff0c;那是不是可以bypass了呢&#xff1f;这今天刚好看见有一个回调函数有这样的功能&#xff0c;而且也不会报毒&#xff…...

【算法】动态规划

⭐️个人主页&#xff1a;小羊 ⭐️所属专栏&#xff1a;Linux 很荣幸您能阅读我的文章&#xff0c;诚请评论指点&#xff0c;欢迎欢迎 ~ 目录 动态规划总结1、常见动态规划Fibonacci数列杨辉三角最小花费爬楼梯孩子们的游戏 2、组合方案李白打酒加强版&#xff08;lqb&…...

MySQL事务及索引复习笔记

本文参考小林coding&#xff0c;地址事务隔离级别是怎么实现的&#xff1f; | 小林coding 事务 一、事务是什么&#xff1f; 比如一个程序是转账&#xff0c;你要扣减a的余额&#xff0c;增加b的余额&#xff0c;但是如果程序执行扣减成功然后挂了&#xff0c;就会出现a的余额…...

API调用大模型推理与第三方API实现业务整合

基于Python实现大模型推理与第三方API调用的集成&#xff0c;需要结合Function Call机制与提示词工程。 一、技术架构设计 双阶段流程 推理阶段&#xff1a;大模型解析用户意图&#xff0c;生成结构化API调用指令执行阶段&#xff1a;Python代码解析指令并触发第三方API # 示例…...

GreenKGC: A Lightweight Knowledge Graph Completion Method(论文笔记)

CCF等级&#xff1a;A 发布时间&#xff1a;2023年7月 代码位置 25年3月17日交 目录 一、简介 二、原理 1.整体 2.表示学习 3.特征修剪 4.决策学习 三、实验性能 1.主要结果 2.消融实验 四、结论和未来工作 一、简介 传统知识图谱补全方法中&#xff0c;嵌入维度…...

Android Composable 与 View 的联系和区别

在 Android 开发中&#xff0c;‌Composable‌&#xff08;Jetpack Compose&#xff09;与‌View‌&#xff08;传统 View 系统&#xff09;是两种不同的 UI 构建范式。本文将从核心联系、核心区别、代码实现三方面展开对比&#xff0c;并通过实例代码帮助开发者理解其应用场景…...

微信小程序wx.request接口报错(errno: 600001, errMsg: “request:fail -2:net::ERR_FAILED“)

来看看报错 报错如下: 请求发送部分,代码如下: uni.request({url: self.serverUrl "/getRealName",method: GET,data: {"code": self.info.code,},header: {"Authorization": uni.getStorageSync(tokenHead) uni.getStorageSync(token)}}…...

多线程与并发编程 面试专题

多线程与并发编程 面试专题 线程的基础概念基础概念线程的创建线程的状态线程的终止方式start 与 run 区别线程的常用方法 锁锁的分类深入synchronized深入ReentrantLock死锁问题 阻塞队列线程池 线程的基础概念 基础概念 进程与线程 进程&#xff1a;指运行中的程序。 比如我…...

大语言模型-1.2-大模型技术基础

简介 本博客内容是《大语言模型》一书的读书笔记&#xff0c;该书是中国人民大学高瓴人工智能学院赵鑫教授团队出品&#xff0c;覆盖大语言模型训练与使用的全流程&#xff0c;从预训练到微调与对齐&#xff0c;从使用技术到评测应用&#xff0c;帮助学员全面掌握大语言模型的…...