Lecture 21 Graphs 3 - A_ Kruskal 02

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

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 关注

相关帖子

欢迎来到这里!

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

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

推荐标签 标签

  • 小薇

    小薇是一个用 Java 写的 QQ 聊天机器人 Web 服务,可以用于社群互动。

    由于 Smart QQ 从 2019 年 1 月 1 日起停止服务,所以该项目也已经停止维护了!

    35 引用 • 468 回帖 • 762 关注
  • NGINX

    NGINX 是一个高性能的 HTTP 和反向代理服务器,也是一个 IMAP/POP3/SMTP 代理服务器。 NGINX 是由 Igor Sysoev 为俄罗斯访问量第二的 Rambler.ru 站点开发的,第一个公开版本 0.1.0 发布于 2004 年 10 月 4 日。

    315 引用 • 547 回帖
  • Wide

    Wide 是一款基于 Web 的 Go 语言 IDE。通过浏览器就可以进行 Go 开发,并有代码自动完成、查看表达式、编译反馈、Lint、实时结果输出等功能。

    欢迎访问我们运维的实例: https://wide.b3log.org

    30 引用 • 218 回帖 • 646 关注
  • 导航

    各种网址链接、内容导航。

    45 引用 • 177 回帖
  • 单点登录

    单点登录(Single Sign On)是目前比较流行的企业业务整合的解决方案之一。SSO 的定义是在多个应用系统中,用户只需要登录一次就可以访问所有相互信任的应用系统。

    9 引用 • 25 回帖 • 3 关注
  • abitmean

    有点意思就行了

    36 关注
  • DNSPod

    DNSPod 建立于 2006 年 3 月份,是一款免费智能 DNS 产品。 DNSPod 可以为同时有电信、网通、教育网服务器的网站提供智能的解析,让电信用户访问电信的服务器,网通的用户访问网通的服务器,教育网的用户访问教育网的服务器,达到互联互通的效果。

    6 引用 • 26 回帖 • 532 关注
  • HHKB

    HHKB 是富士通的 Happy Hacking 系列电容键盘。电容键盘即无接点静电电容式键盘(Capacitive Keyboard)。

    5 引用 • 74 回帖 • 521 关注
  • 面试

    面试造航母,上班拧螺丝。多面试,少加班。

    326 引用 • 1395 回帖
  • PWA

    PWA(Progressive Web App)是 Google 在 2015 年提出、2016 年 6 月开始推广的项目。它结合了一系列现代 Web 技术,在网页应用中实现和原生应用相近的用户体验。

    14 引用 • 69 回帖 • 184 关注
  • OpenCV
    15 引用 • 36 回帖 • 1 关注
  • LaTeX

    LaTeX(音译“拉泰赫”)是一种基于 ΤΕΧ 的排版系统,由美国计算机学家莱斯利·兰伯特(Leslie Lamport)在 20 世纪 80 年代初期开发,利用这种格式,即使使用者没有排版和程序设计的知识也可以充分发挥由 TeX 所提供的强大功能,能在几天,甚至几小时内生成很多具有书籍质量的印刷品。对于生成复杂表格和数学公式,这一点表现得尤为突出。因此它非常适用于生成高印刷质量的科技和数学类文档。

    12 引用 • 59 回帖
  • Maven

    Maven 是基于项目对象模型(POM)、通过一小段描述信息来管理项目的构建、报告和文档的软件项目管理工具。

    188 引用 • 319 回帖 • 236 关注
  • 资讯

    资讯是用户因为及时地获得它并利用它而能够在相对短的时间内给自己带来价值的信息,资讯有时效性和地域性。

    56 引用 • 85 回帖 • 1 关注
  • Netty

    Netty 是一个基于 NIO 的客户端-服务器编程框架,使用 Netty 可以让你快速、简单地开发出一个可维护、高性能的网络应用,例如实现了某种协议的客户、服务端应用。

    49 引用 • 33 回帖 • 42 关注
  • 房星科技

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

    6 引用 • 141 回帖 • 615 关注
  • 创业

    你比 99% 的人都优秀么?

    81 引用 • 1395 回帖
  • Pipe

    Pipe 是一款小而美的开源博客平台。Pipe 有着非常活跃的社区,可将文章作为帖子推送到社区,来自社区的回帖将作为博客评论进行联动(具体细节请浏览 B3log 构思 - 分布式社区网络)。

    这是一种全新的网络社区体验,让热爱记录和分享的你不再感到孤单!

    134 引用 • 1127 回帖 • 109 关注
  • 百度

    百度(Nasdaq:BIDU)是全球最大的中文搜索引擎、最大的中文网站。2000 年 1 月由李彦宏创立于北京中关村,致力于向人们提供“简单,可依赖”的信息获取方式。“百度”二字源于中国宋朝词人辛弃疾的《青玉案·元夕》词句“众里寻他千百度”,象征着百度对中文信息检索技术的执著追求。

    63 引用 • 785 回帖 • 68 关注
  • WebComponents

    Web Components 是 W3C 定义的标准,它给了前端开发者扩展浏览器标签的能力,可以方便地定制可复用组件,更好的进行模块化开发,解放了前端开发者的生产力。

    1 引用 • 14 关注
  • 大数据

    大数据(big data)是指无法在一定时间范围内用常规软件工具进行捕捉、管理和处理的数据集合,是需要新处理模式才能具有更强的决策力、洞察发现力和流程优化能力的海量、高增长率和多样化的信息资产。

    89 引用 • 113 回帖 • 1 关注
  • 安装

    你若安好,便是晴天。

    132 引用 • 1184 回帖 • 1 关注
  • 游戏

    沉迷游戏伤身,强撸灰飞烟灭。

    187 引用 • 832 回帖
  • MySQL

    MySQL 是一个关系型数据库管理系统,由瑞典 MySQL AB 公司开发,目前属于 Oracle 公司。MySQL 是最流行的关系型数据库管理系统之一。

    694 引用 • 537 回帖 • 3 关注
  • CodeMirror
    2 引用 • 17 回帖 • 174 关注
  • DevOps

    DevOps(Development 和 Operations 的组合词)是一组过程、方法与系统的统称,用于促进开发(应用程序/软件工程)、技术运营和质量保障(QA)部门之间的沟通、协作与整合。

    59 引用 • 25 回帖 • 2 关注
  • Gzip

    gzip (GNU zip)是 GNU 自由软件的文件压缩程序。我们在 Linux 中经常会用到后缀为 .gz 的文件,它们就是 Gzip 格式的。现今已经成为互联网上使用非常普遍的一种数据压缩格式,或者说一种文件格式。

    9 引用 • 12 回帖 • 184 关注