avangard-pressa.ru

Задача побудови найкоротших радіальних маршрутів між вузлами мережі перевезень пошти - Технологии

В поштовому зв’язку радіальні маршрути використовуються, в основному, як магістральні та регіональні маршрути, а в разі нестачі часу для проходження кільцевих маршрутів – також як окружні маршрути.

Задача формулюється так: заданий зв’язний зважений граф, вершини якого відповідають вузлам мережі перевезень пошти, ребра – шляхам, що з’єднують ці вузли, а ваги ребер – протяжностям відповідних шляхів. Знайти найкоротші шляхи, що з’єднують задану початкову вершину з рештою вершин графа.

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

Початковій вершині Ві надається вага Рі = 0, решті вершин – нескінченні ваги Рj = ¥.

На кожному кроку формування рельєфу графа знаходиться раніше неперевірена вершина мінімальної ваги, відносно якої формуються ваги тих неперевірених вершин, що безпосередньо з’єднані з перевірною вершиною. Вага неперевіреної вершини замінюється вагою перевірної вершини, збільшеної на вагу ребра, що з’єднує зазначені вершини, якщо перша перевищує другу.

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

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

Алгоритм формування рельєфу графа наведений на рис. 2.5.

Початок

1. Присвоєння початковій вершині

ваги Рi = 0, присвоєння решті

вершин ваг Рj = 999

2. Вибір серед неперевірених вершин

графа вершини Вk мінімальної ваги

3.Обчислення ваги = lk + P(k,j)

чергової неперевіреної вершини

Bj графа, безпосередньо пов’язаної

з перевірною вершиною Bk

Ні

4. < Рj

Так

5. Рj = , запис Bk

6. Всі

вершини Bj, безпосередньо Ні

пов’язані з вершиною Bk,

перевірені

Так

7. Присвоєння перевірній вершині

Bk позначки “перевірена” (*)

Ні 8. Перевірено

n - 1 вершин графа

Так

Кінець

Рисунок 2.5. Алгоритм формування рельєфу графа

Алгоритм містить 8 блоків.

У блоці 1 створюється початковий рельєф графа. Початковій вершині Ві присвоюється мінімальна вага Рі = 0, решті вершин графа Bj (j = 1, 2, … n, j ¹ i) – нескінченні ваги Рj = ¥, які подаються як надмірні ваги Рj = 999.

У блоці 2 серед неперевірених вершин вибирається вершина Вk мінімальної ваги Рk.

У блоці 3 обчислюється вага = Рk + Р(k,j) чергової неперевіреної вершини Bj відносно перевірної вершини Bk, що безпосередньо пов’язана з вершиною Bj графа.

У блоці 4 обчислена вага порівнюється з вагою Рj вершини Bj. При < Рj виконується перехід до блоку 5, при ³ Рj – до блоку 6.

У блоці 5 вага Рj замінюється вагою , тобто значення ваги вершини Bj знижується, і запам’ятовується вершина Bk, від якої одержано значення ваги Рj .

У блоці 6 перевіряється, чи всі вершини Вj графа, безпосередньо пов’язані з перевірною вершиною Bk, перевірені. Якщо так – здійснюється перехід до блоку 7, якщо ні – повернення до блоку 3.

У блоці 7 перевірній вершині Bk присвоюється позначка “перевірена” (*) і вона виключається з подальшого розгляду.

У блоці 8 перевіряється кількість вершин графа, що вже перевірені. Якщо таких вершин менше n - 1 – здійснюється повернення до блоку 2, і процес формування рельєфу графа повторюється, якщо їх n - 1 – рельєф графа сформований і робота алгоритму закінчується.

Алгоритм формування найкоротших шляхів за сформованим рельєфом графа наведено на рис. 2.6.

Алгоритм містить 5 блоків.

У блоці 1фіксується поточна перевірна вершина Bl = Bj (j = 1, 2, … n,

j ¹ i).

У блоці 2 виконується зчитування рядка l таблиці рельєфу графа.

У блоці 3 фіксується значення номера попередньої вершини Bk графа та ваги Рl .

У блоці 4 значення l замінюється значенням k, тобто поточна вершина Bl замінюється поточною вершиною Bk графа.

