Алгоритм на псевдокоде. Вычисление матрицы весов AW (формула 1)

Вычисление матрицы весов AW (формула 1).

DO (i = 0,...,n)

DO (j = i+1,...,n)

Aw_ij:= Aw_{i, j-1} + w_j

OD

OD

Алгоритм на псевдокоде

Вычисление матриц AP и AR (формула 2).

DO (i = 0,...,n - 1)

Ap_ij+1:= Aw_ij+1

Ar_ij+1:= i+1

OD

DO (h = 2,...,n)

DO (i = 0,...,n - h)

j:= i + h

m:= Ar _i,j-1

min: = Ap_i,m-1 + Ap_{m, j}

DO (k = m+1,...,AR_{i+1, j})

x: = Ap_i,k-1 + Ap_{k, j}

IF (x < min) m:=k, min:= x FI

OD

Ap _{i, j}:= min + Aw_{i, j}

Ar_{i, j}:=m

OD

OD

Алгоритм на псевдокоде

Создание дерева (L, R – границы массива вершин V,

Root – указатель на корень дерева)

IF (L < R)

k:= Ar_L,R

Добавить (Root, V_k)

Создание дерева (L, k-1)

Создание дерева (k, R)

FI

Для построения дерева необходимо вызвать процедуру создания дерева с параметрами L=0, R=n, Root=NIL.

14.3 Приближенные алгоритмы построения ДОП

Рассмотренный выше точный алгоритм имеет квадратичную трудоемкость. Однако при больших объемах деревьев такие алгоритмы становятся неэффективными. Известны быстрые алгоритмы, строящие почти оптимальные деревья. Рассмотрим два из них.

Первый алгоритм (А1) предлагает в качестве корня использовать вершину с наибольшим весом. Затем среди оставшихся вершин снова выбирается вершина с наибольшим весом и помещается в левое или правое поддерево в зависимости от ее значения, и т.д.