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

[Янычар]

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

[Янычар]

Я 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