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