Курсова робота на тему : «ЗАДАЧА КОМІВОЯЖЕРА ТА МЕТОДИ ЇЇ РОЗВ’ЯЗАННЯ»

Зміст

 

 

Вступ    1

1.1.Задача комівояжера. Загальний опис    3

1.2. Розв’язання задачі комівояжера    5

1.2.1. Жадібний алгоритм    5

1.2.2. Дерев’яний алгоритм.    9

1.2.3. Метод віток і границь    13

1.2.4. Метод розв’язання задачі комівояжера    20

Практичне застосування задачі комівояжера    23

Висновки    25

Список використаних джерел    26

 

 

 

Вступ

Комбінаторика – розділ математики, присвячений вирішенню завдань вибору і розташування елементів деякої, зазвичай кінцевої множини відповідно до заданих правил.

Кожне таке правило визначає спосіб побудови деякої конструкції з елементів початкової множини, названою комбінаторною конфігурацією. Тому можна сказати, що метою комбінаторного аналізу є вивчення комбінаторних конфігурацій. Це вивчення включає питання існування комбінаторних конфігурацій, алгоритми їх побудови, оптимізацію таких алгоритмів, а також вирішення завдань перерахування, зокрема визначення числа конфігурацій даного класу. Простим прикладом комбінаторних конфігурацій є перестановки, поєднання і розміщення.

Це завдання зацікавило мене тому, що його рішення цікаве з погляду програмування і складання алгоритму. Важливе знаходження такого алгоритму, який дозволить найбільш оптимально вирішити завдання.

Повернення інтересу до комбінаторного аналізу відноситься до 50-х років ХХ ст у зв’язку з бурхливим розвитком кібернетики і дискретної математики і широким використанням електронно-обчислювальної техніки. У цей період активізувався інтерес до класичних комбінаторних завдань.

Класичні комбінаторні завдання – це завдання вибору і розташування елементів кінцевої множини, що мають формулювання розважального змісту типа головоломок.

У 1859 р. У. Гамільтон придумав гру «Кругосвітня подорож», що полягає у відшуканні такого шляху, що проходить через всі вершини (міста, пункти призначення) графа, зображеного на рис. 1, щоб відвідати кожну вершину одноразово і повернутися в початкову. Шляхи, що володіють такою властивістю, називаються гамільтоновими циклами.

Завдання про гамільтонові цикли в графі отримало різні узагальнення. Одне з цих узагальнень – задача комівояжера, що має ряд застосувань в дослідженні операцій, зокрема при вирішенні деяких транспортних проблем.

Зараз розв’язання даної задачі необхідне в багатьох областях пов’язаних із замкнутими і при цьому жорстко зв’язаними за часом системами, такими як: конвеєрне виробництво, багатоопераційні оброблювальні комплекси, суднові і залізничні вантажні системи, перевезення вантажів по замкнутому маршруту, розрахунок авіаційних ліній. Тому дана проблема на сучасному етапі розвитку суспільства має важливе значення.

 

1.1.Задача комівояжера. Загальний опис

 

Задача комівояжера (надалі скорочено — ЗК) є одна із знаменитих завдань теорії комбінаторики. Вона була поставлена в 1934 році, і об неї, як і об Велику теорему Ферма обламували зуби кращі математики. У своїй області (оптимізації дискретних завдань) ЗК служить своєрідним полігоном, на якому випробовуються все нові методи.

Постановка завдання наступна.

Комівояжер (бродячий торговець) повинен вийти з першого міста, відвідати по разу в невідомому порядку міста 2,1,3..n і повернутися в перше місто. Відстані між містами відомі. У якому порядку слід обходити міста, щоб замкнутий шлях (тур) комівояжера був найкоротшим?

Щоб привести завдання до наукового вигляду, введемо деякі терміни. Отже, міста пронумеровані числами jÎТ=(1,2,3..n). Тур комівояжера може бути описа-ний циклічною перестановкою t=(j1,j2..,jn,j1), причому все j1..jn – різні номери; що повторюється на початку і в кінці j1, показує, що перестановка зациклена. Відстані між парами вершин Сij утворюють матрицю С. Задача полягає в тому, щоб знайти такий тур t, щоб мінімізувати функціонал.

Щодо математизованого формулювання ЗК доречно зробити два зауваження. По-перше, в постановці Сij означали відстані, тому вони мають бути невідємними, тобто для всіх j мають місце такі нерівності:

Сij³0; Cjj=∞                     1)

останню рівність означає заборона на петлі в турі).По друге симетричними, тобто для всіх i,j:

Сij= Сji.                      2)

і задовольняти нерівності трикутника, тобто для всіх:

Сij+ Сjk³Cik                  3)

У математичній постановці іде мова про довільну матрицю. Зроблено це тому, що є багато прикладних завдань, які описуються основною моделлю, але всім умовам (1) — (3) не задовольняють. Особливо часто порушується умова (2) (наприклад, якщо Сij — не відстань, а плата за проїзд: часто в одну сторону квиток коштує одну ціну, а назад — іншу). Тому ми розрізнятимемо два варіанти ЗК: симетричне завдання, коли умова (2) виконана, і несиметричну – інакше. Умови (1) —(3) за умовчуванням вважатимемо за виконаними.

Друге зауваження стосується числа всіх можливих турів. У несиметричній ЗК всі тури t=(j1,j2..,jn,j1) і t’=(j1,jn..,j2,j1) мають різну довжину і повинні враховуватися обидва. Число різних турів очевидно (n-1)!.

Зафіксуємо на першому і останньому місці в циклічній перестановці номер j1, а що залишилися n-1 номерів переставимо всіма (n-1)! можливими способами. В результаті отримаємо всі несиметричні тури. Симетричних турів є в два раз менше, оскільки кожен врахований двічі: як t і як t’.

Можна уявити, що С складається тільки з одиниць і нулів. Тоді С можна інтерпретувати, як граф, де ребро (i,j) проведене, якщо Сij=0 і не проведено, якщо Сij=1. Тоді, якщо існує тур довжини 0, то він пройде по циклу, який включає всі вершини по одному разу. Такий цикл називається гамільтоновим циклом. Незамкнутий гамільтоновий цикл називається гамільтонової ланцюгом (гамільтоновим шляхом).

В термінах теорії графів симетричну ЗК можна сформулювати так:

Дана повна мережа з n вершинами, довжина ребра (i,j)= Сij. Знайти гамільтоновий цикл мінімальної довжини.

У несиметричній ЗК замість «цикл» потрібно говорити «контур», а замість «ребра» — «дуги» або «стрілки».

ЗАВАНТАЖИТИ

Для скачування файлів необхідно або Зареєструватись

Zadacha Komivojag (196.8 KiB, Завантажень: 37)

Сторінка: 1 2 3 4 5 6 7
завантаження...
WordPress: 23.49MB | MySQL:26 | 0,318sec