为一组组合建立最高分数

Question

我正在使用Python进行编程。

我有以下形式的数据：

(A, B, C, D, E, F, G, H, I)

这些数据的不同部分都与一个得分相关联，例如:

scores:

    (A, B, C, D) = .99
    (A, B, C, E) = .77
    (A, B, E) = .66
    (G,) = 1
    (I,) = .03
    (H, I) = .55
    (I, H) = .15
    (E, F, G) = .79
    (B,) = .93
    (A, C) = .46
    (D,) = .23
    (D, F, G) = .6
    (F, G, H) = .34
    (H,) = .09
    (Y, Z) = 1

我们可以按照以下方式为这些数据打分：

A B C E + D F G + H I = .77 * .6 * .55 = 0.2541

另一个可能性是：

A B C D + E F G + H + I = .99 * .79 * .09 * .03 = 0.00211167

因此，第一种组合得分更高。

我希望编写一个算法来确定上述数据的最高可能得分。数据成员不应重复超过一次。换句话说：

A B C E + E F G + D + H I 

不是有效的。您建议我如何解决这个问题？

谢谢，

Barry

编辑： 我应该澄清一下，（H，I）！=（I，H），而（I，H）不是ABCDEFGHI的子片段，但它是ABIHJ的子片段。另一个需要提到的事情是，得分是一个非常大的集合（数百万），我们计算得分的片段平均长度约为10。此外，我计算分数的方式可能会在将来发生变化。也许我想要添加子段并取平均数而不是乘法，谁知道......因此，从实际计算得分中分离出计算可能组合的代码可能更好。目前，我倾向于认为itertools.combinations可能是一个很好的起点。

- Baz

---

以上数据的最优分数应该是0.430155，对吗？ - Neil

Answer 1

这听起来像是一个伪 NP 完全问题，是背包问题的一个派生问题。这意味着你可能需要遍历所有可能性才能得到精确的解决方案。

即使如此...等等。你的值在0和1之间。也就是说结果最多只能变小或保持不变。因此，解决方案很简单：获取具有最高价值的单个组，并完成操作。（我知道这可能不是你想要的，但你可能需要添加另一个条件，例如必须使用所有元素...？）

暴力方法的开始：

import operator

segment_scores = {(A, B, C, D): .99, (A, B, C, E): .77} #...

def isvalid(segments):
    """returns True if there are no duplicates
    for i in range(len(segments)-1):
        for element in segments[i]:
            for j in range(len(segments)-i-1):
              othersegment = segments[j+i+1]
              if element in othersegment:
                return False
    return True

    better way:
    """
    flattened = [item for sublist in segments for item in sublist]
    # https://dev59.com/qnNA5IYBdhLWcg3wdtld
    return len(set(flattened)) == len(flattened)

def getscore(segments):
    """
    p = 1.0
    for segment in segments:
      p *= segment_scores[segment]
    return p

    better way:
    """
    return reduce(operator.mul, [segment_scores[segment] for segment in segments])

现在，创建所有2^(段数)可能的段组合，检查每个组合是否有效，如果有效，则计算得分并保持当前获胜者及其最高分数。这只是一个起点...

好的，再更新一下：这里有很多优化空间，特别是因为你正在进行乘法（我现在假设你必须使用每个元素）。

- 由于总分数永远不会增加，所以可以放弃任何探索路径[segment0，segment1]，如果它低于当前高分，则您只能在任何segment2中获得作品。 - 如果您不仅仅迭代所有可能性，而是从探索包含第一个段的所有段列表开始（通过递归地探索所有包含第二个段等的段列表），则可以在第一个和第二个段无效时立即停止，即无需探索(A,B,C,D)和(A,B,C,D,E)的所有分组可能性。 - 由于乘法会受到影响，尝试最小化段数可能是一种合适的启发式方法，因此从具有高分数的大段开始。

- Nicolas78

---

我想这句话的意思是“必须使用所有元素”，对吗？ - Karl Knechtel

是的，我的帖子在某种程度上反映了我实时的理解过程，因此有这个问题。也许我应该在写之前更多地思考，但现在我决定先把它留着... ;) - Nicolas78

Answer 2

通过递归来进行暴力破解（对于每个部分，按顺序递归地使用该部分找到最佳得分，并且在不使用该部分的情况下找到最佳得分。如果余下的项目没有可能的部分组合，则分配0分）：

segment_scores = (('A', 'B', 'C', 'D'), .99), (('A', 'B', 'C', 'E'), .77) #, ...

def best_score_for(items, segments, subtotal = 1.0):
    if not items: return subtotal
    if not segments: return 0.0
    segment, score = segments[0]
    best_without = best_score_for(items, segments[1:], subtotal)
    return max(
        best_score_for(items.difference(segment), segments[1:], subtotal * score),
        best_without
    ) if items.issuperset(segment) else best_without

best_score_for(set('ABCDEFGHI'), segment_scores) # .430155

- Karl Knechtel

---

令人钦佩的代码。但是你在哪里确保不重复使用同一项？对于当前数据集可能不是问题，而且因为你想使用更少的段，而不是更多，所以这有点不太可能，但是在某些情况下，你可能会违反这个条件。因此，我建议只有当段的所有元素都在项目中时才通过第一条路径。 - Nicolas78

segment_scores = (('A', 'B'), 1), (('B','C'), 1), (('C'), 0.5)分段得分 = (('A', 'B'), 1), (('B','C'), 1), (('C'), 0.5) - Nicolas78

啊，我明白你的意思了。很容易修复（现在已经修复了）。 - Karl Knechtel

Answer 3

首先，我建议为有意义的段落分配一个唯一的符号。

然后，您可能想要使用这些符号的组合（或者也许是排列，我相信您比我更了解您的问题），以及一个“legal_segment_combination”函数，您可以使用它来排除不良可能性 - 基于哪些冲突和哪些不冲突的矩阵。

>>> import itertools
>>> itertools.combinations([1,2,3,4], 2)
<itertools.combinations object at 0x7fbac9c709f0>
>>> list(itertools.combinations([1,2,3,4], 2))
[(1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (3, 4)]
>>>

然后，最大化有效的可能性，使其通过legal_segment_combination()。

- dstromberg

Answer 4

首先，您可以对每个分数取对数，这样问题就变成了最大化分数总和而不是乘积。然后，您可以将问题解决为分配问题，其中您为每个数据点分配一个序列。

- Falk Hüffner