Введення
У 1859 р. У. Гамільтон придумав гру В«Навколосвітня подорожВ», що складається у відшуканні такого шляху, що проходить через усі вершини (міста, пункти призначення) графа, щоб відвідати кожну вершину одноразово і повернутися у вихідну. Шляхи, що володіють такою властивістю, називаються Гамільтона циклу. p align="justify"> Задача про гамільтонових циклах в графі отримала різні узагальнення. Одне з цих узагальнень - завдання комівояжера, що має ряд застосувань у дослідженні операцій, зокрема при вирішенні деяких транспортних проблем. p align="justify"> Задача комівояжера актуально й донині тому люди шукають найкоротші шляхи і витрати на ці найкоротші шляхи.
Мета курсового проекту: Рішення завдання комівояжера за допомогою алгоритму Дейкстри.
Завдання курсового проекту:
) Скласти математичну модель;
) Розробити схему алгоритму;
) Скласти програмний код;
) Провести аналіз отриманих результатів.
1. Постановка завдання
Визначити довжину (Q) найкоротшого маршруту (L) комівояжера.
Відстані (Q ij ) < span align = "justify"> між шістьма містами представлені в таблиці 1.
Таблиця 1 - Умова задачі
Город123456164121422263872034310111841281091651471191062220181610
У ході виконання курсового проекту потрібно написати програму, яка виконує рішення аналогічних завдань лінійного програмування за допомогою алгоритму Дейкстри.
2. Етапи рішення задачі
.1 Математична модель
Побудуємо математичну модель:
n - число міст.
X ij , i, j = 1 .. N - матриця витрат, де C < span align = "justify"> ij - витрати на перехід з i-го міста в j-й.
X ij - матриця переходів з компонентами:
X ij = -1, якщо комівояжер робить перехід з i-го міста в j-й,
X ij = 0, якщо не здійснює переходу,
де i, j = 1 .. N і i В№ j.
Критерій:
, (...
