聯盟搜索算法

Question

我正在尋找一種在C，C++，Python或Java中實現的算法，該算法計算出每個代理具有不同票數的代理的代理聯盟集合n。我會很感激任何提示。謝謝！

Answer 1

換句話說，你有一個數組X[1..n]，並希望它的所有子集sum(subset) >= 1/2 * sum(X)，對不對？

這可能意味着整套資格。

之後，你可以放棄任何具有X[k] < 1/2 * sum(X)的元素k，並且每個這樣的聯盟也可以作爲答案。

之後，您可以繼續通過一個下降的元素之一，當你已經達到總和的一半停止。

這是顯然不是最有效的解決方案：你不想放棄k1=1,k2=2如果你已經嘗試過k1=2,k2=1 - 但我相信你能處理這個問題。

Answer 2

將每個代理的投票數排列在一個數組中，然後計算右邊的部分總和，以便通過查找部分總和可以找出SUM_i = k到n個投票[i]。

然後做了{1，2，...，N}的所有可能的子集一個回溯搜索。在回溯中的任何一點，您都接受了代理0..i - 1的一些子集，並且您可以從部分總和中瞭解其他代理可用的最大投票數。所以你可以看看當前的子集是否可以用代理人數> = i來擴展，以形成一個成功的聯盟，如果沒有，就放棄它。

這給了你，你考慮的一個子集，只有當它已經是一個成功的聯盟，否則你將它擴大成爲一個獲勝的聯盟一個回溯搜索。所以我認爲回溯搜索的成本是您發現的獲勝聯盟的總和，這似乎接近最優。在運行這個程序之前，我會試着重新安排代理人，這樣你可以首先以最多的選票處理代理人，但是目前我沒有看到一個說明你從中獲益的爭論。

實際上 - 採取從尖阿爾夫的答案 - 生活中，如果你從全套代理開始，然後用回溯搜索，以決定放棄該藥物是一個容易得多。那麼你不需要一個部分和的數組，你只需要生成你想要的子集。是的，沒有必要事先訂購代理商。

Answer 3

我很高興通過分成兩種情況考慮解決這個的，遞歸：找到所有中獎「聯盟」，包括最後的「代理」，所有那些沒有最後的「代理人」。現在，對於這些子問題中的每一個，都可以應用相同的邏輯，在包含最後一個「代理」的情況下，具有較低的目標投票數。當目標投票數低於或等於零，或者當沒有更多代理人離開時停止遞歸。

注意，在這樣的算法，根據投票數訂購劑是有益的。

例implmentation：

from itertools import combinations 

def _winning_coalitions(agents, target_votes): 
    """recursive solving function 

    @param agents: sequence of (name, votes) pairs 
    @param target_votes: minimum number of votes for a coalition 
    """ 
    if target_votes <= 0: 
     # stop the recursion 
     for coalition_size in range(len(agents)+1): 
      for coalition in combinations(agents, coalition_size): 
       yield coalition 
    elif not agents: 
     pass # no agents, so no possible coalitions 
    else: 
     agent_name, agent_votes = agents[-1] 
     agents = agents[:-1] 
     for coalition in _winning_coalitions(agents, target_votes-agent_votes): 
      yield ((agent_name, agent_votes),) + coalition 
      if sum([votes for (name, votes) in coalition]) >= target_votes: 
       yield coalition 

def winning_coalitions(agents): 
    """find all coalitions with at least target_votes combined votes 

    @param agents: dictionary of the form: name -> number of votes 
    """ 
    target_votes = (sum(agents.values())-1)//2+1 
    agents = sorted(agents.items(), key=operator.itemgetter(1)) 
    coalitions = _winning_coalitions(agents, target_votes) 
    return sorted([sorted([name for (name, votes) in c]) for c in coalitions]) 

而在Python解釋：

>>> agents = {"Alice": 3, "Bob": 5, "Charlie": 7, "Dave": 4} 
>>> # divide sum of votes by 2, rounding up 
>>> target_votes = (sum(agents.values())-1)//2+1 
>>> # solve! 
>>> coalitions = winning_coalitions(agents, target_votes) 
>>> sorted([sorted(c) for c in coalitions]) 
[['Alice', 'Bob', 'Charlie'], 
['Alice', 'Bob', 'Charlie', 'Dave'], 
['Alice', 'Bob', 'Dave'], 
['Alice', 'Charlie'], 
['Alice', 'Charlie', 'Dave'], 
['Bob', 'Charlie'], 
['Bob', 'Charlie', 'Dave'], 
['Charlie', 'Dave']]