Реферати українською » Математика » Задача про комівояжера і її узагальнення


Реферат Задача про комівояжера і її узагальнення

Страница 1 из 3 | Следующая страница

Міністерство освіти і науки РФ

Державне освітнє установа вищого професійної освіти

>АМУРСКИЙ ДЕРЖАВНИЙ УНІВЕРСИТЕТ

(>ГОУВПО «>АмГУ»)

Факультет математики інформатики

Кафедра математичного аналізу та моделювання

>КУРСОВАЯ РОБОТА

на задану тему: «Завдання прокоммивояжере і його узагальнення»

з дисципліни «>Вариационное літочислення і нові методи оптимізації»


>СОДЕРЖАНИЕ

Запровадження

1 Постановка завдання

2Эвристические методи

2.1 АлгоритмБорувки

2.2 АлгоритмКрускала

2.3 Алгоритм Прима

2.4 Висновок

3 Генетичний алгоритм

4NP-полная завдання

5 Метод гілок і національних кордонів

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

Укладання

>Библиографический список


ЗАПРОВАДЖЕННЯ

У 1859 р. Сер Вільям Гамільтон, знаменитий математик, який дав світу теорію комплексного числа ікватерниона, запропонував дитячу головоломку, у якій пропонувалося зробити «круговий подорож» по 20 містам, розміщених у різних різних частинах земної кулі.

>Гамильтонова завдання про мандрівника нерідко перетворюється на завдання прокоммивояжере.Коммивояжер – не вільно подорожуючий турист, а бiзнесмен, обмежений тимчасовими, грошовими або будь-якими іншими ресурсами.Гамильтонова це може стати завданням прокоммивояжере, якщо кожна з ребер забезпечити числової характеристикою. Це то, можливо кілометраж, час дорогу, вартість квитка, витрата пального тощо. Отже, умовні характеристики дадуть числової ряд, елементи його можуть бути розподілені між ребрами скільки завгодно.

Завдання прокоммивояжере належить до класуNP-трудних завдань. Методи виконання завдання прокоммивояжере різні. У цьому курсової коротко розповідається лише про деякі найвідоміших.

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

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


1. ПОСТАНОВКА ЗАВДАННЯ

Мал.1

Припустимо, що бродячий торговець повинен, залишивши місто, якому дамо номер 1, об'їхати ще N – 1 міст повернуться знову у місто номер 1. У розпорядженні дорога, що з'єднують ці міста. Вони повинні вибрати свій маршрут – порядок відвідин міст те щоб шлях, що йому доведеться пройти, був підтриманий якомога коротше. Основне умова це завдання у тому, що комівояжер немає права повертатися знову у це місто, коли він якось вже побував. Це умова називатимемо умовою (>). Ми вважаємо, що відстань між двома містами – функція >f(xі, xj) – визначено. Зрозуміло, функція >f(xі, xj) означатиме як відстань, але, наприклад, певний час чи вади у дорозі тощо. у загальному разі

 

>f(xі, xj) ≠ >f(xj, xі),

а функції >f(xі, xі) природно приписати значення . Довжина l шляху P.S визначається за формулою

                                                                                       (1.1)

Сума вираженні (1) поширена за всі індексам і і j, що задовольняє умові (>), тобто. умові, що з індексів і і j входить у вираз (1) сам і лише одне раз. Функція l = l(x1, …, xN) є, в такий спосіб,аддитивной – вонапредставима як суми доданків, проте сама завдання – завдання відшукання мінімуму l – з обмеження (>) перестав бутиаддитивной і задовольняє принципу оптимальності.

Розглянемо знову площину >t, x, де >t – дискретний аргумент, приймає значення 0,1, 2, …, N, відповідні етапах подорожі торговця. Отже >t = 0 відповідає його початковому стану місті номер 1, >t = 1 – переходу із міста номер 1 до міста, що він вибрав першим відвідання, тощо., >t = N означає останній етап його подорожі – повернення місто номер 1. Аргумент x тепер також приймає дискретні значення 1,2, …, N (Малюнок 1.1). З'єднаємо точку (0, 1) з точками (1,1), (1, 2), …(1, N) ідлинам відрізків, що з'єднують ці точки, припишемо значення >f(x1,xj). Далі точки (1,s) – вузли, що лежать на першої вертикалі, ми з'єднаємо з усімауздами другий вертикалі,длинам відрізків ми припишемо значення >f(x>s, x>k) тощо. точки (N-1, >s) з'єднаємо до точки (N,1).

У результаті побудували певний граф, кожна ламана якого, з'єднує точку (0,1)сточкой (>N,1), описує шлях комівояжера. Нашу завдання ми можемо тепер сформулювати так. Серед усіх ламаних, що належать цьому графу і що з'єднують точки (0,1) і (N,1) i задовольняють умові (>), знайтиломанную найкоротшою довжини. Умова (>) полягає нині у тому, що бажана ламана перетинає (в вузлі) кожну з прямих x = і сам і лише одне раз. Отже, завдання прокоммивояжере формулюється більш звичним нам мовою.

