To nie jest odpowiedź. To prosta, ale długa obserwacja. Mam nadzieję, że się przyda.
Wersja decyzyjna twojego problemu to: Tak X zawierają podzbiór A?
Problem ten związany jest z problemem oceny monotonicznych funkcji boolowskich nzmienne. Podzbiór{1,…,n} jest równoważne z n-bitstring, więc rodzina X jest równoważne funkcji boolowskiej f z nzmienne. Biorąc pod uwagę funkcjęf, można zdefiniować najmniej monotoniczną funkcję, która nie jest większa niż f, mianowicie g(y)=(∃x⊆y,f(x)). Pierwotny problem sprowadza się następnie do ocenyg(A). I odwrotnie, problem oceny monotonicznej funkcji boolowskiej można sprowadzić do pierwotnego problemu, albo naiwnie, przyjmującf=g lub wybierając f sprawia, że X mniejszy.
W praktyce dyski BDD zwykle działają dobrze. Jednym z możliwych podejść jest zbudowanie BDDf, pochodzą z niego BDD dla g, a następnie oceń g. Średnia wielkość BDD dlag musi być Ω((nn/2)), ponieważ istnieje wiele monotonicznych funkcji boolowskich . Stąd teoretycznie jest to złe rozwiązanie.
Ale (1) możliwa jest lepsza analiza i (2) mogą istnieć poprawki w tym podejściu, które czynią go lepszym. Na przykład nie użyłem w żaden sposób korelacji między wielkościąX i rozmiar gBDD. (Musi istnieć korelacja, ale nie wiem, czy jest tutaj prosta czy użyteczna).
Dla kompletności, prosty algorytm obliczania BDD dla g z BDD dla f jest następujący.
m ( x ?fa1:fa0) = x ? ( m (fa0) ∨ m (fa1) ) : m (fa0)
Tutaj
∨ jest standardową operacją na dyskach BDD.