Najmniejszy zbiór, który przecina niektóre podane zbiory

Niech będą zestawami, które mogą mieć wspólne elementy. Szukam najmniejszego zestawu takiego, że .$S_1,S_2,\ldots,S_n$$X$$\forall i,\,X\cap S_i \ne \emptyset$

Czy ten problem ma nazwę? Czy może sprowadza się to do znanego problemu?

W moim kontekście opisują elementarne cykle silnie połączonego komponentu i szukam najmniejszego zestawu wierzchołków który przecina wszystkie cykle.$S_1,\ldots,S_n$$X$

Twój pierwszy problem to problem przekrojowy hipergrafu (zwany także problemem HITTING SET ). Drugi problem to problem ZESTAWU OPINII VERTEX . Oba problemy są zakończone NP .

Jeśli chcesz rozwiązać rzeczywiste instancje, prawdopodobnie polubisz to:

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

Nathann

Jeśli weźmiemy pod uwagę S1, S2 ... Sn jako różne sekwencje i jeśli potrzebujemy najdłuższej podsekwencji, która jest wspólna w tych sekwencjach, wówczas ten typ problemu nazywamy „najdłuższą wspólną podsekwencją (LCS)”. Możemy zmienić warunek, aby był to najmniejszy wspólny podsekwencja, w którym pojedynczy element z zestawu będzie znajdował się jako najmniejszy podsekwencja.

Zobacz przykłady programowania dynamicznego, a otrzymasz szczegółowe informacje ...