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

Ответ 1

Это проблема оптимизации NP-проблемы. Например, проблема раздела) может быть легко сведена к этому (свойство планарности не вызывает проблемы). Таким образом, алгоритм, который вычисляет оптимальное решение (и вы, кажется, запрашиваете оптимальное решение в своем комментарии), вряд ли будет практичным для "десятков тысяч узлов" .

Если вам действительно не нужно оптимальное решение, но хорошее, я бы использовал локальные методы оптимизации, такие как поиск табу или имитированный отжиг.

Поскольку средний вес ваших подграфов - это всего лишь масса общего графика, деленная на количество подграфов, единственное, что имеет значение, это найти максимальное количество подграфов, которые вы можете достичь. Угадайте это число, N, сформируйте начальное разбиение на N подграфов, а затем, например, используйте локальные перемещения (1), перемещая a node из одного подграфа в другой и (2) обменивая два узла между двумя соседними подграфами, в поиск приемлемого решения, где каждый подграф имеет необходимый минимальный вес. Если вы не можете найти приемлемое решение вообще, уменьшите N (например, одним) и перезапустите, пока не найдете решение.

Ответ 2

Детали экземпляра меняют все.

Вызвать вершину тяжелой, если она превысит порог сама по себе. Нет смысла иметь подграф с двумя тяжелыми вершинами, потому что мы могли бы разбить его на две части. Таким образом, число подграфов в оптимальном решении аддитивно связано с числом подграфов, не содержащих тяжелой вершины.

В результате мы можем удалить тяжелые вершины и сосредоточиться на том, чтобы сделать как можно больше действительных подграфов из того, что осталось. Судя по вашей карте, то, что осталось, будет состоять из множества связанных компонентов, каждая из которых имеет только несколько вершин. Действительные подграфы должны быть подключены, поэтому эти компоненты могут быть решены независимо. В небольших случаях можно (например, перечислить все допустимые подграфы), а затем запустить Algorithm X, чтобы найти максимальную упаковку.

Ответ 3

Проблема NP-hard, тогда я выделим экспоненциальное решение. Это решение Есть много улучшений, я выделил бы что-нибудь.

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

В вашем предыдущем подходе у вас нет домена для расширения поиска. Для решения были использованы следующие: - Непересекающиеся наборы: представление раздела - Наборы мощности: для поиска всех возможных наборов кромок

public Partition Solve(Graph g, int min)
{
    int max = 0;
    Partition best;

    // Find all the possible partitions for Edges
    foreach(var S in PowerSet(g.Edges))
    {
        // Build the Vertexes partition
        var partition =  BuildPartition(S);

        // Test the min condition foreach component
        if (IsInvalid(partition, min))
            continue;

        // Continue if we already have something better
        if (max >= partition.Length)
            continue;

        // Update
        max = partition.Length;
        best = partition;
    }

    return best;
}

public Partition BuildPartition(Graph g, IEnumerable<Edge> edges)
{
    // Initially Every Vertex in alone in his partition
    var partition = new DisjointSet(g.Vertexes);

    foreach (var edge in edges)
    {
        // If the Vertexes of this edge are already in the same partition DO NOTHING
        if (partition.Find(edge.V1) == partition.Find(edge.V2))
            continue;

        // Join both subsets
        partition.Union(edge.V1, edge.V2);
    }

    return parition;
}

public bool IsInvalid(Partition p, int min)
{
    return p.Sets.Any(t => t.Sum(v => v.Weight) < min);
}

Вы можете улучшить решение в следующих аспектах: - Добавить parallelism в состояние PowerSet и IsInvalid - Найти лучший способ генерации допустимых наборов Edge - Имейте некоторый начальный случай для Вершины с большим весом, чем minimun (Всегда будет в отдельном подграфе)

Порядок алгоритма задается набором мощности. - Power Set: в этом случае для N вершинного графа вы будете иметь в худшем случае 3N-6 ребра, тогда O (2 ^ N). - Build Partition: V + E * LogV - это O (NLogN) - IsInvalid: O (V)

Наконец, Solve является O (2 ^ N * N * LogN) Используйте эту последнюю формулу для вычисления количества операций

Надеюсь, что эта помощь!