Сделал все сам, так что ежли кому интересно или надо будет, то выкладываю сюда, полученный код и теорию.
Рассмотрим задачу для простой сети Четыре терминала с номерами 2, 3, 4, 5 должны быть соединены с центральным устройством, обозначенным номером I. Пусть значения, измеренные в единицах данных за секунду, интенсивностей графика, генерируемого в узлах, равны Y
2=2,Y
3=3,Y
4=2,Y
5=1. Стоимость установления связи между двумя узлами (включая центральный узел) задается в виде следующей симметричной матрицы стоимостей:
матрица C:
Символом С
ij обозначен элемент матрицы, стоящий на пересечении i строки и j столбца, представляющий стоимость установления связи между узлами i и j . В общем случае матрица С не обязательно должна быть симметричной.
ШАГ 0. Начальное вычисление всех параметров затрат t
ij= C
ij – C
i1 для всех i,j(i!=1,i!=j) . где C
ij элемент матрицы стоимостей C .
Для примера, приведенного на рис.1, матрица Т, элементами которой являются, имеет вид:
матрица T:
Все параметры больше нуля исключаются из рассмотрения, так как очевидна выгодность соединения с центром, а не с этими узлами.
Для рассматриваемого примера первоначальный вектор Y интенсивностей потоков сообщений, выходящих из узлов, имеет вид
Y= (Y
2, Y
3, Y
4, Y
5)=(2,3,2,1).
ШАГ I. Выбрать минимальное t
ij, и рассмотреть соединение узла i с узлом j.
Для нашего примера минимальным является t
53 = -5 . Следовательно, проверяется возможность соединения узла 5 c узлом 3. Новое значение интенсивности потока через узел 3 равняется Y
3’ = Y
5 + Y
3 = 4 , что меньше введенного ограничения (максимально допустимое значение интенсивности потока через узел <=5).
ШАГ 3. Добавить линию i -- j . С учетом этой линии изменить исходные условия (вид матрицы Т, вектор интенсивностей потоков через узлы) и вернуться к шагу I.
Для рассматриваемого примера в силу того, что узел 5 подключен к узлу 3, вектор интенсивностей потоков через узлы примет вид:
Y’ = (Y
2’, Y
3’ ,Y
4’ ,Y
5’) = (2,4,2,1).
В матрице Т все элементы t
51 ,t
52 ,t
53 ,t
54 ,t
35 исключаются из рассмотрения, ибо включение в сеть линии с соответствующими индексами привело бы к образованию петли c включенной в сеть линией 5-3.
В соответствии с шагом I далее рассматривается соединение 4-3, для которого параметр t43 = -2. Однако, если узел 4 соединить с узлом 3 (шаг 2), то новый поток Y
3’’ = 4 + 2 = 6 , что не удовлетворяет ограничению. Следовательно, исключаем из рассмотрения элемент 4-3 и переходим к шагу I.
Теперь минимальным элементом является t
42 = -1. Ограничение в этом случае удовлетворяется, ибо
Y
2’’= Y
2’ + Y
4’ = 2+2 = 4. Узел 4 может быть соединен с узлом 2, а в матрице Т вычеркиваются элементы t
41 ,t
42 ,t
45 ,t
24.
Продолжая этот процесс, получим окончательную схему соединений (рис.4.), совпадающую с оптимальным решением. На рис.4 числа в скобках показывают порядок подсоединения. Стоимость сети L=15.
Код написан на матлабе, надеюсь что всем кому надо будет понятно
Код
clc;
%стоимости установления связи между узлами
N=input('введите число узлов сети N=');
C=rand(N-1, N);
C=ceil(C*10);
R=5;
for i=1:N-1
j=i+1;
C(i,j)=0;
end;
C
% генерируем вектор интенсивностей
Y=rand(1,N-1);
Y=ceil(Y*5)
% Y=[2,3,2,1]
% формируем T - матрицу затрат переходов
T=zeros(N-1,N);
for i=1:N-1
for j=1:N
if (i+1)~=j
T(i,j)=C(i,j)-C(i,1);
end;
end;
end;
T
M=zeros(N-1,N);
l=0;
temp=0;
while(l<N-1)
[minEl,masIndx]=min(T);
[mink,i]=min(minEl);
j=i
i=masIndx(i)
if(mink<0)
Y(i)
Y(j-1)
if( (Y(i)+Y(j-1))<=5 && j~=temp)
l=l+1;
Y(j-1)=Y(i)+Y(j-1);
M(i,j)=1
T(i,:)=10000;
temp=i
else
T(i,j)=10000;
end;
else
T(i,:)=10000;
M(i,1)=1;
l=l+1;
end;
end;
'матрица переходов'
M