การกำหนดกลุ่ม

Question

ฉันมีปัญหาในการกำหนดตัวแปรให้กับชุด แต่ละชุดมีขีด จำกัด ของตัวแปรที่สามารถกำหนดให้และแต่ละตัวแปรสามารถกำหนดให้กับชุดย่อยบางชุดของชุดทั้งหมดได้

ตัวอย่าง:

• aสามารถอยู่ในชุดAหรือB
• b สามารถอยู่ในชุด B
• cสามารถอยู่ในชุดAหรือB
• d สามารถอยู่ในชุด A

ดังนั้นเราสามารถมีA: a, d; B: b, cหรือA: c, d; B: a,b(ลำดับของตัวแปรภายในเซตไม่สำคัญ) /

แน่นอนว่าจะมีบางครั้งที่ไม่สามารถกำหนดตัวแปรทั้งหมดได้, บางครั้งที่เรามีหลายตัวเลือก, และเวลาที่มีเพียง 1 ตัวเลือกเท่านั้น

ฉันรู้สึกว่ามีปัญหานี้ในเวอร์ชันง่ายๆ แต่ดูเหมือนจะวางนิ้วลงไปไม่ได้ คำแนะนำใด ๆ จะได้รับการชื่นชม

Answer 1

แก้ไขได้อย่างมีประสิทธิภาพโดยใช้การไหลสูงสุด จัดเตรียมเครือข่ายการไหลที่มีส่วนโค้งความจุหน่วยจากแหล่งที่มาไปยังตัวแปรแต่ละตัวส่วนโค้งความจุหน่วยจากแต่ละตัวแปรไปยังแต่ละชุดที่สามารถเป็นสมาชิกได้และส่วนโค้งจากแต่ละชุดไปยังอ่างที่มีความจุเท่ากับความจุของชุด . ตัวอย่างเช่น,

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

ใช้อัลกอริทึมการไหลสูงสุดที่คุณชื่นชอบซึ่งสร้างโฟลว์อินทิกรัลและแยกการกำหนดตามตัวแปรที่กำหนดให้โค้งมีโฟลว์

Answer 2

ปัญหานี้เป็นแบบ NP-complete หมายความว่าไม่มีคำตอบเกี่ยวกับเวลาพหุนาม คุณจะต้องใช้การย้อนรอยในกรณีนี้

ดูลิงค์เหล่านี้:

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/