Розглянемо вузол >P, що лежить цього разу третьої вертикалі (Малюнок 1.2). Якби умова (>) не було, то вибір траєкторії, яка з'єднує точку >P до точки (N, 1), не залежав від тієї дороги, який привів нашій точку >P. У разі ситуація інша, і якщо два комівояжера перебувають у точці >P, але них прийшов у цей стан, рухаючись вздовж траєкторії, що проходить через точку >Q, а другий через точку R, їх стану істотно відрізняється друг від друга.

>Коммивояжер, який рухався за другою траєкторії , вже побував на містах номер 2 і номер 5 у майбутньому вона вже немає права знову заїжджати до цих міст. Що ж до комівояжера, який рухався вздовж першої траєкторії, він побував на містах номер 3 і номер 6; не повинен повертатися до цих міст, але він ще зобов'язаний відвідати міста номер 2 і номер 5 тощо. Д.

Оскільки функція >f(xі, xj) визначено на кінцевому безлічі точок, те й функція l(x1,…,xN) також визначено на кінцевому безлічі точок.

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

Легко підрахувати, що кількість можливих варіантів (число значень функції l) одно (N1)!. Отже, безпосередньо перебрати і порівняти між всі можливі шляхи, якими може вийти бродячий торговець, для досить великої кількості міст практично неможливо.

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


2.ЭВРИСТИЧЕСКИЕ МЕТОДИ

Вирішити завдання комівояжера можна з допомогою алгоритмуКрускала. Також нам може допомогти алгоритмиБорувки і Прима, звані «жадібні алгоритми» Ці методи прискорюють розробку алгоритму проти методом повного перебору, проте завжди дають оптимальне рішення. Але трохи розповімо про неї.

Отже, є n міст, потрібно обійти. І тому досить прокласти (n-1) шляхів між містами. Як з'єднати міста те щоб сумарна вартість подорожі була мінімальна?

У випадку, завдання можна сформулювати так. Нехай дано зв'язний,неориентированний граф з вагами на ребрах G(VE), у якому V — безліч вершин (міст), а E — безліч їх можливих попарних сполук (дороги). Нехай кожному за ребра (u,v) однозначно визначено деяке речовинне число w(u,v) — його вага (довжина чи вартість шляху). W(u,v) називається ваговій функцією. Завдання полягає у перебування такого зв'язковогоациклическогоподграфа T ⊂ G, що містить все вершини, що сумарна вага його ребер буде мінімальний.

Оскільки T зв'язний і містить циклів, якого є деревом і називається >остовним чи які покривають їхню деревом.Остовное дерево T, яка має сумарна вага його ребер w(T) = ∑(u,v)T w(u,v) мінімальний, називається мінімальнимостовним чи мінімальним які покривають їхню деревом.

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

Також вважаємо, що з будь-який пари ребер їх вагові характеристики будуть різні. Це гарантує унікальність побудованого мінімальногоостовного дерева. Наприклад, коли всі ребра мають одиничний вагу, то будь-якеостовное дерево буде мінімальним (з сумарним вагою >v-1, де v – кількість вершин в графі).

Зазначений остов будується поступово. Алгоритм використовує певнийациклическийподграф А вихідного графа G, що називається проміжнимостовним лісом. Спочатку G складається з nвершин-компонент, не з'єднаних друг з одним (n дерев з однієї вершини). На кожен крок в A додається одне нове ребро. Граф A завжди єподграфом деякого мінімального остова. Черговедобавляемое ребро e=(u,v) вибирається те щоб не порушити цього властивості: A ∪ {e} також має бутиподграфом мінімального. Таке ребро називається безпечним.

За визначенням A, він повинен залишатисяподграфом деякого мінімального остова після будь-якого числа ітерацій. Звісно, головне запитання у тому, як шукати безпечне ребро. Зрозуміло, що таке ребро завжди існує, якщо A ще є мінімальним кістяком (будь-яке ребро остова, не яке у A). Зауважимо, що оскільки A неспроможна утримувати циклів, то, на кожен крок руба з'єднуються різні компонентисвязности (спочатку всі вершини окремими компонентах, наприкінці A – одна компонента). Отже аналіз графа виконується (>n-1) раз.

Далі наводиться загальне правило відшукання безпечних ребер. На те теорема, яка допоможе знаходити безпечні ребра.

Теорему: Нехай >G(V;E) – зв'язнийнеориентированний граф і безлічі Є визначено вагова функція w. Нехай А – певнийподграф G, що у той часподграфом деякого мінімальногоостовного дерева T. Розглянемо компонентусвязности До з А. Розглянемо безліч >E(K) ребер графа G, лише одне кінець яких лежать у До. Тоді ребро мінімального ваги з >E(K) буде безпечним.

