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