Алгоритм Ежи-вильямс |
Алгоритм Ежи-вильямс |
Янычар |
17.01.2011 18:02
Сообщение
#1
|
Пионер Группа: Пользователи Сообщений: 115 Пол: Мужской Реальное имя: Александр Репутация: 1 |
Ищу подробное описание алгоритма Ежи-вильямс.. Если у кого есть инфа, выложите или ссыль киньте, ну а ежли есть и сама реализация, то буду безмерно благодарен.
|
Янычар |
18.01.2011 17:21
Сообщение
#2
|
Пионер Группа: Пользователи Сообщений: 115 Пол: Мужской Реальное имя: Александр Репутация: 1 |
Сделал все сам, так что ежли кому интересно или надо будет, то выкладываю сюда, полученный код и теорию.
Рассмотрим задачу для простой сети Четыре терминала с номерами 2, 3, 4, 5 должны быть соединены с центральным устройством, обозначенным номером I. Пусть значения, измеренные в единицах данных за секунду, интенсивностей графика, генерируемого в узлах, равны Y2=2,Y3=3,Y4=2,Y5=1. Стоимость установления связи между двумя узлами (включая центральный узел) задается в виде следующей симметричной матрицы стоимостей: матрица C: Символом Сij обозначен элемент матрицы, стоящий на пересечении i строки и j столбца, представляющий стоимость установления связи между узлами i и j . В общем случае матрица С не обязательно должна быть симметричной. ШАГ 0. Начальное вычисление всех параметров затрат tij= Cij – Ci1 для всех i,j(i!=1,i!=j) . где Cij элемент матрицы стоимостей C . Для примера, приведенного на рис.1, матрица Т, элементами которой являются, имеет вид: матрица T: Все параметры больше нуля исключаются из рассмотрения, так как очевидна выгодность соединения с центром, а не с этими узлами. Для рассматриваемого примера первоначальный вектор Y интенсивностей потоков сообщений, выходящих из узлов, имеет вид Y= (Y2, Y3, Y4, Y5)=(2,3,2,1). ШАГ I. Выбрать минимальное tij, и рассмотреть соединение узла i с узлом j. Для нашего примера минимальным является t53 = -5 . Следовательно, проверяется возможность соединения узла 5 c узлом 3. Новое значение интенсивности потока через узел 3 равняется Y3’ = Y5 + Y3 = 4 , что меньше введенного ограничения (максимально допустимое значение интенсивности потока через узел <=5). ШАГ 3. Добавить линию i -- j . С учетом этой линии изменить исходные условия (вид матрицы Т, вектор интенсивностей потоков через узлы) и вернуться к шагу I. Для рассматриваемого примера в силу того, что узел 5 подключен к узлу 3, вектор интенсивностей потоков через узлы примет вид: Y’ = (Y2’, Y3’ ,Y4’ ,Y5’) = (2,4,2,1). В матрице Т все элементы t51 ,t52 ,t53 ,t54 ,t35 исключаются из рассмотрения, ибо включение в сеть линии с соответствующими индексами привело бы к образованию петли c включенной в сеть линией 5-3. В соответствии с шагом I далее рассматривается соединение 4-3, для которого параметр t43 = -2. Однако, если узел 4 соединить с узлом 3 (шаг 2), то новый поток Y3’’ = 4 + 2 = 6 , что не удовлетворяет ограничению. Следовательно, исключаем из рассмотрения элемент 4-3 и переходим к шагу I. Теперь минимальным элементом является t42 = -1. Ограничение в этом случае удовлетворяется, ибо Y2’’= Y2’ + Y4’ = 2+2 = 4. Узел 4 может быть соединен с узлом 2, а в матрице Т вычеркиваются элементы t41 ,t42 ,t45 ,t24. Продолжая этот процесс, получим окончательную схему соединений (рис.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 |
Янычар |
6.02.2011 21:54
Сообщение
#3
|
Пионер Группа: Пользователи Сообщений: 115 Пол: Мужской Реальное имя: Александр Репутация: 1 |
Я 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 |
Текстовая версия | 1.11.2024 0:24 |