1)
де Сij - матриця вартості переходів,
Xij - матриця переходів, де xij = 0, якщо перехід здійснений і xij = 1 в іншому випадку
Обмеження:
, i = 1 .. N (2)
, j = 1 .. N (3)
Ui - Uj + N Г— Xi j ВЈ N-1, i, j = 1 .. N, i В№ j. (4)
, k = 1 .. N, t = k-1 (5)
Умова (2) означає, що комівояжер з кожного міста виїжджає лише один раз; умова (3) - в'їжджає в кожне місто тільки один раз; умова (4) - забезпечує замкнутість маршруту, що містить N міст, і не містить замкнутих внутрішніх петель; умова (5) - принцип трикутника: раніше обраний шлях виявився довшим попереднього.
.2 Розробка алгоритму
Задача комівояжера є однією із знаменитих завдань теорії комбінаторики. Вона була поставлена ​​в 1934 році, і про неї, як про Велику теорему Ферма обламували зуби кращі математики. У своїй області (оптимізації дискретних завдань) завдання комівояжера служить своєрідним полігоном, на якому випробовуються всі нові методи. У даному курсовому проекті реалізується завдання комівояжера методом алгоритму Дейкстри.
У 1959 р. Голландський математик Дейкстра запропонував алгоритм, який вирішує завдання комівояжера для будь матриці вихідний даних: симетричною, несиметричний і змішаної (відсутні деякі ребра графа).
Суть завдання полягає в тому, щоб знайти найкоротший замкнутий шлях обходу декількох міст і повернутися назад у вихідний місто, при цьому виконуючи дві перевірки:
) Довжина знайденого ребра графа повинна бути менше або дорівнює симетричному ребру графа. В іншому випадку вибирається симетричне ребро
) трикутника: раніше обраний шлях виявився довшим попереднього.
.3 Опис програми
Для початку обчислень необхідно ввести кількість міст.
На малюнку 1 показаний етап вибору кількості міст.
програма завдання комівояжер тестування
В
Рисунок 1 - Вибір кількості міст
Після введення даних, необхідно натиснути кнопку В«EnterВ». Після цього програма складе матрицю міст, після чого нам треба ввести з якого міста будемо стартувати, і закінчувати, і зробить розрахунок довжини шляху і порядок обходу міст. Коли програма завершить свій розрахунок, то в блоці відповіді з'являться дані кінцевого результату. br/>В
Рисунок 2 - Консоль програми після розрахунку даних
2.4 Тестування програми
Визначити довжину (Q) найкоротшого маршруту (L) ...
