Biorąc pod uwagę zestaw zestawów, znajdź najmniejsze zestawy zawierające co najmniej jeden element z każdego zestawu

Biorąc pod uwagę zestaw zestawów, chciałbym znaleźć zestaw takie, że każdy zbiór w zawiera co najmniej jeden element . Chciałbym również, aby zawierał jak najmniej elementów, jednocześnie spełniając to kryterium, chociaż może istnieć więcej niż jeden najmniejszy z tą właściwością (rozwiązanie niekoniecznie jest unikalne).$\mathbf{S}$$M$$S$$\mathbf{S}$$M$$M$$M$

Jako konkretny przykład, załóżmy, że zestaw jest zbiorem flag narodowych, a dla każdej flagi w elementami są kolory użyte w fladze tego kraju. Stany Zjednoczone miałyby a Maroko miałby . Następnie będzie zestaw kolorów z własności, że każdy używa flag narodowych co najmniej jeden z kolorów . ( Olimpijskie kolory: niebieski, czarny, czerwony, zielony, żółty i biały są przykładem takiego , a przynajmniej były w 1920 r.)$\mathbf{S}$$S$$\mathbf{S}$$S = \{red, white, blue\}$$S = \{red, green\}$$M$$M$$M$

Czy istnieje ogólna nazwa tego problemu? Czy istnieje zaakceptowany algorytm „najlepszego” wyszukiwania zestawu ? (Bardziej interesuje mnie samo rozwiązanie niż optymalizacja procesu pod kątem złożoności obliczeniowej).$M$

Problemem jest dobrze znany zestaw uderzeń NP-zupełny . Jest ściśle związany z Set-Cover . Dowód kompletności NP można znaleźć w klasycznej książce Garey and Johnson .

Jeśli chcesz to przybliżyć, możesz najpierw przetłumaczyć swoją instancję na Set-Cover, a następnie zastosować algorytm aproksymacji dla Set-Cover. Jednak Set-Cover nie może być aproksymowany stałym współczynnikiem czasu wielomianowego, chyba że P = NP, jak pokazują Lund i Yannakakis .

Jeśli jesteś zainteresowany dokładnymi rozwiązaniami, a twoje dane zachowują się ładnie, polecam użycie stałego parametru parametrycznego . Czas pracy jest tu wyrażony nie tylko jako długość wejściowa ale również jako dodatkowy parametr . Jeśli czas działania wynosi , algorytm nazywamy algorytmem FPT. Tutaj jest funkcją rosnącą. Więc jeśli jest stałe, mamy algorytm czasu policy. Pierwszy rozdział z książki Flum i Grohe , wyjaśnia się FPT algorytm za uderzenie zestaw (dokładniej na$n$$k$$O(f(k)\cdot n^{O(1)})$$f(k)$$k$$p$zestaw uderzeń kartą). Algorytm jest łatwy do wdrożenia i wykorzystuje metodę ograniczonych drzew wyszukiwania. Nadal potrzebuje dużo miejsca, aby wyjaśnić tutaj, w zasadzie rozkładasz niezbędne (?) Poszukiwania siły, na małe kawałki (gdy jest małe).$k$

Pomysł, który może pomóc: jeśli przecięcie wszystkich zbiorów w nie jest puste, możesz wybrać dowolny element na przecięciu i ustawić . Jeśli przecięcie jest puste, znajdź element (kolor) którego występowanie w zestawach jest maksymalne, i zastąp wszystkie zbiory, w których występuje, przez singleton . Rób to dalej, aż liczba wystąpień każdego elementu będzie równa a następnie ustaw na sumę pozostałych zbiorów. Na przykład, jeśli jest zbiorem moc pewnego zbioru czym . Mogę się jednak mylić.$\mathbf S$$s$$M = \{s\}$$c$$\{c\}$$1$$M$$\mathbf S$$A$$M = A$

Spójrz na „Teorię diagnozy od pierwszych zasad” Raya Reitera, w której podaje algorytm obliczania zestawów uderzeń, a także dodatkową notatkę „Korekta ...” .

Algorytm jest ogólnie znany jako algorytm „uderzania w drzewo setów”, nie powinno być zbyt trudno znaleźć implementację. Wspomniałeś, że nie interesujesz się zbytnio środowiskiem uruchomieniowym, ale optymalizacje, takie jak wcześniejsze zakończenie gałęzi itp., Są bardzo ważne dla implementacji, a także interesujące :)

Praktycznie rzecz biorąc, jednym z lepszych sposobów (z pewnością jednym z najłatwiejszych) rozwiązania instancji Set Cover / Hitting Set jest mieszane programowanie liczb całkowitych. Wymaga to przekazania formuły programowania liczb całkowitych do wybranego przez ciebie solwera .