![]() Главная страница Случайная страница КАТЕГОРИИ: АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Підсумкове завдання 3
Задача комівояжера. Є 5 міст. Дана матриця відстаней (вартості): Потрібно знайти гамільтонів контур найменшої довжини. Розв’язання. І етап – операція зведення. Віднімаємо з усіх елементів кожного рядка матриці С мінімальний елемент цього рядка, від усіх елементів кожного стовпчика матриці, що отримали, віднімаємо мінімальний елемент цього стовпця. Матриця, що виникла, є зведеною. Позначимо її
ІІ етап – операція галуження. Галуження треба проводити за дугою (5, 3), оскільки цей елемент має найбільшу позначку ( ІІІ етап – побудова зведених матриць.
Кінцеві множини першого кроку Х11 і Х12. Галуженню підлягає Х12 (з мінімальною оцінкою).
Зведемо матрицю С2:
Галуженню підлягає Х22 за дугою (3, 4):
Галуженню підлягає Х32 за дугою (2, 1): Намалюємо отримане дерево: Запишемо гамільтонів контур:
(5, 3) (4, 2) (3, 4) (2, 1) (1, 5) f(x) = 6+7+1+10+10 =34.
|