最优联盟结构

Question

问题如下：如果有一个集合S = {x1, ..., x_n}和一个函数f：set -> number，它以一个集合作为输入，returns一个数字作为输出，最好的联盟结构是什么（联盟结构是 S 的一组子集。也就是说，找到子集，使得每个子集 s_i 的 f(s_i) 之和] 在 S 中是最大的）。联盟中的集合不应重叠，它们的并集应为 S。模板是这样的：

def optimal_coalition(coalitions):
    """
    :param coalitions: a dictionary of the form {coalition: value}, where coalition is a set, and value is a number
    :return:
    """


optimal_coalition({set(1): 30, set(2): 40, set(1, 2): 71}) # Should return set(set(1, 2))

这是我发现的一篇论文：

Answer 1

我音译了伪代码。毫无疑问，你可以让它变得更好——我非常仔细地砍来证明这种联系。

我确实修复了一个错误（Val(C') + Val(C \ C') > v(C) 应该是 Val(C') + Val(C \ C') > Val(C)，否则我们可能会用一个仅比所有 C 更好的分区覆盖最佳分区）和两个错别字（C / C'应该是C \ C'；而CS*是一个集合，不是树）。

import itertools


def every_possible_split(c):
    for i in range(1, len(c) // 2 + 1):
        yield from map(frozenset, itertools.combinations(tuple(c), i))


def optimal_coalition(v):
    a = frozenset(x for c in v for x in c)
    val = {}
    part = {}
    for i in range(1, len(a) + 1):
        for c in map(frozenset, itertools.combinations(tuple(a), i)):
            val[c] = v.get(c, 0)
            part[c] = {c}
            for c_prime in every_possible_split(c):
                if val[c_prime] + val[c - c_prime] > val[c]:
                    val[c] = val[c_prime] + val[c - c_prime]
                    part[c] = {c_prime, c - c_prime}
    cs_star = {a}
    while True:
        for c in cs_star:
            if part[c] != {c}:
                cs_star.remove(c)
                cs_star.update(part[c])
                break
        else:
            break
    return cs_star


print(
    optimal_coalition({frozenset({1}): 30, frozenset({2}): 40, frozenset({1, 2}): 69})
)

最优联盟结构

Optimal coalition structure

python

algorithm

math

logic