При тестировании n элементов, как покрыть все t-подмножества как можно меньшим количеством s-подмножеств?

10

Эта проблема возникла в результате тестирования программного обеспечения. Проблему немного сложно объяснить. Сначала я приведу пример, а затем постараюсь обобщить проблему.

Есть 10 предметов для тестирования, скажем, от A до J, и инструмент для тестирования, который может проверять 3 предмета одновременно. Порядок пунктов в инструменте тестирования не имеет значения. Конечно, для исчерпывающего тестирования нам понадобится комбинаций предметов.10C3

Проблема более сложная. Существует дополнительное условие, что после того, как пара предметов была протестирована вместе, чем та же пара не нуждается в повторном тестировании.

Например, однажды мы выполнили следующие три теста:

азбука

ADE

BDF

нам не нужно выполнять:

ABD

поскольку пара A, B была охвачена первым контрольным примером, A, D была покрыта вторым, а B, D - третьим.

Итак, проблема в том, какое минимальное количество тестовых случаев нам нужно, чтобы убедиться, что все пары протестированы?

В целом, если у нас есть n элементов, s можно тестировать одновременно, и нам нужно убедиться, что тестируются все возможные t-кортежи (такие, что s> t), какое минимальное количество тестовых случаев нам нужно в условия п, с и т?

И, наконец, какой будет хороший алгоритм для генерации необходимых тестовых случаев?

wookie919
источник
1
Случаи, когда тест является «оптимальным» (каждый кортеж тестируется ровно один раз), охватываются понятием « Проектирование блоков» . Эти совершенные тестовые возможности относительно немногочисленны, поэтому, мне кажется, нужна дополнительная эвристика. t
Хендрик Ян
Ваша тестовая парадигма неверна; может быть недостаточно проверить только пары. Некоторые ошибки могут возникать только в том случае, если три (или более) компонента действуют вместе в определенной комбинации.
Рафаэль
4
@Raphael, спасибо за намного лучший заголовок, но я совершенно не понимаю, как можно утверждать, что «ваша тестовая парадигма неверна» при нулевом понимании реальной проблемы или контекста.
wookie919
@ wookie919 Это потому, что вы не даете никакого контекста, но ставите общую проблему. Я просто заметил, что в общем случае вам может понадобиться проверить все возможные комбинации (в действии).
Рафаэль

Ответы:

11

Проекты блоков, которые вы хотите (для тестирования 3 вещей одновременно и охвата всех пар), называются тройными системами Штейнера . Существует тройная система Штейнера с тройками всякий раз, когда mod , и известны алгоритмы их построения. Посмотрите, например, этот вопрос MathOverflow (со ссылкой на рабочий код Sage!). Для других вы можете округлить до следующего mod и использовать модификацию этой тройной системы для чтобы покрыть все пары для .13(n2)n1 or 36nn1 or 36nn

Если вы хотите получить лучшую конструкцию для других , требуемое количество троек - это покрывающее число , которое задается этой записью в онлайн-энциклопедии целочисленных последовательностей. Это ссылка на репозиторий La Jolla Covering Repository, в котором есть репозиторий хороших покрытий. Онлайн энциклопедия целочисленных последовательностей дает предполагаемую формулу для ; если эта формула справедлива, то это интуитивно означает, что, вероятно, должны быть хорошие алгоритмические способы построения этих покрытий, но поскольку формула предположена, ясно, что в настоящее время их никто не знает.n C(n,3,2)C(n,3,2)

Для больших чисел покрытия найти хорошие покрытия труднее, чем для , и хранилище даст лучшие решения, чем любые известные эффективные алгоритмы.C(n,3,2)

Питер Шор
источник
5

Сформируйте неориентированный граф где каждая вершина является парой элементов и где есть ребро между двумя вершинами, если они совместно используют элемент. Другими словами, где и . Граф имеет вершин, и каждая вершина имеет ребер, падающих на него.GG=(V,E)V={{a,b}:a,bItemsab}E={(s,t):s,tV|st|=1}(n2)2n4

Тогда один подход будет найти соответствие максимальной в . Алгоритм Эдмондса можно использовать для нахождения такого максимального соответствия за полиномиальное время. Если вам повезет, это даст вам идеальное соответствие, и тогда у вас все хорошо. Каждое ребро в сопоставлении соответствует тестовому примеру . Поскольку каждая вершина инцидентна с одним ребром в идеальном сопоставлении, вы покрыли все пары, используя тестовых случая, что находится в пределах коэффициента оптимального. Если вы не получили идеального соответствия, добавьте еще несколько тестовых случаев, чтобы получить полное покрытие.G({A,B},{B,C})EABC(n2)/21.5

DW
источник
4

В случае и вам необходимо выполнить как минимум теста, поскольку существует пар, и каждый тест охватывает 3 пары. Это означает, что вы можете выполнять тривиальные задачи и выполнять тесты, и быть в 3 раза хуже оптимального.s=3t=2(n2)/3(n2)(n2)

Если вы на самом деле программируете это, то способ оптимизировать это может быть сначала выбрать несколько числовых тестов случайным образом, а затем применить грубую силу к парам, которые до сих пор не охватывались тестом.


Для общих и существует нижняя граница тестов . Для верхней границы я утверждаю, что этого достаточно, чтобы сделать тесты.st(nt)/(st)C(nt)(st)log((nt))O(t(ntst)tlog(n))

Давайте посмотрим, что произойдет, мы выберем тесты равномерно случайным образом. Если вы случайно выберете кортеж , то для фиксированного кортежа мы получим . Поэтому, если мы выберем тестов наугад, тоsS[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).

Следовательно, по объединенной границе после случайных проверок все кортежи будут охвачены.O(t(ntst)tlog(n))t

Игорь Шинкарь
источник
Большое спасибо за очень проницательный ответ, но я искал точный алгоритм, который бы генерировал ровно число нижних границ (если это вообще возможно) или что-то очень близкое к нижняя граница. (nt)/s
wookie919