Розрахунково-графічна робота
з теорії алгоритмів
На тему
«гшення задачі комівояжера методом гілок і меж В»
План
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. Необхідно за допомогою алгоритму Літтла вирішити завдання комівояжера.
...
