Наближене розв’язання задачі, яке призводить до оптимального або достатньо близького до оптимального результату, полягає в формуванні деякого початкового (базового) кільцевого маршруту, що проходить через усі вузли мережі, і його послідовному поліпшенні. Мережа поштового зв’язку подається у вигляді графа G (X,Y), вершини якого відповідають вузлам мережі, ребра – шляхам, що з’єднують ці вузли, а ваги ребер – протяжностям відповідних шляхів.
2 5
3
4 4 3
|
 |
 |
 |
 |
4 3 7
Рисунок 4.1
Для побудови базового циклу доцільно провести напрямки з визначеної вершини на решту вершин графа та послідовно з’єднати всі вершини за найкоротшими шляхами у порядку слідування зазначених напрямків.
Для поліпшення базового циклу в ньому послідовно вибираються 4 розташовані підряд вершини i, k, l, j і підраховується протяжність шляху i – k – l – j, після чого послідовність вибраних вершин змінюється на i, l, k, j і підраховується протяжність шляху i – l – k –j. Якщо шлях i – k – l – j більш протяжний, ніж шлях i – l – k –j, перший замінюється останнім.
Алгоритм побудови кільцевого маршруту
1. Побудова матриці найкоротших відстаней між вершинами графа
Таблиця 4.1 Матриця найкоротших відстаней
1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | Максимальна відстань | Сума мінімальних відстаней | |
1 | - | 4 | 1 | 3 | 7 | 4 | 5 | 6 | 7 | 30 |
2 | 4 | - | 5 | 7 | 3 | 4 | 5 | 6 | 7 | 34 |
3 | 1 | 5 | - | 2 | 8 | 3 | 4 | 5 | 8 | 28 |
4 | 3 | 7 | 2 | - | 9 | 4 | 3 | 6 | 9 | 34 |
5 | 7 | 3 | 8 | 9 | - | 5 | 6 | 3 | 9 | 41 |
6 | 4 | 4 | 3 | 4 | 5 | - | 1 | 2 | 5 | 23 |
7 | 5 | 5 | 4 | 3 | 6 | 1 | - | 3 | 6 | 27 |
8 | 6 | 6 | 5 | 6 | 3 | 2 | 3 | - | 6 | 31 |
2. Побудова напрямків між визначеною вершиною графа та рештою його вершинами.
Будуємо напрямки N1 … N6 між вершиною 4 і рештою вершин графа (рис. 4.1).
N2 N3
2 3 5 N4
N
N5
4 3 7 N6
Рисунок 4.2
3. Побудова базового циклу та визначення його протяжності.
Будуємо базовий цикл
4 – 1 – 3 – 2 – 5 – 6 – 8 – 7 – 4,
протяжність якого за найкоротшими шляхами між сусідніми вершинами складає 25(по матриці найкоротших відстаней).
4. Коригування базового циклу.
Послідовність кроків коригування базового циклу наведена в табл. 4.2.
Таблиця 4.2
Крок | Перевірна група вершин | Протяжність шляхів | Цикл | Протяжність циклу | ||
i-k-l-j | i-l-k-j | i-k-l-j | i-l-k-j | |||
0 | -8-7-4 | 25 | ||||
1 | 4-1-3-2 | 4-3-1-2 | 9 | 8 | -8-7-4 | 24 |
2 | 3-1-2-5 | 3-2-1-5 | 8 | 16 | -8-7-4 | 24 |
3 | 1-2-5-6 | 1-5-2-6 | 15 | 18 | -8-7-4 | 24 |
4 | 2-5-6-8 | 2-6-5-8 | 11 | 12 | -8-7-4 | 24 |
5 | 5-6-8-7 | 5-8-6-7 | 11 | 6 | -6-7-4 | 19 |
6 | 8-6-7-4 | 8-7-6-4 | 6 | 8 | -6-7-4 | 19 |
7 | 6-7-4-3 | 6-4-7-3 | 6 | 10 | -6-7-4 | 19 |
8 | 7-4-3-1 | 7-3-4-1 | 6 | 10 | -6-7-4 | 19 |
Таким чином, оптимальним є маршрут
|
Из за большого объема этот материал размещен на нескольких страницах:
1 2 3 4 5 6 7 8 9 10 11 |
