Алгоритм Ежи-вильямс Опции

[Янычар]

Ищу подробное описание алгоритма Ежи-вильямс.. Если у кого есть инфа, выложите или ссыль киньте, ну а ежли есть и сама реализация, то буду безмерно благодарен.

[Янычар]

Сделал все сам, так что ежли кому интересно или надо будет, то выкладываю сюда, полученный код и теорию.

Рассмотрим задачу для простой сети Четыре терминала с номерами 2, 3, 4, 5 должны быть соединены с центральным устройством, обозначенным номером I. Пусть значения, измеренные в единицах данных за секунду, интенсивностей графика, генерируемого в узлах, равны Y₂=2,Y₃=3,Y₄=2,Y₅=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₂, Y₃, Y₄, Y₅)=(2,3,2,1).
ШАГ I. Выбрать минимальное t_ij, и рассмотреть соединение узла i с узлом j.
Для нашего примера минимальным является t₅₃ = -5 . Следовательно, проверяется возможность соединения узла 5 c узлом 3. Новое значение интенсивности потока через узел 3 равняется Y₃’ = Y₅ + Y₃ = 4 , что меньше введенного ограничения (максимально допустимое значение интенсивности потока через узел <=5).
ШАГ 3. Добавить линию i -- j . С учетом этой линии изменить исходные условия (вид матрицы Т, вектор интенсивностей потоков через узлы) и вернуться к шагу I.
Для рассматриваемого примера в силу того, что узел 5 подключен к узлу 3, вектор интенсивностей потоков через узлы примет вид:
Y’ = (Y₂’, Y₃’ ,Y₄’ ,Y₅’) = (2,4,2,1).
В матрице Т все элементы t₅₁ ,t₅₂ ,t₅₃ ,t₅₄ ,t₃₅ исключаются из рассмотрения, ибо включение в сеть линии с соответствующими индексами привело бы к образованию петли c включенной в сеть линией 5-3.
В соответствии с шагом I далее рассматривается соединение 4-3, для которого параметр t43 = -2. Однако, если узел 4 соединить с узлом 3 (шаг 2), то новый поток Y₃’’ = 4 + 2 = 6 , что не удовлетворяет ограничению. Следовательно, исключаем из рассмотрения элемент 4-3 и переходим к шагу I.
Теперь минимальным элементом является t₄₂ = -1. Ограничение в этом случае удовлетворяется, ибо
Y₂’’= Y₂’ + Y₄’ = 2+2 = 4. Узел 4 может быть соединен с узлом 2, а в матрице Т вычеркиваются элементы t₄₁ ,t₄₂ ,t₄₅ ,t₂₄.
Продолжая этот процесс, получим окончательную схему соединений (рис.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

Сообщение отредактировано: Янычар - 18.01.2011 17:31

[Янычар]

Я 1000-кратно извиняюсь, нашел тут ошибку в реализации, а если говорить точнее, то ограничение учитывалось только на два соседних узла, тогда как в цепочку могло быть объединено более двух узлов, так что в последующих транзитных узлах ограничение превышало допустимое(в моем случае это 5).
Вот исправленный вариант, проверил на множестве примеров:

Код

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*4)
% формируем 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);
M(:,1)=1;  
l=0;    
temp=0;
S=0;
tempj=0;
k=0;
jl=0;
CopyY=Y;
mask=0;
      while(l<N-1)
         [minEl,masIndx]=min(T);
         [mink,i]=min(minEl);
         j=i;
         i=masIndx(i)
         jl=j-1
         sum=Y(i)
         k=0;
         mask=0;
         if(mink<0)
             while(jl~=0)
                 if((sum+Y(jl))>R)
                     mask=1;                    
                 else
                     CopyY(jl)=sum+Y(jl);
                 end;
                
                Lk=M(jl,:)
                [Z, k] = max(Lk)                
                jl=k-1  
                
                                            
             end;
             if( mask~=1 )                              
                 l=l+1;    
                 Y=CopyY;
%                  Y(j-1)=Y(i)+Y(j-1)
                 M(i,1)=0;
                 M(i,j)=1
                 T(i,:)=10000;
                 T(j-1,i+1)=10000; % исключаем из рассмотрения чтобы не возникало петли
                 temp=i;
                 tempj=j;
                 S=S+C(i,j);                
             else
                     T(i,j)=10000;
                     end;
                    
         else
             S=S+C(i,1);
             T(i,:)=10000;
             M(i,1)=1;
             l=l+1;
            
         end;
          
               end;    
               'матрица переходов'
     M
               'стоимость сети'
     S

Сообщение отредактировано: Янычар - 6.02.2011 21:56