Знаходження розв'язку задачі комівояжера методом осереднених коефіцієнтів

Розв'язок задачі комівояжера, за методом осереднених коефіцієнтів, та ксамо, як і за методом редекції рядків і колонок, ділиться на (n-2) етапи (у межах кожного етапу, алгоритм розрахунків однаковий).

Отже, розглянемо класичну задачу комівояжера, і знайдемо її розв'язок методом осереднених коефіцієнтів. Комівояжер повинен обїхати 5 міст, побувати в кожному по одному разу і повернутися у початкове. При цьому витрати на переміщення між містами повинні бути мінімальними. Тарифи містяться в наступній таблиці.

Тарифи на переміщення між містами

Рис. 1. Тарифи на переміщення між містами.

Перший етап: обчислюємо середнє значення довжини шляху для кожного рядка і колонки таблиці.

Читати повністю

Розв'язок задачі комівояжера на Delphi методом редукції рядків і колонок

У задачі комівояжера, для формування оптимального маршруту, який включає в себе n міст, необхідно вибрати один кращий з ( n −1) ! варіантів за певним критерієм (мінімальні витрати, мінімальна довжина маршруту). Для рішення даної проблеми, будемо використовувати програму, яка реалізована в середовищі Borland Delphi 7, і для формування маршруту використовує метод редукції рядків і колоное.

Інтерфейс проекту подібний до інтерфейсеу програм, які ми реалізовували для пошуку дерева мінімальної вартості для неорієнтованих графів (алгоритм Примаалгоритм Крускала). Тобто від користувача вимагається створити матрицю тарифів (заздалегіть вказавши її розмірність) і заповнити її необхідними даними. Після чого, для того щоб знайти шуканий маршрут, потрібно (n-2) раз натиснути кнопку «Знайти оптимальний шлях». Тобто кожен раз ми доповнюємо маршрут новим містом, поки не отримаємо кінцевий розв'язок, який і являтиметься оптимальним маршрутом.

metod_redukcii_radkiv_i_kolonok_delphi1

Результат виконання першого етепу методу редукції рядків і колонок

Читати повністю

Роз'вязання задачі комівояжера за методом редукції рядків і колонок

Процес знаходження оптимального маршруту, в задачі комівояжера, методом редукції рядків і колонок розкладається на (n-2) етапа. У межах кожного етапу алгоритм розрахунків однаковий.

Для наглядності, розглянемо конкретний випадок задачі комівояжера, а саме, комівояжер повинен обїхати 5 міст, побувавши в кожному по одному разу і повернутися у початкове. При цьому витрати повинні бути мінімальними.

Тарифи на переміщення між містами знаходяться в наступній таблиці:

Метод редукції рядків і колонок

Перш ніж приступити до першого етапу, знайдемо можливу верхню межу функції мети. Для цього, вибираємо довільний маршрут metod_redukcii_radkiv_i_kolonok19, для якого обчислюємо значення функції Метод редукції рядків і колонок. Значення функції мети Метод редукції рядків і колонок повинно бути меншим за Метод редукції рядків і колонок.

Читати повністю

Задача комівояжера. Математична постановка задачі

Основна ідея задачі комівояжера полягає у наступному: комівояжер повинен проїхати n міст. Для того, щоб зменшити витрати, він повинен побудувати маршрут таким чином, щоб побувати в кожному місті по одному разу і повернутися у початкове.

Математична постановка задачі коміваяжера має наступний вигляд:

Задача комівояжерапри обмеженнях:

Задача комівояжера — обмеження на одноразовий виїзд з міста.

Задача комівояжера — обмеження на одноразовий в'їзд в місто.

де Задача комівояжера — матриця відстаней між усіма містами Задача комівояжера.

Читати повністю

Алгоритм Крускала

Алгоритм Крускала, так само, як і алгоритм Прима призначений для пошуку дерева мінімальної вартості неорієнтованого графа. Основна відмінність між даними алгоритмами полягає в тому, що пошук дерева мінімальної довжини за алгоритмом Крускала починається з n дерев, кожне з яких складається з однієї вершин. І на кожному кроці виконуємо операцію об'єднання двох дерев, використовуючи для цього ребро найкоротшої довжини. Процес продовжується поки не отримаємо єдине дерево, яке охоплює всі n вершин вхідного графа, і не містить циклів.

Розглянемо деякий неорієнтований граф, і спробуємо побудувати для нього дерево мінімальної вартості за вище розглянутим алгоритмом.

Алгоритм Крускала

Крок 1: вибираємо ребро найменшої вартості: 1−3=1. В результаті отримаємо одне дерево, яке складається з двох вершин і одного ребра (на малюнку позначено зеленим кольором) та 4 дерева, які містять по одній вершині.

Читати повністю

Знаходження дерева мінімальної вартості за алгоритмом Крускала на Delphi(2)

Програма знаходить дерево мінімальної вартості неорієнтованого графа використовуючи алгоритм Крускала. Побудова графа здійснюється у візуальному редакторі та з допомогою матриці суміжності.

Головна форма даного проекту аналогічна формі програми, яка реалізує алгоритм Прима, тому більш детально переглянути процес побудови графа та знаходження дерева мінімальної вартості можна перейшовши за посиланням алгоритм Прима на Delphi(2).

Алгоритм Крускала на Delphi

Читати повністю

Алгоритм Прима

Алгоритм Прима полягає в побудові дерева, яке на кожному кроці збільшується на одне ребро. Тобто, побудова починається з графа, який складається з однієї вершини до якої додаємо n-1-ну вершину. При цьому, кожен раз, вибираємо мінімальне ребро, яке з'єднює вершину, що вже належить дереву мінімальної вартості, з вершиною, яка ще не міститься в даному дереві.

Розглянемо деякий неорієнтований граф, і спробуємо знайти для нього дерево мінімальної вартості за вище розглянутим алгоритмом.

algoritm_prima1

В якості початкової вибираємо будь-яку вершину графа, нехай вона буде під номером 1. Вершина №1 з'єднана з вершинами  №2, №3 і №4. Вибираємо серед них ту, яка має з вершиною 1 ребро найменшої довжини. В нашому прикладі такою є вершина 3 (довжина ребра рівна одиниці). Додаємо її до дерева.

Читати повністю

« Попередня сторінкаНаступна сторінка »