3

我有一个松散连接的图。对于该图中的每条边，我知道节点v和w在位置p(v)和p(w ) 之间的近似距离 d(v,w )作为R3 中的向量，而不仅仅是欧几里得距离。误差应该很小（假设 < 3%）并且第一个节点位于 <0,0,0>。

如果根本没有错误，我可以这样计算节点位置：

set p(first_node) = <0,0,0>
calculate_position(first_node)

calculate_position(v):
    for (v,w) in Edges:
        if p(w) is not set:
            set p(w) = p(v) + d(v,w)
            calculate_position(w)
    for (u,v) in Edges:
        if p(u) is not set:
            set p(u) = p(v) - d(u,v)
            calculate_position(u)

距离的误差不相等。但是为了简单起见，假设相对误差(d(v,w)-d'(v,w))/E(v,w)是 N(0,1)-正态分布的。我想最小化平方误差的总和

sum( ((p(v)-p(w)) - d(v,w) )^2/E(v,w)^2 ) for all edges

该图可能具有中等数量的节点（> 100），但节点之间只有一些连接并且已被“预过滤”（如果这些子图之间只有一个连接，则拆分为子图）。

我尝试了一个简单的“物理模型”，钩子很低，但速度慢且不稳定。这类问题有更好的算法或启发式方法吗？

4

1 回答 1

2

这看起来像线性回归。采用以下形式的误差项，即没有正方形并拆分为单独的坐标：

(px(v) - px(w) - dx(v,w))/E(v,w)
(py(v) - py(w) - dy(v,w))/E(v,w)
(pz(v) - pz(w) - dz(v,w))/E(v,w)

如果我对您的理解正确，您正在寻找 valuespx(v)和所有节点py(v)，以使上述项的平方和最小化。pz(v)v

您可以通过以下方式创建矩阵A和向量b来做到这一点：每一行对应于上述形式的方程之一，而A 的每一列对应一个变量，即单个坐标。对于n个顶点和m个边，矩阵A将有 3 m行（因为您将坐标分开）和 3 n -3 列（因为您还固定了第一个节点）。px(0)=py(0)=pz(0)=0

for 的行在 for 的列(px(v) - px(w) - dx(v,w))/E(v,w)中将有一个条目，1/E(v,w)在 for 的列中将有一个条目。所有其他列将为零。向量b中的相应条目将是。px(v)-1/E(v,w)px(w)dx(v,w)/E(v,w)

现在求解线性方程( A T · A ) x = A T · b其中A T表示A的转置。解向量x将包含顶点的坐标。您可以将其分解为三个独立的问题，每个坐标方向一个，以减小线性方程组的大小。

于 2013-05-06T12:52:33.910 回答