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

Методами Монте-Карло називать будь-яку статистичну процедуру, яка використовує статистичну вибірку. Сьогодні застосуємо дану процедуру, для знаходження розв’язку задачі комівояжера. Для цього припустимо, що у задачі комівояжер повинен проїхати міст, і побудувати свій маршрут таким чином, щоб побувати у кожному місті по одному разу і повернутися у початкове. Відмітимо, що, при цьому, витрати на переміщення між містами повинні бути мінімальними.

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

Зауваження: у середовищі програмування delphi, яке ми зазвичай використовуємо для програмної реалізації розглядуваних на даному сайті алгоритмів та методів, існує стандартна функція Random, яка дозволяє програмно формувати випадкові числа. Фактично ця та аналогічні функції в інших мовах програмування є датчиками випадкових чисел.

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

Відмітимо, що з допомогою ЕОМ ця процедура дозволяє за короткий термін оглянути велику кількість маршрутів і обрати серед них якщо не найкращий, то принаймі не найгірший маршрут.

Розв’язок задачі комівояжера методом Монте-Карло – приклад:

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

Метод Монте-Карло приклад

Тарифи на переміщення між містами

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

Метод Монте-Карло приклад

Генерація випадкового маршруту комівояжера

Для цього маршруту () розрахуємо функцію мети (витрати на переміщення)  і запам’ятовуємо як маршрут, так і отримане значення функції.

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

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

Блок-схема алгоритму знаходження розв’язку задачі комівояжера методом Монте-Карло

Метод Монте-Карло блок-схема

Залишити коментар

Your email address will not be published. Required fields are marked *

*