Пример решения задачи последовательным алгоритмом

Задана структура первичной сети в виде неориентированного графа (рис.5.1) и матрица требований V. Число каналов первичной сети задается либо весами ветвей на графе рис.5.1, либо в виде матрицы емкостей ребер U.

U46 = 20

U26 = 20

U12 = 20

U23 = 20

U14 = 20

U34 = 20

U53 = 20

U15 = 20

Рис.5.1. Граф сети

Так как граф неориентированный, то в матрицах емкостей ребер и требований числа каналов можно заполнять только верхнюю половину матрицы.

	1	2	3	4	5	6
1	0	20	0	20	20	0
2		0	20	0	0	20
3			0	20	20	0
4				0	0	20
5					0	0
6						0

               

U=

	1	2	3	4	5	6
1	0	0	18	0	0	0
2		0	0	12	0	0
3			0	0	0	16
4				0	0	0
5					0	16
6						0

V =

      

Цикл 1.

Итерация 1.

 Из матрицы требований V= ║v_st║ выбирается пара узлов, между которыми v_st имеет максимальное значение. В рассматриваемом примере – это пара вершин 1 – 3, для которых v ₁₃ = 18.

2. Из схемы графа рис.5.1 находятся кратчайшие пути по числу ребер

m _1,2,3 ¹ , m _1,5,3 ² , m _1,4,3 ³ .

3. Определяются емкости путей  m _1,2,3 ¹ , m _1,5,3 ² , m _1,4,3 ³ .

c ₁₃ ¹ = min { u ₁₂ , u ₂₃ } = min { 20 , 20 } = 20;

      Аналогично определяются  c ₁₃ ² =20; c ₁₃ ³ =20.

 Так как все пути имеют одинаковую емкость, выбирается первый путь.

4. Из емкости ребер u ₁₂ и u ₂₃ вычитается v ₁₃ и оставшиеся емкости ребер заносятся в таблицу 5.1. Так как v ₁₃ <  с₁₃¹, то на этом распределение требований v ₁₃  заканчивается.

 

Итерация 2.

       5. Из матрицы требований V= ║v_{s t}║ из оставшихся требований выбирается пара вершин с максимальным значением v_st . Это - пара вершин 3 – 6, для которых

v ₃₆ = 16.

       6. Из схемы графа рис.5.1 находятся кратчайшие пути по числу ребер между вершинами 3 и 6

m _3,2,6 ¹ , m _3,4,6 ² .

7. Определяются емкости путей

с₃₆¹ = min { 2 , 20 } = 2;

с₃₆² = min { 20 , 20 } = 20.

Выбирается путь максимальной емкости      m _3,4,6 ² .

8.  Из емкости ребер u ₃₄ и u ₄₆ вычитается емкость v ₃₆  и оставшиеся емкости ребер заносятся в таблицу 5.1. Так как v ₃₆ < с₃₆² , то на этом распределение требований заканчивается.

Итерация 3.

 

9. Из матрицы оставшихся требований выбирается пара вершин с максимальным значением   v_st . Это пара вершин 5 – 6, для которых v ₅₆ = 16 .

10. Из схемы графа рис. 5.1 находятся кратчайшие пути по числу ребер между вершинами 5 и 6

m _5,1,2,6 ¹ , m _5,3,2,6 ² , m _5,1,4,6 ³ , m _5,3,4,6 ⁴ .

 

11. Определяются емкости путей

с₅₆¹= 2,           с₅₆²= 2,       с₅₆³= 4,             с₅₆⁴= 4.

12. После распределения требований v ₅₆ по всем путям осталось v ₅₆ = 8 не распределенных каналов.

 

Итерация 4.

13. Из матрицы требований выбирается последнее требование v ₂₄ = 12 .

14. Из схемы графа рис.5.1 находятся кратчайшие пути

m _2,1,4 ¹ , m _2,3,4 ² , m _2,6,4 ³ .

       15. Определяются емкости путей

