Menetapkan grup

Question

Saya punya masalah di mana saya menetapkan variabel ke set. Setiap set memiliki batas variabel yang dapat ditetapkan ke dalamnya dan setiap variabel dapat ditetapkan ke beberapa subset dari total set.

Contoh:

• abisa dalam set AatauB
• b bisa di set B
• cbisa dalam set AatauB
• d bisa di set A

Jadi, kita dapat memiliki A: a, d; B: b, catau A: c, d; B: a,b(urutan variabel dalam himpunan tidak menjadi masalah) /

Tentu saja, akan ada kalanya tidak mungkin untuk menetapkan semua variabel, saat kita memiliki beberapa opsi, dan waktu dengan hanya 1 opsi.

Saya merasa ada versi sederhana dari masalah ini tetapi sepertinya saya tidak dapat menjelaskannya. Setiap petunjuk akan dihargai.

Answer 1

Dapat dipecahkan secara efisien menggunakan aliran maks. Siapkan jaringan aliran dengan busur kapasitas unit dari sumber ke setiap variabel, busur kapasitas unit dari setiap variabel ke setiap set yang dapat dimilikinya, dan busur dari setiap set ke sink kapasitas yang sama dengan kapasitas set . Sebagai contoh,

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

Gunakan algoritme aliran maks favorit Anda yang menghasilkan aliran integral dan ekstrak tugas sesuai dengan variabel mana yang akan disetel busur memiliki aliran.

Answer 2

Masalah ini NP-complete artinya tidak ada solusi waktu polinomial untuk ini. Anda harus menggunakan backtracking dalam kasus ini.

Lihat tautan berikut:

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/