Podczas testowania n elementów, jak pokryć wszystkie podzbiory t przez jak najmniejszą liczbę podzbiorów s?

Ten problem powstał w wyniku testowania oprogramowania. Problem jest trochę trudny do wyjaśnienia. Najpierw podam przykład, a następnie spróbuję uogólnić problem.

Do przetestowania jest 10 elementów, od A do J, oraz narzędzie testujące, które może testować 3 elementy jednocześnie. Kolejność elementów w narzędziu testowym nie ma znaczenia. Oczywiście do wyczerpujących testów potrzebujemy 10 kombinacji przedmiotów w C 3 .$^{10}C_{3}$

Problem jest bardziej złożony. Istnieje dodatkowy warunek, że gdy para elementów zostanie przetestowana razem, ta sama para nie musi być ponownie testowana.

Na przykład po wykonaniu następujących trzech testów:

ABC

ADE

BDF

nie musimy wykonywać:

ABD

ponieważ para A, B była objęta pierwszym przypadkiem testowym, A, D była objęta drugim, a B, D była objęta trzecim.

Problem w tym, jaka jest minimalna liczba przypadków testowych, których potrzebujemy, aby zapewnić przetestowanie wszystkich par?

Aby uogólnić, jeśli mamy n elementów, s można przetestować w tym samym czasie i musimy upewnić się, że wszystkie możliwe t krotki są testowane (takie, że s> t), jaka jest minimalna liczba przypadków testowych, których potrzebujemy w warunki n, s i t?

I wreszcie, jaki byłby dobry algorytm do generowania wymaganych przypadków testowych?

Projekty bloków, które chcesz (do testowania 3 rzeczy na raz i obejmujące wszystkie pary) są nazywane potrójnymi systemami Steiner . Istnieje potrójny system Steiner z trzykrotnie, gdyn≡1OR3mod6i algorytmy znane skonstruować nich. Zobacz na przykład topytanie MathOverflow(z linkiem do działającego kodu Sage!). Do innychN, można zaokrąglenie w górę do najbliższegon'≡1OR3mod6i użyć modyfikację tego potrójnego układu don"do pokrycia wszystkich parachn.$\frac{1}{3} {n \choose 2}$$n \equiv 1 \mathrm{\ or\ } 3$$6$$n$$n' \equiv 1 \mathrm{\ or\ } 3$$6$$n'$$n$

Jeśli chcesz uzyskać najlepszą konstrukcję dla innych , wymagana liczba trójek jest liczbą obejmującą C ( n , 3 , 2 ) i jest podana w tym wpisie w internetowej encyklopedii ciągów całkowitych. Ten link prowadzi do La Jolla Covering Repository, które ma repozytorium dobrych pokryć. Internetowa encyklopedia sekwencji całkowitych podaje domniemaną formułę dla C ( n , 3 , 2 $n$ $C(n,3,2)$$C(n,3,2)$; jeśli ta formuła obowiązuje, intuicyjnie oznacza to, że prawdopodobnie powinny istnieć dobre algorytmiczne sposoby konstruowania tych osłon, ale skoro formuła jest domniemana, jasne jest, że nikt ich obecnie nie zna.

W przypadku wysokich liczb pokrycia trudniej jest znaleźć dobre pokrycia niż dla , a repozytorium da lepsze rozwiązania niż jakikolwiek znany skuteczny algorytm.$C(n,3,2)$

Utwórz niekierowany wykres którym każdy wierzchołek jest parą elementów, a między dwoma wierzchołkami znajduje się krawędź, jeśli mają one wspólny element. Innymi słowy, G = ( V , E ) gdzie V = { { a , b } : a , b ∈ Pozycje ∧ a ≠ b } i E = { ( s , t ) : s , t ∈ V ∧ | $G$$G=(V,E)$$V=\{\{a,b\} : a,b \in \text{Items} \land a\ne b\}$ . Wykres ma ($E=\{(s,t) : s,t \in V \land |s\cap t|=1\}$ wierzchołki, a każdy wierzchołek ma na sobie2n-4krawędzie.${n \choose 2}$$2n-4$

Potem jedno podejście byłoby znaleźć pasujący Maksimum w . Algorytmu Edmondsa można użyć do znalezienia takiego maksymalnego dopasowania w czasie wielomianowym. Jeśli masz szczęście, da ci to idealne dopasowanie, a potem będziesz dobry. Każda krawędź ( { , B } , { B , C } ) ∈ E na odpowiada dopasowujący się do testu B C . Ponieważ każdy wierzchołek pada z jedną krawędzią w idealnym dopasowaniu, pokryłeś wszystkie pary, używając ($G$$(\{A,B\},\{B,C\}) \in E$$A B C$przypadków testowych, co mieści się w zakresie1,5optymalnego. Jeśli nie uzyskasz idealnego dopasowania, dodaj kilka kolejnych przypadków testowych, aby uzyskać pełne pokrycie.${n \choose 2}/2$$1.5$

W przypadku i t = 2 trzeba przeprowadzić co najmniej ($s=3$$t=2$testy, ponieważ istnieją (${n \choose 2}/3$ pary, a każdy test obejmuje 3 pary. Oznacza to, że możesz zrobić trywialną rzecz i wykonać (${n \choose 2}$ testy i być tylko 3 razy gorsze niż optymalne.${n \choose 2}$

Jeśli faktycznie to programujesz, to sposobem na zoptymalizowanie tego może być wybranie losowo kilku testów liczbowych, a następnie użycie brutalnej siły na parach nieobjętych dotychczas testem.

---

Dla ogólnych i t istnieje dolna granica ($s$$t$ testy. Twierdzę, że dla górnej granicy wystarczy, abyC⋅ (${n \choose t}/{s \choose t}$testy.$C \cdot \frac{{n \choose t}}{s \choose t}\cdot {\log({n \choose t})} \leq O(t \cdot (\frac{n-t}{s-t})^t \log(n))$

Zobaczmy, co się stanie, wybieramy testy równomiernie losowo. Jeśli losowo wybierzesz -pleple S ⊆ [ n ] , to dla stałej t -pleple X ⊆ [ n ] mamy Pr [ X ⊂ S ] = ( n - $s$$S \subseteq [n]$$t$$X \subseteq [n]$ . Dlatego jeśli wybierzemyC⋅($\Pr[X \subset S] = \frac{{n-t \choose s-t}}{{n \choose s}}$$C \cdot {n \choose t} \cdot {\log({n \choose t})}$

$$\Pr[X \text{ does not belong to any of them}] = \left(1 - \frac{{n-t \choose s-t}}{{n \choose s}}\right)^{C \cdot {n \choose t} \cdot {\log({n \choose t})}} \leq \exp \left(-C \frac{{n-t \choose s-t}{n \choose t}}{{n \choose s}{s \choose t}} \cdot \log({n \choose t})\right) = \exp(-C \log{n \choose t})\leq 1/{n \choose t}.$$

Therefore, by the union bound, after $O(t \cdot (\frac{n-t}{s-t})^t \log(n))$ random tests all $t$-tuples will be covered.