15

我有一个元素列表，每个元素都用一种类型标识，我需要重新排序列表以最大化相同类型元素之间的最小距离。

集合很小（10 到 30 个项目），所以性能并不是很重要。

每种类型的项目数量或类型数量没有限制，数据可以被认为是随机的。

例如，如果我有一个列表：

  • 5项A
  • 3项B
  • 2项C
  • 2 项 D
  • 1项E
  • 1 项 F

我想制作类似： A, B, C, A, D, F, B, A, E, C, A, D, B,A

  • A 在两次出现之间至少有 2 项
  • B 在两次出现之间至少有 4 个项目
  • C在出现之间有6个项目
  • D 在出现之间有 6 个项目

有没有一种算法可以实现这一点？

-更新-

在交换了一些意见后，我得出了次要目标的定义：

  • 主要目标：最大化相同类型元素之间的最小距离，仅考虑距离较小的类型。
  • 次要目标：最大化每种类型元素之间的最小距离。IE：如果一个组合增加了某种类型的最小距离而不减少其他，那么选择它。

-更新2-

关于答案。有很多有用的答案，虽然没有一个是两个目标的解决方案，特别是第二个目标，这很棘手。

关于答案的一些想法：

  • PengOne：听起来不错，虽然它没有提供具体的实现，并且并不总是根据第二个目标导致最好的结果。
  • Evgeny Kluev : 为主要目标提供了具体的实现，但并没有根据次要目标导致最好的结果。
  • tobias_k：我喜欢随机方法，它并不总能带来最好的结果，但它是一个很好的近似值并且具有成本效益。

我尝试了 Evgeny Kluev、回溯和 tobias_k 公式的组合，但它需要太多时间才能得到结果。

最后，至少对于我的问题，我认为 tobias_k 是最合适的算法，因为它的简单性和及时的良好结果。可能，它可以使用Simulated annealing来改进。

4

6 回答 6

5

首先，您还没有定义明确的优化问题。如果您想最大化相同类型的两个项目之间的最小距离，那是很好定义的。如果你想最大化两个 A 之间、两个 B 和 ... 之间以及两个 Z 之间的最小距离，那么这不是很好定义的。您如何比较两种解决方案：

  1. A 至少相距 4，B 至少相距 4，C 至少相距 2
  2. A 至少相距 3，B 至少相距 3，C 至少相距 4

你需要一个明确的“好”（或者更准确地说，“更好”）的衡量标准。我现在假设度量是：最大化同一项目中任意两个之间的最小距离。

这是一个实现最小距离的算法，ceiling(N/n(A))其中N是项目的总数，n(A)是 instance 的项目数A，假设它A是最多的。

  • 订购项目类型A1, A2, ... , Ak。n(Ai) >= n(A{i+1})
  • 将列表初始化L为空。
  • 对于jfrom kto 1，将 type 的项Ak尽可能均匀地分布在L.

示例：给定问题中的分布，算法产生：

F
E, F
D, E, D, F
D, C, E, D, C, F
B, D, C, E, B, D, C, F, B
A, B, D, A, C, E, A, B, D, A, C, F, A, B
于 2012-09-11T19:28:24.580 回答
4

这听起来像是一个有趣的问题，所以我只是试了一下。这是我用 Python 完成的超级简单的随机方法：

def optimize(items, quality_function, stop=1000):
    no_improvement = 0
    best = 0
    while no_improvement < stop:
        i = random.randint(0, len(items)-1)
        j = random.randint(0, len(items)-1)
        copy = items[::]
        copy[i], copy[j] = copy[j], copy[i]
        q = quality_function(copy)
        if q > best:
            items, best = copy, q
            no_improvement = 0
        else:
            no_improvement += 1
    return items

正如评论中已经讨论的那样，真正棘手的部分是质量函数，它作为参数传递给优化器。经过一番尝试，我想出了一个几乎总能产生最佳结果的方法。感谢pmoleri指出如何提高效率。

def quality_maxmindist(items):
    s = 0
    for item in set(items):
        indcs = [i for i in range(len(items)) if items[i] == item]
        if len(indcs) > 1:
            s += sum(1./(indcs[i+1] - indcs[i]) for i in range(len(indcs)-1))
    return 1./s

这里有一些随机结果：

