使用给定（错误的）节点距离优化图形的布局-Java 学习之路

我有一个松散连接的图表 . 对于该图中的每个边，我知道位置p（v）和p（w）处的节点v和w之间的近似距离d（v，w）为 a vector in 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），但节点之间只有一些连接，并且已经“预先过滤”（如果这些子图之间只有一个连接，则分成子图） .

我尝试了一个简单的"physical model"与hooks low但它的缓慢和不稳定 . 对于这类问题，是否有更好的算法或启发式算法？

1 回答

2
这看起来像linear regression . 采用以下形式的错误术语，即没有正方形并拆分成单独的坐标：
```
(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) .

现在求解linear equation（AT·A）x = AT·b，其中AT表示A的transpose . 解向量x将包含顶点的坐标 . 您可以将其分解为三个独立的问题，每个问题对应一个坐标方向，以保持线性方程组的大小不变 .
回复于 2024-05-07T04:24:34+08:00

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

1 回答

相关问题