с₂₄¹= 0,           с₂₄²= 0,       с₂₄³= 0.

       16. Так как ни в одном из путей нет свободных каналов, то остаются 

 нераспределенными v ₂₄ = 12 каналов.

Так как на сети остается большой резерв каналов, то, вероятнее всего, принята не оптимальная процедура поиска ПРК. На итерации 1 из трех возможных путей был выбран первый путь. Все итерации следует повторить при выборе на первой итерации второго пути, а затем третьего. Фактически, последовательный алгоритм может привести к полному перебору. Поэтому используется приближенный параллельный алгоритм, либо для поиска оптимального решения используется метод линейного программирования.

В таблице 5.2 приведены результаты распределения каналов последовательным алгоритмом для случая, когда на итерации 1 выбирается вместо пути m _1,2,3 ¹ путь m _1,5,3 ² (цикл 2). Во втором цикле получен лучший ПРК, чем в первом, хотя он, как и полученный в цикле 1, не является допустимым. 

                                                                    

                                                                                         Таблица 5.1

            Результаты нахождения ПРК последовательным алгоритмом (цикл 1)

Номера пар       вершин	Путь, емкость пути, потребность	Значение числа каналов   uij , свободных в ребре ij
		11,2=20	11,4= 20 0 2	51,5= 20	22,3=20	22,6=20	33,4=20	33,5=20	44,6=20
1-3 распределены все каналы	m 123 1 с131= 20 v 13 = 18	2 2	2 20	2 20	2 2	2 20	2 20	2 20	2 20
3 - 6 распределены все каналы	m 346 2 с361= 20 v 36 = 16	2 2	2 20	2 20	2 2	2 20	4 4	2 20	4 4
5 – 6 не распределено 8 каналов	m 5146 3 с563= 4 V 56 = 16	2 2	1 16	1 16	2 2	2 20	4 4	2 20	0 0
	m 5326 2 с561= 2 V 56 = =16-4=12	2 2	1 16	1 16	0 0	1 18	4 4	1 18	0 0
	m 5126 1 с561= 2 V 56 = =12-2=10	0 0	1 16	1 14	0 0	1 16	4 4	1 18	0 0
2 – 4 не распределено 12 каналов	m 214 1, m 234 2, m 264 3 с241=0, с242=0,       с243= 0. v 24 = 12	00	116	114	00	116	44	118	00

ПРК не допустим, т.к. не распределено 20 каналов.

                                                                                                                                                                                                          

                                                                                                                    Таблица 5.2

                 Результаты нахождения ПРК последовательным алгоритмом (цикл 2)

Номера пар вершин	Путь, емкость пути, потребность	Значение числа каналов uij, свободных в ребре ij
		U 1,2=20	21,4= 20 2	11,5=20	22,3=20	22,6=20	33,4=20	33,5=20	4,6= 20
1-3 распределены все каналы	m 153 2 с132= 20 v 13 = 18	2 20	2 20	2 2             2	2 20	2 20	2 20	2 2 2     2	20
3 - 6 распределены все каналы	m 346 1 с362= 20 v 36 = 16	2 20	2 20	2 2        2	4 4	4	2 20	2	20
5 – 6  не распределено 12 каналов	m 5126 1 с561= 2 V 56 = 16	1 18	2 20	0 0	4 4	2 2	2 20	2 20	20
	m 5326 2 с562= 2 V 56 = 14	1 18	2 20	0	2	0	2 20	0 0	20
2 – 4 распределены все каналы	m 214 1 с241=18,          v 24 = 12	66	8 8	00	22	00	220	00	220

ПРК не допустим, т.к. не распределено 12 каналов.

 

                     Параллельный алгоритм нахождения ПРК

Поясним параллельный алгоритм на рассмотренном выше примере (рис.5.1).

 Параллельный алгоритм нахождения ПРК состоит в следующем.

