Міністерство освіти і науки Російської Федерації
Федеральне державне бюджетне освітня установа
вищої професійної освіти
«Магнітогорський державний технічний
університет ім. Г.І. Носова »
Багатопрофільний коледж
ТЕМА: «дерев'яний алгоритм вирішення задачі комівояжера»
Пояснювальна записка до курсового проекту
КП 230105.24.00.00. ПЗ
Керівник проекту
Л.А Фетисова
Розробив студент
Групи ПР - 08 .......... ....... ...... ..Н.Т. Сайфулін
Магнітогорськ, 2012
Зміст
Введення
1. Загальна частина
1.1 Дерев'яний алгоритм
.2 Приклад
.3 Рішення задач засобами Excel
. Алгоритм рішення задачі
.1 Алгоритм основної програми
.2 Алгоритм підпрограми
.3 Лістинг програми
Література
Введення
У 1859р. Сер Вільям Гамільтон, знаменитий математик, що дав світові теорію комплексного числа і кватерниона, запропонував дитячу головоломку, в якій пропонувалося зробити «кругове подорож» по 20 містам, розташованих в різних частинах земної кулі.
Гамильтонова завдання про мандрівника нерідко перетворюється в задачу про комівояжера. Комівояжер - не вільне мандрівний турист, а ділова людина, обмежений тимчасовими, грошовими або будь - якими іншими ресурсами. Гамильтонова завдання може стати завданням про комівояжера, якщо кожне з ребер постачити числовою характеристикою. Це може бути кілометраж, час на дорогу, вартість квитка, витрата пального і т.д. Таким чином, умовні характеристики дадуть числовий ряд, елементи якого можуть бути розподілені між ребрами як завгодно.
Завдання про комівояжера, який повинен об'їхати всі доручені йому міста і повернутися назад за найкоротший термін або з найменшими витратами на проїзд. Це одна з типових завдань, що вирішуються методом динамічного програмування. Про складність її говорить такий факт: якщо міст - 4, то число можливих маршрутів одно 6, а вже при 11 містах існує більше 3,5 млн. Допустимих маршрутів. У загальному випадку, коли число міст «n» кількість маршрутів одно (n - 1) !. Завдання полягає в пошуку скорочених способів розрахунку, що дозволяють відмовлятися від суцільного перебору можливих маршрутів.
. Загальна частина
. 1 Дерев'яний алгоритм
динамічний програмування алгоритм завдання
Етапи знаходження дерев'яного алгоритму:
) Побудова остовного дерева
) Побудова ейлерового циклу
) Знаходження туру
) Для побудови остовного дерева використовується алгоритм Прима
Алгоритм Прима володіє тим властивістю, що ребра в безлічі завжди утворюють єдине дерево. Дерево починається з довільною кореневої вершини R і росте до тих пір, поки не охопить всі вершини. На кожному кроці до дерева додається легке ребро, що з'єднує дерево і окрему вершину з частини графа. Дане правило додає тільки безпечні ребра; отже, по завершенні алгоритму ребра утворюють мінімальне остовное дерево. Дана стратегія є жадібною, оскільки на кожному кроці до дерева додається ребро, яке вносить мінімально можливий внесок у загальну вагу.
Приклад виконання алгоритму Прима:
. Початкова фаза. Мінімальний покриваючий ліс складається з кореня і порожньої безлічі ребер.
Малюнок 1.
. Ребро з вагою 6 є мінімальним ребро, що з'єднує корінь з іншими вершинами. Додаємо його до мінімального остову.
Малюнок 2.
. Наступне безпечне ребро з вагою 11. Додаємо його.
Малюнок 3.
- 8. Додаємо інші безпечні ребра.
Малюнок 4.
Малюнок 5.
Малюнок 6.
Малюнок 7.
Малюнок 8.
Ребра з вагою 17, 19 і 25 - не безпека. Їх кінці лежать в одній компоненті зв'язності. Ребро з вагою 21 - безпечне, тому додаємо його. Мінімальна остовное дерево побудовано.
. Побудова ейлеровимі циклу
Якщо ...
