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

Question

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

То, что я узнал, до сих пор является эвристическим:

create a subgraph out of every node 
while there is an underweight subgraph: 
    select the subgraph S with the lowest weight 
    find a subgraph N that has the lowest weight among the neighbouring subgraphs of S 
    merge S to N 

Очевидно, что это не является оптимальным. Кто-нибудь получил лучшее решение? (Возможно, я просто незначителен, и это не сложная проблема, но я никогда не изучал теорию графа ...)

EDIT (дополнительные сведения о форе): Узлы на этом графике представляют собой низкоуровневые административные единицы, для которых статистические данные должны быть предоставлены. Тем не менее, подразделениям необходимо иметь определенный минимальный размер населения, чтобы избежать конфликтов с законодательством о персональных данных. Моя цель - создать агрегаты, чтобы как можно меньше информации терялось в пути. Соотношения соседства служат ребрами графа, так как результирующие единицы должны быть смежными.

Большинство узлов (узлов) в наборе значительно превышают минимальный порог. Около 5-10% из них находится ниже порогового значения с различными размерами, как это видно на примере (минимальный размер 50):

Answer 1

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

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

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

Answer 2

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

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

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

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); 
} 

Вы можете улучшить решение в следующих аспектах: - Добавить параллелизм в POWERSET и IsInvalid состояния - Найти лучший способ генерировать правильную Грань наборы - Выпей, начиная случай для Vertex с большим весом, чем Minimun (всегда будет находиться в отдельном подграфе)

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

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

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

Answer 3

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

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

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