图python代码中的最大全网格非常慢。

Question

我有一些python代码来计算图中的最大全网格。图的每个节点可以有不同的权重(每个节点的权重由一个数组指定)。我想得到图中的最大加权团大小，给定不存在的边。我为此编写了一些python代码，如下所示：

1. 我从全连通图开始，其中所有的边都存在。
2. 如果一个边在一个全连通图中被打破，它会把它分解成两个全连通图(下面是split_full_meshes方法)。
3. 最后，我对所有可能的类群进行加权求和，得到了具有最大权重的团。

代码包括在下面(maximal_full_mesh计算最大加权团，而split_full_meshes是分裂团的助手)。问题是它缓慢得令人痛苦。我需要能够在一个200万的循环(所有可能有七个节点的图表)中运行这个程序，但是运行它需要整整10分钟。我在寻找关于如何使这件事更快的建议。

def split_full_meshes(meshes=[[0,1,2],[0,1,3]], broken_edge=[0,1]):
    """
    A full mesh is defined as a series of nodes that
    are all interconnected with each other. When we break an edge,
    any full-mesh that has both nodes corresponding to that edge will be 
    broken up
    into two smaller full-meshes.
    args:
        meshes: A jagged array, each entry is an array of indices of nodes 
            that are full-mesh connected.
        broken_edge: The edge that was not earlier broken but is now going
                 to be broken.
    """
    nu_meshes = []
    for mesh in meshes:
        if broken_edge[0] in mesh and broken_edge[1] in mesh:
            for node in broken_edge:
                nu_meshes.append([i for i in mesh if i!= node])
        else:
            nu_meshes.append(np.copy(mesh))
    return nu_meshes


def maximal_full_mesh(a=np.array([2,2,3,4]), \
    broken_edges=np.array([[0,1],[2,3]])):
    """
    The largest weighted full-mesh available in the graph.
    (set of nodes with perfect interconnectivity with each other).
    args:
        a: The weights of each node in the graph.
        broken_edges: The edges between nodes that are broken.
    """
    meshes = [np.arange(len(a))]
    for ed in broken_edges:
        meshes_tmp = np.copy(meshes)
        meshes = split_full_meshes(meshes_tmp, ed)
    max_mesh = 0
    for mesh in meshes:
        max_mesh = max(max_mesh, sum(a[np.array(mesh)]))
    return max_mesh

Answer 1

在这里，我以相反的方式处理这个问题--我生成一组节点，将其排除在原始的全网格之外，使每个节点生成完整的网格。从这一点，我可以很容易地使用一些技巧-跳过不包含在相应的完整网格中的边缘，使用集合差异，并在它们超过权重阈值时尽早修剪次优分支。

class FullMesh:
    def __init__(self, pairs, weights):
        self.pairs = pairs
        self.weights = weights
        self.elements = set(range(len(weights)))

        self.skips = {e:set() for e in self.elements}
        for i, (a, b) in enumerate(pairs):
            self.skips[a].add(i)
            self.skips[b].add(i)

    def find_max(self):
        max_score = sum(self.weights)
        val, nums = self.exclude(0, max_score + 1, set(range(len(self.pairs))))
        return max_score - val, sorted(self.elements - set(nums))

    def exclude(self, curr_score, min_score, search):
        if not search or min_score <= curr_score:
            return curr_score, []

        min_nums = []
        for e in self.pairs[next(iter(search))]:
            score, nums = self.exclude(curr_score + self.weights[e], min_score, search - self.skips[e])
            if score < min_score:
                min_score, min_nums = score, nums + [e]
        return min_score, min_nums