我有一个完整的无向图,其中节点表示平面上点上的点,而边是点之间的近似欧氏距离.我想把这个图"嵌入"二维空间.也就是说,我想将每个顶点转换为(x,y)位置元组,以便对于任意两个顶点v和w,边(v,w)具有接近dist(v,w)的权重.
例如,如果我有带有节点A,B,C和D的图形以及带有权重(A,B)的边:20; (A,C):22; (A,D):26; (B,C):30; (B,D):20,(C,D):19,然后你可以分配点A:(0,0); B:(10,0); C:(0,10); D:(10,10).显然这是不完美的,但它是一个合理的近似值.
我不关心获得最好的解决方案,我只想在合理的时间内找到合理的解决方案.
(如果你想要解决这个问题的动机.我有一个物理系统,我对所有点对的距离进行噪声测量.距离测量是嘈杂的,但往往是真实值的两倍.我有进行了所有这些测量,现在有一个包含数千个节点和数百万个边的图,并希望将这些点放在一个平面上.)