Diberikan satu set set, temukan set terkecil yang mengandung setidaknya satu elemen dari setiap set

Mengingat satu set set, saya ingin menemukan satu set M sehingga setiap set S di S mengandung setidaknya satu unsur M . Saya juga ingin M mengandung elemen sesedikit mungkin sambil tetap memenuhi kriteria ini, meskipun mungkin ada lebih dari satu M terkecil dengan properti ini (solusinya belum tentu unik).$\mathbf{S}$$M$$S$$\mathbf{S}$$M$$M$$M$

Sebagai contoh konkret, anggap bahwa himpunan adalah himpunan bendera nasional, dan untuk setiap bendera S dalam S , unsur-unsurnya adalah warna yang digunakan dalam bendera negara itu. Amerika Serikat akan memiliki S = { r e d , w h i t e , b l u e } dan Maroko akan memiliki S = { r e d , g r e e n } . Kemudian$\mathbf{S}$$S$$\mathbf{S}$$S = \{red, white, blue\}$$S = \{red, green\}$$M$akan menjadi satu set warna dengan properti yang setiap bendera nasional menggunakan setidaknya salah satu warna di . ( Warna Olimpiade biru, hitam, merah, hijau, kuning, dan putih adalah contoh dari M seperti itu , atau setidaknya pada tahun 1920.)$M$$M$

Apakah ada nama umum untuk masalah ini? Apakah ada algoritma "terbaik" yang diterima untuk menemukan set ? (Saya lebih tertarik pada solusi itu sendiri daripada mengoptimalkan proses untuk kompleksitas komputasi.)$M$

Masalahnya adalah masalah Set lengkap NP yang terkenal . Ini terkait erat dengan Set-Cover . Bukti kelengkapan NP dapat ditemukan di klasik buku Garey dan Johnson .

Jika Anda ingin memperkirakannya, Anda mungkin ingin menerjemahkan instance Anda terlebih dahulu ke Set-Cover, dan kemudian menerapkan algoritma perkiraan untuk Set-Cover. Namun, Set-Cover tidak dapat didekati oleh faktor konstan dalam waktu polinomial, kecuali P = NP seperti yang ditunjukkan oleh Lund dan Yannakakis .

Jika Anda tertarik pada solusi yang tepat dan input Anda berperilaku baik, saya akan merekomendasikan menggunakan traktat parameter-tetap . Waktu berjalan di sini tidak hanya dinyatakan dalam panjang input $n$ tetapi juga dalam hal parameter tambahan $k$ . Jika waktu berjalan adalah $O(f(k)\cdot n^{O(1)})$ , kami menyebut algoritma tersebut sebagai FPT-algoritma. Di sini, $f(k)$ adalah fungsi yang meningkat. Jadi, jika $k$ adalah konstan, kita memiliki algoritma polytime. The bab pertama dari buku oleh Flum dan Grohe , jelaskan suatu algoritma-FPT untuk memukul set (lebih tepatnya untuk $p$$k$

An idea that could help: if the intersection of all the sets in $\mathbf S$ in not empty, then you can pick any element $s$ in the intersection and set $M = \{s\}$. If the intersection is empty, find an element (color) $c$ whose occurrence in sets is maximum and replace all the sets in which it occurs by the singleton $\{c\}$. Keep doing this until every element's occurrence count is equal to $1$ and then set $M$ to the union of the remaining sets. For example, if $\mathbf S$ is the power set of some set $A$ then $M = A$. I might be wrong however.

Have a look at Ray Reiter's "A Theory of Diagnosis from First Principles" where he gives an algorithm for computing hitting sets, and this additional note "A correction...".

The algorithm is generally known as "hitting set tree" algorithm, it shouldn't be too hard to find an implementation. You mentioned you weren't too interested in runtime, but optimisations such as early branch termination etc. are quite critical to the implementation, and interesting as well :)

Practically speaking, one of the better ways (certainly one of the easiest) to solve instances of Set Cover/Hitting Set is mixed integer programming. This involves communicating the integer programming formulation to the solver of your choice.