С.В. Вельц
10
1
k
V X
1
k+ k+1
HG HG V ,E
запоминаем созданный слой
1
k k +
end while
После того, как иерархическое представление построено, для
оптимизации используется жадный алгоритм. Алгоритм движется от
меньших слоев (верхних) к большим (нижним), пока не достигнет
начального графа. Для каждого слоя используется жадная стратегия
выбора вершин с учетом их весов. При этом используется следующая
эвристика: в выборе участвуют только вершины, чьи родители были
выбраны в предыдущем (вышележащем) слое. Данный алгоритм
показан в листинге 3.
Алгоритм 3.
Иерархический алгоритм поиска оптимальной
стратегии.
Вход
:
G= V,E
,
P M
(для А) или
P S
(для Б),
R
Выход
:
A
– множество узлов
HG buildHierarchicalGraph G
Строим иерархическое
представление графа
0
k
Находим начальный уровень в иерархии
while
.
.
.
2R
k < HG numberOfLayers H G k numberOfNodes >
do
1
k k +
end while
disabledNodes
Для каждого из слоев решаем задачу
максимизации
A
for
0
i
k,
do
k
A maximize HG k ,P M P S ,R,disabledNodes,weight
if
k=0
then
break
end if
1
:
k
disabledNodes v V parent v A
end for
return
A
Результаты вычислительного эксперимента.
Вычислительный
эксперимент состоял из двух частей. В первой части было проведено