1. Из матрицы Vвыбирается требование V ₁₃ = 18 каналов.

2. Из схемы графа рис. 5.1 определяются кратчайшие пути (по числу ребер).

          m _1,2,3 ¹ , m _1,5.3 ² ,   m _1,4,3 ³ .

3. Распределяются 18 каналов равномерно на три пути

с¹(1,3)= с²(1,3)= с³(1,3)=6 каналов.

4. Повторяются пункты 1-3 для других потоков, не обращая внимания на

емкости ребер.

V ₂₄ =12; m _2,1,4 ¹, m _2,3,.4 ²,   m _2,6,4 ³;   с¹(2,4)= с²(2,4)= с³ (2,4) =4

V ₃₆ =16; m _3,2,1 ¹, m _3,4,.6 ²;  с ¹(3,6)= с²(3,6)= 8.

V ₅₆ =16; m _{5,1,2, 6} ¹, m _{5, 3,.2, 6} ²,   m _{5,1,4, 6} ³ m _5,3,4,6 ⁴; с¹(5,6)= с²(5,6)=   

=с³(5,6) = с⁴(5,6)=4.

5. Составляется матрица задействованных емкостей ребер кратчайших путей для идеального ПРК (без учета заданных емкостей ребер) (таблица 5.3).

6.  Для каждого ребра ij подсчитывается число каналов для идеального ПРК. В графе D с¹ _ij число каналов, которое осталось не загруженным на ребре ij, ставится со знаком плюс и со знаком минус при перегрузке ребра. Т.к. есть перегруженные ребра (23, 34), то полученный ПРК недопустим. 

7. По таблице 5.3 определяется, что перегруженному ребру 23 соответствуют пути с числом каналов с¹(1, 3); с²(2, 4); с¹(3, 6); с²(5, 6) .

8. Выбирается с¹(1,3) и проверяется, есть ли кратчайший путь, соответствующий данной паре вершин и состоящий из ненасыщенных ребер. Если есть, то переходят к пункту 9, если нет, то к пункту 11.

9. Между парой 1-3 есть ненасыщенный путь с числом каналов с²(1, 3). Величина перераспределяемой емкости равна 2 (см. ребро 23). Рассчитывается D с² _ij. Т.к. ПРК недопустим, то переходим к п. 10.

10. Повторяем пункты 7, 8 и 9 для ребра 34. По таблице 5.3 определяем, что перегруженному ребру 34 соответствуют пути с числом каналов с³(1, 3); с²(2, 4);с²(3, 6); с⁴(5, 6). Ищем путь с ненасыщенными ребрами. Находим для  пары 1-3 путь с²(1, 3), который проходит по ненасыщенным ребрам 15 и 35. Рассчитываем D с³ _ij . Полученные элементы D с³ _ij определяют искомый ПРК.

11. Если кратчайшие пути с ненасыщенными ребрами для данной пары вершин не найдены, то переходим к следующему пути. Процесс повторяется до тех пор, пока не будет найден ненасыщенный путь. Если такого пути не существует, то требования не могут быть удовлетворены полностью.

Как видно из рассмотренного примера, параллельный алгоритм по сравнению с последовательным позволил получить лучший ПРК. Однако параллельный алгоритм как и последовательный также является приближенным и не во всех случаях с его помощью получается результат лучший, чем полученный последовательным алгоритмом.

Таблица 5.3

              Результаты нахождения ПРК параллельным алгоритмом

Номера пар вершин	Число каналов на кратчайшем пути между парой вершин	Значение числа каналов, занятых в ребре ij
		112	114	115	223	226	334	335	44 6	Результат решения
1-3	с1(1,3) = 6	4 6   6 4 6			4 6 6 4
	с2(1,3) = 6			6 8 10 0				6 8 10 0
	с3(1,3) = 6		6 4				6 4
2-4	с 1 (2,4) = 4	44	44
	с 2 (2,4) = 4				44		44
	с 3 (2,4) = 4					44			44
