Просматриваются вершины графа G, начиная с основной s, в порядке подчинения; для каждой из вершин Sje{S\s4} определяются все пути, ведущие в s{ из sit и вес каждого пути (под весом пути Рі понимается сумма весов принадлежащих ему вершин, не включая st). Из дуг, заходящих в s{, выбирается дуга, принадлежащая пути с максимальным весом, остальные исключаются.

Возможно ненормальное завершение работы алгоритма, когда множество S стало пустым, а выигрыш в памяти не достиг величины Lmax-L, значит, программа с полученной структурой перекрытия не поместится в заданный объем памяти L.

Построение структуры перекрытия класса «дерево ветвей» производится (как и при решении первой задачи) путем преобразования графа в дерево.

В предлагаемом алгоритме DBD1 для оценки структуры используется ожидаемая частота вызовов сегментов, которая трактуется как уровень подчинения сегмента: считается, что реже вызываются те сегменты, которые ближе к основному сегменту st в графе G = (S, V).

Алгоритм DBD2 дает более точное решение, чем алгоритм DBD1. В этом алгоритме для оценки структуры перекрытия используется число загрузок сегментов, определяемое по последовательности вызовов сегментов К

Вначале с помощью алгоритма DBM решается первая задача и строится структура перекрытия с минимальными требованиями на память. По последовательности вызовов сегментов К определяется число загрузок z< для каждого сегмента st и цена структуры перекрытия Z = гі Затем предпринимаются попытки, не выходя за пределы L, уменьшить цену структуры перекрытия за счет исключения наиболее дорогостоящих перекрытий сегментов.

Выбирается сегмент s.eS с максимальным zt; если таких сегментов несколько, то выбирается сегмент с максимальным номером (при построении структуры перекрытия с минимальными требованиями на память сегменты s; из S упорядочиваются по уровню подчинения). По последовательности вызовов сегментов К отыскивается цикл минимальной длины, включающий st. Множество сегментов цикла делится на подмножества, каждое из которых включает несовместимые сегменты, соответствующие вершинам одного пути графа. Предпринимаются попытки последовательным расположением сегментов исключить перекрытие сначала всех, а затем возможно большей части подмножеств {Sj}i. Удовлетворяется та попытка, при которой требования на память программы с новой структурой не превышают L. Производится соответствующее преобразование структуры перекрытия: для каждого сегмента цикла определяется новый сегментпредшественник и новое значение zt. Если ни одна попытка успеха не имела, то сегменты цикла заносятся в список Q. Затем из множества (S\Q), если оно не пустое, выбирается s{ с максимальным Zi и повторяются описанные действия по улучшению структуры перекрытия. Когда множество (S\Q) становится пустым, работа алгоритма заканчивается.