Практическая работа №3 синтез централизованных сетей методом прима

1. Цель работы

1.1 Изучение построения сетей с применением метода Прима.

2. Теоретическая часть

Алгоритм этого метода отличается от вышеописанного только способом выбора вершины-претендента, т. е. построением множества пометок t_ij(Шаг 0). Описываемый подход основан на идее выбора вершины, ближайшей к S₀ (центральному обрабатывающему устройству) или к вершине S_j, уже соединенной сетью с S₀.

Каждой вершине S_j приписывается пометка w_j, причем в начале расчетов w₀=0, w_j=- , т.е. в сеть входит только вершина S₀.

Шаг 0. Подсчитывается множество Т= {t_ij}

t_ij= C_ij- w_j для тех вершин, где w_j=0.

Конечные значения имеют только t_i0, равные стоимости C_i0(т. к. w₀=0), а все остальные равны . Дальше выполняются те же шаги, что и в методе Ежи- Вильямса.

Шаг 1. Определяется наименьшее значение t_ij, т. е. вершина S_i, ближайшая к S₀ (на 1 итерации).

{ t_ij}= t_kj

Рисунок 8 – Соединение вершины S_i, ближайшей к S₀

Шаг 2. Осуществляются проверки:

a_k>0

a_k<r_kj

a_k+a_j<r_j0

Шаг 3. Вычисляются значения:

a_k^н=0 a_j^н=a_j+a_k

r_kj^н=r_ij-a_k F^’=F⁰+C_kj

Полагается w_k=0

Переход к шагу 0 следующей итерации.

3. Пример решения задачи

Проиллюстрируем алгоритм, описанный выше, примером. Пусть w₀=0, w_j=- . С учетом данных таблицы 6 подсчитаем значения t_ij.

Шаг 0.

Т: t₁₀= C₁₀- w₀=1-0=1

t₂₀= C₂₀- w₀=4-0=4

t₃₀= C₃₀- w₀=3-0=3

t₁₂= C₁₂- w₂=2+ w₂= , t₁₃= ;

t₂₁= C₂₁- w₁=3+ w₁= , t₂₃= _;

t₃₁= C₃₁- w₁=1+ w₁= _; t₃₂= _.

_{Шаг 1. Определим} {tij}

{t_ij}= t₁₀=1

Рисунок 9 - Соединение узлов S₁ и S₀

Шаг 2. а₁=2>0; r₁₀=5; a₁<r₁₀.

Выполнение условий позволяет перейти к шагу 3.

Шаг 3. Вычислим новые значения:

а¹₁=0; a¹₀=-8+2=-6; r¹₁₀=5-2=3; F=C₁₀=1.

Положим w₁=0; t₁₀= и перейдем к шагу 0.

Шаг 0. Подсчитаем:

Т¹: t₂₁= C₂₁- w₁=3-0=3_;

t₃₁= C₃₁- w₁=1-0=1.

Шаг 1. {TUT¹}= t₃₁, т.е. S₃=>S₁.

Шаг 2. а₃=3>0; r₃₁=5>a₃; a₁¹+a₃=0+3 r₁₀=3.

Шаг 3. a₃¹=0; a₀¹¹=-6+3=-3.

r₁₀¹¹=3-3=0.

r₃₁¹=5-3=2.

F¹=F=C₃₁=1+1=2

Рисунок 10 - Соединение узлов S₁ и S₃

Положим w₃=0; t₃₁= _{и перейдем к шагу 0.}

Шаг 0.

Т²: t₂₃=С₂₃- w₃=1.

Шаг 1. Определим {TUT¹ UT²}= {t_ij}=t₂₃.

Шаг 2. а₂=3>0; r₂₃=5>a₂; r₃₁¹=2<a₂, следовательно соединение S₂=>S₃ невозможно, положим t₂₃= и перейдем к шагу 1.

Шаг 1. {TUT¹ UT²}= t₂₀=2.

Шаг 2. а₂=3>0; r₂₀=5>а₂,

Шаг 3. а₂¹=0; r₂₀¹=5-3=2; а₀¹¹¹=-3+3=0

F=2+4=6

Поскольку все а_i¹=0, задача решена.

Рисунок 11 – Оптимальная схема сети на основе метода Прима