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

10

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.10C3

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?

wookie919
quelle
1
Die Fälle waren der Test ist „optimal“ (alles - tupel genau einmal getestet wird) durch den Begriff abgedeckt Blockbauweise . Es gibt relativ wenige dieser perfekten Testmöglichkeiten, daher benötigt man zusätzliche Heuristiken, denke ich. t
Hendrik Jan
Ihr Testparadigma ist fehlerhaft. Es reicht möglicherweise nicht aus, nur Paare zu testen. Einige Fehler können nur auftreten, wenn drei (oder mehr) Komponenten in einer bestimmten Kombination zusammenwirken.
Raphael
4
@Raphael, danke für einen viel besseren Titel, aber ich verstehe überhaupt nicht, wie Sie behaupten können, "Ihr Testparadigma ist fehlerhaft", wenn Sie das eigentliche Problem oder den Kontext nicht verstehen.
Wookie919
@ wookie919 Das ist , weil Sie nicht geben jedem Kontext , sondern eine Pose allgemeine Problem. Ich habe lediglich festgestellt, dass Sie im Allgemeinen möglicherweise alle Kombinationen testen müssen, die auftreten können (in Aktion).
Raphael

Antworten:

11

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 . n1Or36nn'1Or36n'n13(n2)n1 or 36nn1 or 36nn

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)

Peter Shor
quelle
5

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.GG=(V,E)V={{a,b}:a,bItemsab}E={(s,t):s,tV|st|=1}(n2)2n4

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})EABC(n2)/21.5

DW
quelle
4

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=3t=2(n2)/3(n2)(n2)

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.st(nt)/(st)C(nt)(st)log((nt))O(t(ntst)tlog(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örtsS[n]tX[n]Pr[XS]=(ntst)(ns)C(nt)log((nt))

Pr[X does not belong to any of them]=(1(ntst)(ns))C(nt)log((nt))exp(C(ntst)(nt)(ns)(st)log((nt)))=exp(Clog(nt))1/(nt).

Daher werden durch die gebundene Vereinigung nach Zufallstests alle Tupel abgedeckt.tO(t(ntst)tlog(n))t

Igor Shinkar
quelle
Vielen Dank für die sehr interessante Antwort, aber ich war auf der Suche nach einem genauen Algorithmus, der genau erzeugen würde die gebunden Anzahl der Testfälle zu senken (wenn das überhaupt möglich ist), oder etwas ganz in der Nähe die Untergrenze. (nt)/s
Wookie919