де T-множини усіх тестів (Шляхів графу), - результуюча Тестовий набор,
- покриття графу G, что досягається набором Шляхів R,
- покриття графу G, что досягається набором Шляхів T.
такого что є розвязка задачі оптімізації
Тестовий набор будується з використаних жадібного алгоритму.
Жадібній алгоритм дозволяє отріматі оптімальне решение задачі путем Здійснення ряду віборів. У Кожній точці Прийняття решение в алгорітмі робиться вибір, Який в Сейчас віглядає Найкращим.
У запісі алгоритмом Використовують наступні Умовні позначення:
| S | - Потужність множини S
- довжина тесту t, яка вімірюється у кількості тестових вплівів
{} - Порожня множини
<>- Порожній упорядкованій список
Фіксуємо обмеження довжина тестів M, Яке є параметром даного алгоритму. Вважаємо множини непокритий тестових СИТУАЦІЙ C:=повний набор доступних транзакцій, безліч доступних тестів T:=повний набор раніше побудованіх тестів, а Тестовий набор R :=<>.
Для шкірного тесту t з T обчіслюємо Cov (t):=безліч тестових СИТУАЦІЙ з C, что покріваються ім. Если Cov (t)={}, то відаляємо t з T.
procedure ПОБУДОВА_ТЕСТОВОГО НАБОРУ ( M : максимальна довжина кроків тесту, P : вага допустимого перевіщення максімальної довжина на возбудить уголовное покриття); begin
оглушаємо КРАЩИЙ
for шкірного тесту з множини тестів Т
if , а, то тест кращий
if І, однак то тест кращий
if , то тест кращий
if , то тест кращий
if , І, а то тест кращий. Додаємо знайдення кращий тест у набор R. Відаляємо Із безлічі непокритий сітуації З ВСІ елєменти множини.
end
end;
Перше правило - формула (2.10) гарантує, что в Першу Черга ВСІ Можливі Тестові сітуації будут покріватіся тестами з Довжину, что НЕ перевіщує максимальна.
&& (2.10)
Друге правило - формула (2.11) вібірає тести з максимально можливий (в межах обмеження довжина) Тестовий покриття - у більшості віпадків ця еврістіка дозволяє Зменшити сумарная Довжину тестів в наборі за рахунок Зменшення їх кількості.
&& && (2.11)
Трете І чверті правила - формули (2.12) та (2.13) відповідно, віддають перевага тестам, что поліпшують покриття або Довжину и НЕ погіршує притому іншу з ціх двох характеристик.
if && (2.12)
if && (2.13)
Згідно з п ятим правилом - формула (2.14) з двох тестів, что перевіщують максимальну Довжину, один краще Іншого, ЯКЩО Збільшення Довжина компенсується (з урахуванням вагового параметра P ) збільшенням покриття.
&& && (2.14)
Оскількі алгоритм еврістічній, и в ньом вікорістовується перебір по неупорядкованій множіні, в загально випадка результати его РОБОТИ НЕ детерміновані: за різніх запусках на одних и тихий же Даних можлива генерація різніх тестових наборів, а проти в більшості віпадків побудовані таким чином набори мают однакові метрики.
Для налаштування алгоритму Використовують Параметри M и P.: задає максимальну Довжину тестів набору, что генерується, перевіщення...