3-6	с 1 (3,6) = 8				88	88
	с 2 (3,6) = 8						88		88
5-6	с 1 (5,6) = 4	44		44		44
	с 2 (5,6) = 4				44	44		44
	с 3 (5,6) = 4		44	44					44
	с 4 (5,6) = 4						44	44	44
	S Vij	1 14	1 14	1 14	2 22	2 20	2 22	1 14	2 20
Уровень загрузки ребер	D с1 ij	+ +6	+ +6	+ +6	- -2	00	- -2	+ +6	00	ПРК недопустим
	D с2 ij	+ +8	+ +6	+ +4	00	00	- -2	+ +4	00	ПРК недопустим
	D с3 ij	+ +8	+ +8	+ +2	00	00	00	+ +2	00	ПРК допустим

                                                                                                                                         

Варианты заданий

1. Структура первичной сети определена графами на рис. 5. 2 и 5. 3.

2. Матрица требований, ненулевые элементы которой указаны в таблице 5.4 для графов, структура которых приведена для вариантов 1 – 10, и в таблице 5.5 для графов, структура которых приведена для вариантов с 11 по 20. Емкости ребер в числе стандартных каналов заданы весами ребер на графах.

3. Максимальный ранг пути r_max =3 .

 

                                                                                                      Таблица 5.4

Исходные данные для вариантов с первого по десятый.

 

№ вариан.	1	2	3	4	5	6	7	8	9	10
Ненулевые элементы Vst	V25=18 V14=12 V13=14	V13=12 V26=20 V46=33	V13=41 V14=28 V35=17	V16=12 V24=18 V35=12	V13=16 V15=24 V24=30	V14=24 V25=20 V36=16	V13=16 V24=18 V35=32	V14=20 V26=33 V35=15	V14=10 V26=20 V35=14	V13=24 V56=18 V14=10

 

Таблица 5.5

Исходные данные для вариантов с 11 по 20.

 

№ варианта.	11	12	13	14	15	16	17	18	19	20
Ненулевые элементы Vst	V13=24 V16=12 V36=15 V54=21	V25=24 V64=12 V13=16 V23=16	V14=22 V25=20 V36=12	V16=23 V13=20 V24=12	V13=30 V56=21 V14=16	V14=18 V24=20 V36=14 V16=8	V24=30 V16=15 V35=17	V14=18 V25=20 V26=10 V16=5	V13=21 V56=9 V24=12 V15=8	V13=44 V25=20 V56=12

 

Содержание отчета

1. Вариант задания: граф сети, матрица требований, матрица емкостей.

2. Решение задачи нахождения ПРК последовательным алгоритмом.

3. Решение задачи нахождения ПРК параллельным алгоритмом.

4. Сравнение полученных результатов.

 

Литература

1. Глушков В.М., Калиниченко Л..А., Лазарев В.Г., Сифоров В.И., Сети ЭВМ – М.: Связь, 1977.- С. 136-149.

2. Сборник описаний лабораторных работ по курсу “Проектирование и техническая эксплуатация сетей электросвязи”. – М. 1990.

 

                 вариант 1                                       вариант 2

                 вариант 3                                            вариант 4

       

                  вариант 5                                            вариант 6

   

                     вариант 7                                        вариант 8

                             вариант 9                                          вариант 10

Рис.5.2. Структуры графов для вариантов с 1 по 10

 

                         вариант 11                                          вариант 12

                         вариант 13                                          вариант 14

                          вариант 15                                          вариант 16

 

вариант 17                                          вариант 18

 

                        вариант 19                                          вариант 20

 

Рис.5.3. Структуры графов для вариантов с 11 по 20.

 

Тема 6

---

Дата добавления: 2019-03-09; просмотров: 725; Мы поможем в написании вашей работы!

Поделиться с друзьями:

---

---

Мы поможем в написании ваших работ!