Ищу подробное описание алгоритма Ежи-вильямс.. Если у кого есть инфа, выложите или ссыль киньте, ну а ежли есть и сама реализация, то буду безмерно благодарен.
Сделал все сам, так что ежли кому интересно или надо будет, то выкладываю сюда, полученный код и теорию.
Рассмотрим задачу для простой сети Четыре терминала с номерами 2, 3, 4, 5 должны быть соединены с центральным устройством, обозначенным номером I. Пусть значения, измеренные в единицах данных за секунду, интенсивностей графика, генерируемого в узлах, равны Y2=2,Y3=3,Y4=2,Y5=1. Стоимость установления связи между двумя узлами (включая центральный узел) задается в виде следующей симметричной матрицы стоимостей:
матрица C:
http://photo.qip.ru/users/sasha465/115558373/141744673/
Символом Сij обозначен элемент матрицы, стоящий на пересечении i строки и j столбца, представляющий стоимость установления связи между узлами i и j . В общем случае матрица С не обязательно должна быть симметричной.
ШАГ 0. Начальное вычисление всех параметров затрат tij= Cij – Ci1 для всех i,j(i!=1,i!=j) . где Cij элемент матрицы стоимостей C .
Для примера, приведенного на рис.1, матрица Т, элементами которой являются, имеет вид:
матрица T:
http://photo.qip.ru/users/sasha465/115558373/141744698/
Все параметры больше нуля исключаются из рассмотрения, так как очевидна выгодность соединения с центром, а не с этими узлами.
Для рассматриваемого примера первоначальный вектор 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.
Код написан на матлабе, надеюсь что всем кому надо будет понятно
Я 1000-кратно извиняюсь, нашел тут ошибку в реализации, а если говорить точнее, то ограничение учитывалось только на два соседних узла, тогда как в цепочку могло быть объединено более двух узлов, так что в последующих транзитных узлах ограничение превышало допустимое(в моем случае это 5).
Вот исправленный вариант, проверил на множестве примеров: