Рішення задачі комівояжера методом гілок і меж

Розрахунково-графічна робота

з теорії алгоритмів

На тему

«гшення задачі комівояжера методом гілок і меж В»

План

1. Вступ

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

3. Математична модель задачі комівояжера

4. Алгоритм рішення

5. Висновки

6. Список використаної літератури

1. Вступ

У 1859 р. Сер Вільям Гамільтон, знаменитий математик, що дав світові теорію комплексного числа і кватерниона, запропонував дитячу головоломку, в якій пропонувалося зробити В«Круговий подорожВ» по 20 містах, розташованих в різних частинах земної кулі. Кожне місто з'єднувався дорогами з трьома сусідніми так, що дорожня мережа утворювала 30 ребер Додекаедр, в вершинах якого знаходилися міста a, b, ... t. Обов'язковою умовою було вимога: кожне місто за винятком першого можна відвідати один раз.

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

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

Розглянемо задачу про комівояжера.

Є n міст, відстані (вартість проїзду, витрата пального на дорогу і т.д.) між якими відомі. Комівояжер повинен пройти всі n міст по одному разу, повернувшись в те місто, з якого почав. Потрібно знайти такий маршрут руху, при якому сумарне пройдена відстань (вартість проїзду і т.д.) буде мінімальним.

Очевидно, що завдання комівояжера - це задача відшукання найкоротшого Гамільтона циклу в повному графі.

Можна запропонувати наступну просту схему рішення задачі комівояжера: згенерувати всі n! можливих перестановок вершин повного графа, підрахувати для кожної перестановки довжину маршруту і вибрати найкоротший. Однак, n! із зростанням n росте швидше, ніж будь поліном від n, і навіть швидше, ніж. Таким чином, рішення задачі комівояжера методом повного перебору виявляється практично нездійсненним, навіть при досить невеликих n.

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

Існує метод вирішення задачі комівояжера, який дає оптимальне рішення. Цей метод називається методом гілок і меж. Рішення задачі комівояжера методом гілок і меж по-іншому називають алгоритмом Літтла.

Якщо вважати міста вершинами графа, а комунікації (i, j) - його дугами, то вимога знаходження мінімального шляху, проходить один і тільки один раз через кожне місто, і повернення назад, можна розглядати як знаходження на графі гамильтонова контуру мінімальної довжини.

Для практичної реалізації ідеї методу гілок і меж стосовно до задачі комівояжера потрібно знайти метод визначення нижніх меж підмножини і розбиття множини гамільтонових контурів на підмножини (розгалуження).

Визначення нижніх меж базується на тому твердженні, що якщо до всіх елементів i-го рядка або j-го стовпця матриці C додати або відняти число, то задача залишиться еквівалентної колишньою, тобто оптимальність маршруту комівояжера не зміниться, а довжина будь-якого гамильтонова контуру зміниться на дану величину.

Опишемо алгоритм Літтла для знаходження мінімального гамильтонова контуру для графа з n вершинами. Граф представляють у вигляді матриці його дуг. Якщо між вершинами X i і X j немає дуги, то ставиться символ В«в€ћВ».

Алгоритм Літтла для рішення задачі комівояжера можна сформулювати у вигляді наступних правил:

1. Знаходимо в кожній рядку матриці мінімальний елемент і віднімаємо його з усіх елементів відповідного рядка. Отримаємо матрицю, наведену по рядках, з елементами

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

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

3. Підсумовуємо елементи і, отримаємо константу приведення

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

4. Знаходимо ступеня нулів для наведеної по рядках і стовпцях матриці. Для цього подумки нулі в сволоку замінюємо на знак В«в€ћВ» і знаходимо суму мінімальних елементів рядка і стовпця, відповідних цьому нулю. Записуємо її в правому верхньому кутку клітки

5. Вибираємо дугу, для якої ступінь нульового елемента досягає максимального значення

6. Розбиваємо безліч всіх гамільтонових контурів на дві підмножини і. Підмножина гамільтонових контурів містить дугу, - її не містить. Для отримання матриці контурів, що включають дугу, викреслюємо в матриці рядок і стовпець. Щоб не допустити утворення негамільтонова контуру, замінимо симетричний елемент на знак В«в€ћВ».

7. Наводимо матрицю гамільтонових контурів. Нехай - константа її приведення. Тоді нижня межа безлічі визначиться так

8. Знаходимо безліч гамільтонових контурів, що не включають дугу. Виняток дуги досягається заміною елемента в матриці на в€ћ.

9. Робимо приведення матриці гамільтонових контурів. Нехай - константа її приведення. Нижня межа безлічі визначиться так

10. Порівнюємо нижні кордону підмножини гамільтонових контурів і. Якщо, то подальшого розгалуження в першу чергу підлягає безліч. Якщо ж, то разбиению підлягає безліч.

