Проблема комівояжера
Задачі комівояжера стосуються комівояжера та набору міст. Продавець повинен відвідати кожне з міст, починаючи з певного (наприклад, рідного міста) і повертатися в те саме місто. Складність проблеми полягає в тому, що комівояжеру потрібно мінімізувати загальну тривалість поїздки.
Припустимо, що міста дорівнюють x 1 х 2 ..... x п де вартість c ij позначає вартість проїзду з міста x i до х j . Завдання комівояжера полягає в тому, щоб знайти маршрут, який починається і закінчується в точці x 1 що візьмуть у всіх містах з мінімальними витратами.
приклад: Газетний агент щодня доставляє газету у визначений район таким чином, щоб він мав охопити всі будинки у відповідному районі з мінімальними витратами на дорогу. Обчисліть мінімальну вартість поїздки.
Зона, призначена агенту, куди він повинен скинути газету, показана на рис.
Рішення. Матриця суміжності вартості графа G має такий вигляд:
вартість ij =
Тур починається з району H 1 а потім виберіть зону мінімальної вартості, доступну з H 1 .
Позначте область H 6 тому що це зона мінімальних витрат, доступна з H 1 а потім виберіть зону мінімальної вартості, доступну з H 6 .
Позначте область H 7 тому що це зона мінімальних витрат, доступна з H 6 а потім виберіть зону мінімальної вартості, доступну з H 7 .
Позначте область H 8 тому що це зона мінімальних витрат, доступна з H 8 .
Позначте область H 5 тому що це зона мінімальних витрат, доступна з H 5 .
Позначте область H 2 тому що це зона мінімальних витрат, доступна з H 2 .
Позначте область H 3 тому що це зона мінімальних витрат, доступна з H 3 .
Позначте область H 4 а потім виберіть зону мінімальної вартості, доступну з H 4 це Х 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.
