Анотація
Задача про комівояжера полягає в тому, щоб об'їхати задані міста по одному разу в такому порядку, щоб пройдена відстань було мінімальним.
Така завдання актуальна в багатьох областях, таких як автомобільні, суднові і залізничні перевезення, розрахунок авіаційних ліній, конвеєрне виробництво. <В
Зміст
В
Введеніе3
Постановка задачі4
Метод решенія5
Мова программірованія7
Опис алгорітма8
Опис основних структур даних 12
Опис інтерфейсу з пользователем14
Заключеніе16
Література17
Текст программи18
В В В В В Введення
Задача полягає в тому, щоб комівояжер (торговець) обійшов всі намічені міста одного разу і в такому порядку, щоб його шлях був найменшим.
Ця завдання зацікавила мене тому, що її рішення цікаво з точки зору програмування і складання алгоритму. Важливо знаходження такого алгоритму, який дозволить найбільш оптимально вирішити завдання.
Зараз рішення даної задачі необхідно в багатьох областях пов'язаних з замкнутими і при цьому жорстко пов'язаними за часом системами, такими як: конвеєрне виробництво, багатоопераційні оброблювальні комплекси, суднові і залізничні навантажувальні системи, перевезення вантажів по замкнутому маршруту, розрахунок авіаційних ліній.
Тому дана проблема на сучасному етапі розвитку суспільства має не найостанніше за значимістю місце.
В
Постановка завдання
В
Мається N міст, які повинен обійти комівояжер з мінімальними витратами. При цьому на його маршрут накладається два обмеження:
В· маршрут повинен бути замкнутим, тобто комівояжер повинен повернутися в те місто, з якого він почав рух;
В· в кожному з міст комівояжер повинен побувати точно один раз, тобто треба обов'язково обійти всі міста, при цьому не побувавши ні в одному місті двічі.
Для розрахунку витрат існує матриця умов, що містить витрати на перехід з кожного міста в кожен, при цьому вважається, що можна перейти з будь-якого міста в будь-який, крім того ж самого (в матриці діагональ заповнена нулями). Метою рішення є знаходження маршруту, що задовольняє всім умовам і при цьому має мінімальну суму витрат.
В
Метод рішення
Для початку слід сказати, що в основі будь-якого методу вирішення даної задачі лежить повний перебір всіляких варіантів шляхів. [2]
Ми проходимся по кожному маршруту: одні відкидаємо, інші порівнюємо з мінімальним шляхом. Наприкінці перебору ми отримуємо найкоротший шлях. p> Особливістю цього завдання є те, що зі збільшенням кількості міст зростає загальне кількість різних комбінацій проходження шляху. А разом з тим зростає і час розрахунку результату. Тому головним рішенням оптимізації алгоритму можна звести до того, щоб під час обчислень відкидати свідомо не мінімальні шляху. Необхідно задати такий критерій, який відтинав...
