Lecture 21 Graphs 3 - A_ Kruskal 02

本贴最后更新于 338 天前,其中的信息可能已经时移俗易

image

  1. 初始化

    • 每个顶点的初始成本设为无穷大,除了起始顶点 (v1),它的成本为 0。
    • 创建一个优先队列 pqueue​,按照 cost + heuristic​(成本 + 启发式)排序,并且最初只包含起始顶点 (v_)。
    • 这里的启发式函数 ( H ( v1, v2 ) ) 是对从当前顶点到目标顶点的估计成本。
  2. 主循环

    • pqueue​ 不为空时:

      1. pqueue​ 中取出一个顶点 (v) 并标记为访问过。

      2. 对于 (v) 的每个未访问过的邻居 (n):

        • 计算从起始点经过 (v) 到达 (n) 的总成本:v​ 的当前成本 + 边权重 + 启发式估计 (H(n, v2))。
        • 如果 (n) 不在 pqueue​ 中,或者新的成本比 (n) 的当前成本更低,则更新 (n) 的成本,并将 (n) 重新加入 pqueue​ 中,同时记录当前顶点 (v) 作为 (n) 的前驱节点。
  3. 重建路径

    • 当所有节点都处理完毕后,通过追踪前驱节点,重建从目标顶点 (v2) 到起始顶点 (v1) 的最短路径。

  通过引入启发式信息,A*算法在探索路径时更具方向性,它能够优先考虑那些更有可能通向目标的路径,从而提高算法的效率。

  ‍

   哦哦,这里就能看出 A*算法相对于 dijkstra 算法的优越性了,粗糙的说,A*算法是具有方向性的(他不会南辕北辙),因为 A*想要尽可能的靠近两点之间的最短距离,所以南辕北辙的方向会被 A*舍弃。

  一视频胜千言,你最好自己去看看 A*算法是如何减少一半的搜索量的(A*算法只会搜索一个方向)。

  2 分 46 秒。

  顺便一提,如果你的图是无权图,那么 dijkstra 算法就是 BFS。

  “所以 A*算法确实更倾向于朝着目标前进”

  8 分 52 秒, 在现实世界中,地球重力会让水天然的执行 dijkstra 算法。

  流动总是避开高地,沿低地蔓延,你会注意到它并不想往山上走,因为那样代价太大,所以它不喜欢那个方向。

  ‍

  我看懂了,A*算法基于这样一个假设:“两点之间线段最短,虽然正确答案不一定是用铅笔直接从起点画一条线到终点,但至少也应该八九不离十。”

Image #2333:e:\git-supermemobackup\supermemobackup\sm18-lazy-package-1.3.1\sm18\systems\all in one\elements\instantpaste\instantpaste_2024-07-31_21_58_45.png

  所以要是有人搞 A*算法的心态,专门把正确答案做成南辕北辙(比如说我要从中国去美国,但是有人在太平洋造了一堵环球墙把中美两国彻底隔开,只在南极点留一个门),那么最坏的情况下,A*算法很可能要沿着环球墙舔舐地球四分之三周(如图所示,A*算法朝着北极前进,绕地球四分之三圈后到达南极点)才能找到南极点的那个门。

  你的理解非常有趣且准确。A*算法确实假设最短路径大致遵循直线或至少是合理的接近。然而,如果环境中存在特定的障碍或曲折路径,特别是那些与启发式信息相悖的情况,A*算法可能会遇到效率问题。

  在你提到的极端情况中,启发式函数可能会误导 A*算法,使它沿着错误的方向扩展搜索,甚至在最坏的情况下绕很大的圈子(如你描述的绕地球四分之三周的情景)来找到正确的路径。这种情况下,启发式函数的作用反而可能使算法的效率变得低下,甚至逼近 Dijkstra 算法的表现,因为启发式不再能有效引导搜索过程。

  为了解决这样的问题,有些变体的 A*算法可能会采用不同的启发式函数,或者动态调整启发式权重,以应对那些特殊的情况。不过,对于典型的路径规划任务,A*算法通常表现得很好,尤其是在地图或图结构较为“常规”的情况下。

  ‍

  不过,我不确定是否真的存在一种情况,让 A*检查的顶点比 Dijkstra 更多,即使是在这张“环球墙”图里,最坏的 A*看起来也和普通的 dijkstra 是一样的。

  ‍

  ‍

  ​​

  ‍

  • 算法
    424 引用 • 254 回帖 • 24 关注

