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

Question

我有一些用于计算图中最大全网格的Python代码。图的每个节点可以有不同的权重(每个节点的权重由一个数组给出)。考虑到不存在的边缘，我想获得图中的最大加权团大小。我为此编写了一些 python 代码，其工作原理如下:

1. 我从所有边都存在的全连接图开始。
2. 如果全连接图中的一条边被破坏，则会将其分成两个全连接图(下面的 split_full_meshes 方法)。
3. 最后，我将所有可能的派系的权重相加，得到权重最大的派系。

代码包含在下面(maximal_full_mesh 计算最大加权团，而 split_full_meshes 是 split 团的助手)。问题是它的速度慢得令人痛苦。我需要能够在 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