Hier liegt das Problem. Gegeben sei , wobei jedes T i ⊆ { 1 , … , n } ist . Gibt es eine Teilmenge S ⊆ { 1 , ... , n } mit einer Größe von höchstens k , so dass S ∩ T i & ne; ∅ für alle i ? Ich versuche, dieses Problem auf SAT zu reduzieren. Meine Idee einer Lösung wäre, eine Variable x i zu habenfür jede von 1 bis . Für jedes T i , erstellen Sie eine Klausel ( x i 1 ∨ ⋯ ∨ x i k ) wenn T i = { i 1 , ... , i k } . Dann und all diese Klauseln zusammen. Dies ist jedoch eindeutig keine vollständige Lösung, da es nicht die Beschränkung darstellt, die S höchstens k Elemente haben muss. Ich weiß, dass ich mehr Variablen erstellen muss, aber ich bin mir einfach nicht sicher, wie. Ich habe also zwei Fragen:
- Ist meine Lösungsidee auf dem richtigen Weg?
- Wie sollen die neuen Variablen erstellt werden, damit sie zur Darstellung der Kardinalitätsbeschränkung ?
complexity-theory
reductions
np-hard
Aden Dong
quelle
quelle
Antworten:
Es sieht so aus, als würden Sie versuchen, eine Hypergraph-Transversale der Größe zu berechnen . Das heißt, { T 1 , … , T m } ist Ihr Hypergraph und S ist Ihr Transversal. Eine Standardübersetzung besteht darin, die Klauseln so auszudrücken, wie Sie sie haben, und dann die Längenbeschränkung in eine Kardinalitätsbedingung zu übersetzen.k {T1,…,Tm} S
So nutzen Sie Ihre bestehende Codierung, dh und dann Klauseln hinzufügen kodieren Σ 1 ≤ i ≤ n x i ≤ k .⋀1≤j≤m⋁i∈Tjxi ∑1≤i≤nxi≤k
ist ein Kardinalität constraint. Es gibt verschiedene Übersetzungen von Kardinalitätsbeschränkungen in SAT.∑1≤i≤nxi≤k
Die einfachste, aber ziemlich große Kardinalitätsbeschränkungsübersetzung ist nur . Auf diese Weise repräsentiert jede Disjunktion die Bedingung ¬ ⋀ i ∈ X x i - für alle Teilmengen X von { 1 , … , n }⋀X⊆{1,…,n},|X|=k+1⋁i∈X¬xi ¬⋀i∈Xxi X {1,…,n} der Größe k + 1. Das heißt, wir stellen sicher, dass auf keinen Fall mehr als k Variablen festgelegt werden können. Beachten Sie, dass dies keine Polynomgröße in k
Einige Links zu Artikeln über platzsparendere Kardinalitätsbeschränkungsübersetzungen mit Polynomgröße ink :
Wenn Sie tatsächlich an der Lösung solcher Probleme interessiert sind, ist es vielleicht besser, sie als pseudo-boolesche Probleme zu formulieren (siehe Wiki-Artikel über pseudo-boolesche Probleme ) und pseudo-boolesche Löser zu verwenden (siehe pseudo-boolesche Konkurrenz ). Auf diese Weise sind die Kardinalitätsbedingungen nur pseudo-boolesche Bedingungen und Teil der Sprache - hoffentlich behandelt der pseudo-boolesche Löser sie dann direkt und damit effizienter.
quelle
Ich gehe davon aus, dass Sie nach einer expliziten Reduktion suchen, aber wenn nicht, können Sie jederzeit auf das Cook-Levin-Theorem zurückgreifen .
quelle