Практичне заняття 1. Основні поняття теорії графів. Матричне представлення графів. Алгоритм Флойда (стр. 7 )

Практичне заняття 1

РОЗРОБКА ПЛАНІВ СОРТУВАННЯ ПОШТОВИХ ВІДПРАВЛЕНЬ

Мета: 1.1 Ознайомитися з поняттям план сортування поштових відправлень.

1.2 Отримати практичні навики по розробці планів сортування поштових відправлень

Ключові положення

Метод. керівництво: “Застосування методів теорії графів для розв’язування типових задач поштового зв’язку” -, , Одеса 2000.

Навчальний посібник: “Мережі та системи поштового зв’язку” -, , Кріль С. С, Одеса 2008.

Метод. керівництво: “Оптимізація сортування поштових відправлень” -, , Одеса 2003.

, , Беркман зв¢язок. – К.: Техніка, 2003

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

Задача побудови плану сортування ставиться так.

Сортувальна машина містить n накопичувачів А1, А2, … , Аn.

Поштові відправлення, що надходять на сортування, повинні бути розсортовані за m напрямами N1, N2, …, Nm, інформацію про які містять поштові індекси.

Задані ймовірності належності поштових відправлень кожному з напрямів p1, p2, …, pm, причому p1 ³ p2 ³…³ pm, а p1 + p2 +…+ pm = 1.

Відомо, що m > n, внаслідок чого поштові відправлення можуть сортуватися по етапах, тобто проходити через сортувальну машину кілька разів.

Поштове відправлення, адресоване за напрямом Ni, сортується si раз (s1 £ s2 £ …£ sm).

Необхідно мінімізувати середнє число сортувань одного поштового відправлення

s = .

Можливі два основні методи організації сортування: метод виділення напрямів і метод групування напрямів.

Згідно з першим методом на кожному з етапів сортування в кожний з n - 1 накопичувачів спрямовуються поштові відправлення чергових n - 1 напрямів, тобто виділяються n - 1 зазначених напрямів, решта спрямовується в n-й (збірний) накопичувач, з якого на наступному етапі сортування знову виділяються

n - 1 напрямів аж доки всі поштові відправлення не будуть відсортовані за своїми напрямами.

Поштові відправлення за напрямом Ni будуть сортуватися

si =

разів, де - значення Х, округлене до найближчого цілого числа.

Виходячи з цього загальне число етапів сортування складе

k =

з урахуванням того, що поштові відправлення останнього напряму сортування автоматично залишаються в n-му накопичувачі, а середнє число сортувань одного поштового відправлення –

S = .

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

Подаючи число напрямів сортування у виді

nk-1 < m £ nk,

одержимо середнє число сортувань одного поштового відправлення

k - 1 < S £ k,

причому поштові відправлення за напрямами N1, N2, …, Nr пройдуть k - 1 етапів сортування, а поштові відправлення за напрямами Nr+1, Nr+2, …, Nm – k етапів сортування, внаслідок чого середнє число сортувань одного поштового відправлення складе

S = (k-1).

Значення r може бути одержано з виразу

,

де [Х] - ціла частина Х.

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

На рис.1 наведені приклади сортування поштових відправлень на 100 напрямів за наявності 10 накопичувачів (а – методом виділення напрямів, б – методом групування напрямів, в – комбінованим методом). Цифри в овалах – групи напрямів, цифри в колах – виділенні напрями, цифри в прямокутниках – етапи сортування.

0 1…100

1 1 … 9 10…100

2 10 … 18 19…100

… 90 91…100

…

а

0 1…100

1 1…10 … 91…100

2 1 … 10 … 91 … 100

б

0 1…100

…13 … 54…63 64…100

2 4 … 13 … 54 …… 70 71…80 … 91…100

3 71 … 80 … 91 … 100

в

Середнє число сортувань одного поштового відправлення складає:

- в схемі рис. а

S = (p1 + p2 +…+ p9) + 2(p10 + p11 +…+ p18) + …+ 11(p91 + p92 +…+ p99) + 11 p100;

- в схемі рис. 1,б

S = 2;

- в схемі рис. 1,в

S = (p1 + p2 + p3) + 2(p4 + p5 +…+ p70) + 3(p71 + p72 +…+ p100).

Варіанти:

m - количество направлений, n – количество накопителей,

q = ½; p1=a, p2=a*q, p3=a*q2,…, pm=a*qm-1 ; a=(1-q)/1-qm.

1. m=25, n=5

2. m=28, n=4

3. m=28, n=7

4. m=24, n=6

5. m=24, n=4

6. m=24, n=8

7. m=30, n=6

8. m=30, n=5

9. m=30, n=10

10. m=32, n=8

11. m=32, n=4

12. m=27, n=9

13. m=27, n=3

14. m=21, n=7

15. m=21, n=3

16. m=33, n=11

17. m=33, n=3

18. m=20, n=4

19. m=20, n=5

20. m=20, n=10

21. m=30, n=3

22. m=24, n=12

23. m=22, n=11

24. m=30, n=3

25. m=24, n=3

Практичне заняття 2

ОПТИМІЗАЦІЯ МАРШРУТНОГО СОРТУВАННЯ ПОШТОВИХ ВІДПРАВЛЕНЬ

Мета: 1.1 Ознайомитися з поняттям маршрутне сортування поштових відправлень.

1.2 Отримати практичні навики по складанню сортувальних таблиць.

Ключові положення

Метод. керівництво: “Застосування методів теорії графів для розв’язування типових задач поштового зв’язку” -, , Одеса 2000.

Навчальний посібник: “Мережі та системи поштового зв’язку” -, , Кріль С. С, Одеса 2008.

Метод. керівництво: “Оптимізація сортування поштових відправлень” -, , Одеса 2003.

, , Беркман зв¢язок. – К.: Техніка, 2003

Маршрутне сортування широко застосовується при сортуванні поштових відправлень на послідовність пунктів обмінювання пошти розташованих на шляху проходження поштового маршруту (магістральні, обласні, районні маршрути, маршрути обмінювання пошти з міськими відділеннями зв'язку, маршрути МСП тощо), а також на поштові скриньки адресатів (маршрути листонош).

Формально задача маршрутного сортування ставиться як задача переформування неупорядкованої вхідної послідовності поштових відправ- лень, адресованих за п напрямами і,j, ..., к (і, j, ..., к = 0, 1, ..., п - 1), в упорядковану вихідну послідовність і< j <, ...,<к (і, j, ..., к = 0, 1,..., п - 1), в якій кількість відправлень, адресованих за будь-яким напрямом, є довільним цілим числом.

Зазначена задача виступає також як окремий випадок відомої математичної задачі сортування (перетворення) деякої вхідної неупорядкованоі послідовності чисел у вихідну упорядковану послідовність цих чисел.

Наприклад, вхідна послідовність поштових відправлень, адресованих за напрямами 03, 06, 05, 05, 10, 10, 00, 07, 08, 01, 05, 01, 03, 04, 15, 13, 00, 02, 02, 07, 07, 12, 03, 08, повинна бути переформована в вихідну послідовність 00, 00, 01,01, 02, 02, 03, 03, 03, 04, 05, 05, 05, 06, 07, 07, 07, 08, 08, 10, 10, 12, 13, 15.

Відомі алгоритми розв'язання математичної задачі сортування засновані на переставленнях елементів вхідної послідовності чисел і практично непридатні для упорядкування фізичних поштових відправлень.

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

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

Для точного розв'язання задачі співвідношення загальної кількості напрямів сортування n, загальної кількості накопичувачів поштових відправлень q та загальної кількості етапів сортування s повинно відповідати умові