Процес розбиття множин на підмножини супроводжується побудовою дерева розгалужень.

11. Якщо в результаті розгалужень отримуємо матрицю, то визначаємо отриманий ветвлением гамільтонів контур і його довжину.

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

3. Математична модель задачі комівояжера

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

(1)

Умови (2) - (4) в сукупності забезпечують, що кожна змінна дорівнює або нулю, або одиниці. При цьому обмеження (2), (3) виражають умови, що комівояжер побуває в кожному місті один раз в нього прибувши (обмеження (2)), і один раз з нього виїхавши (Обмеження (3)).

Однак цих обмежень не достатньо для постановки задачі комівояжера, так як вони не виключають рішення, де замість простого циклу, що проходить через n вершин, відшукуються 2 і більше окремих циклу (подцикла), проходить через менше число вершин. Тому завдання, описана рівняннями (2) - (4) повинна бути доповнена обмеженнями, що забезпечують зв'язність шуканого циклу.

Для того, щоб виключити при постановці завдання всі можливі підцикли в систему обмежень задачі включають наступне обмеження:

, де, і.

4. Алгоритм рішення

Дана матриця відстаней, представлена ​​в таблиці 1. Необхідно за допомогою алгоритму Літтла вирішити завдання комівояжера.

...Табл.1

j

i

1 2 3 4 5 6 1 в€ћ 7 16 21 2 17 2 13 в€ћ 21 15 43 23 3 25 3 в€ћ 31 17 9 4 13 10 27 в€ћ 33 12 5 9 2 19 14 в€ћ 51 6 42 17 5 9 23 в€ћ

1) Праворуч до таблиці приєднуємо стовпець U i , в якому записуємо мінімальні елементи відповідних рядків. Віднімаємо елементи U i з відповідних елементів рядка матриці.

j

i

1 2 3 4 5 6

U i

1 в€ћ 7 16 21 2 17 2 2 13 в€ћ 21 15 43 23 13 3 25 3 в€ћ 31 17 9 3 4 13 10 27 в€ћ 33 12 10 5 9 2 19 14 в€ћ 51 2 6 42 17 5 9 23 в€ћ 5

2) Внизу отриманої матриці приєднуємо рядок V j , в якій записуємо мінімальні елементи стовпців. Віднімаємо елементи V j з відповідних стовпців матриці.

j

i

1 2 3 4 5 6 1 в€ћ 5 14 19 0 15 2 0 в€ћ 8 2 30 10 3 22 0 в€ћ 28 14 6 4 3 0 17 в€ћ 23 2 5 7 0 17 12 в€ћ 49 6 37 12 0 4 18 в€ћ

V j

0 0 0 2 0 2

3) В результаті обчислень одержуємо матрицю, наве...дену по рядках і стовпцях, яка зображена у вигляді таблиці 2.

Табл.2

j

i

1 2 3 4 5 6 1 в€ћ 5 14 17

0 19

13 2

0 3

в€ћ 8

0 2

30 8 3 22

0 4

в€ћ 26 14 4 4 3

0 0

17 в€ћ 23

0 4

5 7

0 7

17 10 в€ћ 47 6 37 12

0 8

2 18 в€ћ

4) Знаходимо константу приведення

Таким чином, нижній кордоном безлічі всіх гамільтонових контурів буде число

5) Знаходимо ступеня нулів повністю наведеної матриці. Для цього як би замінюємо в ній всі нулі на знак В«в€ћВ» і встановлюємо суму мінімальних елементів відповідного рядка і стовпця. Ступеня нулів записані в правих верхніх кутах клітин, для яких.

6) Визначаємо максимальний ступінь нуля. Вона дорівнює 19 і відповідає клітці (1; 5). Таким чином, претендентом на включення в гамільтонів контур є дуга (1; 5).

7) Розбиваємо безліч всіх гамільтонових контурів на два: і. Матрицю з дугою (1; 5) отримуємо табл.2 шляхом викреслювання рядка 1 і стовпця 5. Щоб не допускати утворення негамільтонова контуру, замінюємо елемент (5; 1) на знак В«в€ћВ».

j

i

1 2 3 4 6 2 0 в€ћ 8 0 8 3 22 0 в€ћ 26 4 4 3 0 17 в€ћ 0 5 в€ћ 0 17 10 47 6 37 12 0 2 в€ћ

8) Матрицю гамільтонових контурів отримаємо з таблиці 2 шляхом заміни елемента (1; 5) на знак В«в€ћВ».

j

i

1 2 3 4 5 6

1 в€ћ 5 14 17 в€ћ 13 5 2 0 в€ћ 8 0 30 8

3 22 0 в€ћ 26 14 4

4 3 0 17 в€ћ 23 0

5 7 0 17 10 в€ћ 47

