Gruppen zuweisen

Question

Ich habe ein Problem, bei dem ich Mengen Variablen zuweisen soll. Jeder Menge ist eine Grenze von Variablen zugeordnet, die ihr zugewiesen werden können, und jede Variable kann einer Teilmenge der Gesamtsätze zugewiesen werden.

Beispiel:

• akann in Sätzen Aoder seinB
• b kann in Sätzen sein B
• ckann in Sätzen Aoder seinB
• d kann in Sätzen sein A

Somit können wir haben A: a, d; B: b, coder A: c, d; B: a,b(Reihenfolge der Variablen innerhalb der Menge spielt keine Rolle) /

Natürlich wird es Zeiten geben, in denen es unmöglich ist, alle Variablen zuzuweisen, Zeiten, in denen wir mehrere Optionen haben, und Zeiten mit nur einer Option.

Ich habe das Gefühl, dass es eine einfache Version dieses Problems gibt, aber ich kann meinen Finger nicht darauf legen. Alle Hinweise wäre dankbar.

Answer 1

Effizient lösbar mit maximalem Durchfluss. Bereiten Sie ein Flussnetzwerk mit einem Einheitskapazitätsbogen von einer Quelle zu jeder Variablen, einem Einheitskapazitätsbogen von jeder Variablen zu jedem Satz, zu dem sie gehören kann, und einem Bogen von jedem Satz zu einer Kapazitätssenke vor, die der Kapazität des Satzes entspricht . Beispielsweise,

ARCS

tail head capacity
------------------
s    a    1
s    b    1
s    c    1
s    d    1
a    A    1
a    B    1
b    B    1
c    A    1
c    B    1
d    A    1
A    t    2
B    t    2

Verwenden Sie Ihren bevorzugten Max-Flow-Algorithmus, der einen integralen Flow erzeugt, und extrahieren Sie die Zuordnung, nach der die zu setzende Variable einen Flow hat.

Answer 2

Dieses Problem ist NP-vollständig, was bedeutet, dass es dafür keine polynomielle Zeitlösung gibt. In diesem Fall müssten Sie Backtracking verwenden.

Schauen Sie sich diese Links an:

https://www.geeksforgeeks.org/vertex-cover-problem-set-1-introduction-approximate-algorithm-2/ https://www.geeksforgeeks.org/set-cover-problem-set-1-greedy-approximate-algorithm/