构造系统所有距离的算法3牛− 63N−6距离

计算科学 算法 计算几何 距离测量
2021-12-27 03:25:28

非线性分子具有个自由度(是原子数;忽略平移和旋转)。因此,一组距离和/或角度足以描述整个系统。3N6N3N6

我正在寻找一种算法,它将是点数)距离作为输入并计算所有距离。3N6NN(N1)/2

2个回答

假设您可以接受近似解决方案:您可以将问题重新表述为图嵌入(或度量嵌入)问题。

您的个原子是图的顶点(节点) 。对于您知道距离的每一对原子中创建一条边(链接) 。为每条边分配一个长度请注意,此图中的边缘与分子中的原子键无关,它们只是用来捕获已知距离。Na1,,aNG(ai,aj)Gd(ai,aj)

你的任务是找到一个嵌入的图形到 3 维空间中,这样,其中中的实际欧几里得距离。f:GR3R3dist(f(ai),f(aj))=d(ai,aj)distR3

一种方法是将边缘建模为弹簧,长度为并模拟生成的机械系统。从原子的任意位置开始。在每个时间步计算所有附着在原子上的弹簧的合力。向那个方向移动一点。重复。系统将在您的问题的解决方案处或附近停止(忽略振荡等)。模拟的停止标准可能是:它(几乎)停止移动,总能量已达到最小值,距离足够接近所需的等。d(ai,aj)d(ai,aj)

查看Forcedirected graph drawing,或者只是使用一些物理引擎来模拟整个事情。有很多关于这类模拟的文献,如何优化它们,如何避免陷入局部最小值等。

关于精确解决方案,我怀疑您无法获得封闭形式的解决方案,即某些公式将作为输入并产生原子的有效位置作为输出。将所有原子距离作为输出也是如此。d(ai,aj)

与 Berth 的建议类似,您可以修复一个原子并尝试最小化该函数

g(f)=(i,j)G[d(fi,fj)2dij2]2
在哪里f是一个 3D 坐标矩阵。此函数是非凸函数,应使用全局优化技术进行优化。