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

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

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

На тему

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

План 

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

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

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

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

Табл.2

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

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

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

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

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

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

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

в€ћ

j

i

1

2

4

6

2

0

в€ћ

0

8

3

22

0

26

в€ћ

4

3

0

в€ћ

0

5

в€ћ

0

10

47

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 ³

в€ћ

0 ²

8

3

22

0 ²²

26

в€ћ

4

3

0 ⁰

в€ћ

0 ⁸

5

в€ћ

0 ¹⁰

10

47

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