Al probar n elementos, ¿cómo cubrir todos los subconjuntos t con el menor número de subconjuntos s posible?

10

Este problema surgió de las pruebas de software. El problema es un poco difícil de explicar. Primero daré un ejemplo, luego trataré de generalizar el problema.

Hay 10 elementos para probar, digamos A a J, y una herramienta de prueba que puede probar 3 elementos al mismo tiempo. El orden de los elementos en la herramienta de prueba no importa. Por supuesto, para pruebas exhaustivas, necesitamos 10 combinaciones de elementos C 3 .10C3

El problema es más complejo. Existe una condición adicional de que una vez que se ha probado un par de elementos juntos, no es necesario volver a probar el mismo par.

Por ejemplo, una vez que ejecutamos las siguientes tres pruebas:

A B C

ADE

BDF

no tenemos que ejecutar:

ABD

porque el par A, B estaba cubierto por el primer caso de prueba, A, D estaba cubierto por el segundo, y B, D estaba cubierto por el tercero.

Entonces, el problema es, ¿cuál es el número mínimo de casos de prueba que necesitamos para garantizar que se prueben todos los pares?

Para generalizar, si tenemos n ítems, s pueden ser probados al mismo tiempo, y debemos asegurarnos de que se prueben todas las tuplas posibles (tal que s> t), ¿cuál es el número mínimo de casos de prueba que necesitamos en términos de n, syt?

Y finalmente, ¿cuál sería un buen algoritmo para generar los casos de prueba requeridos?

wookie919
fuente
1
Los casos en que la prueba es "óptima" (cada tupla se prueba exactamente una vez) están cubiertos por la noción de diseño de bloques . Hay relativamente pocas de estas posibilidades de prueba perfectas, así que uno necesita heurística adicional, supongo. t
Hendrik Jan
Su paradigma de prueba es defectuoso; Puede que no sea suficiente probar solo pares. Algunos errores solo pueden ocurrir si tres (o más) componentes actúan juntos en una combinación específica.
Raphael
44
@Raphael, gracias por un título mucho mejor, pero no entiendo por completo cómo puedes afirmar que "tu paradigma de prueba es defectuoso" al no comprender el problema real o el contexto.
wookie919
@ wookie919 Eso es porque no le das ningún contexto sino que planteas un problema general . Simplemente he observado que, en general, es posible que deba probar todas las combinaciones que pueden ocurrir (en acción).
Raphael

Respuestas:

11

Los diseños de bloques que desea (para probar 3 cosas a la vez y cubrir todos los pares) se denominan sistemas triples Steiner . Existe un sistema triple Steiner con triplica siempre quen1or3mod6, y se sabe que los algoritmos construyen estos. Consulte, por ejemplo, estapregunta de MathOverflow(con un enlace al código de Sage que funciona). Para otrosn, podría redondear al siguienten1or3mod6, y utilizar una modificación de este sistema triple paranpara cubrir todos los pares paran.13(norte2)norte1 or 36 6nortenorte1 or 36 6nortenorte

Si desea la mejor construcción para otro , el número de triples requerido es el número de cobertura C ( n , 3 , 2 ) , y viene dado por esta entrada en la enciclopedia en línea de secuencias enteras. Esto enlaza con el repositorio de cobertura de La Jolla, que tiene un repositorio de buenas coberturas. La enciclopedia en línea de secuencias enteras proporciona una fórmula conjeturada para C ( n , 3 , 2 )norte C(norte,3,2)C(norte,3,2); Si esta fórmula es válida, intuitivamente eso significa que probablemente debería haber buenas formas algorítmicas de construir estos revestimientos, pero dado que la fórmula es conjeturada, está claro que nadie los conoce actualmente.

Para números de cobertura altos, es difícil encontrar buenas cubiertas que para , y el repositorio dará mejores soluciones que cualquier algoritmo eficiente conocido.C(norte,3,2)

Peter Shor
fuente
5

solsol=(V,mi)V={{un,si}:un,siArtículosunsi}mi={(s,t):s,tVEl |stEl |=1}(norte2)2norte-4 4

sol({UN,si},{si,C})miUNsiC(norte2)/ /21,5

DW
fuente
4

s=3t=2(norte2)/ /3(norte2)(norte2)

Si realmente está programando esto, entonces una forma de optimizar esto podría ser seleccionando primero algunas pruebas de números al azar, y luego haciendo la fuerza bruta en los pares no cubiertos por la prueba hasta ahora.


st(nortet)/ /(st)C(nortet)(st)Iniciar sesión((nortet))O(t(norte-ts-t)tIniciar sesión(norte))

sS[norte]tX[norte]Pr[XS]=(norte-ts-t)(nortes)C(nortet)Iniciar sesión((nortet))

Pr[X no pertenece a ninguno de ellos]=(1-(norte-ts-t)(nortes))C(nortet)Iniciar sesión((nortet))Exp(-C(norte-ts-t)(nortet)(nortes)(st)Iniciar sesión((nortet)))=Exp(-CIniciar sesión(nortet))1/ /(nortet).

O(t(norte-ts-t)tIniciar sesión(norte))t

Igor Shinkar
fuente
(nortet)/ /s