Zmniejsz następujący problem do SAT

Oto problem. Biorąc pod uwagę , gdzie każdy T i ⊆ { 1 , … , n } . Czy istnieje podzbiór S ⊆ { 1 , … , n } o rozmiarze co najwyżej k taki, że S ∩ T i ≠ ∅ dla wszystkich ja ? Próbuję zredukować ten problem do SAT. Moim pomysłem na rozwiązanie byłoby posiadanie zmiennej x $k, n, T_1, \ldots, T_m$$T_i \subseteq \{1, \ldots, n\}$$S \subseteq \{1, \ldots, n\}$$k$$S \cap T_i \neq \emptyset$$i$$x_i$dla każdego z 1 do . Dla każdego T i utwórz klauzulę ( x i 1 ∨ ⋯ ∨ x i k ), jeśli T i = { i 1 , … , i k } . Następnie i wszystkie te klauzule razem. Ale to wyraźnie nie jest kompletne rozwiązanie, ponieważ nie reprezentuje ograniczenia, które S musi mieć co najwyżej k elementów. Wiem, że muszę tworzyć więcej zmiennych, ale po prostu nie jestem pewien, jak to zrobić. Mam więc dwa pytania:$n$$T_i$$(x_{i_1} \vee \cdots \vee x_{i_k})$$T_i = \{i_1, \ldots, i_k\}$$S$$k$

1. Czy mój pomysł na rozwiązanie jest właściwy?
2. Jak należy utworzyć nowe zmienne, aby można je było wykorzystać do przedstawienia ograniczenia liczności ?$k$

Wygląda na to, że próbujesz obliczyć przekrój poprzeczny wielkości . Oznacza to, że { T 1 , … , T m } jest twoim hipergrrafem, a S jest twoim poprzecznym. Tłumaczenie standardowe polega na wyrażeniu istniejących klauzul, a następnie przetłumaczeniu ograniczenia długości na ograniczenie liczności.$k$$\{T_1,\dots,T_m\}$$S$

$\bigwedge_{1 \le j \le m} \bigvee_{i \in T_j} x_i$$\sum_{1 \le i \le n} x_i \le k$

$\sum_{1 \le i \le n} x_i \le k$

$\bigwedge_{X \subseteq \{1,\dots,n\}, |X| = k+1} \bigvee_{i \in X} \neg x_i$$\neg \bigwedge_{i \in X} x_i$$X$$\{1,\dots,n\}$$k$

$k$

• Tłumaczenie pseudo-boolowskich ograniczeń na SAT - Niklas Eén i Niklas Sörensson, JSAT vol. 2 (2006), str. 1-26 (dobra ankieta).
• Wydajne kodowanie CNF ograniczeń logicznej kardynalności - Olivier Bailleux i Yacine Boufkhad, Proceedings of Principles and Practice of Constraint Programming 2003, LNCS vol 2833, str. 108-122 (ładne, dość łatwe do wdrożenia tłumaczenie).
• W kierunku optymalnego kodowania CNF ograniczeń logicznej kardynalności - Carsten Sinz - Postępowanie w zakresie zasad i praktyka programowania ograniczeń 2005, LNCS 3709, str. 827-831.
• W kierunku solidnych kodowań ograniczeń kardynalności CNF - Joao Marques-Silva i Inês Lynce, Postępowanie z zasadami i praktyka programowania ograniczeń 2007, LNCS 4741, str. 483-497.

Jeśli faktycznie jesteś zainteresowany rozwiązaniem takich problemów, być może lepiej sformułować je jako problemy pseudo-boolowskie (zobacz artykuł wiki na temat problemów pseudo-boolean ) i użyć solverów pseudo-boolean (patrz konkurencja pseudo-boolean ). W ten sposób ograniczenia liczności są tylko ograniczeniami pseudo-boolowskimi i są częścią języka - miejmy nadzieję, że solver pseudo-boolowski obsługuje je bezpośrednio, a zatem bardziej wydajnie.

$k$

$\Gamma_{2,1}^{+}$$\Gamma_{2,1}^{+}$

Zakładam, że szukasz wyraźnej redukcji, ale jeśli nie, zawsze możesz po prostu wrócić do twierdzenia Cooka-Levina .