Результаты сравнения методов решения задачи.
Прежде чем
сравнивать методы, необходимо договориться о критериях, на основе
которых такое сравнение проводится. Для данной предметной обла-
сти можно выделить следующие основные критерии: время работы,
трудозатраты (память, вычислительные ресурсы), число выполняемых
операций, объем переносимого кода, число обрабатываемых файлов,
отклонение по дате.
Для рассматриваемой в настоящей статье задачи из перечисленно-
го будем учитывать только критерии времени работы и число выпол-
няемых элементарных операций, как наиболее значимые. Поскольку
данные задачи хранятся в базе данных, а основная работа при поиске
решения связана с выбором данных из базы (выполнением реляцион-
ных операторов SELECT), то за эталонную операцию примем опера-
цию извлечения одной записи из базы данных по ключевым атрибутам
(индексированным полям).
В таком контексте критерии учета числа элементарных операций и
времени работы суть одно и то же, так как общее время выбора записей
из базы данных линейно зависит от числа выбираемых записей.
Для аналитического сравнения рассматриваемых методов восполь-
зуемся асимптотическими оценками вычислительной сложности алго-
ритмов типа
O
(
n
)
[4]. Основанием для использования такой оценки
является тот факт, что многие практические задачи имеют большую
размерность.
Приведем оценки для описанных методов. Оценку построим как
функцию одного переменного — объема входных данных. В данном
случае в качестве переменного целесообразно выбрать число требова-
ний и ввести две константы: среднее число функций, приходящихся
на одно требование, и среднее число исходных кодов, приходящих-
ся на одну функцию. Число функций, приходящихся на требование,
обозначим через
p
, а исходных кодов, приходящихся на функцию, —
через
q
. Порядки
p
и
q
гораздо ниже числа исходных кодов входных
данных задачи.
Оценка для жадного алгоритма Радо–Эдмондса.
Этот метод, по-
зволяющий легко решить задачу без учета пересечений, является вспо-
могательным для многих других методов, и его оценка также понадо-
бится. В рамках данного метода совершается обход всех требований
и для каждого требования отыскиваются все функции, среди которых
выбирается функция с наименьшей мощностью подмножества реали-
зующих ее исходных кодов. Если входные данные содержат
n
требова-
ний, для каждого требования определено в среднем
p
функций, то при
поиске решения придется рассмотреть
np
функций. Поскольку каждой
функции соответствует в среднем
q
исходных кодов, то окончательно
оценка примет вид:
ϕ
Р–Э
(
n
) =
npq
.
28 ISSN 0236-3933. Вестник МГТУ им. Н.Э. Баумана. Сер. “Приборостроение”. 2009. № 3
