Set terkecil yang memotong beberapa set yang diberikan

Biarkan menjadi set yang mungkin memiliki elemen yang sama. Saya mencari himpunan terkecil sehingga .$S_1,S_2,\ldots,S_n$$X$$\forall i,\,X\cap S_i \ne \emptyset$

Apakah masalah ini memiliki nama? Atau apakah itu mengurangi masalah yang diketahui?

Dalam konteks saya menggambarkan siklus elementer dari komponen yang sangat terhubung, dan saya sedang mencari sekumpulan simpul terkecil yang memotong semua siklus.$S_1,\ldots,S_n$$X$

Masalah pertama Anda adalah masalah transgral hypergraph (alias masalah HITTING SET ). Masalah kedua adalah masalah SET SET FEEDBACK . Kedua masalah tersebut adalah NP -complete.

Jika Anda ingin menyelesaikan contoh aktual, Anda mungkin akan seperti itu:

http://www.sagemath.org/doc/reference/sage/graphs/digraph.html#sage.graphs.digraph.DiGraph.feedback_vertex_set

Nathann

Jika kita menganggap S1, S2 ... Sn sebagai urutan yang berbeda dan jika kita membutuhkan urutan terpanjang yang umum dalam urutan ini maka jenis masalah ini disebut sebagai "Longest Common Subecessence (LCS)". Kita dapat mengubah kondisi untuk menjadikannya sebagai urutan umum terkecil yang akan menemukan elemen tunggal dari set sebagai urutan terkecil.

Silakan lihat contoh pemrograman dinamis Anda akan mendapatkan detail ...