小龙~ 2017-10-30 08:35 采纳率: 0%
浏览 2017

A* 的可采纳性，谁能证明

没有理解 A* 算法的可采纳性证明，感觉是不完整的。自己理解下来，感觉如果 A* 是可采纳的
需要满足如下条件的一个：
要么在算法过程中扩展当前选中节点的邻居节点时，是考虑对 close 中节点进行松散的
要么启发函数是单调非递增的

或者说如上的某个条件是属于 A* 算法的定义呢？？

  • 写回答

1条回答 默认 最新

  • devmiao 2017-10-30 13:40
    关注

    这个问题你可以结合教材综合分析下

    评论

报告相同问题？

  • A*算法可采纳性、一致性、最优性证明
    2024-06-16 10:33
    a man of sadness的博客 基于求解静态图最短路的经典A*算法（A星算法）论文，系统完整的证明了算法的可采纳性、一致性、最优性，能够深入了解算法的原理及有效性，方便后续代码编写
  • A*算法及其最优性证明
    2023-07-17 22:46
    啵啵张的博客 A*算法结合了代价一致搜索（Uniform Cost Search）中使用的真实后向成本和贪心算法搜索（Greedy Search）中使用的预估前向成本，组成了总估计成本。在选择节点进行扩展时，选择总估计成本最小的节点。——代价一致...
  • 关于A*启发式搜索最优性的证明(图解)
    2022-03-26 16:24
    skyoung13的博客 关于A*启发式搜索最优性的证明(图解) 证明在h(n)可采纳时A*是最优搜索
  • 如何证明在启发函数h(n)是可采纳的情况下树搜索的A*算法的最优性
    2020-01-01 21:10
    phoebus_si的博客 思路：证明最优解A的祖先节点n要比次优解B先被拓展即可。 关于树搜索A*算法的具体概念可以参考：https://blog.csdn.net/zhulichen/article/details/78786493 详细证明思路如图 ...
  • 【读论文】A*算法的最短证明
    2025-10-09 17:15
    szlm的博客 本文解读了A算法原论文中关于结果最短性的证明，重点分析了在启发函数h'(n)满足可采纳性(admissible)时，A算法找到的路径一定是最短路径的证明过程。文章首先定义了相关概念和A算法流程，然后详细解释了关键引理1...
  • Optimality of A* Search A*搜索的最优性
    2021-10-10 20:33
    hulahula118的博客 一致性（consistent）和可采纳性（admissible）（是的 又是这些抽象的词 唉难理解） 然后我们可以知道下面两个性质（你也可以不知道 先记下来） 如果h(n)是可采纳的，那么 A* 的树搜索版本是最优的; 如果h(n)是一致...
  • A*搜索算法之8数码问题
    2026-01-02 14:05
    π同学的博客 本文介绍了A搜索算法在8数码问题中的应用。...实验结果证明，该启发函数对大多数初始状态有效，但存在部分状态不可采纳的情况，导致算法退化为A算法而无法找到解。作者指出寻找完美可采纳的启发函数具有挑战性。
  • A*算法详解
    2016-08-09 15:11
    N_irvana的博客 第一部分：A*算法简介  写这篇文章的初衷是应一个网友的要求，当然我也发现现在有关人工智能的中文站点实在太少，我在这里 抛砖引玉，希望大家都来热心的参与。   还是说正题，我先拿A*算法开刀，是因为A*在...
  • [AI]A*算法
    2020-10-16 23:14
    是土豆大叔啊！的博客 A*算法一、A*算法原理二、做个例题吧~三、A*算法的最优性1.可采纳启发式 Admissible Heuristic2.一致性启发式 Consistent Heuristic四、A*算法的性能 一、A*算法原理 相比贪婪最优搜索的f(n)=h(n)f(n)=h(n)f(n)=h(n)...
  • 【人工智能】—Admissible Heuristics可采纳启发式函数
    2023-03-21 22:58
    之墨_的博客 也是可容许的并且dominates h a ， h b h_a，h_b ha​，hb​ 使用 评价函数 f ( n ) = g ( n ) + h ( n ) f(n) = g(n) +h(n) f(n)=g(n)+h(n)搜索 h(n)=错放数字个数 g(n) = 节点深度 结果如下： 松弛操作 有些复杂...
  • 基于A*算法的旅行商问题求解实战
    2025-11-03 23:06
    无形小手的博客 通过设计合理的估价函数f(n)=g(n)+h(n)，其中g(n)为已走路径代价，h(n)为满足可接纳性条件的启发式估计，可在有限规模下有效缩小搜索空间。本文介绍如何使用C语言实现A 算法解决TSP问题，涵盖图结构构建、开放/关闭...
  • A*算法笔记
    2022-04-05 15:05
    Mapleaf98的博客 一个关于A*算法简单原理与实现
  • A*算法原理以及证明
    2025-11-27 15:10
    糖葫芦君的博客 可采纳性的本质是 “启发函数不吹牛”—— 预估的到终点的代价，永远不会比实际需要的多。因为 “不吹牛”，A * 算法不会因为 “某个节点看起来离终点近（h 值小）” 就盲目扩展它，而是会兼顾 “已经走的路（g 值）...
  • MATLAB路径规划：A*算法与三维空间应用
    2025-06-15 09:23
    周立-ric的博客 易于上手和使用：MATLAB使用的是直观的命令行界面，即使是编程新手也能通过简单的一行命令实现复杂的数学运算。丰富的工具箱：提供了各种专业领域的工具箱，如信号处理、图像处理、神经网络等。强大的绘图功能。
  • A*（Astar）算法详解与应用
    2025-09-03 09:57
    @Mr.stone的博客 A*算法是一种高效的路径搜索算法，结合了...同时指出启发函数必须满足可采纳性（h(n)≤实际代价）才能保证找到最优路径。最后提供了一个交互式HTML演示工具，支持设置障碍物、切换启发函数并实时观察算法执行过程。
  • 人工智能搜索策略：A*算法
    2020-06-04 22:31
    南有芙蕖的博客 局部择优搜索A*算法1. A*算法的可纳性2. A*算法的最优性3. h(n)的单调限制A* 算法应用举例对A*算法的一点思考熟练掌握A*算法的性质A*算法的性质A*算法的最优性h(n)的单调限制讲A*算法的意义！ A算法 在图搜索算法中...
  • 给定一个启发式函数满足h(G)=0,其中G是目标状态，证明如果h是一致的，那么它是可采纳的。
    2019-10-03 11:11
    姬小野的博客 给定一个启发式函数满足h(G)=0,其中G是目标状态，证明如果h是一致的，那么它是可采纳的。 证明如下: 假设nnn为任意状态, GGG为某目标状态, 且n,N1,N2,...,Nm,Gn, N_1, N_2, ..., N_m, Gn,N1​,N2​,...,Nm​,G为从...
  • 搜索专题——A*算法
    2022-04-23 14:45
    04号憨憨的博客 什么是A*算法？ A*算法是一种结合了启发函数的宽搜算法，当搜索空间巨大时，我们可以为宽搜加上一个启发函数，来降低搜索的时空复杂度。 A*算法的原理是什么？ 在A*算法中： 定义 F(n)F(n)F(n) 为搜索树上节点的估计...
  • 没有解决我的问题, 去提问