Програмна реалізація методу подвійного обходу в середовищі delphi

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

Отже, після запуску проекту, на екрані появиться форма наступного вигляду:

Головне вікно проекту “Розв’язок задачі комівояжера методом подвійного обходу мінімального кістяка”

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

Заповнення елементів головної форми відповідними даними

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

zadacha_komivojazhera_metod_podvijnoho_obhody_delphi3
Вивід результатів роботи програми

Зауваження: кнопка «Очистити таблицю» видаляє всі введені користувачем значення і готує проект до нового прикладу.

Скачати delphi-проект Розв’язок задачі комівояжера методом подвійного обходу мінімального кістяка.

Залишити коментар

Your email address will not be published. Required fields are marked *

*