Auswahl eines Elements aus jeder Menge von Mengen, sodass keine zwei Elemente gleich sind.

Angenommen, wir haben eine endliche Menge A deren Elemente Teilmengen einer anderen endlichen Menge sind B ( ϵ ∈ A ⟹ ϵ ⊆ B ) . Nehmen wir als Nächstes an, dass wir bis zu einem Element aus jeder Menge auswählen möchten ϵ ∈ A so dass keine zwei Elemente aus einer dieser Mengen ausgewählt werden ϵ sind gleich. Wie würden wir vorgehen, um die maximale Anzahl von Elementen zu finden, die wir aus diesen Mengen auswählen können, damit diese Bedingungen erfüllt sind?

Offensichtlich ist diese maximale Anzahl von Elementen durch die minimale Größe von begrenzt A und die Größe von B , aber nehmen wir an, wir kennen den Inhalt jeder der Mengen ϵ . Gibt es eine Methode, mit der man rechtzeitig mehr Informationen über dieses Maximum erhalten kann, oder braucht NP Zeit, um dieses Problem zu lösen?

Das klingt nach Sudoku, es kann nützlich sein zu sehen, ob Sie Sudoku darauf reduzieren können, in diesem Fall denke ich, dass dies NP-schwer sein muss. Das heißt, es ist eine Weile her, dass ich über NP nachdenken musste, also könnte ich mich irren

Antworten (1)

Sie können dies lösen, indem Sie den maximalen Durchfluss in polynomieller Zeit verwenden.

Betrachten Sie gerichtete Graphen mit Knoten { S , F } ∪ A ∪ B . Die Kanten, die alle das Gewicht 1 haben, sind { S → A | A ∈ A } ∪ { A → B | B ∈ A , A ∈ A } ∪ { B → F | B ∈ B } .

Dann wird der maximale Durchfluss ab S Zu F ist die Antwort auf Ihr Problem.

Beachten Sie, dass für den maximalen Fluss, wenn alle Kantengewichte des Diagramms Ganzzahlen sind, der maximale Fluss einen ganzzahligen Fluss über jede Kante haben wird. Deshalb funktioniert diese Reduktion.

Bearbeiten:

Tatsächlich kann dies gut als Spezialfall des maximalen bipartiten Matchings angesehen werden.

Auswahl eines Elements aus jeder Menge von Mengen, sodass keine zwei Elemente gleich sind.
AntwortenHierDatenschutz-Bestimmungen1y, 0v