Тестирование софта - статьи



Обход полного графа и его модификаций - часть 2


D(KM(KN))=M × D(KN) + D(KM).

Можно предположить, что при обходе графа, состоящего из нескольких слабо связанных (при помощи одной-двух дуг) частей, длина его обхода получается сложением длин обходов частей и количества проходов по связывающим дугам.

Оценка длины обхода графа KM KN снизу также равна количеству его дуг
E(KM × KN) = M × E(KN) + N × E(KM) = M × N × (N + M - 2).

Графdfsm, длинаdfsm, времяndfsm, длинаndfsm, времямин. длина
K3× K51 269265 62 8108 1 7956
K5× K51 804614 186 14024 5 13770
K7× K51 1694413 406 20348 5 19992
K3× K53 301095 68 8744 2 8576
K5× K53 898884 216 15104 4 14840
K7× K53 1890675 302 21888 5 21520
K3× K55 335337 50 9404 2 9240
K5× K55 1000234 164 16224 3 15950
K7× K55 2101501 365 23484 5 23100

Таблица 5. Длина и время обходов графов KM KN.

Теперь длина обхода с помощью dfsm уже не может быть определена с помощью аналогичной формулы.

Приведенные таблицы показывают, что на многих графах обходчик ndfsm работает эффективнее dfsm, и, если проверка детерминизма графа не является необходимым элементом тестирования, предпочтительнее использовать первый обходчик.

Можно заметить, что при увеличении количества дуг длина обхода с помощью dfsm составляет порядка 50% от произведения количества дуг на количество состояний, что означает практическую невозможность использования dfsm-обходчика в случае насыщенных графов с сотнями состояний.


Содержание  Назад  Вперед