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

算法——对比A*算法与IDA*算法

A*算法与IDA*算法详细解析

1. A*算法

核心思想
A*算法是一种启发式搜索算法,结合了Dijkstra算法的最短路径保证和贪心最佳优先搜索的高效导向性。其核心是评估函数 ( f(n) = g(n) + h(n) ),其中:

  • ( g(n) ): 从起点到当前节点 ( n ) 的实际代价。
  • ( h(n) ): 当前节点 ( n ) 到目标节点的启发式估计代价(需满足可采纳性,即不高估实际代价)。

算法步骤

  1. 初始化:将起点加入优先队列(Open List),记录 ( g ) 值和 ( f ) 值。
  2. 循环扩展
    • 取出 Open List 中 ( f(n) ) 最小的节点 ( n )。
    • 若 ( n ) 是目标节点,回溯路径并结束。
    • 将 ( n ) 移入 Closed List(已处理列表)。
    • 遍历 ( n ) 的邻居 ( m ):
      • 计算临时 ( g_{temp} = g(n) + \text{cost}(n, m) )。
      • 若 ( m ) 不在 Open List 或 Closed List,或 ( g_{temp} < g(m) ),更新 ( m ) 的父节点为 ( n ),并重新计算 ( f(m) ),将 ( m ) 加入 Open List。
  3. 终止条件:Open List 为空时,表示无解。

关键特性

  • 可采纳性:启发函数 ( h(n) ) 必须满足 ( h(n) \leq h^*(n) )(实际代价),确保最优解。
  • 一致性(单调性):若 ( h(n) \leq \text{cost}(n, m) + h(m) )(对任意边 ( n \to m )),则 A* 无需重复处理节点(Closed List 不再更新)。

优缺点

  • 优点:高效、保证最优解(若 ( h(n) ) 可采纳)。
  • 缺点:内存消耗高(需维护 Open/Closed List)。

应用场景

  • 游戏AI路径规划(如RTS游戏单位移动)。
  • 地图导航(如GPS路线计算)。

代码

import heapq# 定义节点类
class Node:def __init__(self, x, y, g=float('inf'), h=float('inf'), parent=None):self.x = xself.y = yself.g = gself.h = hself.f = g + hself.parent = parentdef __lt__(self, other):return self.f < other.f# 启发函数:曼哈顿距离
def heuristic(a, b):return abs(a[0] - b[0]) + abs(a[1] - b[1])# A* 算法实现
def a_star(grid, start, goal):rows, cols = len(grid), len(grid[0])open_list = []closed_set = set()start_node = Node(start[0], start[1], 0, heuristic(start, goal))heapq.heappush(open_list, start_node)while open_list:current = heapq.heappop(open_list)if (current.x, current.y) == goal:path = []while current:path.append((current.x, current.y))current = current.parentreturn path[::-1]closed_set.add((current.x, current.y))neighbors = [(current.x + dx, current.y + dy) for dx, dy in [(-1, 0), (1, 0), (0, -1), (0, 1)]if 0 <= current.x + dx < rows and 0 <= current.y + dy < cols and grid[current.x + dx][current.y + dy] == 0]for neighbor in neighbors:if neighbor in closed_set:continuetentative_g = current.g + 1neighbor_node = Node(neighbor[0], neighbor[1])if tentative_g < neighbor_node.g:neighbor_node.parent = currentneighbor_node.g = tentative_gneighbor_node.h = heuristic(neighbor, goal)neighbor_node.f = neighbor_node.g + neighbor_node.hheapq.heappush(open_list, neighbor_node)return None# 示例使用
grid = [[0, 0, 0, 0],[0, 1, 1, 0],[0, 1, 0, 0],[0, 0, 0, 0]
]
start = (0, 0)
goal = (3, 3)
path = a_star(grid, start, goal)
print("A* 算法找到的路径:", path)

