Лекции 7-8. Расчет кратчайшей связывающей сети заданной конфигурации (1153085)
Текст из файла
ЛЕКЦИИ 7-8РАСЧЕТ КРАТЧАЙШЕЙ СВЯЗЫВАЮЩЕЙ СЕТИ ЗАДАННОЙКОНФИГУРАЦИИ5.1 Постановка задачиПри проектировании вычислительных сетей разработчику необходимонайти такой вариант системы, который удовлетворял бы широкому спектрутребований по критериям: стоимости, надежности, времени доставкисообщений, живучести и т.д.
Реальные методы проектирования ориентируютсяна итеративную 'процедуру, при которой производится последовательноеулучшение базовой конфигурации ВС по различным критериям до тех пор,пока не будут достигнуты требуемые характеристики.Одной из задач, возникающих при итеративной процедуре проектирования,является размещение конфигурации ВС, выбранной, например, по критериюнадежности в пространстве, взвешенном; например, стоимостью каналов связи.ajsijaiAРассматриваемая задача может бытьсформулирована следующим образом.Пусть задана конфигурация S, (см. рис.5.1) содержащая множество узлов ∈A,̅̅̅̅̅i = 1,, каждая пара которых соединенасвязями, число их равно .bmbМРис.
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 может быть записана в виде матрицы конфигурации22113310105544667998Рис. 5.3. Пример конфигурации ВС1. Расстояние между точками записываются в виде матрицы стоимости каналовМ=12345678910102671348111220715414 1525336709231211124715901211788651491201174956314911105211 127415 12 17750832882184280412911518911340111013126512212 110Начальное значение первого варианта = 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;0110= 24.4. Цены после перестановки П определяются по соотношению (5.8) и дляненулевых значений можно записать:П111= 12 12 + 16 16 + 21 21 + 61 61 = 2+3+2+3= 10;П112= 12 12 + 16 26 + 21 21 + 61 62 = 2+14+2+14= 32;П113= 12 32 + 16 26 + 21 21 + 16 36 = 7+3+7+3= 20;Аналогично рассчитывают остальные значения, которые записаны в матрицецен для первой итерации:1 П1 =23456789101103220323034408341021826305614344626423632678626478784872666242044425218165818828548143082830412664030204824343826464873621205042244024223482212216182268822930623252443632283652101214241846242224(5-6)’.Оценку возможного улучшения перестановки узлов вычисляют посоотношению (5.8):=1П1П111= − 101 − 101 + 11+ 11= -10-10+10+10=0min Q= 0; p = 1; = 1 .=1П1П1(5-6)’’ 12= − 101 − 201 + 12+ 21= -10-26+32+18=14.Для компактности изложенияпредставим в виде матрицы:112203456результаты78расчета91014-26-10630261218802022-1242244200-108-16-4-20640-12-2216-26-28-3001024612-220-12612-40-18-22-60-8-80-63 1 =промежуточные456789100из которой следует, что результаты расчета п.
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Вари Итераант ция11231223312142341523416234127345618234113822533339955101066697101010101085599222333995883777777771077722222210311411586666666688969988811010111101010552667777888899888895551110102555666778555999910101010111118999576661010108599331010511333222277333347778884410101010133322223333334444583399910101111222231114444445888699977711222231155555555999666634441442244444444444466666677778minQ-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-501209476128908210056967668541369078501028870521381048884746298867472114910234567123952222101010101010101010111111111555225886333777777444888555222599968669666699796333333888444444977-24-10-4-4-4-14-14-12-4908076726854847268Самоконтроль знанийКонтрольные вопросы1.
Характеристики
Тип файла PDF
PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.
Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
