Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Інформація про навчальний заклад
ВУЗ:
Інші
Інститут:
Не вказано
Факультет:
Комп’ютерні науки
Кафедра:
Не вказано
Інформація про роботу
Рік:
1998
Тип роботи:
Задача
Предмет:
Системи автоматизованого проектування ЗВТ
Частина тексту файла (без зображень, графіків і формул):
МІНІСТЕРСТВО ОСВІТИ УКРАЇНИ
Державний університет “Львівська політехніка”
АЛГОРИТМ РІШЕННЯ ЗАДАЧІ КОМІВОЯЖЕРА
І Н С Т Р У К Ц І Я
до лабораторної роботи № 3
з курсу
“Дискретні моделі в САПР”
для базового напрямку 6.0804 “Комп’ютерні науки”
Затверджено:
на засіданні кафедри “Системи
автоматизованого провектування”
Протокол N 14 від 03.04.1997 р.
Львів - 1998
Алгоритм рішення задачі комівояжера. Інструкція до лабораторної роботи N3 з курсу “Дискретні моделі в САПР” для базового напрямку 6.0804 “Комп’ютерні науки”
/Склали: В.І.Каркульовський, С.П.Ткаченко, І.І.Чура. -Львів: ДУ “Львівська політехніка”, 1998.
Укладачі: В.І.Каркульовський, канд.техн.наук, доц.,
С.П.Ткаченко, канд.техн.наук, доц.
І.І.Чура, канд.техн.наук, доц..
Відповідальний за випуск: Д.В.Федасюк, канд.техн.наук, доц.
Рецензенти: Стех Ю.В. , канд.техн.наук, доц.
Мотика І.І. , канд.техн.наук, доц.
1. МЕТА РОБОТИ
Метою даної лабораторної роботи є вивчення і дослідження алгоритмів рішення задачі комівояжера.
2. КОРОТКІ ТЕОРЕТИЧНІ ВІДОМОСТІ
ФОРМУЛЮВАННЯ ТА ДЕЯКІ ВЛАСТИВОСТІ ЗАДАЧІ КОМІВОЯЖЕРА
Комівояжеру потрібно відвідати кожне місто в певній зоні обслуговування і повернутися додому. Відомо, що комівояжеру хотілось би вибрати такий порядок обходу клієнтів, при якому його шлях був би найкоротшим. Таким чином, комівояжер зтикається із задачою пошуку маршрута мінімальної довжини, тривалості чи вартості.
Задача комівояжера може бути сформульована, як задача на графі. Для цього необхідно побубувати граф G=(X,A), вершини якого відповідають містам в зоні комівояжера, а ребра(дуги) відображають комунікації, що з’єднують пари міст. Довжина a=(x,y)0 кожної дуги (x,y)A може бути рівна відстані, вартості чи часу або числовому значенню деякого комплексного критерію.
Контур, що включає кожну вершину графа G хоча б один раз, називають маршрутом комівояжера. Контур, який включає кожну вершину графа G рівно один раз називають гамільтоновим.
Загальною задачею комівояжера називають задачу пошуку маршруту найменшої довжини.
Задачею комівояжера називають задачу пошуку гамільторового контура найменшої довжини.
Контур комівояжера, який має найменшу довжину, називають оптимальним гамільтоновим контуром він є оптимальним рішенням задачі комівояжера. Оптимальний маршрут комівояжера не обов`язково є гамільтоновим контуром.
Виникає питання, в яких випадках гамільтоновий контур є рішенням загальної задачі комівояжера? Відповідь дає наступна теорема.
Теорема 1. Якщо для кожної пари вершин (х,у) виконується умова:
a(x,y)a(x,z)+a(z,y) , для всіх zxy. (1)
то гамільтоновий контур є рішенням загальної задачі комівояжера на графі G (якщо рішення задачі взагалі існує).
Умова (1) говорить лише про те, що відстань безпосередньо від х до у ніколи не перевищує відстані від х до у через будь-яку іншу вершину z. Умову (1) називають нерівностю трикутника.
УМОВИ ІСНУВАННЯ ГАМІЛЬТОНОВОГО КОНТУРУ.
НИЖНІ ГРАНИЦІ.
Рішенням задачі комівояжера є оптимальний гамільтоновий контур. Нажаль, не всі графи містять гамільтоновий контур. Отже перед тим, ніж перейти до пошуку оптимального гамільтонового контура потрібно довести факт його існування в даному графі.
Введемо ряд визначень, які в подальшому нам знадобляться. Граф називається сильно зв`язаним, якщо в ньому для будь-яких двох вершин “х” і “у” існує шлях від “х” до “у”. Підмножина вершин Х деякого графа називається сильно зв`язаною, якщо для будь-яких пар вершин х Х і у Х існує шлях з “х” в “у” і Х не є підмножиною ніякої іншої множини вершин, які володіють тими ж властивостями. Сформулюємо загальну теорему Гуйя-Урі.
Теорема 2. Якщо граф G(X,A) задовільняє умовам :
1) граф G силно зв’язаний ;
2) d(х)n для всіх х ( Х, де d(x) - степінь вершини х, п - кількість вершин, то він містить гамільтоновий контур.
На практиці достатньо легко встановити, чи задовільняє деякий граф умовам (I.) і (II.) теореми 2.
Умова (1.) перевіряється застосуванням до кожної пари вершин алгоритма Флойда або алгоритма Данцига для побудови найкоротшого шляху. Ця умова виконуєтся, якщо для кожної пари вершин в графі існує зв’язуючий їх шлях скінченної довжини.
Умова ( 2.) легко перевіряється підрахунком дуг, інцидентних кожній вершині графа.
Умови існування гамільтонового циклу на неорієнтованому графі сформульовані Квателем. Нехай, як і раніше, через n позначимо кількість вершин в графі. Пронумеруємо вершини так, щоб виконувалось відношення :
d(xi) ( d(xi) ( ... (d(xn)
Теорема 3. Граф G=(Х,.А) містить гамільтоновий цикл,якщо :
n ( 3 і d(хк) ( k ( 1/2 n (d(xn-к)n-k (2)
Умову (2) легко перевірити. Необхідно впорядкувати вершини по зростанню їх степеней і перевірити, чи виконується умова для перших n/2 вершин.
Розглянемо тепер методи розрахунку нижніх границь довжини оптимальних гамільтонових контурів на орієнтованому графі G=(X,A). Якщо від довжини довільного гамільтонового контура відняти значення нижньої границі, то отримана різниця рівна максимальному значенню, на яке довжина гамільтонового контура може перевищувати довжину оптимального гамільтонового контура. Значення цієї вершини потрібно для оцінки різниці довжин знайденого і оптимального гамільтонового контура.
Для орграфа дуги, що входять в гамільтоновий контур, повинні володіти наступними двома властивостями:
1. Кожна вершина повинна бути інцидентна двом іншим дугам, одна з яких направлена до неї, а інша від неї;
2. Всі дуги повинні бути зв’язані. Дуги, які входять в будь-яку множину незв’язаних контурів, що містять всі вершини, володіють властивістю 1.
Будь-яка зв’язана множина дуг володіє властивістю 2. І тільки гамільтоновий контур володіє властивостями 1 і 2 одночасно.
Розглянемо сімейство F всіх підмножин множини А, які володіють властивістю 1. (Будемо вважати, що сімейство F не пусте). Зрозуміло, що кожен гамільтоновий контур входить в F. Таким чином, нижньою границею довжини оптимального гамільтонового контура є найменше значення суми довжин дуг, які утворюють підмножини в F. Позначимо через L1 цю нижню границю. Нижню границю оптимального гамільтонового контура можна обчислити за наступним алгоритмом.
Крок 1. На основі графа G (рис.1.) будується граф G’=(X’,A’)(рис.2).
Рис.1.
Рис.2.
Для цього кожній вершині х, що належить множині Х ставиться у відповідність пара вершин x1 є X’ і x2 є X’. Кожній дузі (х,у) є А ставиться у відповідність проміжна дуга (x1,y2) є A’. Нехай кожна проміжна дуга має пропускну здатність, рівну 1, вартість, рівну довжині відповідної дуги в А. Введемо вершину-джерела “s” і вершину-стік “t” і з’єднаємо вершину “s” з направленими з неї дугами (s, x1) з кожною з вершин x1єX’. З’єднаємо вершину “t” з кожною з вершин x2єX’ направленими в неї дугами (x2, t). Нехай кожна з дуг (s, x1) i (x2, t) для всіх x1 і x2 є X має пропуску здатність, рівну 1, і нульову вартість (рис.2).
Крок 2. Визначимо на графі G’ максимально можливий потік з “s” в “t”, що має мінімальну загальну вартість. Такий потік шукається за допомогою алгоритму побудови потоку мінімальної вартості. Нехай L1 рівна вартості отриманого потоку. Так як пропускні здатності всіх дуг в графі G’ рівні 1, отриманий потік складається з одиничних потоків, що протікають в дугах графа G’ від вершини “s” до “t”. Крім того, кожна з проміжних вершин інцидентна не більше ніж одній дузі, по якій протікає одиничний потік. Далі, кожній проміжній дузі в A’ відповідає деяка дуга в А. Розглянемо множину всіх проміжних дуг, по яким протікає одиничний потік. Нехай через М позначимо відповідну множину дуг в А. Дуги в множині М утворюють незв’язні контури в G. В противному випадку існувала би деяка вершина хєХ, яка не була б інцидентна направленій до неї чи з неї дуги в М. Це відповідало тому, що в графі G’ у вершину “x2”не входив би чи з вершини “x1“ не виходив би ні один з одиничних потоків. В кожному з цих двох випадків сумарний потік з “s” в “t” складався б менше, ніж з |X| oдиничних потоків. Але це неможливо, так як кожній підмножині в F відповідає потік в G’, рівний |X| одиниць, і крім того множина F не пуста. Оскільки не нульову вартість мають лише проміжні дуги, то сумарна вартість знайденого потоку рівна сумі довжин дуг, які входять у відповідні підмножини в F. Оскільки знайдений потік має найменшу сумарну вартість, то відповідна йому підмножина в F повинна мати мінімальну суму довжин дуг. Таким чином, L1 є нижньою границею довжини оптимального намільтонового контура в графі G.
Якщо в граф G входять не орієнтовані дуги, то кожна неорієнтована дуга може бути замінена парою протилежно направлених дуг, які з’єднують цю ж пару вершин. Нехай кожна з цих направлених дуг має довжину, рівну довжині неорієнтованої дуги. Граф, який при цьому отримується, буде містити лише направлені дуги і для нього може бути застосований описаний вище метод обчислення L1.
Якщо множина М утворює гамільтоновий контур, то ми знайшли не тільки нижню границю довжини оптимального гамільтонового контура, але й сам оптимальний контур.
МЕТОДИ РІШЕННЯ ЗАДАЧІ КОМІВОЯЖЕРА
Відомо багато різних методів рішення задачі комівояжера. Серед них можна виділити методи розроблені Белмором і Немхаузером, Гарфинкелем і Немхаузером, Хелдом і Карном, Стекханом. Всі ці методи відносяться до одного з двох класів: а) методи рішення, які завжди приводять до знаходження оптимального рішення, але потребують для цього, в найгіршому випадку, недопустимо великої кількості операцій(метод гілок та границь); б) методи, які не завжди приводять до находження оптимального результату, але потребують для цього допустимої великої кількості операцій (метод послідовного покращення рішення).
ЗАСТОСУВАННЯ МЕТОДУ ГІЛОК І ГРАНІЦЬ ДЛЯ ВИРІШЕННЯ ЗАДАЧІ КОМІВОЯЖЕРА
Нехай розглядається граф G= ( X , A ). Для отримання нижньої границі L1 довжини гамільтонового контура найменшої довжини на графі G може бути використаний алгоритм побудови потоку мінімальної вартості.
Якщо отриманий за допомогою цього алгоритма оптимальний потік відповідає деякому контуру на графі G, то цей контур є оптимальним гамільтоновим контуром, і на цьому рішення задачі закінчується. Але існує достатньо велика ймовірність того, що оптимальний потік, отриманий для будь-якого графа, буде відповідати декільком незв’язним контурам. В цьому випадку довільно вибираємо один контур і позначаємо його через Gi, тоді Xc = { x1, x2, …, xk } множина вершин, що входить в нього.
В оптимальному рішенні комівояжер, виходячи з вершини х1 ( Хс переміщується або у вершину, яка належить множині Хс, або у вершину, яка не належить множині Хс. Якщо він прийшов у вершину х ( Хс, то з неї він знову переміщується або у вершину множини Хс, або у вершину, що не належить Хс і т. д. Таким чином, оптимальне рішення повинно бути представлено по крайній мірі в одному з наступних графів :
Графі G, з якого виключені всі дуги ( х1, у ), у ( Хс ;
Графі G, з якого виключені всі дуги ( х1, у ), у ( Хс і дуги ( х2, z ), z ( Xc ;
Графі G, з якого виключені всі дуги ( х1, у ), ( х2, у ), у ( Хс і дуги ( х3, z ), z ( Xc ;
Графі G, з якого виключені всі дуги ( х1, у ), ( х2, у ), ( х3, у ), у ( Хс і дуги ( х4, z ),z( Xc ;
…
Графі G, з якого виключені всі дуги ( х1, у ), ( х2, у ), ( х3, у ), ( xк-1, у), у ( Хс і дуги ( хk, z ), z ( Xc.
Назвемо перераховані вище графи відповідно G1, G2,…Gk. Отже довжина кожної дуги в графі Gi, i=1,2,…,k не менша довжини оптимального гамільтонового контура в графі G. Більше того, оптимальне рішення на графі
G є також оптимальним рішенням по крайній мірі на одному з графів G1, G2,…,Gk. Визначимо далі за допомогою алгоритма знаходження потоку мінімальної вартості нижню границю L1 довжини оптимального гамільтонового контура для кожного з графів G1, G2,…,Gk. Назвемо ці нижні границі відповідно L1( G1 ), L1( G2 ), … , L1( Gk ).
Якщо отриманий для деякого графа Gс оптимальний потік протікає по дугам, які утворюють гамільтоновий контур, то в подальшому не розглядаються графи Gj , для яких L1( Gj ) ( L1( Gc ), так як L1( Gc ) є нижньою границею, що досягається. Таким чином деякі з графів G1, G2,…,Gk відкидаються з подальшого перегляду.
Для кожного з графів Gі, для яких L1( Gі ) ( L1( Gc ), повторюється дана операція, що описана вище. При цьому граф Gі заміняється графами Gі1, Gі2,… . На кожному з графів Gij вираховується границя L1( Gij ) довжини оптимального гамільтонового контура. Після цього, як і раніше, виключається з перегляду, як можна більшу кількість знову створених графів.
В кінці кінців один граф, в якому знайдений гамільтоновий контур мінімальної довжини, виключить з подальшого перегляду всі графи, що залишилися. Цей гамільтоновий контур повинен бути гамільтоновим контуром мінімальної довжину в вихідному графі G.
Приклад. Скористаємось методом гілок і границь для знаходження оптимального гамільтонового контура в графі, що зображений на рис. 3.
Граф G.
Контури мінімальної вартості графа G.
Рис.3.
Оскільки граф ( має невелику розмірність, ми відразу можемо помітити, що в результаті використання алглритму знаходження потоку мінімальної потужності(вартості) на графі ( отримується потік, що відповідає двом контурам ((, (), ((, (), ((, () і ((, (), ((, (), ((, (). Загальна довжина цих двох
контурів дорівнює 11. Таким чином, L1(() =11. Використовуючи вершини Xc={a,b,c} першого контуру, ми можемо побудувати три графа Ga, Gb, Gc, зображених на рис.4.
Граф Ga
Граф Gb
Граф Gc
Рис.4а
Рис.4б
Рис.4в
Граф Ga отриманий шляхом виключення з графа G дуги, направленої з а в ( або (, тобто дуги ((, (). Граф Gb отриманий шляхом виключення з графа G всіх дуг, що направлені з а в (,(,(, і всіх дуг, що направлені з ( в ( і с. Таким чином, граф Gb отримується шляхом виключення з графа ( дуг ((,() і ((,(). Граф Gc отримується шляхом виключення з графа ( всіх дуг, що направлені з а і ( в (, (, (, і всіх дуг, що направлені з с в а і (. Таким чином, граф Gc отриманий шляхом виключення з графа ( дуг ((, (), ((, () і ((, ().
Оскільки граф має невелику розмірність, ми можемо зразу побачити, що використання алгоритму знаходження потоку мінімальної вартості привело б до таких контурів і нижніх границь довжини оптимальних гамільтонових контурів в графах Ga, Gb, Gc.
Граф Контур Нижня границя
Ga ((, (), ((, (), ((, (), ((, (), ((, (), ((, () L1(Ga) = 21
Gb ((, (), ((, (), ((, (), ((, (), ((, (), ((, () L1(Ga) = 12
Gc ((, (), ((, (), ((, (), ((, (), ((, (), ((, () L1(Ga) = 16
Оскільки при Gc визначенні нижньої границі довжини оптимального гамільтонового контура в графі Gb одержаний гамільтоновий контур довжиною 12, то графи Ga і Gc можуть в подальшому не розглядатися (дійсно L1(Gb) < L1(Gc) < L1(Ga). Відпoвідно, гамільтоновий контур ((, (), ((, (), ((, (), ((, (), ((, (), ((, () є гамільтоновим контуром в початковому графі (.
ЗАСТОСУВАННЯ МЕТОДУ ПОСТУПОВОГО ПОКРАЩЕННЯ ДЛЯ
ВИРІШЕННЯ ЗАДАЧІ КОМІВОЯЖЕРА
Метод поступового покращення рішення задачі комівояжера використовується для знаходження в графі G близького до оптимального (а
інколи і оптимального) гамільтонового контура і полягає в наступному. Спочатку береться деякий гамільтоновий контур. Нехай х1, х2, ..., хn визначає послідовність , в якій в цьому контурі обходяться вершини графа G.
Для і=1, 2,..., n-1 i j=i+1,...,n визначити, чи зменшується довжина гамільтонового контура при перестановці в заданій вище послідовності обходу вершин пари вершин хі і хj. Якщо це приводить до зменшення довжини гамільтонового контура, то внести таку перестановку в порядок обходу вершин графа G. Повторювати цей процес до тих пір, поки за допомогою попарних перестановок досягається зменшення довжини гамільтонового контура.
Перестановка вершин “і” і “j” в дійсності означає заміну дуг :
( хі-1, хі ), ( хі, хі+1), ( хj-1, xj ), ( xj, xj+1 )
дугами :
( хі-1, xj ), ( xj, хі+1 ), ( хj-1, хі ), ( хі, xj+1 )
Процес попарних перестановок повинен бути скінченним, так як :
- існує тільки скінченне число різних методів обходу n вершин графа ( різних перестановок ) ;
- кожен раз формується нова послідовність обходу, відмінна від попередніх.
При цьому може бути отриманий новий гамільтоновий контур, який має строго меншу довжину, ніж попередній.
Потрібно зауважити, що при використанні метода покращення рішень результуючий гамільтоновий контур залежить від того, яким був вибраний початковий гамільтоновий контур.
Вдосконалення метода послідовного покращення рішення можна знайти в роботах Стекхана, а також Лина і Кернінга.
КОНТРОЛЬНІ ЗАПИТАННЯ
Які ви знаєте алгоритми рішення задачі комівояжера?
Ідея рішення задачі комівояжера методом гілок та границь.
Ідея рішення задачі комівояжера методом послідовного покращення рішення.
4. ЛАБОРАТОРНЕ ЗАВДАННЯ
1.Отримати у викладача індивідуальне завдання.
2. Підготувати вхідне завдання на ЕОМ за зразком описаним в інструкції для роботи з учбовою програмою DIP. Подальші пункти повторити для рішення задачі методом гілок та границь і методом поступового покращання.
3. Запустити на виконання програму відповідного методу.
4. Проглянути результат роботи програм. Результат роботи може бути позитивним (шлях знайдено) або негативним (шлях відсутній).
5. У випадку, коли шлях знайдено (не знайдено), необхідно модифікувати граф, коректуючи два або три зв’язки, щоб знайти такий граф, на якому задача комівояжера не вирішується (вирішується).
Порівняти результати, отримані за допомогою різних алгоритмів і зробити висновок.
Зафіксувати результати роботи у викладача.
Оформити і захистити звіт.
5. ЗМІСТ ЗВІТУ
Опис двох алгоритмів рішення задачі комівояжера.
Нарисувати графи і вхідні дані, що їх описують для двох результатів розрахунку.
Результати розрахунків (гамільтоновий контур).
Висновки по результатах розрахунків.
6. ЛІТЕРАТУРА
Оре О. Теория графов. -М.: Наука. Главная редакция физико-математической литературы, 1980. -336с.
Асельдеров З.М. и др. Представление графов и операции над ними. -Киев, 1987. 18с.
Зыков А.А. Основы теории графов. -М.: Наука, 1987. -384с.
Оцуки Т. Эвристические алгоритмы для комбинаторных задач с большим обьемом вычислений. “Дэнси цусим гакайси”. 1975. 58. N4. -С.416-423
. Навчальне видання
АЛГОРИТМ РІШЕННЯ ЗАДАЧІ КОМІВОЯЖЕРА
І Н С Т Р У К Ц І Я
до лабораторної роботи №3
з курсу
“Дискретні моделі в САПР”
для базового напрямку 6.0804 “Комп’ютерні науки”
Укладачі: Володимир Іванович Каркульовський
Сергій Петрович Ткаченко
Ігор Іванович Чура
Редактор
17.07.2020 15:07-
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора