0

我目前正在通过使用一种贪心算法通过从最大到最小的集合迭代集合来做到这一点。如果我更关心找到最佳解决方案而不是效率，那么选择什么好的算法？

详细信息：
1）每个集合都有一个预定义的范围
2）我的目标是最终得到很多密集的集合，而不是减少集合的总数。

示例：假设范围是8。

集合可能是：[1,5,7], [2,6], [3,4,5], [1,2], [4],[1]
一个好的结果是[1,5,7,2,6,4], [3,4,5,1,2],[1]

4

3 回答 3

1

这是一个非常复杂的问题。很可能使用更复杂的图形算法可以以比我想出的更有效的方式解决这个问题，但这就是我所拥有的。生成所有解决方案会很慢，但由于它是一个生成器，可能从第一个n中选择一个解决方案可能是一种选择，具体取决于您的具体情况。

它不解决哪个解决方案最好的问题，它只是生成所有可能的解决方案。此外，您没有足够清楚地指定“最佳”密集包装是什么。在您的原始示例中（没有[4]），解决方案是否12567-12345-1优于123456-157-12？如果是这样，为什么？说到长度，解决方案 1 将是 (5, 5, 1)，而解决方案 2 将是 (6, 2, 3)。哪个更好？

input = map(set, [ [1,5,7], [2,6], [3,4,5], [1,2], [4], [1] ])

def eachCombination(input):
  if input:
    for combination, rest in eachCombination(input[1:]):
      yield combination, input[0:1] + rest
      if not (input[0] & combination):  # fits?
        yield input[0] | combination, rest
  else:
    yield set(), []

def eachPacked(input):
  for combination, rest in eachCombination(input):
    for restPart in rest:
      if not (combination & restPart):  # not densely packed?
        break
    else:
      yield combination, rest

def eachSolution(input):
  for packed, rest in eachPacked(input):
    if rest:
      for subsolution in eachSolution(rest):
        yield [ packed ] + subsolution
    else:
      yield [ packed ]

for solution in eachSolution(input):
  print '   '.join('-'.join('%d' % n for n in set) for set in solution)

这将打印

1-2-3-4-5   1-2-4-5-6-7   1
1-2-3-4-5   1-2-4-6   1-5-7
1-2-4-5-6-7   1-2-3-4-5   1
1-2-4-5-6-7   1-3-4-5   1-2
1-2-4   1-2-5-6-7   1-3-4-5
1-2-4   1-2-3-4-5-6   1-5-7
1-2-3-4-5-6   1-4-5-7   1-2
1-2-3-4-5-6   1-2-4   1-5-7
1-2-4-6   1-5-7   1-2-3-4-5
1-2-4-6   1-2-3-4-5   1-5-7
于 2013-05-24T13:04:38.217 回答
1

这是一个近似值，使用动态规划：

http://ideone.com/SI1wEs

from operator import itemgetter

def find_maximum_set(sets):
    results = []
    for si,s in enumerate(sets):
        sn = len(s)
        new_set = set(s) # if nothing else works, add the set by itself
        new_len = sn
        new_is = [si]

        # try to combine it with all the previous results, picking the one that
        # would produce the largest union
        for rn,ris,r in results:
            if r.isdisjoint(s):
                rs = r.union(s)
                if rn+sn > new_len:
                    new_set = rs
                    new_len = rn+sn
                    new_is = ris + [si]

        # add the new set to the result collection
        results.append((new_len,new_is,new_set))

    # return the largest result
    return max(results, key=itemgetter(0))

def find_all_maximum_sets(sets):
    sets = list(sets)
    result = []
    while len(sets) > 0:
        _, indexes, largest = find_maximum_set(sets)
        result.append(largest)
        sets = [s for i,s in enumerate(sets) if i not in indexes]
    return result

例子：

>>> find_all_maximum_sets([[1,5,7], [2,6], [3,4,5], [1,2] , [4], [1]])
[set([1, 2, 4, 5, 6, 7]), set([1, 2, 3, 4, 5]), set([1])]
于 2013-05-24T13:23:02.297 回答
0

我不确定它是否会给出最佳解决方案，但只是重复合并两个最大的非重叠集不起作用？

于 2013-05-24T12:34:38.203 回答