距离度量的组合优化

Question

我有一组轨迹，由轨迹上的点组成，并与每个点相关联的坐标。我将它们存储在一个3d数组中(轨迹、点、参数)。我想找出在这些轨迹的可能成对组合之间具有最大累积距离的r个轨迹集。我的第一次尝试，我认为是有效的，如下所示：

max_dist = 0
for h in itertools.combinations ( xrange(num_traj), r):
    for (m,l) in itertools.combinations (h, 2):
        accum = 0.
        for ( i, j ) in itertools.izip ( range(k), range(k) ):
            A = [ (my_mat[m, i, z] - my_mat[l, j, z])**2 \
                    for z in xrange(k) ]
            A = numpy.array( numpy.sqrt (A) ).sum()
            accum += A
    if max_dist < accum:
        selected_trajectories = h

这需要很长时间，因为num_traj可能在500-1000左右，r可能在5-20左右。K是任意的，但通常可以高达50。

为了变得超级聪明，我把所有东西都放到了两个嵌套的列表理解中，大量使用了itertools：

chunk = [[ numpy.sqrt((my_mat[m, i, :] - my_mat[l, j, :])**2).sum() \
        for ((m,l),i,j) in \
        itertools.product ( itertools.combinations(h,2), range(k), range(k)) ]\
        for h in itertools.combinations(range(num_traj), r) ]

除了相当难读(！)之外，它还需要很长时间。有没有人能建议一些改进的方法呢？

Answer 1

您可以从计算所有轨迹对之间的距离开始，而不是根据需要重新计算每对轨迹之间的距离。您可以将它们存储在字典中，并根据需要进行查找。

这样，您的内部循环for (i,j) ...将被替换为常量时间查找。

Answer 2

您可以在距离计算上放弃平方根计算...最大和也将具有最大平方和，尽管这只会产生恒定的加速比。

Answer 3

除了每个人都提到的以外，这里还有一些有趣的观点和建议。(顺便说一下，mathmike建议生成一个所有配对距离的查找列表，这是您应该立即实施的建议。它从你的算法复杂度中去除了O(r^2)。)

首先，台词

for ( i, j ) in itertools.izip ( range(k), range(k) ):
    A = [ (my_mat[m, i, z] - my_mat[l, j, z])**2 \
        for z in xrange(k) ]

可以替换为

for i in xrange(k):
    A = [ (my_mat[m, i, z] - my_mat[l, i, z])**2 \
        for z in xrange(k) ]

因为i和j在每个循环中总是相同的。这里根本不需要使用izip。

第二，关于这条线

A = numpy.array( numpy.sqrt (A) ).sum()

你确定这是你想要的计算方式吗？可能是这样，但我觉得这很奇怪，因为如果这更像是向量之间的欧几里得距离，那么这条线就是：

A = numpy.sqrt (numpy.array( A ).sum())

或者只是

A = numpy.sqrt(sum(A))

因为我认为使用numpy的sum函数将A转换为numpy数组会比使用内置的Python sum函数慢，但我可能错了。而且，如果它真的是你想要的欧几里德距离，那么你这样做的sqrt就会更少。

第三，你是否意识到你可能会尝试迭代多少个潜在的组合？对于num_traj = 1000和r= 20的最坏情况，据我估计大约是6.79E42个组合。使用您当前的方法，这是相当难处理的。即使对于num_traj = 500和r= 5的最好情况，也是1.28E12组合，这是相当多的组合，但也不是不可能的。这是你在这里遇到的真正的问题，因为根据mathmike的建议，我提到的前两点并不是很重要。

那你能做什么呢？嗯，你需要更聪明一点。我还不清楚什么是最好的方法。我猜你需要以某种方式使算法具有启发式。我的一个想法是尝试一种带有启发式的动态编程方法。对于每个轨迹，您可以找到它与另一个轨迹的每个配对的距离的总和或平均值，并将其用作适应度度量。一些具有最低适合度的轨迹可以在转移到三人组之前删除。然后，你可以对三人组做同样的事情:找到每个轨迹所涉及的所有三人组(在剩余的可能轨迹中)的累积距离的总和或平均值，并将其用作适应度度量，以决定在进入四人组之前丢弃哪些轨迹。它不能保证最优解，但它应该很好，而且我相信它会大大降低解决方案的时间复杂度。