Формулювання комбінаторних оптимізаційних задач

В багатьох практичних випадках виникає необхідність підрахунку кількості можливих комбінацій об’єктів, які задовольняють певним властивостям. Такі задачі називаються комбінаторними. Багатоманітність комбінаторних задач неможливо описати, але серед них є цілий ряд таких, які зустрічаються особливо часто та для яких відомі способи підрахунку. Для формулювання та розв’язку комбінаторних задач використовуються різні моделі комбінаторних конфігурацій.

¾ Повний перебір;

¾ Метод гілок та границь;

¾ Моделювання відпалу;

¾ Найближчий сусід;

¾ Генетичні та евристичні алгоритми;

¾ Колективної поведінки;

¾ Meretic

Повний перебір

Є задачі де потрібний повний перебір.

Складність:

Число вузлів:

Кількість розгалужень:

Метод гілок та границь

 

 

…….

 

 

Границі: ; найгірші і найкращі значення задачі

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

Особливості:

Якщо границі визначено точно, тоді метод гарантує розв’язок.

Недолік:

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

Моделювання відпалу

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

З моменту своєї появи в 1983 році моделювання відпалу було застосоване до досить великої кількості різних проблем у різних областях. Більше 20 років досвіду привели такі загальні спостереження:

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

· У багатьох практичних ситуаціях, де наявні алгоритми не працюють, моделювання відпалу має великі плюси: загальність застосування і простота реалізації.

Таким чином, моделювання відпалу є алгоритмом, який всі практики математики та науковці комп'ютерних наук повинні мати у своєму інструментарії.

Найближчий сусід

Алгоритм найближчого сусіда — один з перших і найбільш простих евристичних методів розв'язування задачі комівояжера. Відноситься до категорії жадібних алгоритмів. За кожен крок його виконання до знайденої частини маршруту додається нове ребро. Алгоритм припиняє роботу, коли розв’язок знайдено і не намагається його покращити.

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

Вхідні дані: множина точок V розмірністю N Вихідні дані: маршрут Т, що складається з послідовності відвідування точок множини V