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

10

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 kombinacji przedmiotów w . $^{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?

algorithms combinatorics software-testing

— wookie919
źródło

1

Przypadki były testem jest „optymalna” (co

-tuple testuje dokładnie raz) są objęte pojęciem konstrukcja bloku . Istnieje stosunkowo niewiele z tych doskonałych możliwości testowych, więc chyba potrzebuję dodatkowej heurystyki.

t

$t$

— Hendrik,

Twój paradygmat testowy jest wadliwy; testowanie tylko par może być niewystarczające. Niektóre błędy mogą wystąpić tylko wtedy, gdy trzy (lub więcej) składniki działają razem w określonej kombinacji.

— Raphael

4

@Raphael, dziękuję za znacznie lepszy tytuł, ale zupełnie nie rozumiem, jak możesz twierdzić, że „Twój testowy paradygmat jest wadliwy”, ponieważ nie rozumiem rzeczywistego problemu ani kontekstu.

— wookie919,

@ wookie919 To dlatego, że nie dają żadnego kontekstu, ale stwarzają żadnego problemu. Zauważyłem jedynie, że generalnie może być konieczne przetestowanie wszystkich kombinacji, które mogą wystąpić (w działaniu).

— Raphael

11

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, gdymodi algorytmy znane skonstruować nich. Zobacz na przykład topytanie MathOverflow(z linkiem do działającego kodu Sage!). Do innych, można zaokrąglenie w górę do najbliższegomodi użyć modyfikację tego potrójnego układu dodo pokrycia wszystkich parach. $\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ą 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 $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)$

— Peter Shor
źródło

5

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, gdzie i $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 sobiekrawę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ź na odpowiada dopasowujący się do testu . 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 zakresieoptymalnego. Jeśli nie uzyskasz idealnego dopasowania, dodaj kilka kolejnych przypadków testowych, aby uzyskać pełne pokrycie. ${n \choose 2}/2$ $1.5$

— DW
źródło

4

W przypadku i 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 istnieje dolna granica $s$ $t$ testy. Twierdzę, że dla górnej granicy wystarczy, aby ${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 , to dla stałej -pleple mamy $s$ $S \subseteq [n]$ $t$ $X \subseteq [n]$ . Dlatego jeśli wybierzemy $\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 does not belong to any of them] = {(1 - \frac{(\binom{n - t}{s - t})}{(\binom{n}{s})})}^{C \cdot (\binom{n}{t}) \cdot \log ((\binom{n}{t}))} \leq \exp (- C \frac{(\binom{n - t}{s - t}) (\binom{n}{t})}{(\binom{n}{s}) (\binom{s}{t})} \cdot \log ((\binom{n}{t}))) = \exp (- C \log (\binom{n}{t})) \leq 1 / (\binom{n}{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.

— Igor Shinkar
źródło

Thank you very much for the very insightful answer, but I was looking for an exact algorithm that would generate exactly the

(\binom{n}{t}) / s

${n \choose t}/s$ lower bound number of test cases (if that is even possible), or something very close to the lower bound.

— wookie919