6 37 12 0 2 18 в€ћ

14

9) Робимо додаткове приведення... матриці контурів: = 0. Нижня межа безлічі дорівнює.

10) Знаходимо константу приведення для безлічі контурів

:

Отже, нижня межа безлічі дорівнює

11) Порівнюємо нижні кордону підмножин і. Так як

то подальшому галуженню піддаємо безліч.

На рис.1 представлено розгалуження по дузі (1; 5).

Рис.1

Переходимо до розгалуження підмножини. Його наведена матриця представлена ​​в таблиці нижче.

j

i

1 2 3 4 6 2

0 3

в€ћ 8

0 2

8 3 22

0 4

в€ћ 26 4 4 3

0 0

17 в€ћ

0 4

5 в€ћ

0 10

17 10 47 6 37 12

0 10

2 в€ћ

12) Дізнаємося ступеня нулів матриці. Претендентами на включення в гамільтонів контур будуть кілька дуг (5; 2) і (6; 3). Для подальших розрахунків виберемо дугу (6, 3). Розбиваємо безліч на два підмножини: і (табл. 3 і 4). Щоб не допустити освіти негамільтонова контуру, в таблиці 3 замінюємо елемент (3; 6) на знак В«в€ћВ»

Табл.3

j

i

1 2 4 6 2 0 в€ћ 0 8 3 22 0 26 в€ћ 4 3 0 в€ћ 0 5 в€ћ 0 10 47

Табл.4

j

i

1 2 3 4 6

2 0 в€ћ 8 0 8

3 22 0 в€ћ 26 4

4 3 0 17 в€ћ 0

5 в€ћ 0 17 10 47

6 37 12 в€ћ 2 в€ћ 2

8

Визначимо константи приведення для цих матриць

,

Отже

,

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

j

i

1 2 4 6 2

0 3

в€ћ

0 2

8 3 22

0 22

26 в€ћ 4 3

0 0

в€ћ

0 8

5 в€ћ

0 10

10 47

Претендентом до включення в гамільтонів контур стане дуга (3, 2). Розбиваємо безліч на два і.

j

i

1 4 6

2 0 0 8

4 3 в€ћ 0

5 в€ћ 10 47 10

j

i

1 2 4 6

2 0 в€ћ 0 8

3 22 в€ћ 26 в€ћ 22 4 3 0 в€ћ 0

5 в€ћ 0 10 47

Очевидно

,

Отже, чергового галуженню потрібно піддати підмножина.

Переходимо до розгалуження підмножини. Визначаємо ступені нулів. Претендентом на включення в гамільтонів контур є дуга (5; 4). Розбиваємо безліч на дві підмножини: і.

Знаходимо нижні межі

,

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

Визначимо отриманий гамільтонів контур. До нього увійшли дуги

Довжина контуру дорівнює

Так як кордону обірваних гілок більше довжини контуру 1 - 5 - 4 - 6 - 3 - 2 - 1, то цей контуру має найменшу довжину.

алгоритм Крускала комівояжер

Рис.25

Висновки

Задача комівояжера є частковим випадком гамильтоновой завдання про мандрівника. Суть завдання комівояжера полягає в знаходженні сумарної мінімальної характеристики (Відстані, вартості проїзду і т.д.), при цьому комівояжер повинен пройти всі n міст по одному разу, повернувшись в те місто, з якого почав.

Існують декілька методів рішення задачі комівояжера: метод повного перебору, за допомогою методу гілок і меж (алгоритм Літтла), алгоритму Крускала, В«дерев'яногоВ» алгоритму і т.д. Однак тільки метод гілок і меж дає нам в підсумку найоптимальніше рішення.

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

Для практичної реалізації ідеї методу гілок і меж стосовно до задачі комівояжера потрібно знайти метод визначення нижніх меж підмножини і розбиття множини гамільтонових контурів на підмножини (розгалуження). Таке визначення нижніх кордонів базується на тому твердженні, що якщо до всіх елементів i-го рядка або j-го стовпця матриці C додати або відняти число, то задача залишиться еквівалентної колишньою, тобто оптимальність маршруту комівояжера не зміниться, а довжина будь-якого гамильтонова контуру зміниться на дану величину.

Використовуючи ЕОМ, методом гілок і меж можна вирішити задачі комівояжера для.

6. Список використаної літератури

1. О. Є. Акімов В«Дискретна математика. Логіка, групи, графи В», Москва, 2003, 376 с., Іл., Вид. будинок В«Лабораторія базових знаньВ».

2. Ф. А. Новиков В«Дискретна математика для програмістів В»С.-Петербург, 2002 р. 304 с., іл., вид. будинок В«ПітерВ».

3. В. М. Бондарєв В«Основи програмування В»1998 р., 368 с. изд. будинок В«ФеніксВ»