У зв'язку з наведеної теоремою введемо таке: б>езопасним руба e щодо деякою компонентисвязности До з А назвемо ребро з із мінімальною вагою, рівно один кінець якого в До.

2.1 АЛГОРИТМБОРУВКИ

У першому кроці A складається з всіх вершин G і порожнього безлічі ребер. На початку черговий фази алгоритмуБорувки, кожної компонентисвязности проміжногоостовного лісу вибирається лідер чи корінь – вершина,сопоставляемая кожної компоненті. Зробити це можна зробити в найпростішому випадку з допомогою обходу A завглибшки: вершина, з якого починається обхід черговий компоненти, і буде цього лідером.

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

2.2 АЛГОРИТМКРУСКАЛА

АлгоритмКрускала об'єднує вершини графа на кілька зв'язкових компонент, кожна з яких є деревом. На кожен крок із усіх ребер, що з'єднують вершини із різних компонентсвязности, вибирається ребро з найменшою вагою. Необхідно перевірити, що є безпечним. Безпека ребра гарантується раніше показаної теоремою про безпечних ребрах. Оскільки ребро є легким із усіх ребер, які виходять із даної компоненти, він буде безпечним.

Залишається зрозуміти, як реалізувати вибір безпечного ребра кожному кроці. І тому в алгоритміКрускала все ребра графа G перебираються зі збільшення ваги. Для чергового ребра перевіряється, не лежать чи кінці ребра у різних компонентахсвязности, і якщо це, ребро додається, і компоненти об'єднуються.

Зручно використовуватиме зберігання компонент структури даних для непересічних множин, як, наприклад, списки чи, краще, ліс непересічних множин зі стиском колій та об'єднанням рангом (одне із найбільш швидких відомих методів).Элементами множин є вершини графа, кожне безліч містить вершини однієї зв'язковою компоненти.

2.3 АЛГОРИТМ ПРИМА

Як можна і алгоритмКрускала, алгоритм Прима відповідає загальній схемі алгоритму побудови мінімальногоостовного дерева: кожному кроці ми додаємо до зводжуваного кістяку безпечне ребро. Алгоритм Прима належить до групи алгоритмів нарощування мінімального остова: кожному кроці є до однієї нетривіальною (не що з однієї вершини) компонентисвязности, й у до неї додається ребро найменшого ваги, з'єднуюче вершини компоненти з іншими вершинами. По теоремі таке ребро є безпечною.

При реалізації треба вміти кожному кроці швидко вибирати безпечне ребро. І тому зручно скористатися чергою в пріоритетах (купою). Алгоритм отримує на вхід граф G та її корінь >r – вершина, де нарощуватиметься мінімальний остов. Усі вершини G, ще хто у дерево, зберігаються у черги з пріоритетом. Пріоритет вершини v визначається значенням key[v], що дорівнює мінімального вазі ребер, що з'єднують v з вершинами мінімального остова. Поле p[v] для вершин дерева свідчить про батька, а вершин з черги, свідчить про остов дерева, в якою веде ребро із key[v] (одна з таких ребер, якщо слід їх дещо).


2.4ВЫВОД

 

На завершення розповіді про жадібних алгоритми наведу приклад. Розглянемо невелику «дитячу» завдання. Припустимо, що маємо є монети гідністю 25, 10, 5 копійок і одну копійка і треба повернути здачу 63 копійки. Майже не роздумуючи, ми перетворимо цю величину на два монети по 25 копійок, одну монету удесятеро копійок і трьох монети за однією копійці. Нам як вдалося швидко визначити перелік монетнуясного гідності, а й, власне, ми склали найкоротший список монет необхідного гідності.

Алгоритм, яких ми у разі скористалися, був у виборі монети найбільшого гідності (25 копійок), але збольще 63 копійок, додаванню їх у список здачі і віднімання її вартості з 63 (виходить 38 копійок). Потім знову вибираємо монету самогобольщого гідності, але збольще залишку (38 копійок): цієї монетою знову виявляється монета в 25 копійок. Цю монету ми знову додаємо до списку здачі, віднімаємо і її з залишку тощо.

Цей метод внесення змін називається «жадібним» алгоритмом. В кожній окремої стадії «жадібний» алгоритм вибирає той варіант, що є локально оптимальним у цьому чи іншому сенсі. Зверніть увагу, що алгоритм визначення здачі забезпечує загалом оптимальнерещениелищь внаслідок особливостей монет. Якби нас були монети гідністю 1 копійка, 5 і одинадцять копійок і було порадити здачу 15 копійок, то «жадібний» алгоритм обрав би спочатку монету гідністю 11 копійок, та був чотири

Страница 1 из 3 | Следующая страница

Схожі реферати:

Навігація