У блоці 5 порівнюються значення l і i. При l ¹ i виконується повернення до блоку 2 і формування шляху між вершинами Bi та Bj графа продовжується. При l = i шлях між вершинами Bi та Bj графа сформований і робота алгоритму закінчується.

Початок

1. l = j (j = 1, 2 …, n, j ¹ i)

2.Зчитування рядка l таблиці

рельєфу графа

3. Запис номера попередньої

вершини Bk графа і ваги Pl

4. l = k

Ні 5. l = i

Так

Кінець

Рисунок 2.6. Алгоритм формування найкоротших шляхів

Послідовність кроків формування рельєфу графа рис. 2.3 відносно вершини 4 наведено в табл. 2.3 … 2.10 (Bi – будь-яка вершина, Рi – вага вершини Bi, * - позначка вершини “перевірена”, Bk – вершина, від якої одержана вага Рi).

Таблиця 2.3. Формування рельєфу графа Таблиця 2.4. Формування рельєфу графа Таблиця 2.5. Формування рельєфу графа


Крок 0: початковий Крок 1: Рi = 0, Bi = 4 Крок 2: Рi = 2, Bi = 3 Bi * Рi Bk Bi * Рi Bk Bi * Рi Bk * * *

Таблиця 2.6. Формування рельєфу графа Таблиця 2.7. Формування рельєфу графа Таблиця 2.8. Формування рельєфу графа


Крок 3: Рi = 3, Bi = 1 Крок 4: Рi = 3, Bi = 7 Крок 5: Рi = 4, Bi = 6 Bi * Рi Bk Bi * Рi Bk Bi * Рi Bk * * * * * * * * * * * *

Крок 6: Рi = 6, Bi = 8 Крок 7: Рi = 7, Bi = 2 Bi * Рi Bk Bi * Рi Bk * * * * * * * * * * * * * Таблиця 2.9. Формування рельєфу графа Таблиця 2.10. Формування рельєфу графа

Сформовані найкоротші шляхи між вершиною 4 та рештою вершин графа наведено у табл. 2.11 (в дужках зазначені протяжності відповідних шляхів або їх частин)

Таблиця 2.11. Перелік найкоротших шляхів


4 (0) – 3 (2) – 1 (3) 4 (0) – 3 (2) – 1 (3) – 2 (7) 4 (0) – 3 (2) 4 (0) – 6 (4) – 8 (6) – 5 (9) 4 (0) – 6 (4) 4 (0) – 7 (3) 4 (0) – 6 (4) – 8 (6)

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

У задачах поштового зв’язку такі шляхи використовуються для перевезень важкої (посилочної) пошти з метою скорочення витрат, пов’язаних з її перевантаженням у транзитних вузлах.

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

У табл. 2.12 … 2.18 наведена послідовність кроків формування рельєфу графа рис. 2.3 відносно вершини 4 за умови рівності ваг усіх його ребер одиниці (позначення – такі ж самі, що в табл. 2.3 … 2.10).

Таблиця 2.12. Формування рельєфу графа Таблиця 2.13. Формування рельєфу графа Таблиця 2.14. Формування рельєфу графа


Крок 0: початковий Крок 1: Рi = 0, Bi = 4 Крок 2: Рi = 2, Bi = 3 Bi * Рi Bk Bi * Рi Bk Bi * Рi Bk * * *

Таблиця 2.15. Формування рельєфу графа Таблиця 2.16. Формування рельєфу графа Таблиця 2.17. Формування рельєфу графа


Крок 3: Рi = 3, Bi = 1 Крок 4: Рi = 3, Bi = 7 Крок 5: Рi = 4, Bi = 6 Bi * Рi Bk Bi * Рi Bk Bi * Рi Bk * * * * * * * * * * * *

Оскільки на кроці 6 всі вершини отримали ваги, формування рельєфу закінчується.

У табл. 2.19 наведено найкоротші за числом проміжних вершин шляхи між вершиною 4 та рештою вершин графа.

Таблиця 2.19. Перелік найкоротших шляхів


4 – 1 4 – 1 – 2 4 – 3 4 – 1 – 2 – 5 4 – 6 4 – 7 4 – 6 – 8