Максимальная полная сетка в графе - код Python очень медленный

Question

У меня есть некоторый код на Python для вычисления максимальной полной сетки в графе.Каждый узел графа может иметь различный вес (веса каждого узла задаются массивом).Я хочу получить максимальный размер взвешенной клики на графике, учитывая ребра, которых нет.Для этого я написал некоторый код на Python, который работает следующим образом:

1. Я начну с полностью связного графа, в котором присутствуют все ребра.
2. Если ребро сломано в полностьюсвязного графа, он разбит его на два полностью связанных графа (метод split_full_meshes ниже).
3. Наконец, я суммирую веса по всем возможным кликам и получаю клику с максимальным весом.

Код приведен ниже (maximal_full_mesh вычисляет максимальную взвешенную клику, а split_full_meshes - помощник для разделения кликов).Проблема в том, что это мучительно медленно.Я должен быть в состоянии запустить это в цикле из 2 миллионов (все возможные графики с семью узлами), но это займет целых 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