Таблиця 5.14 – Матриця переходів між позиціями посилки
| -X | X | -Y | Y | -Z | Z | |
| 11 | 41 | 21 | 14 | 12 | 61 | 51 |
| 12 | 42 | 22 | 11 | 13 | 62 | 52 |
| 13 | 43 | 23 | 12 | 14 | 63 | 53 |
| 14 | 44 | 24 | 13 | 11 | 64 | 54 |
| 21 | 11 | 31 | 54 | 62 | 24 | 22 |
| 22 | 12 | 32 | 51 | 63 | 21 | 23 |
| 23 | 13 | 33 | 52 | 64 | 22 | 24 |
| 24 | 14 | 34 | 53 | 61 | 23 | 21 |
| 31 | 21 | 41 | 32 | 34 | 53 | 63 |
| 32 | 22 | 42 | 33 | 31 | 54 | 64 |
| 33 | 23 | 43 | 34 | 32 | 51 | 61 |
| 34 | 24 | 44 | 31 | 33 | 52 | 62 |
| 41 | 31 | 11 | 64 | 52 | 42 | 44 |
| 42 | 32 | 12 | 61 | 53 | 43 | 41 |
| 43 | 33 | 13 | 62 | 54 | 44 | 42 |
| 44 | 34 | 14 | 63 | 51 | 41 | 43 |
| 51 | 52 | 54 | 44 | 22 | 11 | 33 |
| 52 | 53 | 51 | 41 | 23 | 12 | 34 |
| 53 | 54 | 52 | 42 | 24 | 13 | 31 |
| 54 | 51 | 53 | 43 | 21 | 14 | 32 |
| 61 | 64 | 62 | 24 | 42 | 33 | 11 |
| 62 | 61 | 63 | 21 | 43 | 34 | 12 |
| 63 | 62 | 64 | 22 | 44 | 31 | 13 |
| 64 | 63 | 61 | 23 | 41 | 32 | 14 |
Рисунок 5.17 – Граф можливих поворотів посилки
Будемо вважати позицію 11 позицією зчитування ПІ, отже, при початковому розташуванні міток на інших позиціях вони повинні бути переведені на позицію 11.
Для аналізу можливих послідовностей переходу від довільних позицій до позиції 11 на другому етапі зручно користуватися рельєфом графа рис. 5.17, в якому кожній вершині графа надана вага відносно вершини 11.
Рельєф графа наведений у табл. 5.15.
Таблиця 5.15 – Рельєф графа посилки
| -X | X | -Y | Y | -Z | Z | ||
| 3 | 23 | 13 | 33 | 52 | 64 | 22 | 24 |
| 3 | 32 | 22 | 42 | 33 | ЗІ | 54 | 64 |
| 3 | 34 | 24 | 44 | 31 | 33 | 52 | 62 |
| 3 | 43 | 33 | 13 | 62 | 54 | 44 | 42 |
| 3 | 53 | 54 | 52 | 42 | 24 | 13 | 31 |
| 3 | 63 | 62 | 64 | 22 | 44 | 31 | 13 |
| 2 | 13 | 12 | 14 | ||||
| 2 | 22 | 12 | 51 | 21 | |||
| 2; 2 | 24 | 14 | 61 | 21 | |||
| 31 | 21 | 41 | |||||
| 2 | 33 | 51 | 61 | ||||
| 2 | 42 | 12 | 61 | 41 | |||
| 2 | 44 | 14 | 51 | 41 | |||
| 2 | 52 | 51 | 41 | 12 | |||
| 2 | 54 | 51 | 21 | 14 | |||
| 2; 2 | 62 | 61 | 21 | 12 | |||
| 64 | 61 | 41 | 14 | ||||
| 1 | 12 | 11 | |||||
| 1 | 14 | 11 | |||||
| 1 | 21 | 11 | |||||
| 1 | 41 | 11 | |||||
| 1 | 51 | 11 | |||||
| 1 | 61 | 11 | |||||
| 0 | 11 |
З рис. 5.17 і табл. 5.15 випливає, що з позицій 12, 14, 21, 41, 51, 61 можна здійснити перехід до позиції 11 за один поворот посилки; з позицій 13, 22, 24, 31, 33, 42, 44, 52, 54, 62, 64 – за два повороти посилки; з позицій 23, 32, 34, 43, 53, 63 – за три повороти посилки, отже мінімальне значення середньої кількості поворотів посилки, яку можна досягти при розміщенні 24 пристроїв для пошуку міток на всіх 24 позиціях складає
Найкоротший шлях від довільної вершини графа до кінцевої вершини 11 створюється як перелік з'єднаних вершин, вага яких послідовно зменшується на одиницю.
Наприклад, найкоротший шлях від вершини 23 (вага 3) до вершини 11 (вага 0) може бути сформований наступним чином:
• від вершини 23 (вага 3) можливі переходи до вершин 13 (-X, 33 (X), 52 (-Y), 64 (П, 22 (-Z), 24 (Z) (вага 2); обираємо 24 (Z);
• від вершини 24 (вага 2) можливі переходи до вершин 14 (-X, 41 (X) (вага 1); обираємо 14 (-X);
• від вершини 14 (вага 1) можливий перехід лише до вершини 11 (Y) (вага 0).
Таким чином, можливий найкоротший шлях від вершини 23 до вершини 11 мас вид: 23, 24, 14, 11 (Ζ, -X, Y).
З рис. 5.16 і табл. 5.14 можна також побудувати повні переліки послідовностей поворотів від довільних позицій до позиції 11.
Так, повний перелік містить 16 послідовностей поворотів від позиції 23 до позиції 11:
• 23-13-12-11 (повороти -Х, -Y, -Υ);
• 23-13-14-11 (повороти -Х, Y, Υ);
• 23-22-12-11 (повороти -Ζ, -X -У);
Сторінки
В нашій електронній бібліотеці ви можете безкоштовно і без реєстрації прочитати «Логістика поштового зв’язку» автора Ящук Л.О. на телефоні, Android, iPhone, iPads. Зараз ви знаходитесь в розділі „Побудова мінімальної послідовності поворотів посилок“ на сторінці 2. Приємного читання.
