функции будут соединяться ребрами, и в итоге граф будет содержать
единственную компоненту связности, соответствующую найденному
решению.
Математическая постановка оптимизационной задачи.
Для вы-
ставленных требований
τ
k
∈
T
n
найти
Φ
n
-opt
∈ {
Φ
n
}
:
M
(
∪
ϕ
k
i
)
→
min
,
ϕ
k
i
∈
Φ
n
-opt
при условии
Φ
n
-opt
→
T
n
, или для выставленных требова-
ний
τ
k
∈
T
n
выполнить преобразование
D
:
G
D
−→
Φ
n
-opt
:
M
(
∪
ϕ
k
i
)
→
min
,
ϕ
k
i
∈
Φ
n
-opt
при условии
Φ
n
-opt
→
T
n
, где
τ
k
—
k
-е требование;
n
—
число требований (
τ
k
,
k
= 1
, n
)
;
k
— индекс требования;
ϕ
k
i
— функция
номер
i
, отвечающая требованию
τ
k
;
G
— множество всех функций;
Φ
n
— результирующее множество отобранных функций;
Φ
n
-opt
— ре-
зультирующее множество функций, принятое за оптимальное при
данном решении (при неточном методе — локально-оптимальное);
M
(
∪
ϕ
k
i
)
— мощность объединения функций, входящих в результи-
рующее множество
Φ
n
-opt
;
T
n
— подмножество множества всех тре-
бований мощности
n
, соответствующее выставленным требованиям;
→
— отношение порядка “реализовывать”. Под этим будем пони-
мать отношение на множествах функций и исходных кодов. Запись
Φ
n
→
T
n
означает, что мощности множеств
Φ
n
и
T
n
совпадают и для
∀
τ
k
∈
T
n
∃
ϕ
k
i
∈
Φ
n
:
ϕ
k
i
→
τ
k
.
Учет общих исходных кодов функций при решении задачи.
Ра-
нее уже говорилось о том, что подмножества исходных кодов, сопо-
ставленные функциям, могут пересекаться. Учет этого фактора в зна-
чительной степени влияет на сложность задачи. Рассмотрим вариант
задачи, который не учитывает пересечение подмножеств.
Пусть есть перечень из
n
требований
τ
, которые должны быть
удовлетворены полностью. По результатам обзора системы контроля
версий, которая хранит в себе все исходные коды, для каждого
τ
k
,
k
= 1
, n
, найден некий набор функций, которые реализуют
k
-е требо-
вание и не пересекаются между собой (рис. 6). В этом случае требуется
для каждого из
n
требований выбрать по одной функции, реализующей
это требование. Таким образом, получается результирующее множе-
ство функций. В этом виде задача является линейной и решается с
помощью жадного алгоритма Радо–Эдмондса [2]. Однако на практике
чаще встречаются задачи, в которых необходимо учитывать пересе-
чение подмножеств исходных кодов, сопоставленных функциям. На
рис. 7 схематично изображено наличие общих исходных кодов. Штри-
ховыми линиями соединены исходные коды, которые являются общи-
ми для различных функций. Фактически это одни и те же исходные
коды, единые физические файлы. В этом случае выбор функции для
i
-го требования влияет на выбор функций для остальных требований.
Согласно положениям о классах сложности задач постановка за-
дачи, не учитывающая пересечение подмножеств исходных кодов, ре-
ализующих функции, относится к классу сложности P. Постановка
26 ISSN 0236-3933. Вестник МГТУ им. Н.Э. Баумана. Сер. “Приборостроение”. 2009. № 3
