Расчет кратчайшей связывающей сети заданной конфигурации

ЛЕКЦИИ 7-8 РАСЧЕТ КРАТЧАЙШЕЙ СВЯЗЫВАЮЩЕЙ СЕТИ ЗАДАННОЙ КОНФИГУРАЦИИ 5.1 Постановка задачи При проектировании вычислительных сетей разработчику необходимо найти такой вариант системы, который удовлетворял бы широкому спектру требований по критериям: стоимости, надежности, времени доставки сообщений, живучести и т.д. Реальные методы проектирования ориентируются на итеративную 'процедуру, при которой производится последовательное улучшение базовой конфигурации ВС по различным критериям до тех пор, пока не будут достигнуты требуемые характеристики. Одной из задач, возникающих при итеративной процедуре проектирования, является размещение конфигурации ВС, выбранной, например, по критерию надежности в пространстве, взвешенном; например, стоимостью каналов связи. aj sij ai A Рассматриваемая задача может быть сформулирована следующим образом. Пусть задана конфигурация S, (см. рис. 5.1) содержащая множество узлов 𝑎𝑖 ∈A, ̅̅̅̅̅ i = 1, 𝑁, каждая пара которых соединена связями, число их равно 𝑠𝑖𝑗 . b m b М Рис. 5.1 Конфигурация S и взвешенное пространство М ̅̅̅̅̅ Узлы 𝑎𝑖 могут распределяться по точкам 𝑏𝛼 , 𝛼 = 1, 𝑁, размешенным во взвешенном пространстве М на расстоянии 𝑚𝛼𝛽 друг от друга. Требуется определить, при каком распределении узлов {𝑎𝑖 } по точкам {𝑏𝛼 } обеспечивается минимальная суммарная длина взвешенных расстояний 𝑚𝛼𝛽 , соответствующих конфигурации S. Целевая функция сформулированной задачи: 𝑁 𝑁 𝑁 𝑄 = min𝑢,𝑡 ∑𝑁 𝑖=1 ∑𝑗=1 𝑠𝑖𝑗 ∑𝛼=1 ∑𝛽=1 𝑚𝛼𝛽 𝑢𝛼𝑖 𝑡𝛽𝑗 (5.1) где 𝑢𝑖𝛼 , 𝑡𝛽𝑗 - булевые неизвестные, удовлетворяющие соотношениям 𝑢𝛼𝑖 = { 1, если 𝑎𝑖 ∈ 𝑏𝛼 } 0, если 𝑎𝑖 ∉ 𝑏𝛼 1, если 𝑎𝑗 ∈ 𝑏𝛽 𝑡𝛽𝑗 = { } 0, если 𝑎𝑖 ∉ 𝑏𝛽 (5.2) Решение задачи должно удовлетворять условиям: каждый узел 𝑎𝑖 может быть размещен только в одной точке 𝑏𝛼 и каждой точке 𝑏𝛼 должен соответствовать один узел 𝑎𝑖 , что можно записать в виде ограничений: 𝑎𝑖 ≠ 𝑎𝑗 ; 𝑏𝛼 ≠ 𝑏𝑗 ; 𝑁 𝑁 𝑁 ∑𝑁 𝑖=1 𝑢𝛼𝑖 = 1 ; ∑𝛼=1 𝑢𝛼𝑖 = 1; ∑𝑗=1 𝑡𝛽𝑗 = 1; ∑𝑖=1 𝑡𝛽𝑗 = 1. (5.3) Сформулированная задача относится к классу нелинейных задач с булевыми переменными, для решения которой при N < 50 можно использовать методы динамического программирования. Однако для ВС реальной размерности (N = 100 – 200) методы динамического программирования требуют больших затрат вычислительных ресурсов, что приводит к необходимости разрабатывать новые алгоритмы. 5.2 Алгоритм определения кратчайшей связывающей сети заданной конфигурации В излагаемом алгоритме последовательно задаются исходные распределения узлов {𝑎𝑖 } по точкам {𝑏𝛼 } и оценивается возможность улучшения размещения каждой пары узлов 𝑎𝑖 , 𝑎𝑗 по точкам 𝑏𝛼 , 𝑏𝛽 при их взаимной перестановке. Для варианта перестановки, обеспечивающего наибольшее уменьшение целевой функции 𝑄 , производится взаимное перемещение узла 𝑎𝑖 , в точку 𝑏𝛽 , а узла 𝑎𝑗 в точку 𝑏𝛼 . Каждый исходный вариант 𝜔 размещения корректируется путем последовательной оценки и перестановок узлов до тех пор, пока обеспечивается уменьшение целевой функции 𝑄, т.е., определяется размещение, обеспечивающее локальный оптимум 𝑄𝜔 . После корректировки ̅̅̅̅̅ всех исходных распределений из локальных оптимумов 𝑄𝜔 , 𝜔 = 1, 𝑁 выбирается решение с минимальным значением функции 𝑄0 , Для удобства алгоритмической реализации и на основании ограничений (5.3) в дальнейшем изложении используется запись определяемых неизвестных ̅̅̅̅̅ ‖𝑥𝑖𝛼 ‖ в виде списка {𝑦𝑖 }∗ , где 𝑦𝑖 = 𝛼 для i=1, 𝑁. Каждый исходный вариант 𝜔, ̅̅̅̅̅ (𝜔 = 1, 𝑁) распределения узлов {𝑎𝑖 } описывается списками {𝑦𝑖 }𝜔 , каждый из которых формируется по следующим рекуррентным соотношениям: 𝑦𝑖𝜔 = { (𝑖 + 𝜔 − 1) для 1 ≤ 𝑖 ≤ (𝑁 − 𝜔 + 1); } (𝑖 + 𝜔 − 𝑁 − 1) для 𝑖 > (𝑁 − 𝜔 + 1); (5.4) Используя список {𝑦𝑖 } , соотношение (5.1) запишем в виде: 𝑁 𝑄 = ∑𝑁 𝑖=1 ∑𝑗=1 𝑠𝑖𝑗 𝑚𝑦𝑖 𝑦𝑗 (5.5) 𝜔 Оценка 𝑄𝑖𝑗 возможного улучшения Q при перестановке узлов 𝑎𝑖 , и 𝑎𝑗 определяется выражением: 𝜔 𝑄𝑖𝑗 = − 𝐶𝑖0𝜔 − 𝐶𝑗0𝜔 + 𝐶𝑖𝑗П𝜔 + 𝐶𝑗𝑖П𝜔 , 𝑁 𝐶𝑖0𝜔 = ∑𝑁 𝑘=1 𝑠𝑖𝑘 𝑚𝑦𝑖 𝑦𝑘 + ∑𝑘=1 𝑠𝑘𝑖 𝑚𝑦𝑘 𝑦𝑖 где (5.6) (5.7) 𝐶𝑖0𝜔 - цена до перестановки узла 𝑎𝑖 ; (аналогично для 𝑎𝑗 , ) 𝑁 𝐶𝑖𝑗П𝜔 = ∑𝑁 𝑘=1 𝑠𝑖𝑘 𝑚𝑦𝑗 𝑦𝑘 + ∑𝑘=1 𝑠𝑘𝑖 𝑚𝑦𝑘 𝑦𝑗 + 𝑠𝑖𝑗 𝑚𝑦𝑖 𝑦𝑗 + 𝑠𝑗𝑖 𝑚𝑦𝑗 𝑦𝑖 (5.8) 𝐶𝑖𝑗П𝜔 - цена перестановки узла 𝑎𝑖 в точку, которую занимал узел 𝑎𝑗 С𝑗𝑖П𝜔 - цена перестановки узла 𝑎𝑗 в точку, которую занимал узел 𝑎𝑖 , определяемая по соотношению, аналогичному (5.8). Приведенные соотношения (5.4) - (5.8).позволяют записать последовательность решения задачи в виде совокупности следующих вычислительных блоков.(см. рис 5.2) ̅̅̅̅̅ ̅̅̅̅̅ 1. Ввод исходных данных: N; ‖𝑠𝑖𝑗 ‖, 𝑖, 𝑗 = 1, 𝑁; ‖𝑚𝛼𝛽 ‖; 𝛼𝛽, = 1, 𝑁; 𝜔 = 1, ∗ ̅̅̅̅̅ 𝑄0 = ∞; {𝑦𝑖 } = {0} (𝑖 = 1, 𝑁). 2. Формирование для варианта 𝜔 исходного списка {𝑦𝑖 }𝜔 по соотношению ̅̅̅̅̅ (5.4) для i = 1, 𝑁. ̅̅̅̅̅ 3. Расчет цен 𝐶𝑖0𝜔 для i = 1, 𝑁 по соотношению (5.7) и формирование 0𝜔 списка {𝐶𝑖 }. ̅̅̅̅̅ 4. Расчет цен 𝐶𝑖𝑗п𝜔 для i,j = 1, 𝑁 по соотношению (5.8) и формирование матрицы ‖𝐶𝑖𝑗п𝜔 ‖. 𝜔 5. Расчет оценки 𝑄𝑖𝑗 пo соотношению (5.6). 6. Расчет минимальной оценки min 𝑄 и фиксирование номеров i,j, которые соответствуют min 𝑄. 7. Проверка, если min 𝑄 < 0, то перейти к п. 8, если min 𝑄 ≥ 0, то перейти к п. 9. Приведенные соотношения (5.4) (5.8).позволяют записать последовательность решения задачи в виде совокупности следующих вычислительных блоков.(см. рис 5.2) 8. Корректировка исходного списка {𝑦𝑖 }𝜔 за счет ′ перестановок (𝑦𝑝𝜔 ) = 𝑦𝜐𝜔 ; (𝑦𝜐𝜔 )′ = 𝑦𝑝𝜔 ; переход а п.3. 9. Расчет 𝑄𝜔 по соотношению (5.5). 10. Если 𝑄𝜔 < 𝑄0 , то перейти к п. 11. Если 𝑄𝜔 ≥ 𝑄0 , то перейти к п. 12. 11. Корректировка оптимального значения целевой функции 𝑄0 =𝑄𝜔 и списка оптимального решения {𝑦𝑖 }∗ ={𝑦𝑖 }𝜔 . 12. Корректировка номера исходного варианта 𝜔 = 𝜔 + 1. 13. Если номера исходного варианта 𝜔 ≤ N, то перейти к п.2, иначе – к п. 14. 14. Вывод результата расчета оптимального значения целевой функции 𝑄0 и списка оптимального решения {𝑦𝑖 }∗ . Рис. 5.2 Алгоритм определение кратчайшей связывающей сети заданной конфигурации Из изложенной процедуры следует, что емкость требуемой памяти ОЗУ, используемой для проведения расчетов, в основном определяется матрицами S, M, 𝐶 п𝜔 размерностью NxN каждая и списками {𝑦𝑖 }∗ , {𝑦𝑖 }𝜔 , {𝐶𝑖0𝜔 } размерностью N. Данная эвристическая процедура обеспечивает автоматизацию генерации исходных вариантов и с помощью парных перестановок определяет локальный оптимум для каждого варианта, что предохраняет ее от зацикливания и обеспечивает оценку достаточно большого числа вариантов решений. Пример 5.1. Известно, что рассматриваемая ВС должна иметь конфигурацию S, представленную на рис. 5.3. Число элементов N = 10, конфигурация S может быть записана в виде матрицы конфигурации 22 11 33 10 10 55 44 6 6 7 9 9 8 Рис. 5.3. Пример конфигурации ВС 1. Расстояние между точками записываются в виде матрицы стоимости каналов М= 1 2 3 4 5 6 7 8 9 10 1 2 6 7 1 3 4 8 11 1 2 2 7 15 4 14 15 2 5 3 3 6 7 9 2 3 12 1 1 12 4 7 15 9 12 1 17 8 8 6 5 1 4 9 12 11 7 4 9 5 6 3 14 9 1 11 5 2 11 12 7 4 15 12 17 7 5 8 3 2 8 8 2 1 8 4 2 8 4 12 9 11 5 1 8 9 11 3 4 11 10 1 3 12 6 5 12 2 12 11 Начальное значение первого варианта 𝜔 = 1 целевой функции 𝑄о =0. {𝑦𝑖 }𝜔 = 2. Для 𝜔 = 1 по соотношению (5.4) исходный список (1,2.3,4,5,6,7,8,9,10}. 3. Цены до перестановки 𝐶𝑖0𝜔 определяются по соотношению (5.7) и для ненулевых значений можно записать: 𝐶101 = 𝑠12 𝑚12 + 𝑠16 𝑚16 + 𝑠21 𝑚21 + 𝑠61 𝑚61 = 2+3+2+3 = 10; 𝐶201 = 𝑠21 𝑚21 + 𝑠23 𝑚23 + 𝑠25 𝑚25 + 𝑠12 𝑚12 + 𝑠32 𝑚32 + 𝑠52 𝑚52 = =2+7+4+2+7+4 = 26; 𝐶301 = 𝑠32 𝑚32 + 𝑠34 𝑚34 + 𝑠36 𝑚36 + 𝑠3.10 𝑚3.10 + 𝑠23 𝑚23 + +𝑠43 𝑚43 + 𝑠63 𝑚63 + 𝑠10.3 𝑚10.3 = 7+9+3+12+7+9+3+12 = 62; Аналогично получаем 𝐶401 =52; 𝐶501 =8; 𝐶601 =34; 𝐶701 =40; 𝐶801 = 8; 𝐶901 = ; 36; 01 𝐶10 = 24. 4. Цены после перестановки 𝐶𝑖𝑗П𝜔 определяются по соотношению (5.8) и для ненулевых значений можно записать: П1 𝐶11 = 𝑠12 𝑚12 + 𝑠16 𝑚16 + 𝑠21 𝑚21 + 𝑠61 𝑚61 = 2+3+2+3= 10; П1 𝐶12 = 𝑠12 𝑚12 + 𝑠16 𝑚26 + 𝑠21 𝑚21 + 𝑠61 𝑚62 = 2+14+2+14= 32; П1 𝐶13 = 𝑠12 𝑚32 + 𝑠16 𝑚26 + 𝑠21 𝑚21 + 𝑠16 𝑚36 = 7+3+7+3= 20; Аналогично рассчитывают остальные значения, которые записаны в матрице цен для первой итерации: 1 𝐶 П1 = 2 3 4 5 6 7 8 9 10 1 10 32 20 32 30 34 40 8 34 10 2 18 26 30 56 14 34 46 26 42 36 3 26 78 62 64 78 78 48 72 66 62 4 20 44 42 52 18 16 58 18 8 28 5 4 8 14 30 8 28 30 4 12 6 6 40 30 20 48 24 34 38 26 46 48 7 36 21 20 50 42 24 40 24 22 34 8 22 12 2 16 18 22 6 8 8 22 9 30 62 32 52 44 36 32 28 36 52 10 12 14 24 18 4 6 24 2 2 24 𝜔 (5-6)’.Оценку возможного улучшения 𝑄𝑖𝑗 перестановки узлов вычисляют по соотношению (5.8): 𝜔=1 П1 П1 𝑄11 = − 𝐶101 − 𝐶101 + 𝐶11 + 𝐶11 = -10-10+10+10=0 min Q= 0; p = 1; 𝜐= 1 . 𝜔=1 П1 П1 (5-6)’’ 𝑄12 = − 𝐶101 − 𝐶201 + 𝐶12 + 𝐶21 = -10-26+32+18=14. Для компактности изложения представим в виде матрицы: 1 1 2 2 3 4 5 6 результаты 7 8 расчета 9 10 14 -26 -10 6 30 26 12 18 8 20 22 -12 4 22 4 42 -10 8 -16 -4 -20 6 4 -12 -22 16 -26 -28 -30 10 24 6 12 -22 -12 6 12 -4 -18 -22 -6 -8 -8 -6 3 𝐶 𝜔1 = промежуточные 4 5 6 7 8 9 10 из которой следует, что результаты расчета п. 5-6 являются: min Q= -31 ; p = 4; 𝜐= 10 . (7-8)’ В связи с тем, что min Q= -31<0, корректируем {𝑦𝑖 } {𝑦𝑖 }𝜔 ={3,2,1,10,5,6,7,8,9,4} . и получаем Для последующих итераций варианта 𝜔 имеем {𝑦𝑖 }′′ ={3,2,1,10,5, 6,7,8,9,4}; {𝑦𝑖 }′′′ ={8,2,1,10,5, 6,7,3,9,4}. 9. Целевая функция варианта 𝜔 =1; 𝑄𝜔 =76. 10 – 14. Контролируем окончание вычислений, что позволяет определить 𝑄0 = 50, {𝑦𝑖 }∗ = {10,7,6,8,9,1,3,2,5,4} Все промежуточные результаты, иллюстрирующие основные промежуточные значения для всех итераций и всех вариантов, приведены в табл. 5.1. Рассмотренный пример иллюстрирует, что процедура позволяет выбирать эффективные топологии для реальных объектов. Таблица 5.1 Вари Итера ант𝝎 ция 1 1 2 3 1 2 2 3 3 1 2 1 4 2 3 4 1 5 2 3 4 1 6 2 3 4 1 2 7 3 4 5 6 1 8 2 3 4 1 𝒚𝟏 1 3 8 2 2 5 3 3 3 3 9 9 5 5 10 10 6 6 6 9 7 10 10 10 10 10 8 5 5 9 9 𝒚𝟐 2 2 2 3 3 3 9 9 5 8 8 3 7 7 7 7 7 7 7 7 10 7 7 7 2 2 2 2 2 2 10 𝒚𝟑 3 1 1 4 1 1 5 8 6 6 6 6 6 6 6 6 8 8 9 6 9 9 8 8 8 1 10 10 1 1 1 𝒚𝟒 10 10 10 5 5 2 6 6 7 7 7 7 8 8 8 8 9 9 8 8 8 8 9 5 5 5 1 1 10 10 2 𝒚𝟓 5 5 5 6 6 6 7 7 8 5 5 5 9 9 9 9 10 10 10 10 1 1 1 1 1 8 9 9 9 5 7 𝒚𝟔 6 6 6 10 10 10 8 5 9 9 3 3 10 10 5 1 1 3 3 3 2 2 2 2 7 7 3 3 3 3 4 𝒚𝟕 7 7 7 8 8 8 4 4 10 10 10 10 1 3 3 3 2 2 2 2 3 3 3 3 3 3 4 4 4 4 5 𝒚𝟖 8 3 3 9 9 9 10 10 1 1 1 1 2 2 2 2 3 1 1 1 4 4 4 4 4 4 5 8 8 8 6 𝒚𝟗 9 9 9 7 7 7 1 1 2 2 2 2 3 1 1 5 5 5 5 5 5 5 5 9 9 9 6 6 6 6 3 𝒚𝟏𝟎 4 4 4 1 4 4 2 2 4 4 4 4 4 4 4 4 4 4 4 4 6 6 6 6 6 6 7 7 7 7 8 min Q -30 -26 -18 -70 -38 -8 -78 -44 -38 -20 -8 -14 -48 -46 -12 -28 -40 -14 -18 -18 -48 -34 -16 -4 -10 -12 -20 -12 -12 -2 -50 𝑸𝟎 120 94 76 128 90 82 100 56 96 76 68 54 136 90 78 50 102 88 70 52 138 104 88 84 74 62 98 86 74 72 114 9 10 2 3 4 5 6 7 1 2 3 9 5 2 2 2 2 10 10 10 10 10 10 10 10 10 1 1 1 1 1 1 1 1 1 5 5 5 2 2 5 8 8 6 3 3 3 7 7 7 7 7 7 4 4 4 8 8 8 5 5 5 2 2 2 5 9 9 9 6 8 6 6 9 6 6 6 6 9 9 7 9 6 3 3 3 3 3 3 8 8 8 4 4 4 4 4 4 9 7 7 -24 -10 -4 -4 -4 -14 -14 -12 -4 90 80 76 72 68 54 84 72 68 Самоконтроль знаний Контрольные вопросы 1. Объясните, почему потребовалось заменить матричную запись определяемых неизвестных ‖𝑋𝑖𝛼 ‖, ‖𝑋𝛽𝑗 ‖ на запись в виде списка {𝑦𝑖 }∗ . 2. Обосновать корректность замены определения целевой функции Q соотношением (5.1) на ее представление соотношением (5.5). 3. Какие варьируемые переменные используются в математической модели и как они представлены в алгоритме решения 4. Поясните, в чем состоят отличия соотношения (5.8) от соотношения (5.7) и чем они вызваны. 5. Почему предложенная эвристическая процедура решения не гарантирует глобального оптимума целевой функции. 6. Поясните, почему использованный в алгоритме способ перестановки двух узлов обеспечивает определение локального оптимума. Контрольные задания 1. Напишите численные значения для списка {𝑦𝑖 }𝜔 для вариантов 𝜔 = 1 и ̅̅̅̅ , поясните полученные значения. 𝜔 = 4 при i=1,8 2. Поясните по численным данным примера 5.1, почему соотношение 5.7 (цена до перестановки узлов 𝑎𝑖 , 𝑎𝑗 ) отличается от соотношения 5.8 (цена перестановки узлов 𝑎𝑖 , 𝑎𝑗 ) . 3. Поясните по численным данным примера 5.1, почему значения {𝐶𝑖0𝜔 } представляют собой список, а значения 𝐶𝑖𝑗п𝜔 представляют собой несимметричную матрицу. 4. Прокомментируйте результаты, приведенные в таблице 5.1. 3. Поясните по численным данным примера 5.1, почему значения {𝐶𝑖0𝜔 } представляют собой список, а значения 𝐶𝑖𝑗п𝜔 представляют собой несимметричную матрицу. 4. Прокомментируйте результаты, приведенные в таблице 5.1.