Grup atama

Question

Kümelere değişken atamakla ilgili bir problemim var. Her küme, kendisine atanabilecek bir değişken sınırına sahiptir ve her değişken, toplam kümelerin bazı alt kümelerine atanabilir.

Misal:

• asetler halinde olabilir AveyaB
• b setler halinde olabilir B
• csetler halinde olabilir AveyaB
• d setler halinde olabilir A

Böylece, A: a, d; B: b, cveya A: c, d; B: a,b(küme içindeki değişkenlerin sırası önemli değildir) /

Tabii ki, tüm değişkenleri atamanın imkansız olduğu zamanlar, birden fazla seçeneğimiz olduğu zamanlar ve sadece 1 seçenekli zamanlar olacaktır.

Bu sorunun basit bir versiyonu varmış gibi hissediyorum ama parmağımı üzerine koyamıyorum. Herhangi bir işaretçi takdir edilecektir.

Answer 1

Maksimum akış kullanarak verimli bir şekilde çözülebilir. Bir kaynaktan her değişkene bir birim kapasite arkı, her değişkenden ait olabileceği her bir sete bir birim kapasite arkı ve her setten setin kapasitesine eşit bir kapasite havuzuna bir yay ile bir akış ağı hazırlayın . Örneğin,

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

İntegral bir akış üreten en sevdiğiniz maksimum akış algoritmasını kullanın ve yayların ayarlanacağı değişkene göre atamayı çıkarın.

Answer 2

Bu problem NP-tamdır, yani bunun için polinom zaman çözümü yoktur. Bu durumda geriye dönük izlemeyi kullanmanız gerekir.

Şu bağlantılara bir göz atın:

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/