Эта проблема возникла в результате тестирования программного обеспечения. Проблему немного сложно объяснить. Сначала я приведу пример, а затем постараюсь обобщить проблему.
Есть 10 предметов для тестирования, скажем, от A до J, и инструмент для тестирования, который может проверять 3 предмета одновременно. Порядок пунктов в инструменте тестирования не имеет значения. Конечно, для исчерпывающего тестирования нам понадобится комбинаций предметов.
Проблема более сложная. Существует дополнительное условие, что после того, как пара предметов была протестирована вместе, чем та же пара не нуждается в повторном тестировании.
Например, однажды мы выполнили следующие три теста:
азбука
ADE
BDF
нам не нужно выполнять:
ABD
поскольку пара A, B была охвачена первым контрольным примером, A, D была покрыта вторым, а B, D - третьим.
Итак, проблема в том, какое минимальное количество тестовых случаев нам нужно, чтобы убедиться, что все пары протестированы?
В целом, если у нас есть n элементов, s можно тестировать одновременно, и нам нужно убедиться, что тестируются все возможные t-кортежи (такие, что s> t), какое минимальное количество тестовых случаев нам нужно в условия п, с и т?
И, наконец, какой будет хороший алгоритм для генерации необходимых тестовых случаев?
источник
Ответы:
Проекты блоков, которые вы хотите (для тестирования 3 вещей одновременно и охвата всех пар), называются тройными системами Штейнера . Существует тройная система Штейнера с тройками всякий раз, когда mod , и известны алгоритмы их построения. Посмотрите, например, этот вопрос MathOverflow (со ссылкой на рабочий код Sage!). Для других вы можете округлить до следующего mod и использовать модификацию этой тройной системы для чтобы покрыть все пары для .13(n2) n≡1 or 3 6 n n′≡1 or 3 6 n′ n
Если вы хотите получить лучшую конструкцию для других , требуемое количество троек - это покрывающее число , которое задается этой записью в онлайн-энциклопедии целочисленных последовательностей. Это ссылка на репозиторий La Jolla Covering Repository, в котором есть репозиторий хороших покрытий. Онлайн энциклопедия целочисленных последовательностей дает предполагаемую формулу для ; если эта формула справедлива, то это интуитивно означает, что, вероятно, должны быть хорошие алгоритмические способы построения этих покрытий, но поскольку формула предположена, ясно, что в настоящее время их никто не знает.n C(n,3,2) C(n,3,2)
Для больших чисел покрытия найти хорошие покрытия труднее, чем для , и хранилище даст лучшие решения, чем любые известные эффективные алгоритмы.C(n,3,2)
источник
Сформируйте неориентированный граф где каждая вершина является парой элементов и где есть ребро между двумя вершинами, если они совместно используют элемент. Другими словами, где и . Граф имеет вершин, и каждая вершина имеет ребер, падающих на него.G G=(V,E) V={{a,b}:a,b∈Items∧a≠b} E={(s,t):s,t∈V∧|s∩t|=1} (n2) 2n−4
Тогда один подход будет найти соответствие максимальной в . Алгоритм Эдмондса можно использовать для нахождения такого максимального соответствия за полиномиальное время. Если вам повезет, это даст вам идеальное соответствие, и тогда у вас все хорошо. Каждое ребро в сопоставлении соответствует тестовому примеру . Поскольку каждая вершина инцидентна с одним ребром в идеальном сопоставлении, вы покрыли все пары, используя тестовых случая, что находится в пределах коэффициента оптимального. Если вы не получили идеального соответствия, добавьте еще несколько тестовых случаев, чтобы получить полное покрытие.G ({A,B},{B,C})∈E ABC (n2)/2 1.5
источник
В случае и вам необходимо выполнить как минимум теста, поскольку существует пар, и каждый тест охватывает 3 пары. Это означает, что вы можете выполнять тривиальные задачи и выполнять тесты, и быть в 3 раза хуже оптимального.s=3 t=2 (n2)/3 (n2) (n2)
Если вы на самом деле программируете это, то способ оптимизировать это может быть сначала выбрать несколько числовых тестов случайным образом, а затем применить грубую силу к парам, которые до сих пор не охватывались тестом.
Для общих и существует нижняя граница тестов . Для верхней границы я утверждаю, что этого достаточно, чтобы сделать тесты.s t (nt)/(st) C⋅(nt)(st)⋅log((nt))≤O(t⋅(n−ts−t)tlog(n))
Давайте посмотрим, что произойдет, мы выберем тесты равномерно случайным образом. Если вы случайно выберете кортеж , то для фиксированного кортежа мы получим . Поэтому, если мы выберем тестов наугад, тоs S⊆[n] t X⊆[n] Pr[X⊂S]=(n−ts−t)(ns) C⋅(nt)⋅log((nt))
Следовательно, по объединенной границе после случайных проверок все кортежи будут охвачены.O(t⋅(n−ts−t)tlog(n)) t
источник