>>> print optimize(items, quality_maxmindist)
['A', 'B', 'C', 'A', 'D', 'E', 'A', 'B', 'F', 'C', 'A', 'D', 'B', 'A']

请注意，通过另一个质量函数，相同的优化器可以用于不同的列表重新排列任务，例如作为（相当愚蠢的）随机排序器。

于 2012-09-11T19:36:45.950 回答
3

这是一种算法，它只最大化相同类型元素之间的最小距离，除此之外什么都不做。以下列表用作示例：

AAAAA BBBBB CCCC DDDD EEEE FFF GG
  • 按每种类型的元素数量以降序对元素集进行排序。实际上，只有最大的集合 (A & B) 以及那些少一个元素的元素集合 (C & D & E) 应该放在列表的头部。其他集合可能未排序。
  • 为每个最大集合中的一个元素在数组中保留 R 个最后位置，将剩余数组平均分配给最大集合的 S-1 个剩余元素。这给出了最佳距离：K = (N - R) / (S - 1)。将目标数组表示为具有 K 列和 L = N / K 整行（并且可能是具有 N % K 个元素的部分行）的 2D 矩阵。例如，我们有 R = 2、S = 5、N = 27、K = 6、L = 4 的集合。
  • 如果矩阵有 S - 1 个完整行，则使用最大集合 (A & B) 的元素填充此矩阵的前 R 列，否则从最后一个开始依次填充所有列。

对于我们的示例，这给出了：

AB....
AB....
AB....
AB....
AB.

如果我们尝试以相同的顺序用其他集合填充剩余的列，则会出现问题：

ABCDE.
ABCDE.
ABCDE.
ABCE..
ABD

最后一个'E'距离第一个'E'只有5个位置。

  • 从最后一列开始依次填充所有列。

对于我们的示例，这给出了：

ABFEDC
ABFEDC
ABFEDC
ABGEDC
ABG

回到线性数组，我们有：

ABFEDCABFEDCABFEDCABGEDCABG

以下是对这个问题使用模拟退火的尝试（C 源）：http: //ideone.com/OGkkc。

于 2012-09-12T14:06:31.567 回答
0

我相信你可以把你的问题看作是一堆物理上相互排斥的粒子。您可以迭代到“稳定”的情况。

基本伪代码：

force( x, y ) = 0 if x.type==y.type
                1/distance(x,y) otherwise 

nextposition( x, force ) = coined?(x) => same
                           else => x + force

notconverged(row,newrow) = // simplistically
   row!=newrow

row=[a,b,a,b,b,b,a,e]; 
newrow=nextposition(row);
while( notconverged(row,newrow) )
   newrow=nextposition(row);

我不知道它是否会收敛，但这是一个想法:)

于 2012-09-11T19:37:44.267 回答
0

这是另一种方法。

如果每个项目必须与同一类型的每个其他项目保持至少 k 个位置，则从左到右写下项目，跟踪每种类型剩下的项目数量。在每一点放下一个你可以合法放下的最大数量的项目。

如果同一类型的项目不超过 ceil(N / k) 个，这将适用于 N 个项目，因为它将保留此属性 - 在放下 k 个项目后，我们有 k 个更少的项目，并且我们已经放下了至少一个以该类型的 ceil(N / k) 个项目开头的每种类型。

给定一堆混合项目，你可以计算出你可以支持的最大 k，然后布置项目来解决这个 k。

于 2015-03-27T20:49:17.427 回答
0

我确信可能有更有效的解决方案，但这里有一种可能性：

首先，请注意，很容易找到产生相同类型的最小距离为 1 的排序。只需使用任何随机排序，MDBIOST 将至少为 1，如果不是更多的话。

因此，从 MBIOST 为 2 的假设开始。基于 MBIOST 为 2 的假设，对可能排序的空间进行递归搜索。您可以使用许多条件来修剪此搜索中的分支。如果找到有效的排序，则终止搜索。

如果您找到了一个有效的方法，请再试一次，假设 MBDIST 将为 3。然后 4... 以此类推，直到搜索失败。

更新：实际上最好从一个高数字开始，因为这会更多地限制可能的选择。然后逐渐减少数量，直到找到有效的排序。

于 2012-09-11T19:42:47.493 回答