Зміст Вступ 3
Постановка задачі 4
Метод рішення 5
Мова програмування 7
Опис алгоритму 8
Опис основних структур даних 12
Опис інтерфейсу з користувачем 14
Висновок 16
Література 17
Текст програми 18
Введення
Завдання полягає в тому, щоб комівояжер (торговець) обійшов всі намічені міста один раз і в такому порядку, щоб його шлях був найменшим.
Це завдання зацікавила мене тому, що її рішення цікаво з точки зору
програмування і складання алгоритму. Важливо знаходження такого алгоритму, який дозволить найбільш оптимально вирішити задачу.
Зараз рішення даної задачі необхідно в багатьох областях пов'язаних із замкнутими і при цьому жорстко пов'язаними за часом системами, такими як: конвеєрне виробництво, багатоопераційні обробні комплекси, суднові та залізничні вантажні системи, перевезення вантажів по замкнутому маршруту, розрахунок авіаційних ліній.
Тому дана проблема на сучасному етапі розвитку суспільства має не найостанніше за значимістю місце.
Постановка завдання
Є N міст, які повинен обійти комівояжер з мінімальними витратами. При цьому на його маршрут накладається два обмеження:
· Маршрут повинен бути замкненим, тобто комівояжер повинен повернутися в те
місто, з якого він почав рух;
· У кожному з міст комівояжер повинен побувати точно один раз, тобто треба обов'язково обійти всі міста, при цьому не побувавши в жодному місті двічі.
Для розрахунку витрат існує матриця умов, що містить
витрати на перехід з кожного міста у кожний, при цьому вважається, що можна перейти з будь-якого міста в будь-який, окрім
того ж самого (в
матриці діагональ заповнена нулями). Метою рішення є знаходження маршруту, що задовольняє всім умовам і при цьому має мінімальну суму витрат.
Метод рішення
Для початку слід сказати, що в основі будь-якого методу вирішення даної задачі лежить повний перебір всіляких варіантів шляхів. [2]
Ми проходимо по кожному маршруту: одні відкидаємо, інші порівнюємо з мінімальним шляхом. В кінці перебору ми отримуємо найкоротший шлях.
Особливістю цього завдання є те, що зі збільшенням кількості міст зростає загальна кількість різних комбінацій проходження шляху. А разом з тим зростає і час розрахунку результату. Тому головним рішенням оптимізації алгоритму можна звести до того, щоб під час обчислень відкидати свідомо не мінімальні шляху. Необхідно поставити
такий критерій, який відсікав б зайві гілки в дереві пошуку найкоротшого шляху.
Для пояснення мого варіанту розв'язання задачі слід ввести кілька понять. Проміжну довжину шляху можна визначити наступним чином: уявімо, що торговець вибрав якийсь шлях,
він вийшов з першого міста і зараз знаходиться в якомусь місті
i. Тоді все пройдене відстань з початку до міста
i будемо називати проміжна довжина шляху. Якщо виходити з того, що торговець у кожен момент часу буде перебувати в якомусь
i-му місті, то завжди можна підрахувати яку відстань він пройшов з початку до цього міста, тобто проміжну довжину шляху.
Мінімальним шляхом будемо називати маршрут, що проходить по всіх містах і має мінімальну довжину.
Мій критерій будується на одному простому твердженні: якщо проміжна довжина шляху більше мінімального шляху, тоді очевидно наступне:
1. проміжна довжина буде рости, коли торговець буде рухатися до кінцевого місту,
2. а значить довжина всього шляху буде більше довжини мінімального маршруту.
отже такий маршрут можна відкинути.
Проміжна довжина шляху = 102
|
Пояснення показані на малюнку 1.
У даній програмі використовується наступний критерій: при переході від одного міста до іншого розраховується проміжна довжина шляху, і якщо вона більше поточного мінімального шляху, то обчислення з даної гілки припиняються. Таким чином, відсікаються зайві гілки.
Рішення даного завдання призводить до перебору можливих варіантів шляху, але критерії такого роду можуть значно скоротити обчислення і зменшити час
роботи програми.
Мова програмування
Для написання програми була обрана
мова Сі + + з наступних причин:
1. Середовище програмування Windows-додатків Microsoft Visual C + + 6.0 дозволяє в моїй завданню наочно відобразити карту міст і схему їх з'єднання.
2. Це одна з мов, в якому я непогано розбираюся. Тому мені зручніше писати програму з допомогою Visual C + +.
Опис алгоритму
У програмі міститься рекурсивна
функція, яка забезпечує перебір можливих шляхів для пошуку найкоротшого.
Саме тут укладено алгоритм вирішення задачі «комівояжера». Розглянемо його докладніше:
1. Для кожного міста
(i = від
1 до
n), де ми ще не були.
2. Припустимо, що ми прийшли в якесь місто
i. Позначаємо його, що ми тут вже були.
3. Підраховуємо довжину пройденого шляху.
4. Якщо вона більше ніж довжина мінімального шляху,
4.1. Тоді немає сенсу йти по цьому шляху далі.
4.1.1. позначаємо місто як не відвіданий, виходимо з міста.
4.2. Інакше,
4.2.1.
Якщо ми в кінці шляху
4.2.1.1.
Тоді, порівнюємо з мінімальним шляхом, якщо він менше найкоротшого шляху, тоді мінімальний шлях = найкоротший шлях.
4.2.1.2.
Інакше переходимо до пункту 1.
5. Переходимо до наступного міста, де ми не були.
Слід розглянути один з основних моментів алгоритму, пов'язаних з перебором маршрутів. З малюнка № 2 можна простежити порядок формування шляхів і розглянути на конкретному прикладі, як
працює алгоритм. Тут наведено приклад для 4 міст. Зупинимося на малюнку по докладніше.
А) Ми починаємо шлях з пункту 1. У нашому маршруті записаний перший місто. Розглядаємо ті міста, де ми не були: це 2, 3 і 4. Спочатку переходимо до другого.
Б) Додаємо до маршрутом 2 місто. Дивимося, чи можна кудись перейти з другого міста. Можна відвідати третій і четвертий. Ми вибираємо третє місто.
В) Ставимо на третє місце в нашому маршруті місто 3. Далі ми дивимося, куди можна відправитися - до пункту 4.
Г) На
четверте місце в маршруті ставимо місто 4. Тут ми бачимо, що в нашому маршруті заповнені всі чотири місця і значить наш шлях закінчений. Порівнюємо довжину нашого шляху з мінімальним. Потім ми виходимо назад з пункту 4 до пункту 3 і в маршруті переміщаємося на третє місце. Дивимося, що в місті 3 ми були, тоді беремо наступний не відвіданий місто - четвертий.
Д) Ставимо на третє місце маршруту четверте місто. З четвертого пункту можна відвідати тільки третій.
Е) Прийшли в третій пункт. Ставимо на четверте місце маршруту місто 3. Бачимо, що всі чотири місця в нашому шляху заповнені і значить шлях закінчений. Порівнюємо довжину нашого шляху з мінімальним. Виходимо тому - з пункту 3 до пункту 4 і в маршруті переміщаємося на третє місце. Бачимо що тут теж немає не відвіданих міст. Знову переходимо на рівень вгору: з пункту 4 в пункт2 і в маршруті переміщаємося на друге місце. У пункті 2 ми були, але залишилися не відвідуванними міста 3 і 4. Переходимо до третьої. На друге місце в маршруті записуємо третє місто.
Ж) Звідси можна потрапити у другий і четвертий. Переходимо до другого. На третє місце в маршруті ставимо друге місто. І так далі.
З наведеного прикладу вже можна виділити, як алгоритм перебирає шляху. Він діє за такою схемою:
0. Початкове значення j = 1 (перше місце в маршруті).
1. Ми знаходимося в місті k.
2. Для кожного міста (i = від 1 до n)
3. Розглядаємо місто i.
4. Якщо це місто ще не відвідано,
4.1. тоді переходимо до міста i; j збільшуємо на одиницю. Додаємо номер міста до маршруту на місце j. Позначаємо місто як відвіданий. Переходимо до пункту 1 (k = i).
4.2. інакше йти
нікуди, тобто всі міста ми відвідали.
4.2.1. якщо j = кількості міст (n), тобто ми дісталися до останнього пункту в маршруті і наш шлях сформований, тоді порівнюємо довжину шляху з довжиною мінімального маршруту.
4.2.2. Позначаємо місто як не відвіданий і виходимо з нього. Зменшуємо j на одиницю.
5. Беремо наступний
місто (i = i +1).