我有一个网格,在这个网格中,我必须将多个节点(单元)与单个分支路径(在不同位置的障碍物单元)连接起来。从本质上说,路径是双向的。任何节点都可以是源或目标,而不影响问题。我想用一个最便宜的分支路径连接所有选定的节点。
目前,我所使用的方法如下:
我们选择一个任意顺序的节点,比如1,2,5,0,3,4.
对于各种这样的订单,重复上述过程,直到我们找到最便宜的可能路径。然而,我觉得这个方法非常,非常不理想,必须有一个更好的方法来解决这个问题。
我还发现了这个类似的问题(pathfinding with multiple source and sinks?),但在本例中,输出似乎有多个paths.But,在我的示例中,我希望有一个连接所选节点的路径(允许分支)。我有一种感觉,Dijkstra的算法(至少根据我对它的有限理解)可能是在这种情况下起作用的算法。
任何帮助(论文或文章)将不胜感激。谢谢。
发布于 2022-09-30 13:03:18
我想你是在找一棵支撑树

https://en.wikipedia.org/wiki/Spanning_tree
不希望连接所有节点,但是在一个由大量节点组成的网格中,只有很少的特定节点。
计算每个特定节点( Dijkstra )之间最便宜的路径(Dijkstra),删除所有不是specific
https://stackoverflow.com/questions/73904249
复制相似问题