algorithm - 元素放置算法

Question

因此，我正在寻找一种算法来确定元素的放置位置，但是，我很难将我对位置“优度”的测量形式化。

这就是问题所在:我有一组 k 项，我想将它们沿一条线放置。每个项目都有一个宽度，并且任何两个项目都不能重叠。每个项目也有一个对应的区间——所有的区间都是固定的，不重叠的，并且形成了某段线的分区。

我想放置每个项目，使其在其间隔中居中，但我不能保证间隔比项目宽。

因此，作为妥协，我愿意将项目部分(或全部)移出它们的间隔。但是，我不愿意更改项目的顺序(它们必须保持间隔的顺序)。

是否有一个好的算法可以根据我的(松散定义的)度量找到项目沿线的“最佳”位置？

Answer 1

好吧，这里有一个解决方案，也许是我可以解释您的问题的最简单方法:

让我们假设对于每个项目，我们考虑两种可能性:

1. 我们将其放置在预期位置(即区间的中心)

2. 我们不

然后，我们可以将这个问题重新表述为以下函数:找到可以放置在其区间中心而不重叠的项的最大子集合。

这似乎应该有一个贪婪的解决方案，但我必须承认，我能做的最好的事情就是想出一个非常简单的动态规划算法。以下是我制定递归的方式:

假设我们正在考虑第 n 个项目(从左边开始)，并且我们想要分配它以使该项目的左边缘不超过所有前面项目的最右前方。那么，最优分配必须满足:

best_align(n, right) = 
     if center[n]-radius[n] > right[n]:
          max(best_align(n+1, right+radii[n], 1+best_align(n+1,center[n]+radius[n])
     else:
          best_align(n+1, right+radius[n])

这有一个明显的 DP 解决方案，我用 python 编写了它。这是结果:

#Assumes that the items are sorted left-to-right by their centers
def best_align(radii, centers):

    assignments = { (radii[0]+centers[0]):[0], (-100000):[] }

    for i in range(1, len(radii)):

        nc = centers[i] + radii[i]
        nassignments = { nc : [i] }

        for right, assigned in assignments.items():

            #Handle case where object is not inserted
            nr = right+radii[i]
            if not nr in nassignments or len(assigned) > len(nassignments[nr]):
                nassignments[nr] = assigned

            #Handle inclusion case
            if right <= centers[i]-radii[i] and len(assigned) >= len(nassignments[nc]):
                nassignments[nc] = assigned + [i]


        assignments = nassignments

    return max([ (len(l), l) for l in assignments.values() ])[1]

变量半径是各个项目的半径，而中心是目标分配位置。该算法返回可以放置在所需位置的项目的最大子集。剩下的项目只需要尽可能地捏造。例如，这里有一些输出:

In [11]: plc.best_align( [ 1, 5, 1], [0, 2, 3] )

Out[11]: [2]

另一个例子:

In [18]: plc.best_align( [1, 10, 1, 1, 1, 1, 1], [0, 2, 4, 6, 8, 10, 12] )

Out[18]: [2, 3, 4, 5, 6]

由于处理分配集的方式很朴素，此实现的时间复杂度是立方的。通过将 python 列表替换为对它们构建的先前列表的引用，可以轻松优化以获得二次解决方案(尽管这会使演示文稿更糟糕)。