147494 (691936), страница 3

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 3)

15

Постійна

12

[172,15]

Постійна

2

[237,15]

Постійна

21

[512,15]

Постійна

31

[801,21]

Постійна

23

[810,12]

Постійна

22

[933,2]

Тимчасова

22

[810+535,23]= [1345,23]

Тимчасова

38

[992,31]

Тимчасова

38

[810+929,23]= [1739,23]

Тимчасова

3

[810+1045,23]= [1855,23]

Тимчасова

Тимчасовий статус мітки [933,2] вузла 22 заміняється на постійний (U22=933).

Крок 7. З вузла 22 можна досягти вузлів 38, 3. Після обчислення міток одержимо наступний їх список:

Вузол

Мітка

Статус мітки

15

Постійна

12

[172,15]

Постійна

2

[237,15]

Постійна

21

[512,15]

Постійна

31

[801,21]

Постійна

23

[810,12]

Постійна

22

[933,2]

Постійна

38

[992,31]

Тимчасова

38

[933+427,22]= [1360,22]

Тимчасова

3

[1855,23]

Тимчасова

3

[933+938,22]= [1871,22]

Тимчасова

Тимчасовий статус мітки [992,31] вузла 38 заміняється на постійний (U38=992).

Крок 8. З вузла 38 можна досягти вузла 3. Після обчислення міток одержимо наступний їх список:

Вузол

Мітка

Статус мітки

15

Постійна

12

[172,15]

Постійна

2

[237,15]

Постійна

21

[512,15]

Постійна

31

[801,21]

Постійна

23

[810,12]

Постійна

22

[933,2]

Постійна

38

[992,31]

Постійна

3

[1855,23]

Тимчасова

3

[992+116,38]= [1108,38]

Тимчасова

На останньому кроці знайдено найкоротшу відстань для вузла 3 – [1108.38]. Таким чином статус мітки вузла 3 змінюється на постійний.

Кінцевий результат міток має такий вигляд:

Вузол

Мітка

Статус мітки

15

Постійна

12

[172,15]

Постійна

2

[237,15]

Постійна

21

[512,15]

Постійна

31

[801,21]

Постійна

23

[810,12]

Постійна

22

[933,2]

Постійна

38

[992,31]

Постійна

3

[1108,38]

Постійна

Найкоротший шлях між вузлом 15 і будь-яким іншим вузлом визначається починаючи з вузла призначення шляхом проходження їх у зворотному напрямку за допомогою інформації, представленої в постійних мітках. Найкоротший маршрут між вузлами 15 і 3 має таку послідовність вузлів: (3)→ [1108.38] →(38)→ [992.31] →(31)→ [801.21] →(21)→ (15).

Таким чином, одержуємо шлях загальною довжиною 1108 км.

4. Задача про максимальний потік (алгоритм Форда-Фалкерсона)

Рішення задачі складається з підготовчого етапу і кінцевого числа кроків, на кожнім з яких відбувається припустиме збільшення потоку. На підготовчому етапі формується матриця пропускних здатностей дуг мережі.

Таблиця 4.1. Матриця пропускних здатностей дуг мережі

	15	12	2	21	31	23	22	38	3
15	-	10	10	10-
12	7	-	7			7	7
2	13	13	-	13	13		13
21	18+		18	-	18-
31			22	22+	-		22	22-
23		22				-	22	22	22
22		21	21		21	21	-	21	21
38					28+	28	28	-	28-
3						7	7	7+	-

По табл. 4.1. знаходимо шлях l1=(15,21,31,38) зі станції 15 у 3 з позитивною пропускною здатністю. Елементи цього шляху позначаємо знаком «мінус», а симетричні – знаком «плюс». Визначаємо пропускну здатність знайденого шляху, що дорівнює найменшій з пропускних здатностей дуг: C1= min {10,18,22,28}=10.

Визначаються залишкові пропускні здатності дуг знайденого шляху і симетричних йому дуг. Для цього з елементів табл. 4.1. віднімаємо , а до елементів додаємо . У результаті одержимо нову табл. 4.2 зі зміненими пропускними здатностями.

Таблиця 4.2. Матриця пропускних здатностей дуг мережі

	15	12	2	21	31	23	22	38	3
15	-	10	10-	0
12	7	-	7			7	7
2	13+	13	-	13	13		13-
21	28		18	-	8
31			22	32	-		22	12
23		22				-	22	22	22
22		21	21+		21	21	-	21	21-
38					38	28	28	-	18
3						7	7+	17	-

Позначаємо стовпці табл. 4.2, знаходимо другий шлях l2=(15,2,22) зі станції 15 у 3, і розставляємо знаки. Визначаємо пропускну здатність знайденого шляху, що дорівнює найменшій з пропускних здатностей дуг:

C2= min {10,13,21}=10.

Змінимо пропускні здатності позначених дуг на (табл. 4.3).

Таблиця 4.3. Матриця пропускних здатностей дуг мережі

	15	12	2	21	31	23	22	38	3
15	-	10-	0	0
12	7+	-	7			7-	7
2	23	13	-	13	13		3
21	28		18	-	8
31			22	32	-		22	12
23		22+				-	22	22	22-
22		21	31		21	21	-	21	11
38					38	28	28	-	18
3						7+	17	17	-

Позначивши стовпці знаходимоl3=(15,12,23).

Величина потоку по шляху : C3= min {10,7,22,}=7.

Розрахувавши нові пропускні здатності дуг, приходимо до табл. 4.4.

Таблиця 4.4. Матриця пропускних здатностей дуг мережі

	15	12	2	21	31	23	22	38	3
15	-	3-	0	0
12	14+	-	7			0	7-
2	23	13	-	13	13		3
21	28		18	-	8
31			22	32	-		22	12
23		29				-	22	22	15
22		21+	31		21	21	-	21	11-
38					38	28	28	-	18
3						14	17+	17	-

Позначивши стовпці знаходимоl4=(15,12,22).

Величина потоку по шляхуl4: C4= min {3,7,11}=3.

Розрахувавши нові пропускні здатності дуг, приходимо до табл. 4.5

Таблиця 4.5. Матриця пропускних здатностей дуг мережі

	15	12	2	21	31	23	22	38	3
15	-	0	0	0
12	17	-	7			0	4
2	23	13	-	13	13		3
21	28		18	-	8
31			22	32	-		22	12
23		29				-	22	22	15
22		24	31		21	21	-	21	8
38					38	28	28	-	18
3						14	20	17	-

Переглядаючи рядки і позначаючи стовпці переконуємося в тім, що рядок 15 позначити неможливо. Отже, більше не існує жодного шляху з позитивною пропускною здатністю з вершини 15 у вершину 3.

Характеристики

Список файлов курсовой работы