Algorithmus: Entfernen von so wenige Elemente wie möglich aus einem Satz, um keine Teilmengen zu erzwingen

Question

Ich habe ein Problem, das ich nicht weiß, wie zu lösen:

Ich habe eine Reihe von Sätzen A = {A_1, A_2, ..., A_n} und ich habe einen Satz B.

Jetzt Ziel ist es so wenige Elemente wie möglich von B (Erstellen B'), so dass nach dem Entfernen der Elemente für alle 1 <= i <= n zu entfernen, A_i ist nicht eine Teilmenge von B'.

Zum Beispiel, wenn wir A_1 = {1,2}, A_2 = {1,3,4}, A_3={2,5} und B={1,2,3,4,5}, konnten wir zum Beispiel Entfernen 1 und 2 von B (das B'={3,4,5} ergeben würde, was nicht ein Superset eines des A_i ist).

Gibt es einen Algorithmus zur Bestimmung der (minimale Anzahl von) Elementen entfernt werden?

Answer 1

Es klingt wie Sie den minimalen schlug Satz von A von B entfernen mögen (dies ist eng mit dem Vertex Cover Problem im Zusammenhang).

Ein Satz schlägt einig Set-of-Sets A ist selbst ein so eingestellt, dass es enthält mindestens ein Element aus jedem Satz in A (it "Treffer" jeder Satz). Der minimale Schlag Satz ist der kleinste solcher Schlagsatz. Also, wenn Sie eine MHS für Ihre Set-of-Sets A haben, haben Sie ein Element aus jedem Satz in A. Das Entfernen dieser aus B bedeutet kein Satz in A eine Teilmenge von B sein kann.

Alles was Sie brauchen zu tun, berechnen die MHS für (A ₁ , A ₂ , ... A _n ), dann entfernen dass von B. Leider ist die MHS zu finden, ist ein NP-vollständiges Problem. Zu wissen, dass, obwohl, haben Sie ein paar Optionen:

1. Wenn Ihr Datensatz klein ist, tun die offensichtliche Brute-Force-Lösung
2. Verwenden Sie einen probabilistischen Algorithmus, um eine schnell zu bekommen, ungefähre Antwort (siehe diese PDF )
3. Ausführen weit, weit weg in der entgegengesetzten Richtung

Answer 2

Wenn Sie nur eine Annäherung benötigen, mit dem kleinsten Satz in A beginnen, und entfernen Sie ein Element aus B. (Sie sind nur ein zufällig greifen könnten, oder prüfen Sie, welches Element in den Sätzen in A ist je nach wie genau, wie schnell Sie benötigen)

Nun ist die kleinste Menge in A nicht eine Teilmenge von B. Verschieben von dort, aber prüfen Sie zuerst, um zu sehen, ob die Sätze Sie untersuchen Untergruppen sind an dieser Stelle oder nicht.

Das erinnert mich an den Scheitelpunkt bedeckt Problem, und ich erinnere mich etwas Approximationsalgorithmus für die, die zu diesem ähnlich ist.

Answer 3

Ich denke, man sollte die Mindestlänge von diesen Sätzen finden und dann diese Elemente löschen, die in dieser Reihe ist.