Lecture 21 Graphs 3 - A_ Kruskal 02

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

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 是一样的。

  ‍

  ‍

  ​​

  ‍

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

相关帖子

欢迎来到这里!

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

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

推荐标签 标签

  • Vim

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

    29 引用 • 66 回帖 • 3 关注
  • uTools

    uTools 是一个极简、插件化、跨平台的现代桌面软件。通过自由选配丰富的插件,打造你得心应手的工具集合。

    7 引用 • 28 回帖 • 2 关注
  • danl
    188 关注
  • PostgreSQL

    PostgreSQL 是一款功能强大的企业级数据库系统,在 BSD 开源许可证下发布。

    22 引用 • 22 回帖 • 4 关注
  • AngularJS

    AngularJS 诞生于 2009 年,由 Misko Hevery 等人创建,后为 Google 所收购。是一款优秀的前端 JS 框架,已经被用于 Google 的多款产品当中。AngularJS 有着诸多特性,最为核心的是:MVC、模块化、自动化双向数据绑定、语义化标签、依赖注入等。2.0 版本后已经改名为 Angular。

    12 引用 • 50 回帖 • 519 关注
  • SOHO

    为成为自由职业者在家办公而努力吧!

    7 引用 • 55 回帖
  • DNSPod

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

    6 引用 • 26 回帖 • 533 关注
  • OneNote
    1 引用 • 3 回帖 • 3 关注
  • Linux

    Linux 是一套免费使用和自由传播的类 Unix 操作系统,是一个基于 POSIX 和 Unix 的多用户、多任务、支持多线程和多 CPU 的操作系统。它能运行主要的 Unix 工具软件、应用程序和网络协议,并支持 32 位和 64 位硬件。Linux 继承了 Unix 以网络为核心的设计思想,是一个性能稳定的多用户网络操作系统。

    957 引用 • 944 回帖
  • sts
    2 引用 • 2 回帖 • 248 关注
  • BND

    BND(Baidu Netdisk Downloader)是一款图形界面的百度网盘不限速下载器,支持 Windows、Linux 和 Mac,详细介绍请看这里

    107 引用 • 1281 回帖 • 44 关注
  • 小说

    小说是以刻画人物形象为中心,通过完整的故事情节和环境描写来反映社会生活的文学体裁。

    32 引用 • 108 回帖 • 1 关注
  • Kafka

    Kafka 是一种高吞吐量的分布式发布订阅消息系统,它可以处理消费者规模的网站中的所有动作流数据。 这种动作(网页浏览,搜索和其他用户的行动)是现代系统中许多功能的基础。 这些数据通常是由于吞吐量的要求而通过处理日志和日志聚合来解决。

    36 引用 • 35 回帖 • 1 关注
  • Google

    Google(Google Inc.,NASDAQ:GOOG)是一家美国上市公司(公有股份公司),于 1998 年 9 月 7 日以私有股份公司的形式创立,设计并管理一个互联网搜索引擎。Google 公司的总部称作“Googleplex”,它位于加利福尼亚山景城。Google 目前被公认为是全球规模最大的搜索引擎,它提供了简单易用的免费服务。不作恶(Don't be evil)是谷歌公司的一项非正式的公司口号。

    49 引用 • 192 回帖
  • Tomcat

    Tomcat 最早是由 Sun Microsystems 开发的一个 Servlet 容器,在 1999 年被捐献给 ASF(Apache Software Foundation),隶属于 Jakarta 项目,现在已经独立为一个顶级项目。Tomcat 主要实现了 JavaEE 中的 Servlet、JSP 规范,同时也提供 HTTP 服务,是市场上非常流行的 Java Web 容器。

    162 引用 • 529 回帖 • 10 关注
  • C++

    C++ 是在 C 语言的基础上开发的一种通用编程语言,应用广泛。C++ 支持多种编程范式,面向对象编程、泛型编程和过程化编程。

    108 引用 • 153 回帖
  • 工具

    子曰:“工欲善其事,必先利其器。”

    302 引用 • 772 回帖
  • RemNote
    2 引用 • 16 回帖 • 26 关注
  • Windows

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

    232 引用 • 484 回帖
  • 人工智能

    人工智能(Artificial Intelligence)是研究、开发用于模拟、延伸和扩展人的智能的理论、方法、技术及应用系统的一门技术科学。

    120 引用 • 323 回帖
  • FlowUs

    FlowUs.息流 个人及团队的新一代生产力工具。

    让复杂的信息管理更轻松、自由、充满创意。

    1 引用 • 1 关注
  • Hibernate

    Hibernate 是一个开放源代码的对象关系映射框架,它对 JDBC 进行了非常轻量级的对象封装,使得 Java 程序员可以随心所欲的使用对象编程思维来操纵数据库。

    39 引用 • 103 回帖 • 726 关注
  • 互联网

    互联网(Internet),又称网际网络,或音译因特网、英特网。互联网始于 1969 年美国的阿帕网,是网络与网络之间所串连成的庞大网络,这些网络以一组通用的协议相连,形成逻辑上的单一巨大国际网络。

    98 引用 • 367 回帖
  • 996
    13 引用 • 200 回帖 • 1 关注
  • 友情链接

    确认过眼神后的灵魂连接,站在链在!

    24 引用 • 373 回帖 • 2 关注
  • SSL

    SSL(Secure Sockets Layer 安全套接层),及其继任者传输层安全(Transport Layer Security,TLS)是为网络通信提供安全及数据完整性的一种安全协议。TLS 与 SSL 在传输层对网络连接进行加密。

    70 引用 • 193 回帖 • 414 关注
  • Ngui

    Ngui 是一个 GUI 的排版显示引擎和跨平台的 GUI 应用程序开发框架,基于
    Node.js / OpenGL。目标是在此基础上开发 GUI 应用程序可拥有开发 WEB 应用般简单与速度同时兼顾 Native 应用程序的性能与体验。

    7 引用 • 9 回帖 • 412 关注