Massimizza il numero di sottografi con un peso minimo specificato

Question

Ho un grafico planare non orientato in cui ogni nodo ha un peso. Voglio dividere il grafico in quanti più sottoprogrammi connessi disgiunti possibile (EDIT: o per raggiungere un peso medio minimo dei sottografi possibile), data la condizione che ogni sottografo debba raggiungere un peso minimo fisso (che è una somma di pesi dei suoi nodi). Anche un sottografo che contiene solo un singolo nodo è OK (se il peso del nodo è maggiore del minimo fisso).

Quello che ho scoperto finora è un euristico:

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 

Chiaramente questo non è ottimale. Qualcuno ha una soluzione migliore? (Forse sono solo ignorante e questo non è un problema complesso, ma non ho mai studiato la teoria dei grafi ...)

EDIT (ulteriori dettagli in background): i nodi in questo grafico sono unità amministrative su scala ridotta per le quali dati statistici devono essere forniti. Tuttavia, le unità devono avere una certa dimensione minima della popolazione per evitare conflitti con la legislazione sui dati personali. Il mio obiettivo è creare aggregati in modo che il minor numero possibile di informazioni si perda. Le relazioni di vicinato servono come bordi del grafico, in quanto le unità risultanti devono essere contigue.

La maggior parte delle unità (nodi) nel set sono ben al di sopra della soglia minima. Circa 5-10% di essi è inferiore alla soglia di varie dimensioni, come visto sull'esempio (dimensione minima 50):

Answer 1

Questo è un problema di ottimizzazione NP-hard. Ad esempio, lo Partition problem può essere facilmente ridotto (la proprietà di planarità non causa problemi). Quindi un algoritmo che calcola una soluzione ottimale (e sembra che tu chieda una soluzione ottimale nel tuo commento) è improbabile che sia pratico per "decine di migliaia di nodi".

Se non si ha effettivamente bisogno di una soluzione ottimale ma buona, utilizzerei metodi di ottimizzazione locali, come ricerca tabu o ricottura simulata.

Poiché il peso medio dei sottografi è solo il peso del grafico totale diviso per il numero di sottografi, l'unica cosa che conta è trovare il numero massimo di sottografi che è possibile ottenere. Indovina che questo numero, N, forma un partizionamento iniziale in N sottografi, e quindi, per esempio, usa mosse locali di (1) spostare un nodo da un sottografo all'altro e (2) scambiare due nodi tra due sottografi adiacenti, in cerca di una soluzione accettabile in cui ogni sottografo ha il peso minimo richiesto. Se non riesci a trovare una soluzione accettabile, diminuisci N (ad esempio di uno) e riavvia finché non trovi una soluzione.

Answer 2

Il problema è NP-difficile quindi evidenzierò una soluzione esponenziale. Questa soluzione ha molti punti di miglioramento, metterò in evidenza somes.

L'idea generale è: ciascuna partizione di vertici è collegata da alcuni bordi, quindi è possibile garantire che se si tenta con tutti i possibili gruppi di bordi che rende una partizione corretta del grafico. È possibile trovare il caso migliore contando il numero di serie di ciascuna partizione (condizione ottimale).

Nel tuo approccio precedente non hai Dominio per espandere la ricerca.Per la soluzione sono stati utilizzati i seguenti: - insiemi disgiunti: Partition rappresentanza - gruppi elettrogeni: Per trovare tutti gli spigoli possibili imposta

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

È possibile migliorare la soluzione nei seguenti aspetti: - Aggiungere il parallelismo al PowerSet e IsInvalid condizione - trovare un modo migliore di generare bordo valida imposta - avere qualche caso di partenza per Vertex con più peso rispetto al minimo (sempre sarà in un sottografo separato)

l'ordine dell'algoritmo è dato da il set di potenza. - Power Set: in questo caso per il grafico N vertice avrete nel caso peggiore i bordi 3N-6 e poi O (2^N). - Costruire ripartizione: V + E * LogV allora è O (N log N) - IsInvalid: O (V)

Infine il Solve è O (2^N * N * log N) Utilizzare questa ultima formula per calcolare il numero di di operazioni

Spero che questo aiuto!

Answer 3

I dettagli dell'istanza cambiano tutto.

Chiama un vertice pesante se supera la soglia da solo. Non ha mai senso avere un sottografo con due vertici pesanti, perché potremmo dividerlo in due. Quindi, il numero di sottografi nella soluzione ottimale è correlato additivamente al numero di sottografi che non contengono vertici pesanti.

Come risultato, possiamo eliminare i vertici pesanti e concentrarci sul rendere quanti più sottografi validi possibili da ciò che è rimasto. A giudicare dalla tua mappa, ciò che resterà sarà composto da molti componenti connessi, ciascuno con solo una manciata di vertici. Devono essere collegati i sottografi validi, quindi questi componenti possono essere risolti in modo indipendente. Su piccole istanze, è possibile (ad esempio) enumerare tutti i sottografi validi e quindi eseguire Algorithm X per trovare un pacchetto di cardinalità massima.