Ich suche nach einem Algorithmus, um das folgende Problem zu lösen. Ich habe eine Anzahl von Teilmengen (1-n) einer gegebenen Menge (a-h). Ich möchte die kleinste Sammlung von Teilmengen finden, die es mir ermöglichen, alle gegebenen Teilmengen durch Kombination zu konstruieren. Diese Sammlung kann Untergruppen enthalten, die noch nicht in 1-n vorhanden sind.
%Vor%Im Folgenden sind zwei mögliche Sammlungen aufgeführt, von denen die kleinste sieben Untergruppen enthält. Ich habe neue Teilmengen mit einem x bezeichnet.
%Vor%Ich glaube, das muss ein bekanntes Problem sein, aber ich bin mit Algorithmen nicht sehr vertraut. Jede Hilfe wird sehr geschätzt, ebenso wie ein Vorschlag für einen besseren Thementitel.
Danke!
Graph Coloring bringt mir einen langen Weg, danke. In meinem Fall dürfen sich Teilmengen jedoch überlappen. Zum Beispiel:
%Vor%Graph coloring gibt mir diese Lösung:
%Vor%Aber dieser ist auch gültig und kleiner:
%Vor%Dieses Problem ist bekannt als "Set-Basis" und es ist NP-vollständig (Larry J. Stockmeyer: Das festgelegte Basisproblem ist NP-vollständig. Technischer Bericht RC-5431, IBM, 1975). Seine Formulierung als Grafikproblem ist Bipartite Dimension . Da es im Allgemeinen sehr schwierig zu lösen ist, kann es nützlich sein, zu prüfen, ob es hilfreiche Eigenschaften Ihrer Daten gibt (z. B. sind die Mengen klein? Ist die Lösung klein? Können alle Mengen vorkommen?)
Ich kann mir keine einfache ILP-Formulierung vorstellen. Stattdessen könnten Sie versuchen, das Problem auf Clique Cover zu reduzieren, das besser untersucht ist, indem Sie entweder die Reduktion von Kou & amp; Wong verwenden oder die von Nor et al. . Ich habe ein Papier beigesteuert, in dem Algorithmen für Clique Cover besprochen und ein Clique Cover Solver mit einem genauen Solver und zwei Heuristiken.
Dieses Problem wurde in einem der Videos von Courseras Discrete Optimization Lectures gezeigt. IIRC, es ist das Set Cover Problem.
IIRC, es ist NP-vollständig oder NP-schwer, also schauen Sie sich die typischen Algorithmen an (exakte Algorithmen für kleine Datensätze, Metaheuristiken für mittlere / große Datensätze) und typische Frameworks ( OptaPlanner , ...)
Für diese Variante des Set Cover -Problems gibt es hier einen Integer Programming-Ansatz mit Zeilengenerierung .
Bezeichnen wir die Komponenten a, b, c, d ... mit ihrer Spaltennummer. a = 1, b = 2 usw.
Die Zeilen sind 'Teilmengen'. Nehmen wir an, dass die bestehenden Teilmengen S1, ... Sm sind. (Dies sind diejenigen, die abgedeckt werden müssen.)
Dies ist der Schritt, in dem wir neue Teilmengen einführen.
Nennen wir die "atomaren" Teilmengen als a_x . Alle a Subsets haben nur eine Komponente.
Lassen Sie bxy Teilmengen mit zwei Komponenten sein.
Gegeben eine existierende Menge, erzeugen wir nur die benötigten NEW a, b, c ... Untermengen, wie wir brauchen.
%Vor%VORBEREITUNGSSTUFE: Erzeugen Sie für jedes SJ in bestehenden Sätzen neue Untermengen, indem Sie die oben genannte Prozedur verwenden. Wir erstellen nur so viele ax, bxy, cxyz dxyzw ... wie benötigt. Dieser Schritt wird vor dem Formulierungsschritt benötigt.
Im schlimmsten Fall werden (2 ^ num_components-1) Teilmengen pro Sj benötigt. Aber sie sind einfach zu generieren.
Nun die Formulierung für das folgende Problem:
%Vor%Wir haben für jede ROW eine Einschränkung. Jeder Satz muss "bedeckt" werden
Für das obige Problem, hier ist die Formulierung
Obere Grenze: Indem Sie die Tatsache ausnutzen, dass Sie höchstens j Teilmengen (Anzahl der vorhandenen Teilmengen) benötigen, können Sie sogar einen Schnitt hinzufügen. Objektive Funktion muss j oder niedriger sein.
Ich hoffe, das hilft.