Підсумкове завдання 3

Задача комівояжера.

Є 5 міст. Дана матриця відстаней (вартості):

Потрібно знайти гамільтонів контур найменшої довжини.

Розв’язання.

І етап – операція зведення.

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

ІІ етап – операція галуження.

Галуження треба проводити за дугою (5, 3), оскільки цей елемент має найбільшу позначку ().

ІІІ етап – побудова зведених матриць.

Кінцеві множини першого кроку Х₁₁ і Х₁₂. Галуженню підлягає Х₁₂ (з мінімальною оцінкою).

Зведемо матрицю С₂:

Галуження буде за дугою (4, 2).

Галуженню підлягає Х₂₂ за дугою (3, 4):

Галуженню підлягає Х₃₂ за дугою (2, 1):

Намалюємо отримане дерево:

Запишемо гамільтонів контур:

(5, 3) (4, 2) (3, 4) (2, 1) (1, 5) f(x) = 6+7+1+10+10 =34.