Page 117 - 6197

Для отримання верхньої оцінки скористаємося «жадібним»
*
алгоритмом : «йди в найближче місто, де ще не був».
Маршрут комівояжера починається в пункті 1 (див. табл.
2.8). Найближчим пунктом є пункт під номером 4: c  16 .
14
Тепер маршрут буде продовжуватись від пункту 4 до
найближчого пункт, який визначиться найменшим значенням
елементу у 4 рядку табл. 2.8. Таким елементом буде - c  16 .
42
Отже, комівояжер після пункту 4 повинен відвідати пункт 2.
Наступним пунктом після пункту 2 буде пункт 4, якому
відповідає найменше значення елементу c  16 . Але
24
комівояжер уже відвідав цей пункт. Тому в другому рядку
вибираємо наступний найменший елемент - c  16 .
23
Продовжуючи процес пошуку верхньої оцінки приходимо
до висновку, що
6
5
2
4
3
i  1       1 і
1
L   16 16 16 0 5 12 65i        .
1
Отже, величина віддалі в оптимальному маршруті буде
знаходитись між значеннями 48 і 65, тобто
*
48 L   65i  .
  1
Знаходимо  . Аналізуємо перший рядок матриці C і
ij 2
знаходимо в ньому нульовий елемент. Таким елементом буде
  1
c . У першому рядку і четвертому стовпці матриці
14
  1
C знаходимо відповідно найменші елементи і знайдені
2
значення додаємо, тобто
  1
  1
  min :c  min :c  10 0 10  .
14 1 j 4 i
j 4 i 1

*
Горбійчук М. І. Алгоритми і методи обчислень; навчальний посібник / М.
І. Горбійчук. – Івано-Франківськ: Факел, 2014. – 309 с. (с. 34 – 38)
117