5.3. Оптимізація планів сортування пошти

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

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

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

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

Задані ймовірності належності поштівок кожному з напрямів p₁, p₂, …, p_m, причому p₁  p₂ … p_m, а p₁ + p₂ +…+ p_m = 1.

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

Поштівка, адресована за напрямом N_i, сортується s_i раз (s₁  s₂  … s_m).

Необхідно мінімізувати середню кількість сортувань однієї поштівки

s = .

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

Згідно з першим методом на кожному з етапів сортування в кожний з

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

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

Поштівки за напрямом N_i будуть сортуватися

s_i =

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

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

k =

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

S = .

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

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

n^k-1  m  n^k,

одержимо середню кількість сортувань однієї поштівки

k - 1  S  k,

причому поштівки за напрямами N₁, N₂, …, N_r пройдуть k - 1 етапів сортування, а поштівки за напрямами N_r+1, N_r+2, …, N_m – k етапів сортування, внаслідок чого середня кількість сортувань однієї поштівки складе

S = (k-1) .

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

,

де Х – ціла частина Х.

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

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

Рисунок 5.3. Приклади сортування поштівок

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

• в схемі рис. 5.3,а

S = (p₁ + p₂ +…+ p₉) + 2(p₁₀ + p₁₁ +…+ p₁₈) + …+ 11(p₉₁ + p₉₂ +…+ p₉₉) + 11 p₁₀₀;

• в схемі рис. 5.3,б

S = 2;

• в схемі рис. 5.3,в

S = (p₁ + p₂ + p₃) + 2(p₄ + p₅ +…+ p₇₀) + 3(p₇₁ + p₇₂ +…+ p₁₀₀).

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

Візьмемо за основу схему рис. 5.3,б, в якій S = 2.

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

R₀ = N₁…N₁₀, N₁₁…N₂₀, …, N₉₁…N₁₀₀,

за якого в кожний з накопичувачів А₁… А₁₀ потрапляють поштові відправлення 10 напрямів.

Виділимо напрям N₁, якому відповідає розподіл напрямів сортування

R₁ =  N₁, N₂…N₁₁, N₁₂…N₂₁, …, N₈₂…N₁₀₀.

З розподілу R₁ видно, що в накопичувач А₁ потрапляють поштові відправлення одного напряму, в накопичувачі А₂… А₉ – 10 напрямів, в накопичувач А₁₀ – 19 напрямів.

З зазначених 19 напрямів на другому етапі сортування виділяються 9 і на третьому етапі 10.

Таким чином, виділення напряму N₁, тобто зменшення на одиницю кількості його сортувань, призводить до збільшення на одиницю кількості сортувань 10 напрямів (N₉₁…N₁₀₀).

Очевидно, що при виконанні нерівності

p₁  p₉₁ + p₉₂ + …+ p₁₀₀

виділення напряму N₁ доцільно, а при невиконанні – недоцільно.

Якщо виділення напряму N₁ доцільно, виділимо напрям N₂, якому відповідає розподіл напрямів сортування

R₂ =  N₁, N₂, N₃…N₁₂, N₁₃…N₂₂, …, N₇₃…N₁₀₀.

Виділення напряму N₂ доцільно, якщо виконується нерівність

p₂  p₈₁ + p₈₂ + … + p₉₀,

і недоцільно, якщо вона не виконується.

Якщо виділення напряму N₂ доцільно, виділимо напрям N₃, якому відповідає розподіл напрямів сортування

R₃ = N₁, N₂, N₃, N₄…N₁₃, N₁₄…N₂₃, …, N₆₄…N₁₀₀.

Виділення напряму N₃ доцільно, якщо виконується нерівність

p₃  p₇₁ + p₇₂ + … + p₈₀,

і недоцільно, якщо вона не виконується.

Зазначений процес послідовного порівняння ймовірностей напрямів сортування закінчується, якщо чергова нерівність не виконується (в разі виконання всіх нерівностей одержимо схему рис. 5.3,а; в разі виділення напрямів N₁, N₂, N₃ – схему рис. 5.3,в).

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