Lors du test de n éléments, comment couvrir tous les sous-ensembles t avec le moins de sous-ensembles s possible?

Ce problème est né des tests de logiciels. Le problème est un peu difficile à expliquer. Je vais d'abord donner un exemple, puis essayer de généraliser le problème.

Il y a 10 éléments à tester, disons de A à J, et un outil de test qui peut tester 3 éléments en même temps. L'ordre des éléments dans l'outil de test n'a pas d'importance. Bien sûr, pour des tests exhaustifs, nous avons besoin de combinaisons d'éléments.$^{10}C_{3}$

Le problème est plus complexe. Il y a une condition supplémentaire qu'une fois qu'une paire d'articles a été testée ensemble, la même paire n'a pas besoin d'être testée à nouveau.

Par exemple, une fois que nous avons exécuté les trois tests suivants:

abc

ADE

BDF

nous n'avons pas à exécuter:

ABD

parce que la paire A, B était couverte par le premier cas de test, A, D était couverte par le second, et B, D était couverte par le troisième.

Donc, le problème est, quel est le nombre minimum de cas de test dont nous avons besoin pour nous assurer que toutes les paires sont testées?

Pour généraliser, si nous avons n éléments, s peut être testé en même temps, et nous devons nous assurer que tous les tuples possibles sont testés (tels que s> t), quel est le nombre minimum de cas de test dont nous avons besoin dans termes de n, s et t?

Et enfin, quel serait un bon algorithme pour générer les cas de test requis?

Les conceptions de blocs que vous souhaitez (pour tester 3 choses à la fois et couvrir toutes les paires) sont appelées systèmes triples Steiner . Il existe un triple système de Steiner avec triples chaque fois que mod , et des algorithmes sont connus pour les construire. Voir, par exemple, cette question MathOverflow (avec un lien vers le code Sage fonctionnel!). Pour les autres , vous pouvez arrondir au mod , et utiliser une modification de ce triple système pour pour couvrir toutes les paires pour . 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$

Si vous voulez la meilleure construction pour les autres , le nombre de triplets requis est le nombre de couverture , et est donné par cette entrée dans l'encyclopédie en ligne des séquences entières. Ce lien vers le référentiel de couverture de La Jolla qui a un référentiel de bonnes couvertures. L'encyclopédie en ligne des séquences entières donne une formule conjecturée pour ; si cette formule tient, intuitivement, cela signifie qu'il devrait probablement y avoir de bonnes façons algorithmiques de construire ces revêtements, mais puisque la formule est conjecturée, il est clair que personne ne les connaît actuellement.C ( n , 3 , 2 ) C ( n , 3 , 2 $n$ $C(n,3,2)$$C(n,3,2)$

Pour des nombres de couverture élevés, de bonnes couvertures sont plus difficiles à trouver que pour , et le référentiel donnera de meilleures solutions que tout algorithme efficace connu.$C(n,3,2)$

Formez le graphe non orienté où chaque sommet est une paire d'éléments et où il y a un bord entre deux sommets s'ils partagent un élément en commun. En d'autres termes, où et . Le graphe a sommets, et chaque sommet a arêtes incidentes.G = ( V , E ) V = { { a , b } : a , b ∈ Articles ∧ a ≠ b $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\}$ 2n-${n \choose 2}$$2n-4$

Ensuite , une approche serait de trouver une correspondance maximum dans . L'algorithme d'Edmonds peut être utilisé pour trouver une telle correspondance maximale en temps polynomial. Si vous êtes chanceux, cela vous donnera une correspondance parfaite, et alors vous êtes bon. Chaque arête dans la correspondance correspond à un cas de test . Étant donné que chaque sommet est incident avec une arête dans la correspondance parfaite, vous avez couvert toutes les paires, en utilisant cas de test, ce qui est dans un facteur optimal. Si vous n'obtenez pas une correspondance parfaite, ajoutez quelques cas de test supplémentaires au besoin pour obtenir une couverture complète.( { A , B } , { B , C } ) ∈ E A B C ($G$$(\{A,B\},\{B,C\}) \in E$$A B C$${n \choose 2}/2$$1.5$

Dans le cas de et vous devez effectuer au moins tests, car il y a paires et chaque test couvre 3 paires. Cela signifie que vous pouvez faire la chose triviale et effectuer des tests , et n'être qu'un facteur de 3 pire que l'optimum.t = 2 ($s=3$$t=2$ (${n \choose 2}/3$(${n \choose 2}$${n \choose 2}$

Si vous programmez réellement cela, alors un moyen d'optimiser cela pourrait être de choisir d'abord quelques tests numériques au hasard, puis de faire la force brute sur les paires non couvertes par le test jusqu'à présent.

---

Pour et , il existe une borne inférieure des tests . Pour une limite supérieure, je prétends que cela suffit pour faire tests.t ($s$$t$ C⋅ (${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))$

Voyons ce qui se passe, nous choisissons les tests uniformément au hasard. Si vous choisissez un -tuple au hasard, puis pour un -uple fixe , nous avons . Par conséquent, si nous choisissons tests au hasard, alorsS ⊆ [ n ] t X ⊆ [ n ] Pr $s$$S \subseteq [n]$$t$$X \subseteq [n]$$\Pr[X \subset S] = \frac{{n-t \choose s-t}}{{n \choose s}}$Pr[X n'appartient à aucun d'eux]$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}.$$

Par conséquent, par l'union liée, après tests aléatoires, tous les -uplets seront couverts.$O(t \cdot (\frac{n-t}{s-t})^t \log(n))$$t$