首页
学习
活动
专区
圈层
工具
发布
社区首页 >问答首页 >寻找连接多个节点的最便宜路径

问寻找连接多个节点的最便宜路径
EN

Stack Overflow用户
提问于 2022-09-30 05:05:19
回答 1查看 147关注 0票数 0

我有一个网格,在这个网格中,我必须将多个节点(单元)与单个分支路径(在不同位置的障碍物单元)连接起来。从本质上说,路径是双向的。任何节点都可以是源或目标,而不影响问题。我想用一个最便宜的分支路径连接所有选定的节点。

目前,我所使用的方法如下:

我们选择一个任意顺序的节点,比如1,2,5,0,3,4.

  • First,我们在两个节点之间创建最便宜的路径,在这种情况下,我们使用A*在节点1和2之间创建最便宜的路径。然后,我们使用第三个节点(在本例中为5个),找到第三个节点和1到2个最便宜路径之间的最便宜的路径。然后,我们选择路径,这是所有路径中最短的。

  • ,我们重复这个过程,直到我们有了连接所有节点的路径为止。

对于各种这样的订单,重复上述过程,直到我们找到最便宜的可能路径。然而,我觉得这个方法非常,非常不理想,必须有一个更好的方法来解决这个问题。

我还发现了这个类似的问题(pathfinding with multiple source and sinks?),但在本例中,输出似乎有多个paths.But,在我的示例中,我希望有一个连接所选节点的路径(允许分支)。我有一种感觉,Dijkstra的算法(至少根据我对它的有限理解)可能是在这种情况下起作用的算法。

任何帮助(论文或文章)将不胜感激。谢谢。

EN

回答 1

Stack Overflow用户

回答已采纳

发布于 2022-09-30 13:03:18

我想你是在找一棵支撑树

​

​

https://en.wikipedia.org/wiki/Spanning_tree

不希望连接所有节点,但是在一个由大量节点组成的网格中,只有很少的特定节点。

计算每个特定节点( Dijkstra )之间最便宜的路径(Dijkstra),删除所有不是specific

  • Remove的节点,所有边缘都是

  • ,用them

  • Calculate生成树之间最便宜的路径的代价在特定节点之间添加边缘。
票数 1
EN
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://stackoverflow.com/questions/73904249

复制
相关文章

相似问题

领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档