MATLAB的答案

试用软件

最小生成树——路径或起始-结束

13个视图(30天)

显示旧的评论

先生 2021年6月17日

0

评论道: 先生2021年6月18日

答:接受克里斯汀Tobler

你好,

我计算3 d点的最小生成树和现在想提取路径(即节点每个节点)整个MST。

(编辑)

我用下面的代码:

                         %德劳内三角
                        
                         DT = delaunayTriangulation (pts);% pts (nx3):输入点
                        
                         e = DT.edges;
                        
                         %的边缘距离权重
                        
                         plist1 =分(e (: 1):);
                        
                         plist2 =分(e (:, 2):);
                        
                         差别= plist2-plist1;
                        
                         dist = vecnorm(差别);
                        
                         %创建图
                        
                         图G = (e (: 1), e(:, 2),距离);
                        
                         %建立最小生成树
                        
                         (mst, pred) = minspantree (G);

我完全忘了描述非常特殊的输入数据。从一个轨道数据采样测量系统(3 d位置),所以MST 几乎一个完美的路径,鲜有例外。

前任节点矢量并不似乎适合我的需要。我希望点拓扑排序,但事实并非如此,如果我使用这个向量输入点。

基本上,对我来说就足够了就确定“开始”和“结束”树的节点,就像内置的plot-function。然后,我可以计算最短路径,这将给我一个节点列表。换句话说,我想从mst提取(19578、2207)。

这是一幅plot-function结果。如果情节函数立即几乎可以做到这一点,必须有一个方法我能做到。

谢谢你！

(编辑)

我现在想出了这个解决方案。它不需要太长,但是超过情节功能,也发现node-pair“开始”和“结束”,所以我想有可能是一个“诡计”。

                         函数idx = sortMST(分)
                        
                         %函数来构建mst如上图所示
                        
                         [mst, ~] = buildMST (pts);
                        
                         %的端点
                        
                         d1nodes =找到(学位(mst) = = 1);
                        
                         %的node-pair最大距离是我正在寻找的
                        
                         dist =距离(mst d1nodes d1nodes);
                        
                         最大= max (max(经销));
                        
                         [我~]=找到(dist = =最大);
                        
                         %图广度优先搜索,连接所有节点并寻找路径
                        
                         idx = bfsearch (mst d1nodes(我));
                        
                         结束

0评论
显示隐藏1以上的评论

登录置评。

在回答这个问题。

接受的答案

克里斯汀Tobler 2021年6月17日

0
链接

直接链接到这个答案

//www.tatmou.com/matlabcentral/answers/858495-minimum-spanning-tree-path-or-start-end answer_726995

一般来说,你不能指望一个最小生成树就是一条路。然而,如果你有一个图形,是这样,你可以找到的两个叶节点之间的路径是如下:

rng默认的;

图G = (sprandn (10、10、0.6),“上”)

G =

图属性:边缘:[22×2表]节点:(10×0表)

T = minspantree (G);

%图G,突出节点和边的T

p =情节(G);

突出(p、T);

%计算T的叶节点(节点只有一个边)

leafNodes =找到(学位(T) = = 1)

leafNodes = 4×1

1 2 6 8

%如果T只是一长串,leafNodes两个元素,

%,您可以使用

% shortestpath (t, leafNodes (1) leafNodes (2));

%发现路径

5个评论
显示隐藏 4年长的评论

克里斯汀Tobler 2021年6月17日

啊,我明白了,然后有分支在MST图,只是太小看到可能(也就是说,某些节点在MST危害性程度2)。

你可以尝试使用数据从情节,情节的对象有XData和YData坐标可用。但这算法只是承诺给一个好的近似的结构,没有保证的极端XData / YData将包含相距最远的节点。

还可以写一个迭代算法来避免计算所有节点之间的距离,但它会很复杂,所以不确定这将是值得的,我没有试过以下任何编码。谨慎行事。

作为第一步,你会选择一个节点作为根,并使用shortestpathtree计算有向图从根节点开始。

向上移动的节点,从叶节点(倒序bfsearch或dfsearch从根)。

为每个节点,跟踪到它下面的叶子节点的距离最远的一个,和距离的节点。同时,在全球范围内我们要跟踪的两个叶节点之间的最大距离发现到目前为止,和叶节点。

当一个分支到达(节点有超过一个的继任者),你可以总结两个后续节点之间的距离最远的距离他们的叶节点。如果这是比当前最大限度地遥远的两个叶节点,更新。

当到达树的顶端,全局变量将包含最遥远的叶节点。

它发生在我我们可能需要确保根节点并不是一个叶子节点的算法。

先生 2021年6月18日

谢谢你的详细回答!我将标志着这是解决目前但我会记住你的想法的迭代算法,如果距离计算变得昂贵。现在,在50000的输入点,只有200叶节点,所以跑的非常快。

登录置评。

答案(1)

史蒂文的主 2021年6月17日

0
链接

直接链接到这个答案

//www.tatmou.com/matlabcentral/answers/858495-minimum-spanning-tree-path-or-start-end answer_726990

如果情节函数可以这样做几乎立即

的情节函数中扮演“连接这些点”。的开始和结束线是向量中第一个和最后一个点,你进入它,所以没有“确定”。(好吧,如果你策划图或有向图 ,并试图确定节点应该使用的文档中描述的各种布局功能的布局图和有向图的输入情节功能,但我认为这不是你的意思。)

你是如何计算最小生成树吗?你创建一个图或有向图对象和调用 minspantree 吗?

你会怎么考虑的“开始”和“结束”巴基图的最小生成树吗?

图g =(巴基);

m = minspantree (g);

h =情节(g);

持有在

情节(m,“XData”h.XData,“YData”h.YData,“EdgeColor”,“r”,“线宽”4)

从目视检查节点42,58岁,30岁,47岁,59岁,或者57都是潜在的候选人很多其他节点。你说这棵树开始和结束在哪里?

1评论
显示隐藏 None

先生 2021年6月17日

谢谢你的回答!我更新了我的问题细节。情节函数(或布局管理器)似乎对点进行排序,因为订单,或者开始和结束节点总是完全节点我寻找。很不幸的是,这些点并不简单地对应于第一行和最后一行的MST输出。我发现解决我的问题,但它不是最优的。也许也不是最优,但plot-function设法让它迷惑我。

登录置评。

在回答这个问题。

类别

MATLAB 数学图和网络算法

标签

社区寻宝

找到宝藏在MATLAB中央,发现社区如何帮助你!

开始狩猎!

试用软件