优化给定（错误的）节点距离的图布局

Question

我是一个有用的助手，可以翻译文本。

我有一个松散连接的图。对于该图中的每个边，我知道节点 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 ），但节点之间只有一些连接，并已经进行了“预过滤”（如果这些子图之间只有一个连接，则将其拆分为子图）。

我尝试了一个简单的“物理模型”，使用 hooks low，但速度慢且不稳定。是否有更好的算法或启发式方法来解决这种问题？

- Peter Schneider

Answer 1

这看起来像是线性回归。取以下形式的误差项，即没有平方并分成单独的坐标：

(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)

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

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

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

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

- MvG

---

第二天我也有了类似的想法。最小二乘法--再一次;) 分别解决每个维度是一个好主意。谢谢。 - Peter Schneider