寻路算法的可视化解释 关于 Dijkstra A* BFS (寻路算法的可行性)

文章编号:36850 最新资讯 2024-11-30 寻路算法

译者:AI研习社( 季一帆 )

双语原文链接: Interactive Pathfinding


点此链接进入交互展示页面:

广度优先搜索、Dijkstra和A*是图上的三种典型路径规划。它们都可用于图搜索,不同之处在于队列和启发式函数两个参数。

本项目探索并可视化不同算法如何根据选择参数进行图搜索。

算法的一般性原理如下:

将边界初始化为包含起始节点的队列。

当边界队列不为空时,从队列中“访问”并删除一个“当前”节点,同时将访问节点的每个邻居节点添加到队列,其成本是到达当前节点的成本加上从当前节点访问邻居的成本再加上邻居节点和目标节点的启发式函数值。其中,启发式函数是对两个节点的路径成本的估计。

存储访问路径(通常存储在cameFrom图中),以便后续重建路径。如果邻居节点已经在列表中,同时新路径的成本较低,那么更改其成本。

找到目标路径(提前退出)或列表为空时,停止算法。

使用先进先出队列实现BFS。这种队列会忽略路径中链接的开销,并根据跳数进行扩展,因此可以确保找到最短路径的跳数,而跳数相关的成本。启发式函数的选择是任意的,因为在这个过程中其并不起作用。

使用数组可实现先进先出,即将元素附加到末尾并从头删除。

关于 A*、Dijkstra、BFS 寻路算法的可视化解释

在图上使用优先级队列和始终返回0的启发式函数,便得到Dijkstra。

相比于BFS,Dijkstra最大的不同在于考虑了成本。通过该算法,可以根据节点到节点的成本找到最短路径。

优先级队列使用数组实现,在每次插入新节点后对该数组进行排序。尽管实现优先级队列还有其他更高效的方式,但在我们的场景中,数组是足够快的,而且实现起来也简单。

关于 A*、Dijkstra、BFS 寻路算法的可视化解释

为实现A*,需要传递一个实际启发式函数,例如两个节点之间的欧式距离。通过“节点成本”+“节点到目标节点的估算成本”对节点进行加权,通过优先搜索更大可能的节点加快搜索速度。

关于 A*、Dijkstra、BFS 寻路算法的可视化解释

非允许的启发式函数

只有应用可允许启发式函数,A*才能找到最短路径,这也意味着永远不会高估实际路径长度。由于欧氏距离是两点之间的最短距离/路径,因此欧氏距离绝不会超出。

但如果将其乘以常数k>0会怎样呢?这样会高估距离,成为非允许的启发式函数。

关于 A*、Dijkstra、BFS 寻路算法的可视化解释

实现

本项目通过script实现,以便读者在Web上进行访问。另外,我使用react渲染UI,使用react-konva渲染图形。

路径发现是指接受队列类型和启发式函数,并返回另一个函数,即真实路径发现(称为currying)。

这样,用户每次更改设置后,都会使用确定参数创建一个新的路径发现函数,并将之用于图搜索。

为可视化路径发现的步骤,我使用javascript生成器,这意味着函数返回一个迭代器,而不仅仅是一个值。因此,访客在每一步都可以生成算法的整个状态,并将其保存到数组,然后通过页面顶部的滑块显示特定状态。


AI研习社是AI学术青年和AI开发者技术交流的在线社区。我们与高校、学术机构和产业界合作,通过提供学习、实战和求职服务,为AI学术青年和开发者的交流互助和职业发展打造一站式平台,致力成为中国最大的科技创新人才聚集地。

如果,你也是位热爱分享的AI爱好者。欢迎与 译站 一起,学习新知,分享成长。

关于 A*、Dijkstra、BFS 寻路算法的可视化解释

版权文章,未经授权禁止转载。详情见 转载须知 。

关于 A*、Dijkstra、BFS 寻路算法的可视化解释


本文地址: /article/d18e54c799879e3bb758.html
全局中部横幅
全局中部横幅
新疆生活服务网站 - 新疆生活服务网站排名 - 网站排行榜

新疆生活服务网站排名,根据网站的综合值按照不同的新疆生活服务网站进行筛选排名结果,通过筛选新疆生活服务网站可以看到每个新疆生活服务网站里面的网站排名优质的网站是哪些

360游戏中心,我创造你快乐 - 首页-360网页游戏|webgame|网页游戏|免费游戏|游戏开服|游戏攻略|游戏大全

360游戏中心是超好玩的的免费安全游戏平台,为亿万360玩家提供各种新鲜好玩的免费游戏及超值游戏礼包福利-360游戏中心,我创造你快乐!

小游戏网站导航大全-LOL网址导航网

LOL网址导航网是专业的上网导航网站,精心收录各类优质热门网站信息,同时提供天气、快递、违章等各种生活便民查询工具网址,为您提供安全便捷的上网导航服务,现已被众多网友设为上网主页,网址导航大全首选LOL网址导航.

下厨房

下厨房美食菜谱网倡导在家烹饪、健康的生活方式,提供有版权的实用菜谱做法与饮食知识,提供厨师和美食爱好者一个记录、分享的平台。

饼干的家常做法_饼干的做法大全_怎么做饼干

饼干的做法_家常饼干的做法非常简单易学。豆果美食提供的图文饼干的家常做法大全和饼干的视频,用最短的时间让你学会饼干的做法

BLUEHORIZON 海润

中国绿色建筑行业和建筑通风行业领导者

电动滚筒,防爆电动滚筒-淄博欧汉特电动滚筒有限公司

淄博欧汉特电动滚筒有限公司,是生产电动滚筒的专业厂家。全套型号有YDB型,YDB-h型,YZB型隔爆油冷式防爆电动滚筒,YTH,YZW,WD型外装隔爆。电话:0533-4661118

中国香港身份多种方式仅需8999  去中介化一站式服务平台

我们洗牌传统香港移民行业,打破传统移民行业思维和模式,迎来移民新时代。直击痛点,服务上来,费用下去。我们承诺只做服务与咨询,无套路,无中介,去中间商差价,只做申请源头;让每一个申请的客户以市场申请的实际成本价申请自己所需的项目。

傲蓝眼镜销售管理软件-眼镜店管理系统(眼镜店软件)|眼镜门店销售软件|眼镜店收银系统|眼镜店连锁管理软件|眼镜店行业管理软件|眼镜进销存软件

傲蓝眼镜店销售管理软件全面支持眼镜,镜架,镜片,隐形眼镜等的销售管理,满足眼镜行业所有商品需求。眼镜店管理系统的功能可以支持条码扫描,会员管理,验光单管理,单码单品,单码多品,丰富营业统计报表...通过傲蓝眼镜店销售管理软件,管理员随时随地全面掌握企业状况,下达指示。

安徽金冠玻璃有限责任公司

安徽金冠玻璃有限责任公司是一家集设计,研发,生产制造,深加工为一体的中型民营企业,专业生产,加工各种中,高档日用玻璃器皿与瓶罐产品

中胜涂料(宁波)有限公司

中胜涂料(宁波)有限公司主营业务为船舶油漆,工业重防腐水性漆,销售网络遍布国内国外,并与多家公司合作代理各种品牌油漆。

全局底部横幅