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

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

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

metod_redukcii_radkiv_i_kolonok_delphi1

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

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

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

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

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

Вивід оптимального маршруту для задачі комівояжера

Вивід оптимального маршруту для задачі комівояжера

Скачати метод редукції рядків і колонок.

Матеріал був корисним, поділись в соціальних мережах:

Якщо тобі сподобалась дана тема, залиш свій коментар