相关帖子

欢迎来到这里!

我们正在构建一个小众社区,大家在这里相互信任,以平等 • 自由 • 奔放的价值观进行分享交流。最终,希望大家能够找到与自己志同道合的伙伴,共同成长。

注册 关于
请输入回帖内容 ...

推荐标签 标签

  • Facebook

    Facebook 是一个联系朋友的社交工具。大家可以通过它和朋友、同事、同学以及周围的人保持互动交流,分享无限上传的图片,发布链接和视频,更可以增进对朋友的了解。

    4 引用 • 15 回帖 • 444 关注
  • 黑曜石

    黑曜石是一款强大的知识库工具,支持本地 Markdown 文件编辑,支持双向链接和关系图。

    A second brain, for you, forever.

    24 引用 • 246 回帖
  • Hadoop

    Hadoop 是由 Apache 基金会所开发的一个分布式系统基础架构。用户可以在不了解分布式底层细节的情况下,开发分布式程序。充分利用集群的威力进行高速运算和存储。

    93 引用 • 122 回帖 • 619 关注
  • Vim

    Vim 是类 UNIX 系统文本编辑器 Vi 的加强版本,加入了更多特性来帮助编辑源代码。Vim 的部分增强功能包括文件比较(vimdiff)、语法高亮、全面的帮助系统、本地脚本(Vimscript)和便于选择的可视化模式。

    29 引用 • 66 回帖
  • JWT

    JWT(JSON Web Token)是一种用于双方之间传递信息的简洁的、安全的表述性声明规范。JWT 作为一个开放的标准(RFC 7519),定义了一种简洁的,自包含的方法用于通信双方之间以 JSON 的形式安全的传递信息。

    20 引用 • 15 回帖 • 25 关注
  • Log4j

    Log4j 是 Apache 开源的一款使用广泛的 Java 日志组件。

    20 引用 • 18 回帖 • 37 关注
  • SMTP

    SMTP(Simple Mail Transfer Protocol)即简单邮件传输协议,它是一组用于由源地址到目的地址传送邮件的规则,由它来控制信件的中转方式。SMTP 协议属于 TCP/IP 协议簇,它帮助每台计算机在发送或中转信件时找到下一个目的地。

    4 引用 • 18 回帖 • 633 关注
  • 大疆创新

    深圳市大疆创新科技有限公司(DJI-Innovations,简称 DJI),成立于 2006 年,是全球领先的无人飞行器控制系统及无人机解决方案的研发和生产商,客户遍布全球 100 多个国家。通过持续的创新,大疆致力于为无人机工业、行业用户以及专业航拍应用提供性能最强、体验最佳的革命性智能飞控产品和解决方案。

    2 引用 • 14 回帖
  • CodeMirror
    2 引用 • 17 回帖 • 173 关注
  • Eclipse

    Eclipse 是一个开放源代码的、基于 Java 的可扩展开发平台。就其本身而言,它只是一个框架和一组服务,用于通过插件组件构建开发环境。

    76 引用 • 258 回帖 • 624 关注
  • Spark

    Spark 是 UC Berkeley AMP lab 所开源的类 Hadoop MapReduce 的通用并行框架。Spark 拥有 Hadoop MapReduce 所具有的优点;但不同于 MapReduce 的是 Job 中间输出结果可以保存在内存中,从而不再需要读写 HDFS,因此 Spark 能更好地适用于数据挖掘与机器学习等需要迭代的 MapReduce 的算法。

    74 引用 • 46 回帖 • 565 关注
  • FFmpeg

    FFmpeg 是一套可以用来记录、转换数字音频、视频,并能将其转化为流的开源计算机程序。

    23 引用 • 32 回帖 • 2 关注
  • OpenCV
    15 引用 • 36 回帖
  • Angular

    AngularAngularJS 的新版本。

    26 引用 • 66 回帖 • 561 关注
  • Office

    Office 现已更名为 Microsoft 365. Microsoft 365 将高级 Office 应用(如 Word、Excel 和 PowerPoint)与 1 TB 的 OneDrive 云存储空间、高级安全性等结合在一起,可帮助你在任何设备上完成操作。

    5 引用 • 34 回帖
  • IDEA

    IDEA 全称 IntelliJ IDEA,是一款 Java 语言开发的集成环境,在业界被公认为最好的 Java 开发工具之一。IDEA 是 JetBrains 公司的产品,这家公司总部位于捷克共和国的首都布拉格,开发人员以严谨著称的东欧程序员为主。

    181 引用 • 400 回帖
  • Rust

    Rust 是一门赋予每个人构建可靠且高效软件能力的语言。Rust 由 Mozilla 开发,最早发布于 2014 年 9 月。

    59 引用 • 22 回帖 • 9 关注
  • 外包

    有空闲时间是接外包好呢还是学习好呢?

    26 引用 • 233 回帖 • 6 关注
  • iOS

    iOS 是由苹果公司开发的移动操作系统,最早于 2007 年 1 月 9 日的 Macworld 大会上公布这个系统,最初是设计给 iPhone 使用的,后来陆续套用到 iPod touch、iPad 以及 Apple TV 等产品上。iOS 与苹果的 Mac OS X 操作系统一样,属于类 Unix 的商业操作系统。

    89 引用 • 150 回帖 • 3 关注
  • H2

    H2 是一个开源的嵌入式数据库引擎,采用 Java 语言编写,不受平台的限制,同时 H2 提供了一个十分方便的 web 控制台用于操作和管理数据库内容。H2 还提供兼容模式,可以兼容一些主流的数据库,因此采用 H2 作为开发期的数据库非常方便。

    11 引用 • 54 回帖 • 671 关注
  • VirtualBox

    VirtualBox 是一款开源虚拟机软件,最早由德国 Innotek 公司开发,由 Sun Microsystems 公司出品的软件,使用 Qt 编写,在 Sun 被 Oracle 收购后正式更名成 Oracle VM VirtualBox。

    10 引用 • 2 回帖 • 18 关注
  • 七牛云

    七牛云是国内领先的企业级公有云服务商,致力于打造以数据为核心的场景化 PaaS 服务。围绕富媒体场景,七牛先后推出了对象存储,融合 CDN 加速,数据通用处理,内容反垃圾服务,以及直播云服务等。

    29 引用 • 230 回帖 • 123 关注
  • Windows

    Microsoft Windows 是美国微软公司研发的一套操作系统,它问世于 1985 年,起初仅仅是 Microsoft-DOS 模拟环境,后续的系统版本由于微软不断的更新升级,不但易用,也慢慢的成为家家户户人们最喜爱的操作系统。

    229 引用 • 476 回帖
  • SQLite

    SQLite 是一个进程内的库,实现了自给自足的、无服务器的、零配置的、事务性的 SQL 数据库引擎。SQLite 是全世界使用最为广泛的数据库引擎。

    4 引用 • 7 回帖 • 1 关注
  • 博客

    记录并分享人生的经历。

    273 引用 • 2389 回帖
  • 房星科技

    房星网,我们不和没有钱的程序员谈理想,我们要让程序员又有理想又有钱。我们有雄厚的房地产行业线下资源,遍布昆明全城的 100 家门店、四千地产经纪人是我们坚实的后盾。

    6 引用 • 141 回帖 • 606 关注
  • 反馈

    Communication channel for makers and users.

    120 引用 • 906 回帖 • 277 关注