2. IDA*算法(Iterative Deepening A*

核心思想
将迭代加深(Iterative Deepening)与A*结合,通过逐步放宽的阈值进行深度优先搜索(DFS),每次搜索限制 ( f(n) ) 不超过当前阈值,避免内存爆炸。

算法步骤

  1. 初始化:阈值 ( \text{threshold} = f(\text{起点}) = h(\text{起点}) )。
  2. 深度优先搜索
    • 从起点出发,递归访问节点 ( n )。
    • 若 ( f(n) > \text{threshold} ),记录超限的最小 ( f ) 值作为下次阈值。
    • 若找到目标,返回路径。
  3. 迭代更新:若未找到目标,将阈值设为上一步记录的最小超限值,重新开始DFS。

关键特性

  • 每次迭代类似一次深度受限的DFS,但限制条件是 ( f(n) \leq \text{threshold} )。
  • 内存占用低(仅需存储递归栈)。

优缺点

  • 优点:内存效率极高(无Open/Closed List),适合状态空间大的问题。
  • 缺点:可能重复访问节点(需权衡启发式函数质量)。

应用场景

  • 解谜问题(如15数码、华容道)。
  • 内存受限环境下的路径搜索。

代码:

# 启发函数:曼哈顿距离
def heuristic_ida(a, b):return abs(a[0] - b[0]) + abs(a[1] - b[1])# 递归深度优先搜索
def dfs(grid, node, goal, limit, path):f = node[2] + heuristic_ida((node[0], node[1]), goal)if f > limit:return fif (node[0], node[1]) == goal:path.append((node[0], node[1]))return Truemin_val = float('inf')rows, cols = len(grid), len(grid[0])neighbors = [(node[0] + dx, node[1] + dy, node[2] + 1) for dx, dy in [(-1, 0), (1, 0), (0, -1), (0, 1)]if 0 <= node[0] + dx < rows and 0 <= node[1] + dy < cols and grid[node[0] + dx][node[1] + dy] == 0]for neighbor in neighbors:result = dfs(grid, neighbor, goal, limit, path)if result is True:path.append((node[0], node[1]))return Trueif result < min_val:min_val = resultreturn min_val# IDA* 算法实现
def ida_star(grid, start, goal):limit = heuristic_ida(start, goal)while True:path = []result = dfs(grid, (*start, 0), goal, limit, path)if result is True:return path[::-1]if result == float('inf'):return Nonelimit = result# 示例使用
grid = [[0, 0, 0, 0],[0, 1, 1, 0],[0, 1, 0, 0],[0, 0, 0, 0]
]
start = (0, 0)
goal = (3, 3)
path = ida_star(grid, start, goal)
print("IDA* 算法找到的路径:", path)

3. A* vs IDA*:对比与选择
特性A*IDA*
内存占用高(需维护Open/Closed List)极低(仅递归栈)
时间复杂度通常更低(无重复搜索)可能更高(重复访问节点)
启发式要求可采纳性(必须)可采纳性(必须)
适用场景内存充足、需快速求解的问题内存受限、状态空间爆炸的问题
实现复杂度中等(需优先队列)简单(递归DFS)

4. 示例与启发式函数
  • 网格路径规划
    • 曼哈顿距离:( h(n) = |x_n - x_{goal}| + |y_n - y_{goal}| )(可采纳)。
  • 15数码问题
    • 错位方块数:不在目标位置的方块数(可采纳但较弱)。
    • 曼哈顿距离和:所有方块到目标位置的曼哈顿距离之和(更强启发式)。

5. 总结
  • 选择A*:需要快速求解且内存充足时优先使用。
  • 选择IDA*:面对超大状态空间或严格内存限制时(如嵌入式系统)。

两者均依赖启发式函数的质量,设计优秀的 ( h(n) ) 可大幅提升性能。实际应用中,可结合问题特点进行优化(如双向搜索、剪枝策略)。

相关文章:

算法——对比A*算法与IDA*算法

A*算法与IDA*算法详细解析 1. A*算法 核心思想&#xff1a; A*算法是一种启发式搜索算法&#xff0c;结合了Dijkstra算法的最短路径保证和贪心最佳优先搜索的高效导向性。其核心是评估函数 ( f(n) g(n) h(n) )&#xff0c;其中&#xff1a; ( g(n) ): 从起点到当前节点 ( …...

GitLab CI/CD 的配置详解:从零开始使用 .gitlab-ci.yml 文件

在现代软件开发中&#xff0c;CI/CD&#xff08;持续集成与持续部署&#xff09;已成为提高开发效率和代码质量的核心实践。GitLab CI/CD 提供了强大的功能&#xff0c;帮助开发者自动化构建、测试和部署应用程序。而 .gitlab-ci.yml 文件是 GitLab CI/CD 配置的关键所在&#…...

python语言进阶之函数

目录 前言 函数的创建和调用 函数创建 调用函数 参数传递 形式参数和实际参数 位置参数 数量必须与定义时一致 位置必须与定义时一致 关键字参数 为参数设置默认值 可变参数 **parameter 返回值 变量的作用域 局部变量 全局变量 匿名函数 前言 提到函数&…...

网络安全等级保护基本要求、测评要求、高风险判定指引综合梳理

网络安全等级保护基本要求、测评要求、高风险判定指引综合梳理 等级保护基本要求、测评要求、高风险判定指引综合梳理测评要求思维导图二级三级 花了些时间把网络安全等级保护涉及的以下三份标准文件进行了整理&#xff0c;以表格的形式进行展现&#xff0c;能帮助初学者更加直…...

JSON入门略要

JavaScript对象表示法&#xff08;JavaScript Object Notation&#xff0c;JSON&#xff09;已经成为RESTful接口设计中的事实标准。 JSON数据格式使得应用程序可以通过RESTful API等方式在网络上进行数据通信。 REST: 表现层状态转化&#xff08;REpresentation State Transf…...

Python爬虫抓取数据时,如何设置请求头?

在Python爬虫中设置请求头是确保爬虫能够正常运行并获取目标数据的关键步骤之一。请求头可以帮助我们模拟浏览器行为&#xff0c;避免被目标网站识别为爬虫。以下是如何在Python爬虫中设置请求头的详细指南&#xff1a; 一、使用requests库设置请求头 requests库是Python中最…...

以若依移动端版为基础,实现uniapp的flowable流程管理

1.前言 此代码是若依移动端版为基础&#xff0c;实现flowable流程管理&#xff0c;支持H5、APP和微信小程序三端。其中&#xff0c;APP是在安卓在雷电模拟器环境下完成的&#xff0c;其他环境未测试&#xff0c;此文章中所提及的APP均指上述环境。移动端是需要配合若依前后端分…...

DeepSeek 助力 Vue 开发:打造丝滑的开关切换(Switch)

前言&#xff1a;哈喽&#xff0c;大家好&#xff0c;今天给大家分享一篇文章&#xff01;并提供具体代码帮助大家深入理解&#xff0c;彻底掌握&#xff01;创作不易&#xff0c;如果能帮助到大家或者给大家一些灵感和启发&#xff0c;欢迎收藏关注哦 &#x1f495; 目录 Deep…...

unity学习39:连续动作之间的切换,用按键控制角色的移动

目录 1 不同状态之间的切换模式 1.1 在1个连续状态和一个连续状态之间的transition&#xff0c;使用trigger 1.2 在2个连续状态之间的转换&#xff0c;使用bool值切换转换 2 至少现在有2种角色的移动控制方式 2.1 用CharacterController 控制角色的移动 2.2 用animator…...

C++ ——构造函数

1、作用&#xff1a;创建对象时&#xff0c;给对象的属性进行初始化 2、特点 &#xff08;1&#xff09;构造函数与类同名 &#xff08;2&#xff09;如果没有显式给出构造函数&#xff0c;编译器会给出默认的构造函数&#xff08;参数为空&#xff0c;并且函数体也为空&#…...

Python实现语音识别详细教程【2025】最新教程

文章目录 前言一、环境搭建1. 下载 Python2. 安装 Python3 使用 pip 安装必要的库 二、使用 SpeechRecognition 库进行语音识别1.识别本地音频文件2.实时语音识别3. 使用其他语音识别引擎 注意事项 前言 以下是一份较为完整的 Python 语音识别教程&#xff0c;涵盖环境搭建、使…...

【第12章:深度学习与伦理、隐私—12.4 深度学习与伦理、隐私领域的未来挑战与应对策略】

凌晨三点的自动驾驶测试场,AI系统突然在暴雨中做出惊人决策——它选择撞向隔离带而不是紧急变道,因为算法推演发现隔离带后的应急车道站着五个工程师。这个惊悚的伦理困境,揭开了深度学习伦理危机最尖锐的冰山一角。 一、潘多拉魔盒已开:深度学习伦理的四大原罪 1.1 数据原…...

Django中数据库迁移命令

在 Django 中&#xff0c;数据库迁移是确保数据库结构与 Django 模型定义保持一致的重要过程。以下是 Django 中常用的数据库迁移命令&#xff1a; 1. python manage.py makemigrations 功能&#xff1a;此命令用于根据 Django 项目的模型文件&#xff08;models.py&#xff…...

Win11 远程 连接 Ubuntu20.04(局域网)

Win11 远程 连接 Ubuntu20.04(局域网&#xff09; 0. Ubuntu 开启共享1. Ubuntu系统中安装RDP服务器2.windows中连接使用方式1&#xff1a;远程桌面连接(winr: mstsc)方式2&#xff1a;mobaXterm 3 问题远程连接后出现黑屏 参考文献: 0. Ubuntu 开启共享 在ubunt设置中&#x…...

安卓手游内存call综合工具/内部call/安卓注入call/数据分析(类人猿学院)

进程分析注入综合工具总界面 模块分析函数分析遍历 函数分析 so汇编分析 汇编call植入器&#xff0c;支持模拟器x86 x64 和手机arm64指令全平台 防ce搜索数据功能 全国首套发布&#xff0c;阿凡老师学院最好的安卓内存逆向老师&#xff0c;几乎行业最强的&#xff0c;有兴趣可以…...

PPT工具集

PPT模版 免费下载 爱PPT优品PPTPPT之家第一PPTOfficePlus部分免费 AI生成PPT Kimi秘塔搜索 可以输入内容生成PPT大纲。...

SpringBoot:使用spring-boot-test对web应用做单元测试时如何测试Filter?

对SpringBoot的Web应用做单元测试时&#xff0c;一般会使用spring-boot-test&#xff0c;pom.xml中会添加如下内容&#xff1a; <dependency><groupId>org.springframework.boot</groupId><artifactId>spring-boot-starter-test</artifactId><…...

解锁 Java 回调函数:异步编程与事件处理的利器

什么是 Java 回调函数 在 Java 中&#xff0c;回调函数是一种编程模式&#xff0c;允许将一个方法作为参数传递给另一个方法&#xff0c;当某个特定事件发生或某个任务完成时&#xff0c;调用该方法。回调机制可以使代码更加灵活和可扩展&#xff0c;因为它允许在运行时动态地…...

记PasteSpider部署工具的Windows.IIS版本开发过程之草稿-Web.IIS.Administration解读(5)

本文是记录PasteSpider的Windows.IIS开发过程, 在应用开发中,结果很重要,但是开发过程中遇到的问题和思考绝对是更有意义的事情! 经历过不同的需求后,你会发觉案例项目还真的只是案例项目,和实际项目天差地别!!! PasteSpider是开发者专属部署工具, 新版本的支持Windo…...

MySQL Workbench安装教程以及菜单汉化

WorkBench的下载 直接给下载MySql WorkBench的链接&#xff0c;直接进入正题&#xff1a;MySQL :: Download MySQL Workbenchhttps://dev.mysql.com/downloads/workbench/进入了下载界面&#xff1a; &#xff08;安装路径自己看着办&#xff0c;注意安装路径不能有中文&#…...

【Axure高保真原型】引导弹窗

今天和大家中分享引导弹窗的原型模板&#xff0c;载入页面后&#xff0c;会显示引导弹窗&#xff0c;适用于引导用户使用页面&#xff0c;点击完成后&#xff0c;会显示下一个引导弹窗&#xff0c;直至最后一个引导弹窗完成后进入首页。具体效果可以点击下方视频观看或打开下方…...

Docker 离线安装指南

参考文章 1、确认操作系统类型及内核版本 Docker依赖于Linux内核的一些特性&#xff0c;不同版本的Docker对内核版本有不同要求。例如&#xff0c;Docker 17.06及之后的版本通常需要Linux内核3.10及以上版本&#xff0c;Docker17.09及更高版本对应Linux内核4.9.x及更高版本。…...

【根据当天日期输出明天的日期(需对闰年做判定)。】2022-5-15

缘由根据当天日期输出明天的日期(需对闰年做判定)。日期类型结构体如下&#xff1a; struct data{ int year; int month; int day;};-编程语言-CSDN问答 struct mdata{ int year; int month; int day; }mdata; int 天数(int year, int month) {switch (month){case 1: case 3:…...

超短脉冲激光自聚焦效应

前言与目录 强激光引起自聚焦效应机理 超短脉冲激光在脆性材料内部加工时引起的自聚焦效应&#xff0c;这是一种非线性光学现象&#xff0c;主要涉及光学克尔效应和材料的非线性光学特性。 自聚焦效应可以产生局部的强光场&#xff0c;对材料产生非线性响应&#xff0c;可能…...

【Linux】shell脚本忽略错误继续执行

在 shell 脚本中&#xff0c;可以使用 set -e 命令来设置脚本在遇到错误时退出执行。如果你希望脚本忽略错误并继续执行&#xff0c;可以在脚本开头添加 set e 命令来取消该设置。 举例1 #!/bin/bash# 取消 set -e 的设置 set e# 执行命令&#xff0c;并忽略错误 rm somefile…...

《Qt C++ 与 OpenCV:解锁视频播放程序设计的奥秘》

引言:探索视频播放程序设计之旅 在当今数字化时代,多媒体应用已渗透到我们生活的方方面面,从日常的视频娱乐到专业的视频监控、视频会议系统,视频播放程序作为多媒体应用的核心组成部分,扮演着至关重要的角色。无论是在个人电脑、移动设备还是智能电视等平台上,用户都期望…...

大型活动交通拥堵治理的视觉算法应用

大型活动下智慧交通的视觉分析应用 一、背景与挑战 大型活动&#xff08;如演唱会、马拉松赛事、高考中考等&#xff09;期间&#xff0c;城市交通面临瞬时人流车流激增、传统摄像头模糊、交通拥堵识别滞后等问题。以演唱会为例&#xff0c;暖城商圈曾因观众集中离场导致周边…...

屋顶变身“发电站” ,中天合创屋面分布式光伏发电项目顺利并网!

5月28日&#xff0c;中天合创屋面分布式光伏发电项目顺利并网发电&#xff0c;该项目位于内蒙古自治区鄂尔多斯市乌审旗&#xff0c;项目利用中天合创聚乙烯、聚丙烯仓库屋面作为场地建设光伏电站&#xff0c;总装机容量为9.96MWp。 项目投运后&#xff0c;每年可节约标煤3670…...

Qt Http Server模块功能及架构

Qt Http Server 是 Qt 6.0 中引入的一个新模块&#xff0c;它提供了一个轻量级的 HTTP 服务器实现&#xff0c;主要用于构建基于 HTTP 的应用程序和服务。 功能介绍&#xff1a; 主要功能 HTTP服务器功能&#xff1a; 支持 HTTP/1.1 协议 简单的请求/响应处理模型 支持 GET…...

相机Camera日志分析之三十一:高通Camx HAL十种流程基础分析关键字汇总(后续持续更新中)

【关注我,后续持续新增专题博文,谢谢!!!】 上一篇我们讲了:有对最普通的场景进行各个日志注释讲解,但相机场景太多,日志差异也巨大。后面将展示各种场景下的日志。 通过notepad++打开场景下的日志,通过下列分类关键字搜索,即可清晰的分析不同场景的相机运行流程差异…...