Метод осереднених коефіцієнтів на Delphi

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

Головне вікно програми містить одне поле вводу, чотири кнопки та статусний рядок, в який виводяться результати виконання програми, тобто оптимальний маршрут.

Головне вікно програми

Головне вікно програми методу осереднених коефіцієнтів

Для того, щоб отримати шуканий розв'язок, потрібно в текстове поле ввести кількість міст і створити матрицю тарифів натиснувши кнопку «Створити матрицю». Після цього, як матриця створена, заповнюємо її відповідними даними, активуємо кнопку «Після введення даних натиснути». Дана кнопка створює копію таблиці тарифів. Це зроблено для того, щоб на екрані збереглися вхідні дані введені користувачем (обчислення проводяться над таблицею «копією»).

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

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

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

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

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

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

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

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