Задача про складання маршруту комівояжера. Метод гілок і меж
Введення
Актуальність даної теми полягає в наступному, Для вирішення оптимізаційних та інших задач будівництва нерідко вдаються до формулювання поставленого завдання у вигляді якихось добре відомих математичних задач: транспортна задача, задача пошуку оптимального шляху (задача комівояжера) та інші. Сформульовану таким чином задачу вирішують, використовуючи такі математичні методи, як метод гілок і кордонів, симплексний метод, метод Фогеля (наближеного рішення), метод дефектів та інші методи.
переборного алгоритми не ефективні (у розрахунку на гіршу задачу), тому успіх у вирішенні кожної конкретної задачі істотно залежить від способу організації перебору.
Знаменита задача комівояжера, поставлена ​​ще в 1934 р., є однією з найбільш найважливіших завдань в теорії графів. У своїй області (оптимізації дискретних задач) задача комівояжера служить своєрідним полігоном, на якому випробовуються всі нові методи.
Метою даної роботи буде:
1. Познайомити читача з основними поняттями теорії графів.
2. Дати уявлення про задачі комівояжера.
3. Описати метод гілок і меж.
4. Привести приклад використання методу гілок і меж для розв'язування задачі комівояжера.
1. Постановка завдання
Комівояжер (Бродячий торговець) повинен вийти з першого міста, відвідати по разу в невідомому порядку міста 2,3,4 ... n і повернутися в перший місто. Відстані між усіма містами відомі. У якому порядку слід обходити міста, щоб замкнутий шлях комівояжера був найкоротшим? У термінах теорії графів: знайти гамільтонів цикл в графі мінімальної довжини.
Задача комівояжера є так званою NP-важкою задачею, тобто завданням, точне рішення якої в загальному випадку може бути отримане тільки за експоненційний час. Отже, вирішувати її переборного алгоритмом неефективно при великому кількості вершин графа.
Одним з підходів до її рішенням є скорочення перебору методом гілок і меж. Цей метод дозволяє пізнати безперспективні часткові рішення, в результаті чого від дерева пошуку на одному кроці відсікається ціла гілка. Тим не менш, задовільних оцінок швидкодії алгоритму Літтла, заснованого на цьому методі, і родинних алгоритмів немає, хоча практика показує, що на сучасних ЕОМ вони іноді дозволяють вирішити задачу комівояжера для графів з кількістю вершин, меншим 100.
Вперше метод гілок і меж був запропонований Лендом і Дойга в 1960 для вирішення загальної задачі цілочисельного лінійного програмування. Інтерес до цього методу і фактично його В«друге народженняВ» пов'язане з роботою Літтла, Мурті, Суїні і Керела, присвяченій задачі комівояжера. Починаючи з цього моменту, з'явилася велика кількість робіт, присвячених методу гілок і меж і різним його модифікаціям. Настільки великий успіх пояснюється тим, що автори першими звернули увагу на широту можливостей методу, відзначили важливість використання специфіки завдання і самі скористалися специфікою задачі комівояжера. В основі методу гілок і меж лежить ідея послідовного розбиття множини припустимих рішень на підмножини (стратегія В«розділяй і володарюйВ»). На кожному кроці методу елементи розбиття піддаються перевірці для з'ясування, містить дане підмножина оптимальне рішення чи ні. В якості прикладу конкретного застосування методу може бути запропонована прикладна задача, пов'язана з проблемою розміщення та обслуговування обладнання, в якій вимагається визначити оптимальну траєкторію циклічного маршруту руху робота-транспортера по траєкторії цеху з метою періодичного обслуговування устаткування.
2. Огляд інших методів рішення задачі комівояжера
Інші методи, запропоновані для пошуку найкоротших гамільтонових циклів - алгебраїчний метод, заснований на роботі Йоу, Даніельсона і Дхавана (Включає в себе побудову всіх простих ланцюгів за допомогою послідовного перемножування матриць), метод перебору Робертса та Флореса (метод перебору має справу з одним ланцюгом, безперервно подовжувати аж до моменту, коли або стає ясно, що цей ланцюг не може призвести до гамільтонових циклів. Тоді ланцюг модифікується деяким систематичним способом, після чого продовжується пошук Гамільтона циклу. Інший підхід - мультіцепной метод, запропонований Селбі.
3. Теорія графів
3.1 Основні поняття теорії графів. Визначення
Граф G задається безліччю точок або вершин x 1 , x 2 , ... x n (яке позначається через X) і безліччю ліній або ребер a 1 , a 2 , ... a m (яке позначається символом А), що з'єднують між собою всі або частину цих точок. Таким чином, граф G повністю задається парою (X, A).
Якщо ребра з множини А орієнтірованни, що зазвичай показується стрілкою, то вони називаються дугами, і граф з такими ребрами називають орієнтованим графом. Інше, вживане частіше опис орієнтованого графа G полягає у завданні безлічі вершин Х і відповідності Г, яке показує, як між собою пов'язані вершини. Граф в цьому випадку позначається парою G = (X, Г).
Шляхом (або орієнтованим маршрутом) орієнтованого графа називається послідовність дуг, в якій кінцева вершина всякої дуги, відмінною від останньої, є початковій вершиною наступної.
орієнтованих ланцюгом називається такий шлях, в якому кожна дуга використовується не більше одного разу. Простий ланцюгом називається такий шлях, в якому кожна вершина використовується не більше одного разу. Очевидно, що проста орцепь є також орцепью, але зворотне вже невірно.
Іноді дугам графа G зіставляються (приписуються) числа - дузі (x i , x j ) ставиться у відповідність деяке число c i j , зване вагою, або довгою. Тоді граф G називається графом зі зваженими дугами. Іноді ваги приписуються вершин x i графа, і тоді виходить граф зі зваженими вершинами. Якщо в графі ваги приписані і дуг, і вершин, то він називається просто виваженим. При розгляді шляху, представленого послідовністю дуг, за його вага (або довжину) приймається число, рівне сумі ваг всіх дуг, що входять в, тобто .
Гамільтоном цикл в Орграф - це орієнтований цикл (контур), що проходить рівно один раз через кожну вершину графа (тобто проста орцепь).
комівояжер граф завдання метод
Якщо G = (X, A) - неорієнтований граф з n вершинами, то Остовним деревом (або, коротше, остовом) графа G називається всякий остовного підграф G, що є деревом (тобто графом які не мають циклів, в якому кожна пара вершин з'єднана однією і тільки однією простою ланцюгом). Наприклад, якщо G - Граф, показаний на мал. 1а, то графи на мал. 1.б, в є остовом цього графа.
3.2 Завдання комівояжера
Знаменита задача комівояжера, поставлена ​​ще в 1934 р., є однією з найбільш найважливіших завдань в теорії графів. У своїй області (оптимізації дискретних задач) задача комівояжера служить своєрідним полігоном, на якому випробовуються всі нові методи.
Постановка завдання. Комівояжер (бродячий торговець) повинен вийти з першого міста, відвідати по разу в невідомому порядку міста 2,3,4 ... n і повернутися в перший місто. Відстані між усіма містами відомі. У якому порядку слід обходити міста, щоб замкнутий шлях комівояжера був найкоротшим? У термінах теорії графів: знайти гамільтонів цикл в графі мінімальної довжини.
Задача комівояжера є так званою NP-важкою задачею, тобто завданням, точне рішення якої в загальному випадку може бути отримане тільки за експоненційний час. Отже, вирішувати її переборного алгоритмом неефективно при великому кількості вершин графа.
Рішення узагальнено...
