建立一組組合的最高分

我有以下形式的數據：該數據與得分有關的

(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

無效。你會如何推薦我去解決這個問題？

感謝，

巴里

編輯： 我要澄清的是（H，I）=（I，H）和（I，H）是不是子片段爲ABCDEFGHI，但是ABIHJ的子部分。我應該提及的另一件事是分數是一個非常大的集合（百萬），我們計算得分的分段的平均長度大約爲10個。此外，我計算得分的方式可能會在未來。也許我想添加子段並取平均值而不是偶數倍，誰知道......因此，分離計算可能組合的代碼可能更好，因爲計算得分的實際計算可能更好。目前，我傾向於認爲itertools.combinations可能會提供一個很好的起點。

來源

2011-12-26 Baz

推測上述數據的最佳分數爲0.430155？ – Neil 2011-12-26 21:27:10

暴力破解，通過使用遞歸（在順序每個段，我們遞歸使用段找到最好的成績，最好的成績不使用的部分。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

來源

2011-12-26 22:04:11

令人欽佩的一段代碼。但你在哪裏確保你不使用同一個項目兩次？可能不是當前數據集的問題，並且這是不太可能的，因爲您想要使用LESS段，而不是更多，但在某些情況下您可能會違反該條件。所以我建議只有在所有的元素都在 – Nicolas78 2011-12-26 22:10:32

segment_scores =（（'A'，'B'），1），（（'B'，'C'），1），（（'C'），0.5） – Nicolas78 2011-12-26 22:19:02

啊，我明白你的意思了。輕鬆修復（現在修復）。 – 2011-12-26 22:25:34

這聽起來像是一個僞裝的NP完全問題，是Knapsack problem的衍生物。這意味着您可能需要通過各種可能性來獲得確切的解決方案。

即使......等待。你的值在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] 
    # http://stackoverflow.com/questions/952914/making-a-flat-list-out-of-list-of-lists-in-python 
    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 ^（num段）可能的分段組合，檢查每個分段是否有效，如果是，則計算分數，同時保持當前獲勝者及其高分。只是一個起點...

好的只是另一個更新：這裏有很多優化的空間，特別是因爲你在乘法（我假設你現在必須使用每個元素）。

由於你的總成績永遠不會增加，你可以刪除任何探索路徑[segment0，SEGMENT1]那滴當前高分以下，因爲你得到的就只是任何分段2的作品。
如果您不只是遍歷所有可能性，而是從包含第一個段的所有段列表開始（通過遞歸探索包含第二個段的所有段列表等），您可以按照例如，第一段和第二段即爲無效，即不需要探索所有可能的分組（A，B，C，D）和（A，B，C，D，E）
由於倍增傷害，儘量減少細分的數量可能是一個合適的啓發式，所以從大分數高分開始。

來源

2011-12-26 21:26:33 Nicolas78

我想，「所有元素都必須使用」是有意的，是的。 – 2011-12-26 21:54:39

是的。我的帖子莫名其妙地反映了我對實時的理解過程，因此是一個問題。也許我應該在*之前考慮更多*我寫，但現在我已決定離開它;;） – Nicolas78 2011-12-26 22:00:36

首先，我建議分配一個唯一的符號有意義的部分。

然後，你可能想要這些符號的組合（或者可能是排列組合，我相信你比我更瞭解你的問題），以及你用來拋出不良可能性的「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（）的有效可能性。

來源

2011-12-26 23:00:29 dstromberg

首先，你可以取每個分數的對數，因爲那麼問題是最大化分數的總和而不是產品。然後，您可以將問題解決爲Assignment Problem，在哪裏爲每個數據點分配一個序列。

來源

2012-01-12 11:50:13

建立一組組合的最高分

回答

相關問題