Größte Schnittmenge von N-Mengen mit der Fähigkeit, bestimmte Mengen zu ignorieren (Komprimierung einstellen)
Angenommen, Sie haben N Gruppen unsortierter Zeichen, und diese Gruppen haben gemeinsame Zeichen. Ich möchte so viele Charaktere herausfiltern, wie ich aus diesen Sets kann, um sie kleiner zu machen. Es gibt jedoch eine Einschränkung bei der Faktorisierung von Zeichen: Die Zeichen müssen sich im Schnittpunkt von M Mengen befinden, die Sie aus N auswählen. Dies ist ein etwas verlustfreier Komprimierungsalgorithmus. Die folgenden Beispiele sind geordnete Mengen, aber dies dient zum leichteren Lesen. Gehen Sie nicht davon aus, dass Sets bestellt werden.
Ein einfaches Beispiel:
%Vor%Die Antwort ist, nur S1 und S2 zu schneiden und auszumerzen: a b c. Dies schneidet 6 Zeichen aus, bei denen jede andere Schnittmengenkombination weniger benötigt.
Ein heikles Beispiel:
%Vor%Die Antwort wäre, die Sätze S1 und S5 zu ignorieren und den Schnittpunkt der übrigen Sätze S2, S3 und S4 zu nehmen: j k l.
Der Grund, warum a b c d nicht korrekt ist, liegt darin, dass, wenn Sie diese Zeichen aus den Mengen faktorieren, 19 Zeichen übrig bleiben, wobei, wenn Sie j k und l out machen, nur noch 18 Zeichen übrig bleiben.
Gibt es einen Algorithmus, um diese Art von Problemen schneller als die exponentielle Zeit zu lösen? Es scheint, als müssten Sie den Schnittpunkt jeder Menge im Power Set der Sets ({}, {S1}, {S2}, {S3}, {S1, S2}, {S1, S3}, {S2) testen , S3}, {S1, S2, S3} - 8 Schnittpunkte zur Berechnung, wenn nur 3 Sätze vorhanden waren.
P.S. Das ist keine dringende Frage, aber ich dachte, es wäre ein interessantes Problem, auf das ich gestoßen bin.
1 Antwort
Wenn die Größe des Alphabets nicht zu groß ist ... würde ich die dynamische Programmierung verwenden, um dieses Problem zu lösen ... die Laufzeit sollte O (S * 2 ^ n), S = Anzahl der Sätze, n = Anzahl der Sätze sein Alphabete
Definiere DP (i, bitmask) sei die maximale Anzahl von Zeichen, die für jede Teilmenge innerhalb von set-0 gelöscht werden könnten, um set-i zu verwenden, wobei diese Bitmaske verwendet wird
Zum Beispiel haben wir jetzt 3 Sätze und 5 Alphabete {a, b, c, d, e}
S0 = {a,d,e}, S1 = {b,c,e}, S2 = {a,c,e}
Versuchen Sie, 0-1 Bit zu verwenden, um jeden Satz zu maskieren:
S0 = 11001 = 25, S1 = 10110 = 22, S2 = 10101 = 21
Es gibt insgesamt 2 ^ 5 verschiedene mögliche Masken und wir werden alle durchgehen, wenn wir DP (i, bitmask) berechnen
Jetzt initialisiere mit DP (0, x) (d. h. fülle einfach die # von 1-Bit von x) und benutze folgenden Übergang, um DP (i, x) für i & gt; 0:
DP(i, x) = DP(i-1,x) + { # of 1-bit of x if (Si & x == x); 0 otherwise}
Si is the bitmask of the Set i, & is bitwise and operation
Die Antwort ist das Maximum von DP (S-1, x) für alle x
Dieser Ansatz kann alle möglichen Lösungen finden, wenn es viele von ihnen gibt, unten ist Beispielcode in C ++, der das obige Beispiel löst:
%Vor%Immer wenn die Ausgabe des DP-Zustands gleich der maximalen abgebrochenen Zahl ist, ist die Bitmaske die entsprechende Lösung. Sie können einfach zurück in englische Zeichen umwandeln, dh {c, e} oder {a, e} im obigen Beispiel
BEARBEITET : Um den folgenden Kommentar zu beantworten, versuche ich hier Teile für Teile zu antworten:
Q1. Ist es immer noch exponentiell? Nur von Exponential zu der # von Satzübertragung auf die # von Alphabeten?
A1. Ja, so ist es. Ich habe diesen Gedanken, weil ich denke, dass die Größe des Alphabets in Wirklichkeit nicht zu groß wäre ... aber in der Theorie ist es immer noch die exponentielle Zeit
Q2. Ist dieses Problem NP abgeschlossen?
A2. Okay, das ist der interessante Teil, hier ist mein Gedanke, wenn ich falsch liege, korrigiere mich bitte, ich denke, JA, es ist NP Complete . Mein Gedanke ist, dieses Problem in ein Graphenproblem zu modellieren, siehe das Bild unten (bare meine schlechte Fähigkeit)
Wir haben einen bipartiten Graphen, und im selben Sinn wie Ihr ursprüngliches Problem, wollen wir nun den Maximum Complete Subgraph finden - Das ist ein Clique im allgemeinen Graph, der ein bekanntes NP-Komplettes Problem ist.
Und dann denke ich, es ist ein Bipartite Graph! Vielleicht Clique in zweiteiligen Grafik ist nicht NP Complete, aber dank Google, fand ich ein anderes Problem Komplette Bipartite Graphik und konzentrieren Sie sich auf die erste Eigenschaft auf der Seite:
Wenn ein bipartiter Graph gegeben wird und getestet wird, ob er einen vollständigen zweiteiligen Untergraphen Ki enthält, ist i für einen Parameter i ein NP-vollständiges Problem.
Zum Schluss denke ich, das ist NP-Complete
Q3. Wie man mit solcher DP-Lösung kommt?
A3. Kombiniere mit A1., Viele NPC-Probleme haben tatsächlich eine Pseudo-Polynom-Lösung , und O (x * 2 ^ y) ist eine weit verbreitete Form, soweit ich weiß, ein Beispiel wäre Hamiltonian Path , der in O (n ^ 2 * 2 ^ n) gelöst werden kann. Als ein zusätzliches Bit, wenn Sie sich fragen, habe ich ähnliche Idee von Knapsack Problem auch beim Denken dieser DP-Lösung ... aber das ist ein bisschen nicht im Zusammenhang mit Ihrer Frage ...
Tags und Links algorithm set intersection