Возникает вопрос, на какие ошибки в программе / в сайте скорее всего наткнется пользователь. Представим такую ситуацию: у нас имеется 6 вопросов, для каждого из которых имеется 10 вариантов ответа. Допустим, мы опросили миллион пользователей, и каждый из них ответил уникально. Теперь представим, что в форме для заполнения ответами скрывается ошибка. Если ошибка обнаруживается только при определенной комбинации ответов на все 6 вопросов, то на неё натолкнется один лишь человек. Если же ошибка вылетает при наборе определенных ответов на какие-то 3 вопроса, то количество людей, обнаруживших ошибку возрастет до тысячи. Очевидно, что чем меньше элементов в комбинации, требуемой для ошибки, тем больше людей на неё наткнется. Соответственно, перед нами теперь стоит задача: если мы не можем обнаружить все ошибки, то давайте хотя бы найдем самые критичные, то есть те, на которые наткнется больше всего людей.
Таким образом мы должны сформировать тест-кейсы (и чем меньше, тем лучше), при переборе которых мы наткнемся на самые легкодоступные ошибки. Допустим, у нас имеется множество вопросов A, которое мы задаем количеством вариантов ответа на каждый из них: А = {2, 3, 5, 2, …}. Пусть n — количество вопросов, а 1≤m≤n — степень критичности ошибок, она же степень покрытия. Чем меньше значение m, тем критичнее ошибка. Задавая степень покрытия мы строим тестовый набор, который позволит обнаружить все ошибки, степень критичности которых меньше данного m. Если m = n, то поиск ошибок сводится к перебору всех вариантов. Чем меньше задаем степень, тем меньше тест-кейсов будет сформировано и тем меньше ошибок мы найдем.
Представим набор тестов в виде таблицы, где строчки соответствуют номеру теста, а столбцы — выбор ответов на вопросы. Для примера возьмем список вопросов A = {3, 3, 3, 3} и набор тестов:
| Номер теста | A1 | A2 | A3 | A4 |
|---|---|---|---|---|
| 1 | 1 | 1 | 1 | |
| 1 | 1 | 1 | 1 | |
| 1 | 1 | 1 | 1 | |
| 1 | 1 | 1 | 1 | |
| 1 | 1 | 1 | 1 | |
| 1 | 1 | 1 | 1 | |
| 1 | 1 | 1 | 1 |
Такой набор отлично подходит для покрытия степени m = 2, так как при выборе любых m столбцов в данном наборе будут перебраны всевозможные комбинации.
Задача эта достаточно широко освещена и с ней нередко сталкиваются, например, в Яндексе.
Три дня и три ночи я пытался придумать алгоритм, который будет работать наилучшим образом или хотя бы лучше, чем Jenny.
Каким же было мое удивление, когда я узнал, что схожий алгоритм уже существует и называется In Parameter Order, иначе говоря, алгоритм основанный на добавлении нового параметра.
Вот как можно классифицировать эти стратегии:
Алгоритм, о котором пойдет речь в моей статье — детерминированный параметризованный IPO с моей модификацией.
Стратегия IPO делится на две части: вертикальный и горизонтальный рост.
Пример работы алгоритма для ситуации A = {2, 2, 2}, m = 2.
Для сравнения, для такого примера Jenny построит пять тест-кейсов.
Пример работы алгоритма для ситуации A = {3, 3, 3}, m = 2.
Шаг первый. Формируются первые две колонки, добавляется третья.
Шаг второй. Добавляем четвертую колонку. Пустые места заполняем случайными числами.
ссылка на оригинал статьи http://habrahabr.ru/post/205546/
Добавить комментарий