Wie können beim Testen von n Elementen alle t-Teilmengen durch möglichst wenige s-Teilmengen abgedeckt werden?

Dieses Problem ergab sich aus Softwaretests. Das Problem ist etwas schwer zu erklären. Ich werde zuerst ein Beispiel geben und dann versuchen, das Problem zu verallgemeinern.

Es müssen 10 Elemente getestet werden, z. B. A bis J, und ein Testwerkzeug, mit dem 3 Elemente gleichzeitig getestet werden können. Die Reihenfolge der Elemente im Testwerkzeug spielt keine Rolle. Für umfassende Tests benötigen wir natürlich Kombinationen von Elementen.$^{10}C_{3}$

Das Problem ist komplexer. Es gibt eine zusätzliche Bedingung, dass, sobald ein Paar von Elementen zusammen getestet wurde, dasselbe Paar nicht erneut getestet werden muss.

Zum Beispiel, nachdem wir die folgenden drei Tests ausgeführt haben:

ABC

ADE

BDF

wir müssen nicht ausführen:

ABD

da das Paar A, B vom ersten Testfall abgedeckt wurde, wurde A, D vom zweiten und B, D vom dritten abgedeckt.

Das Problem ist also, wie viele Testfälle müssen mindestens erforderlich sein, um sicherzustellen, dass alle Paare getestet werden?

Um zu verallgemeinern, wenn wir n Elemente haben, können s gleichzeitig getestet werden, und wir müssen sicherstellen, dass alle möglichen t-Tupel getestet werden (so dass s> t), wie viele Testfälle wir mindestens benötigen Terme von n, s und t?

Und schließlich, was wäre ein guter Algorithmus, um die erforderlichen Testfälle zu generieren?

Die gewünschten Blockdesigns (zum Testen von 3 Dingen gleichzeitig und zum Abdecken aller Paare) werden als Steiner-Tripelsysteme bezeichnet . Es gibt ein Steiner-Tripelsystem mit Tripeln, wenn mod , und es ist bekannt, dass Algorithmen diese konstruieren. Siehe zum Beispiel diese MathOverflow-Frage (mit einem Link zum funktionierenden Sage-Code!). Für andere könnten Sie auf das nächste mod aufrunden und eine Modifikation dieses Tripelsystems für , um alle Paare für abzudecken . n≡1Or36nn'≡1Or36n'$\frac{1}{3} {n \choose 2}$$n \equiv 1 \mathrm{\ or\ } 3$$6$$n$$n' \equiv 1 \mathrm{\ or\ } 3$$6$$n'$$n$

Wenn Sie die beste Konstruktion für andere wünschen , ist die Anzahl der erforderlichen Tripel die Deckungszahl und wird durch diesen Eintrag in der Online-Enzyklopädie von Ganzzahlsequenzen angegeben. Dies ist ein Link zum La Jolla Covering Repository, das ein Repository mit guten Coverings enthält. Die Online-Enzyklopädie ganzzahliger Sequenzen liefert eine vermutete Formel für ; Wenn diese Formel gilt, bedeutet dies intuitiv, dass es wahrscheinlich gute algorithmische Möglichkeiten zur Konstruktion dieser Abdeckungen geben sollte. Da die Formel jedoch vermutet wird, ist klar, dass sie derzeit niemand kennt.C ( n , 3 , 2 ) C ( n , 3 , 2 $n$ $C(n,3,2)$$C(n,3,2)$

Bei hohen Abdeckungszahlen sind gute Abdeckungen schwerer zu finden als bei , und das Repository bietet bessere Lösungen als alle bekannten effizienten Algorithmen.$C(n,3,2)$

Bilden Sie den ungerichteten Graphen in dem jeder Scheitelpunkt ein Paar von Elementen ist und in dem sich zwischen zwei Scheitelpunkten eine Kante befindet, wenn sie ein gemeinsames Element haben. Mit anderen Worten, wobei und . Der Graph hat Eckpunkte und jeder Eckpunkt hat Kanten, die auf ihn fallen.$G$$G=(V,E)$$V=\{\{a,b\} : a,b \in \text{Items} \land a\ne b\}$$E=\{(s,t) : s,t \in V \land |s\cap t|=1\}$${n \choose 2}$$2n-4$

Dann wäre ein Ansatz, eine maximale Übereinstimmung in . Der Edmonds-Algorithmus kann verwendet werden, um eine solche maximale Übereinstimmung in der Polynomzeit zu finden. Wenn Sie Glück haben, erhalten Sie eine perfekte Übereinstimmung, und dann sind Sie gut. Jede Kante in der Übereinstimmung entspricht einem Testfall . Da jeder Scheitelpunkt mit einer Kante in der perfekten Übereinstimmung einfällt, haben Sie alle Paare mit Testfällen abgedeckt , was innerhalb eines fachen Optimals liegt. Wenn Sie keine perfekte Übereinstimmung erhalten, fügen Sie nach Bedarf einige weitere Testfälle hinzu, um eine vollständige Abdeckung zu erzielen.$G$$(\{A,B\},\{B,C\}) \in E$$A B C$${n \choose 2}/2$$1.5$

Im Fall von und Sie mindestens Tests durchführen, da es Paare gibt und jeder Test 3 Paare abdeckt. Das bedeutet, dass Sie das Triviale tun und -Tests durchführen können und nur um den Faktor 3 schlechter als das Optimum sind.$s=3$$t=2$${n \choose 2}/3$${n \choose 2}$${n \choose 2}$

Wenn Sie dies tatsächlich programmieren, können Sie dies optimieren, indem Sie zunächst einige zufällige Zahlentests auswählen und dann die Brute Force auf die Paare anwenden, die bisher nicht vom Test abgedeckt wurden.

---

Für allgemeine und gibt es eine Untergrenze von Tests. Für eine Obergrenze behaupte ich, dass dies ausreicht, um Tests.$s$$t$${n \choose t}/{s \choose t}$$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))$

Mal sehen , was passiert , wir wir die Tests gleichmäßig auf gelegentliches wählen Sie wählen ein - tupel zufällig, dann für eine feste tupel , haben wir . Wenn wir also zufällig Tests , dann gehört$s$$S \subseteq [n]$$t$$X \subseteq [n]$$\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}.$$

Daher werden durch die gebundene Vereinigung nach Zufallstests alle Tupel abgedeckt.$O(t \cdot (\frac{n-t}{s-t})^t \log(n))$$t$