Задачі комівояжера стосуються комівояжера та набору міст. Продавець повинен відвідати кожне з міст, починаючи з певного (наприклад, рідного міста) і повертатися в те саме місто. Складність проблеми полягає в тому, що комівояжеру потрібно мінімізувати загальну тривалість поїздки.
Припустимо, що міста дорівнюють x1х2..... xпде вартість cijпозначає вартість проїзду з міста xiдо хj. Завдання комівояжера полягає в тому, щоб знайти маршрут, який починається і закінчується в точці x1що візьмуть у всіх містах з мінімальними витратами.
приклад: Газетний агент щодня доставляє газету у визначений район таким чином, щоб він мав охопити всі будинки у відповідному районі з мінімальними витратами на дорогу. Обчисліть мінімальну вартість поїздки.
Зона, призначена агенту, куди він повинен скинути газету, показана на рис.
Рішення. Матриця суміжності вартості графа G має такий вигляд:
вартістьij=
Тур починається з району H1а потім виберіть зону мінімальної вартості, доступну з H1.
Позначте область H6тому що це зона мінімальних витрат, доступна з H1а потім виберіть зону мінімальної вартості, доступну з H6.
Позначте область H7тому що це зона мінімальних витрат, доступна з H6а потім виберіть зону мінімальної вартості, доступну з H7.
Позначте область H8тому що це зона мінімальних витрат, доступна з H8.
Позначте область H5тому що це зона мінімальних витрат, доступна з H5.
Позначте область H2тому що це зона мінімальних витрат, доступна з H2.
Позначте область H3тому що це зона мінімальних витрат, доступна з H3.
Позначте область H4а потім виберіть зону мінімальної вартості, доступну з H4це Х1Отже, використовуючи жадібну стратегію, ми отримуємо наступне.
4 3 2 4 3 2 1 6 H<sub>1</sub> → H<sub>6</sub> → H<sub>7</sub> → H<sub>8</sub> → H<sub>5</sub> → H<sub>2</sub> → H<sub>3</sub> → H<sub>4</sub> → <sub>H<sub>1</sub></sub>.
Таким чином, мінімальна вартість проїзду = 4 + 3 + 2 + 4 + 3 + 2 + 1 + 6 = 25
Матроїди:
Матроїд — це впорядкована пара M(S, I), яка задовольняє такі умови:
- S — скінченна множина.
- I — непорожня сім’я підмножин S, яка називається незалежними підмножинами S, така що B ∈ I і A ∈ I. Ми говоримо, що I є спадковою, якщо вона задовольняє цю властивість. Зауважимо, що порожня множина ∅ обов’язково є членом I.
- Якщо A ∈ I, B ∈ I і |A|<|b|, then there is some element x ∈ b ? a such that a∪{x}∈i. we say m satisfies the exchange property.< li>
Ми кажемо, що матроїд M (S, I) є зваженим, якщо існує асоційована вагова функція w, яка призначає строго додатну вагу w (x) кожному елементу x ∈ S. Вагова функція w поширюється на підмножину S шляхом підсумовування :
w (A) = ∑<sub>x∈A</sub> w(x)
для будь-якого A ∈ S.